Notice for Example: IfStatement The entry Mlelse-part, else] contains two entries, i. e. the dangling else ambiguity Disambiguating rule: always prefer the rule that generates the current look-ahead token over any other, and thus the production Else-part-else statement ove Else-part→E With this modification the above table will become unambiguous The grammar can be parsed as if it were an ll()grammar
Notice for Example: If-Statement • The entry M[else-part, else] contains two entries, i.e. the dangling else ambiguity. • Disambiguating rule: always prefer the rule that generates the current look-ahead token over any other, and thus the production Else-part → else statement ove Else-part →ε • With this modification, the above table will become unambiguous – The grammar can be parsed as if it were an LL(1) grammar
The parsing based ll(1) Table The parsing actions for the string: If(O)if (1)other else other for conciseness, statement=s, if-stmt=I else-part-L, exp=E, if, else=e, other=o)
The parsing based LL(1) Table • The parsing actions for the string: If (0) if (1) other else other • ( for conciseness, statement= S, if-stmt=I, else-part=L, exp=E, if=I, else=e, other=o)
Steps Parsing Stack Input Action i(0)i(1)oeos s→I i(0i(1)oeos I→i(E)SL SLSEG i(0i(1)oeos Match 4 S LSEC (O)i(1)oeo S Match S LSE Oi(leo S E Match Match Match Match Match teh natch L→eS Match match
Steps Parsing Stack Input Action 1 $S i(0)i(1)oeo$ S→I 2 $I i(0)i(1)oeo$ I→i(E)SL 3 $LS)E(i i(0)i(1)oeo$ Match 4 $ LS)E( (0)i(1)oeo $ Match 5 $ LS)E 0)i(1)oeo $ E→o Match Match S→I I→i(E)SL Match Match E→1 Match match S→o match L→eS Match S→o match L→ε 22 $ $ accept
42 3 Left recursion removal and Left Factoring
4.2.3 Left Recursion Removal and Left Factoring
Repetition and choice Problem Repetition and choice in ll(1)parsing suffer from similar problems to be those that occur in recursive descent parsing and for that reason we have not yet been able to give an Ll(I parsing table for the simple arithmetic expression grammar of previous sections Solve these problems for recursive-descent by using EBNF notation We cannot apply the same ideas to ll(1) parsing; instead, we must rewrite the grammar within the BNF notation into a form that the ll(1) parsing algorithm can accept
Repetition and Choice Problem • Repetition and choice in LL(1) parsing suffer from similar problems to be those that occur in recursivedescent parsing – and for that reason we have not yet been able to give an LL(1) parsing table for the simple arithmetic expression grammar of previous sections. • Solve these problems for recursive-descent by using EBNF notation – We cannot apply the same ideas to LL(1) parsing; – instead, we must rewrite the grammar within the BNF notation into a form that the LL(1) parsing algorithm can accept