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

Root at 11:11, 12 February 2019

2019-02-12T11:11:56Z

← Older revision		Revision as of 11:11, 12 February 2019
Line 15:		Line 15:

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

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

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

	S' in S and S in L:		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 → z y S x S' \| x y S x S' \| w L y S' \| v y S' \| ε		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
	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):		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 → 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
	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 → 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
	L' → y S' v \| ε 12\|13
	~~</text>~~

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

	Parse table (note the ambiguities):		Parse table (note the ambiguities):
	<text>		<source lang="text">
	\| v \| w \| x \| y \| z \| $ \|		\| v \| w \| x \| y \| z \| $ \|
	-------+-------+-------+-------+-------+-------+-------+		-------+-------+-------+-------+-------+-------+-------+
Line 64:		Line 53:
	L \| 11 \| 8 \| 10 \| \| 9 \| \|		L \| 11 \| 8 \| 10 \| \| 9 \| \|
	L' \| \| \| \| 12/13 \| \| \|		L' \| \| \| \| 12/13 \| \| \|
	</~~text~~>		</source>

	Input analysis:		Input analysis:
	<text>		<source lang="text">
	STACK \| INPUT \| ACTION		STACK \| INPUT \| ACTION
	---------------------------		---------------------------
Line 80:		Line 69:
	S'$ \| $ \| 7		S'$ \| $ \| 7
	$ \| $ \| ACCEPT		$ \| $ \| ACCEPT
	</~~text~~>		</source>

	[[category:Compiladores]]		[[category:Compiladores]]
	[[category:Ensino]]		[[category:Ensino]]

Root: /* Solution */

2015-04-08T08:29:36Z

Solution

← Older revision		Revision as of 08:29, 8 April 2015
Line 60:		Line 60:
	\| v \| w \| x \| y \| z \| $ \|		\| v \| w \| x \| y \| z \| $ \|
	-------+-------+-------+-------+-------+-------+-------+		-------+-------+-------+-------+-------+-------+-------+
	S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|		S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|
	S' \| 6/7 \| \| 7 \| \| \| 7 \|		S' \| 6/7 \| \| 7 \| \| \| 7 \|
	L \| 11 \| 8 \| 10 \| \| 9 \| \|		L \| 11 \| 8 \| 10 \| \| 9 \| \|
	L' \| \| \| \| 12/13 \| \| \|		L' \| \| \| \| 12/13 \| \| \|
	</text>		</text>

Root: /* Solution */

2015-04-08T08:29:08Z

Solution

← Older revision		Revision as of 08:29, 8 April 2015
Line 62:		Line 62:
	S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|		S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|
	S' \| 6/7 \| \| 7 \| \| \| 7 \|		S' \| 6/7 \| \| 7 \| \| \| 7 \|
	L \| 11 \| 8 \| 10 \| \| 9 \| \|		L \| 11 \| 8 \| 10 \| \| 9 \| \|
	L' \| \| \| \| 12/13 \| \| \|		L' \| \| \| \| 12/13 \| \| \|
	</text>		</text>

Root: /* Solution */

2015-04-08T08:28:49Z

Solution

← Older revision		Revision as of 08:28, 8 April 2015
Line 62:		Line 62:
	S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|		S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|
	S' \| 6/7 \| \| 7 \| \| \| 7 \|		S' \| 6/7 \| \| 7 \| \| \| 7 \|
	L \| 10 \| 11 \| 9 \| \| 8 \| \|		L \| 11 \| 8 \| 10 \| \| 9 \| \|
	L' \| \| \| \| 12/13 \| \| \|		L' \| \| \| \| 12/13 \| \| \|
	</text>		</text>

Root at 14:40, 6 April 2015

2015-04-06T14:40:39Z

← Older revision		Revision as of 14:40, 6 April 2015
Line 82:		Line 82:
	</text>		</text>

	[[category:~~Teaching~~]]		[[category:Compiladores]]
	[[category:~~Compilers~~]]		[[category:Ensino]]

Root: /* Solution */

2013-06-20T17:02:39Z

Solution

← Older revision		Revision as of 17:02, 20 June 2013
Line 14:		Line 14:
	= Solution =		= Solution =

	~~<text>~~
	Singularity M in S:		Singularity M in S:
	<text>		<text>

Root: /* Solution */

2013-04-08T18:53:03Z

Solution

@@ Line 14: / Line 14: @@
 = Solution =
