Consider the following grammar, where ** S** is the initial symbol and

S -> u B z B -> B v | D D -> E u E | B y E E -> v | v x

- Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.
- Compute the FIRST and FOLLOW sets for all non-terminal symbols in the new grammar and build the parse table.
- Show the analysis table (stack, input, and actions) for the parsing process of the
input sequence.`uvuvxz`

The grammar can be parsed by an LL(1) parser if it does not have left recursion and no ambiguity is present (i.e., the LOOKAHEADs for all productions of each non-terminal are disjoint).

A simple inspection of the grammar shows that indirect left recursion is present in rules **B** and **D**. Also, there are left corners that may hide ambiguity (**E**).

The first step, then, is to rewrite the grammar so that mutual recursion is eliminated (**D** becomes unreachable and can be removed from the grammar):

S -> u B z B -> B v | E u E | B y E D -> E u E | B y E E -> v | v x

Now we handle the left corner (**E** in **B**) (since **E** is not completely replaced, it cannot be removed from the grammar):

S -> u B z B -> B v | v u E | v x u E | B y E E -> v | v x

Now, left recursion can be eliminated:

S -> u B z B -> v u E B1 | v x u E B1 B1 -> v B1 | y E B1 | ε E -> v | v x

Factoring...

S -> u B z B -> v B2 B1 -> v B1 | y E B1 | ε B2 -> u E B1 | x u E B1 E -> v E1 E1 -> x | ε

The FIRST and FOLLOW sets are as follows:

FIRST(S) = FIRST(u B z) = {u} FIRST(B) = FIRST(v B2) = {v} FIRST(B1) = FIRST(v B1) ∪ FIRST(y E B1) ∪ {ε} = {v, y, ε} FIRST(B2) = FIRST(u E B1) ∪ FIRST(x u E B1) = {u, x} FIRST(E) = FIRST(v E1) = {v} FIRST(E1) = {x} ∪ {ε} = {x, ε}

FOLLOW(S) = {$} FOLLOW(B) = {z} FOLLOW(B1) ⊇ FOLLOW(B2) FOLLOW(B2) ⊇ FOLLOW(B) FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z} FOLLOW(E) = FIRST(B1)\{ε} ∪ FOLLOW(B1) ∪ FOLLOW(B2) = {v, y, z} FOLLOW(E1) = FOLLOW(E) = {v, y, z}

For building the parse table, we will consider the FIRST and FOLLOW sets above.

u | v | x | y | z | $ | |
---|---|---|---|---|---|---|

S | S -> u B z | |||||

B | B -> v B2 | |||||

B1 | B1 -> v B1 | B1 -> y E B1 | B1 -> ε | |||

B2 | B2 -> u E B1 | B2 -> x u E B1 | ||||

E | E -> v E1 | |||||

E1 | E1 -> ε | E1 -> x | E1 -> ε | E1 -> ε |

The following table shows the parsing of the **uvuvxz** input sequence.

STACK |
INPUT |
ACTION |

S $ |
u v u v x z $ | S -> u B z |

u B z $ |
u v u v x z $ | -> u |

B z $ | v u v x z $ | B -> v B2 |

v B2 z $ | v u v x z $ | -> v |

B2 z $ | u v x z $ | B2 -> u E B1 |

u E B1 z $ | u v x z $ | -> u |

E B1 z $ | v x z $ | E -> v E1 |

v E1 B1 z $ | v x z $ | -> v |

E1 B1 z $ | x z $ | E1 -> x |

x B1 z $ | x z $ | -> x |

B1 z $ | z $ | B1 -> ε |

z $ | z $ | -> z |

$ | $ | ACCEPT |