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

{{TOCright}}
= Problem =

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

 S → M y S x | L y | ε
 L → w L | S v
 M → z | 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 '''<tt>zyvyx</tt>''' 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>

[[category:Teaching]]
[[category:Compilers]]