Two standard techniques for Repetition and choice Left recursion removal exp>exp addo term term (in recursive-descent parsing, EBNF: exp- term faddop term) Left Factoring If-stmt>if( exp)statement I if(exp)statement else statement (in recursive-descent parsing, EBNF: if-stmt->if(exp) statement else statement)
Two standard techniques for Repetition and Choice • Left Recursion removal exp → exp addop term | term (in recursive-descent parsing, EBNF: exp→ term {addop term}) • Left Factoring If-stmt → if ( exp ) statement ∣ if ( exp ) statement else statement (in recursive-descent parsing, EBNF: if-stmt→ if (exp) statement [else statement])
Left recursion removal Left recursion is commonly used to make operations left associative, as in the simple expression grammar, where exp-exp addo term term Immediate left recursion The left recursion occurs only within the production of a single non-terminal exp-exp+ term exp-term term Indirect left recursion: Never occur in actual programming language grammars but be included for completeness A→Bb|
Left Recursion Removal • Left recursion is commonly used to make operations left associative, as in the simple expression grammar, where exp → exp addop term | term • Immediate left recursion: The left recursion occurs only within the production of a single non-terminal. exp → exp + term | exp - term |term • Indirect left recursion: Never occur in actual programming language grammars, but be included for completeness. A → Bb |… B → Aa |…
CASE 1: Simple Immediate Left R excursion A→A|阝 Where, aandBare strings of terminals and non-terminals; β does not begin with A. The grammar will generate the strings of the form. Ba We rewrite this grammar rule into two rules A→阝A To generateβ first; A→aA To generate the repetitions of a, using right recursion
CASE 1: Simple Immediate Left Recursion • A → Aα| β Where, αandβare strings of terminals and non-terminals; βdoes not begin with A. • The grammar will generate the strings of the form. • We rewrite this grammar rule into two rules: A → βA’ To generate β first; A’ → αA’| ε To generate the repetitions of α, using right recursion. n
Example exp ->exp adop term term To rewrite this grammar to remove left recursion we obtain exp→> term exp exp→ addo term exp'|ε
Example • exp → exp addop term | term • To rewrite this grammar to remove left recursion, we obtain exp → term exp’ exp’ → addop term exp’ | ε
CASE General Immediate Left R excursion A→Aa1AQ2|……Anβ1|β2|.|βm Where none ofβ1,,β m begin with A The solution is similar to the simple case A→→β1AB2A1.|BmA2 A→1Aa2A…|nA|
CASE2: General Immediate Left Recursion A → Aα1| Aα2| … |Aαn|β1|β2|…|βm Where none ofβ1,…,βm begin with A. The solution is similar to the simple case: A →β1A’|β2A’| …|βmA’ A’ → α1A’| α2A’| … |αnA’|ε