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

<text> 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 | 10 | 11 | 9 | | 8 | | 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>