A complete example

1 The grammar

Consider the grammar:

E : E '+' E
  | E '-' E
  | '(' E ')'
  | id
  | num
  ;

where the syntactic variables are {E} and the tokens are {num, id, + , -, (, )}.

Note:

• from discussion, we know that this grammar is ambiguous.

2 Left factoring

First we perform left-factoring. We can see that the grammar is not left-factored. Let’s rewrite the grammar to an equivalent left-factored form.

E : E A | '(' E ')' | id | number
A : + E | -E

3 Remove general left recursion

There is an immediate left recursion for E.

E : '(' E ')' B
  | id B
  | number B
  ;
  
B : "" | '+' E B | '-' E B;

Don’t forget the rule for A:

A : + E | -E

4 First sets

We can compute the first sets.

• first(A) = {+, -}
• first(B) = {+, -, epsilon}
• first(E) = {(, id, number}

5 Follow sets

Now, we can compute the follow sets:

follow(E) = {$, ), +, -}
follow(B) = follow(E) = {$, ), +, -}
follow(A) = {$, ), +, -}

6 Checking the LL(1) condition

For E:

• first sets of all alternations are distinct. ✅

For A:

• first sets of all alternations are distinct. ✅

For B:

• first sets of all alternations are distinct. ✅

• since B is nullable epsilon\(\in\)first(B), we need to check first(B)\(\cap\)follow(B). This is where the ambiguity is found:

  first(B)\(\cap\)follow(B) = {+, -} ❌

7 Building the predictive parsing table

Because the grammar failed LL(1) condition, the table will have cells with multiple entries.

	id	number	(	)	+	-	$
E	E -> id B	E -> number B	E -> ( E ) B
B				B -> ""	B -> A B; B -> ""	B -> A B; B -> ""	B -> ""
A					A -> + E	A -> - E

Note

The parsing has a choice when expanding B nodes when the next token is + or -.

\[ B \rightarrow \left\{ \begin{array}{ll} A B & \mathrm{or} \\ \epsilon \end{array} \right. \]

8 Applying the parser

Consider the input of id + id.

1. Initial case: next token id.

E

(2): apply table[E][id]: E ->id B

      E
     / \
   id   B

3. expand B with next token +

      E
     / \
   id  B
     /  \
    A   B

4. expand A with next token +

      E
     / \
   id   B
       / \
      A  B
     / \
    +  E

5. expand E with next token id

      E
     / \
   id   B
       / \
      A  B
     / \
    +   E
       / \
     id   B

6. expand B with next token $

      E
     / \
   id   B
       /  \
      A    B
     / \
    +   E
       / \
     id   B
          |
          ε

7. expand B with next token $

      E
     / \
   id   B
       /  \
      A    B
     / \   |
    +   E  ε
       / \
     id   B
          |
          ε

8. Done because no more nodes to expand, and next token is $.