UMBC CMSC 331 ONLINE LECTURE 3 PART1What is Left Recursion?What’s the General Rule?Removing Left RecursionThe MechanicsUMBC CMSC 331 ONLINE LECTURE 3 PART1SD VickWhat is Left Recursion?Left Recursion is when you have a grammar with one or more rules of the following formA -> A | Example where is and is cA -> A a b | cIn the technique I’ll show you can’t directly (or indirectly) start with A 1) A -> A a b | Ac is illegal 2) A -> A a b | Bc so is this B -> d | Ae A -> B -> A Why?Why?What’s the General Rule? A -> A | A | … A m | n A A’ | A’ … n A’ A’ -> A’ | A’ | … m A’ | <z> -> <w>' ? <x> | <z> ! <y> | a <z><x> -> <z> * <x> | <x> / <y> | <w><w>-> e | fRemoving Left RecursionConsider the following GrammarWhy is this Left Recursive?Now we must justpick our ’sandour’sThe Mechanics <z> -> <w>' ? <x> | <z> ! <y> | a <z><z> -> <w>' ? <x> <z’> | a <z> <z’> <z’> -> ! <y> <z’> | Try the second rule on your ownHere we have 2 ‘s and 1 , what if the situation was
View Full Document
Unlocking...