Top-Down Parsing/Exercise 10: Test 2013/04/03

Problem

Consider the following grammar, where S is the initial symbol and {v, w, x, y, z} is the set of terminal symbols:

S → M y S x | L y | ε
L → w L | S v
M → z | x

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

Solution

Singularity M in S: <text> S → z y S x | x y S x | L y | ε L → w L | S v </text>

Non-terminal left-corner L in S (also: mutual recursion): <text> S → z y S x | x y S x | w L y | S v y | ε L → w L | S v </text>

Elimination of left recursion in S: <text> S → z y S x S' | x y S x S' | w L y S' | S' S' → v y S' | ε L → w L | S v </text>

S' in S and S in L: <text> S → z y S x S' | x y S x S' | w L y S' | v y S' | ε S' → v y S' | ε L → w L | z y S x S' v | x y S x S' v | w L y S' v | v y S' v | v </text>

Identifying common prefixes in L (final grammar form): <text> S → z y S x S' | x y S x S' | w L y S' | v y S' | ε 1|2|3|4|5 S' → v y S' | ε 6|7 L → w L L' | z y S x S' v | x y S x S' v | v L' 8|9|10|11 L' → y S' v | ε 12|13 </text>

FIRST and FOLLOW sets for the transformed grammar: <text> FIRST(S) = { v, w, x, z, ε } FOLLOW(S) = { $, x } FIRST(S') = { v, ε } FOLLOW(S') = { $, v, x } FIRST(L) = { v, w, x, z } FOLLOW(L) = { y } FIRST(L') = { y, ε } FOLLOW(L') = { y } </text>

Parse table (note the ambiguities): <text>

      |   v   |   w   |   x   |   y   |   z   |   $   |

---

+-------+-------+-------+-------+-------+-------+

S | 4 | 3 | 2/5 | | 1 | 5 | S' | 6/7 | | 7 | | | 7 | L | 11 | 8 | 10 | | 9 | | L' | | | | 12/13 | | | </text>

Input analysis: <text>

 STACK  | INPUT  | ACTION

---

     S$ | zyvyx$ | 1
zySxS'$ | zyvyx$ | (z)
 ySxS'$ |  yvyx$ | (y)
  SxS'$ |   vyx$ | 4

vyS'xS'$ | vyx$ | (v)

yS'xS'$ |    yx$ | (y)
 S'xS'$ |     x$ | 7
   xS'$ |     x$ | (x)
    S'$ |      $ | 7
      $ |      $ | ACCEPT

</text>