-[[Image:CompilersTopDownParsingExercise10.jpg|700px]]
+<text>
 [[category:Teaching]]
 [[category:Compilers]]

Root at 18:27, 8 April 2013

2013-04-08T18:27:09Z

← Older revision		Revision as of 18:27, 8 April 2013
Line 12:		Line 12:
	# Show the analysis table (stack, input, and actions) for the parsing process of the '''<tt>zyvyx</tt>''' input sequence.		# Show the analysis table (stack, input, and actions) for the parsing process of the '''<tt>zyvyx</tt>''' input sequence.

	== Solution ==		= Solution =

	[[Image:CompilersTopDownParsingExercise10.jpg\|700px]]		[[Image:CompilersTopDownParsingExercise10.jpg\|700px]]

Root: /* Problem */

2013-04-08T18:26:52Z

Problem

← Older revision		Revision as of 18:26, 8 April 2013
Line 2:		Line 2:
	= Problem =		= Problem =

	Consider the following grammar, where '''<tt>S</tt>''' is the initial symbol and '''<tt>{x, y, z}</tt>''' is the set of terminal symbols:		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 \| ε		S → M y S x \| L y \| ε

Root: Created page with "{{TOCright}} = Problem = Consider the following grammar, where '''`S`''' is the initial symbol and '''`{x, y, z}`''' is the set of terminal symbols: S → M y S ..."

2013-04-08T18:26:29Z

Created page with "{{TOCright}} = Problem = Consider the following grammar, where '''<tt>S</tt>''' is the initial symbol and '''<tt>{x, y, z}</tt>''' is the set of terminal symbols: S → M y S ..."

New page

{{TOCright}}
= Problem =

Consider the following grammar, where '''<tt>S</tt>''' is the initial symbol and '''<tt>{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 ==

[[Image:CompilersTopDownParsingExercise10.jpg|700px]]

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

← Older revision		Revision as of 08:29, 8 April 2015
Line 60:		Line 60:
	\| v \| w \| x \| y \| z \| $ \|		\| v \| w \| x \| y \| z \| $ \|
	-------+-------+-------+-------+-------+-------+-------+		-------+-------+-------+-------+-------+-------+-------+
	S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|		S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|
	S' \| 6/7 \| \| 7 \| \| \| 7 \|		S' \| 6/7 \| \| 7 \| \| \| 7 \|
	L \| 11 \| 8 \| 10 \| \| 9 \| \|		L \| 11 \| 8 \| 10 \| \| 9 \| \|
	L' \| \| \| \| 12/13 \| \| \|		L' \| \| \| \| 12/13 \| \| \|
	</text>		</text>

← Older revision		Revision as of 08:29, 8 April 2015
Line 62:		Line 62:
	S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|		S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|
	S' \| 6/7 \| \| 7 \| \| \| 7 \|		S' \| 6/7 \| \| 7 \| \| \| 7 \|
	L \| 11 \| 8 \| 10 \| \| 9 \| \|		L \| 11 \| 8 \| 10 \| \| 9 \| \|
	L' \| \| \| \| 12/13 \| \| \|		L' \| \| \| \| 12/13 \| \| \|
	</text>		</text>

← Older revision		Revision as of 08:28, 8 April 2015
Line 62:		Line 62:
	S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|		S \| 4 \| 3 \| 2/5 \| \| 1 \| 5 \|
	S' \| 6/7 \| \| 7 \| \| \| 7 \|		S' \| 6/7 \| \| 7 \| \| \| 7 \|
	L \| 10 \| 11 \| 9 \| \| 8 \| \|		L \| 11 \| 8 \| 10 \| \| 9 \| \|
	L' \| \| \| \| 12/13 \| \| \|		L' \| \| \| \| 12/13 \| \| \|
	</text>		</text>

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

Root at 11:11, 12 February 2019

Root: /* Solution */

Root: /* Solution */

Root: /* Solution */

Root at 14:40, 6 April 2015

Root: /* Solution */

Root: /* Solution */

Root at 18:27, 8 April 2013

Root: /* Problem */

Root: Created page with "{{TOCright}} = Problem = Consider the following grammar, where '''S''' is the initial symbol and '''{x, y, z}''' is the set of terminal symbols: S → M y S ..."

Root: Created page with "{{TOCright}} = Problem = Consider the following grammar, where '''`S`''' is the initial symbol and '''`{x, y, z}`''' is the set of terminal symbols: S → M y S ..."