Revision as of 20:27, 8 April 2013 (view source) Root (talk | contribs) ← Older edit		Revision as of 20:53, 8 April 2013 (view source) Root (talk | contribs) (→‎Solution) Newer edit →
Line 14:		Line 14:
	= Solution =		= Solution =
−	[[Image:CompilersTopDownParsingExercise10.jpg|700px]]	+	<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:Teaching]]
	[[category:Compilers]]		[[category:Compilers]]

---

Revision as of 20:53, 8 April 2013

Contents 1 Problem 2 Solution

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>