Top-Down Parsing/Exercise 4: Test 2010/04/17 - Revision history

Root at 14:41, 6 April 2015

2015-04-06T14:41:04Z

← Older revision		Revision as of 14:41, 6 April 2015
Line 75:		Line 75:


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

Root: /* Parse Table */

2011-03-21T22:46:35Z

Parse Table

← Older revision		Revision as of 22:46, 21 March 2011
Line 68:		Line 68:
	C \| \| C -> x B w C' \| \| \| \|		C \| \| C -> x B w C' \| \| \| \|
	---+----------------------+----------------------+----------------------+----------------------+-----------------------+		---+----------------------+----------------------+----------------------+----------------------+-----------------------+
	C' \| C' -> (eps) \| C' -> x C' \| \| \| \|		C' \| C' -> (eps) \| C' -> x C' \| \| \| C' -> (eps) \|
	\| \| C' -> (eps) \| \| \| \|		\| \| C' -> (eps) \| \| \| \|
	---+----------------------+----------------------+----------------------+----------------------+-----------------------+		---+----------------------+----------------------+----------------------+----------------------+-----------------------+

Root: /* Computing the FIRST and FOLLOW Sets */

2011-03-21T22:45:02Z

Computing the FIRST and FOLLOW Sets

← Older revision		Revision as of 22:45, 21 March 2011
Line 52:		Line 52:
	FIRST(B") = { w, z } FOLLOW(B") = FOLLOW(B) = { $, w }		FIRST(B") = { w, z } FOLLOW(B") = FOLLOW(B) = { $, w }
	FIRST(C) = { x } FOLLOW(C) = FIRST(B') \ { (eps) } <amsmath>\cup</amsmath> FOLLOW(B') = { $, x, w }		FIRST(C) = { x } FOLLOW(C) = FIRST(B') \ { (eps) } <amsmath>\cup</amsmath> FOLLOW(B') = { $, x, w }
	FIRST(C') = { x, (eps) } FOLLOW(C') = { w } <amsmath>\cup</amsmath> FOLLOW(C) = { x, w }		FIRST(C') = { x, (eps) } FOLLOW(C') = { w } <amsmath>\cup</amsmath> FOLLOW(C) = { $, x, w }

	== Parse Table ==		== Parse Table ==

Root: /* Parse Table */

2011-03-21T22:17:59Z

Parse Table

← Older revision		Revision as of 22:17, 21 March 2011
Line 62:		Line 62:
	B \| \| B -> x B w C' w y B" \| B -> y B' \| \| \|		B \| \| B -> x B w C' w y B" \| B -> y B' \| \| \|
	---+----------------------+----------------------+----------------------+----------------------+-----------------------+		---+----------------------+----------------------+----------------------+----------------------+-----------------------+
	B' \| B' -> (eps) \| B' -> x C B' \| \| \| \|		B' \| B' -> (eps) \| B' -> x C B' \| \| \| B' -> (eps) \|
	---+----------------------+----------------------+----------------------+----------------------+-----------------------+		---+----------------------+----------------------+----------------------+----------------------+-----------------------+
	B" \| B" -> w B' \| \| \| B" -> z B' \| \|		B" \| B" -> w B' \| \| \| B" -> z B' \| \|

Root: /* Parse Table */

2011-03-21T22:15:04Z

Parse Table

← Older revision		Revision as of 22:15, 21 March 2011
Line 68:		Line 68:
	C \| \| C -> x B w C' \| \| \| \|		C \| \| C -> x B w C' \| \| \| \|
	---+----------------------+----------------------+----------------------+----------------------+-----------------------+		---+----------------------+----------------------+----------------------+----------------------+-----------------------+
	C' \| C' -> (eps) \| C' -> x C' \| \| \| ~~C' -> (eps)~~ \|		C' \| C' -> (eps) \| C' -> x C' \| \| \| \|
	\| \| C' -> (eps) \| \| \| \|		\| \| C' -> (eps) \| \| \| \|
	---+----------------------+----------------------+----------------------+----------------------+-----------------------+		---+----------------------+----------------------+----------------------+----------------------+-----------------------+

Root: /* Computing the FIRST and FOLLOW Sets */

2011-03-21T22:11:06Z

Computing the FIRST and FOLLOW Sets

← Older revision		Revision as of 22:11, 21 March 2011
Line 48:		Line 48:
	== Computing the FIRST and FOLLOW Sets ==		== Computing the FIRST and FOLLOW Sets ==

	FIRST(B) = { x, y } FOLLOW(B) = { w }		FIRST(B) = { x, y } FOLLOW(B) = { $ } <amsmath>\cup</amsmath> { w }
	FIRST(B') = { x, (eps) } FOLLOW(B') = FOLLOW(B) <amsmath>\cup</amsmath> FOLLOW(B") = { w }		FIRST(B') = { x, (eps) } FOLLOW(B') = FOLLOW(B) <amsmath>\cup</amsmath> FOLLOW(B") = { $, w }
	FIRST(B") = { w, z } FOLLOW(B") = FOLLOW(B) { w }		FIRST(B") = { w, z } FOLLOW(B") = FOLLOW(B) = { $, w }
	FIRST(C) = { x } FOLLOW(C) = ~~{ $ } <amsmath>\cup</amsmath>~~ FIRST(B') \ { (eps) } <amsmath>\cup</amsmath> FOLLOW(B') = { $, x, w }		FIRST(C) = { x } FOLLOW(C) = FIRST(B') \ { (eps) } <amsmath>\cup</amsmath> FOLLOW(B') = { $, x, w }
	FIRST(C') = { x, (eps) } FOLLOW(C') = { w } <amsmath>\cup</amsmath> FOLLOW(C) = { $, x, w }		FIRST(C') = { x, (eps) } FOLLOW(C') = { w } <amsmath>\cup</amsmath> FOLLOW(C) = { x, w }

	== Parse Table ==		== Parse Table ==

Root: /* FIRST and FOLLOW Sets */

2010-04-24T19:33:41Z

FIRST and FOLLOW Sets

← Older revision		Revision as of 19:33, 24 April 2010
Line 46:		Line 46:
	C' -> x C' \| (eps)		C' -> x C' \| (eps)

	== FIRST and FOLLOW Sets ==		== Computing the FIRST and FOLLOW Sets ==

	FIRST(B) = { x, y } FOLLOW(B) = { w }		FIRST(B) = { x, y } FOLLOW(B) = { w }

Root: New page: {{TOCright}} = Problem = Consider the following grammar, where '''`B`''' is the initial symbol and '''`{w,x,y,z}`''' is the set of terminal symbols: A -> y B -> B x C | C...

2010-04-24T19:33:23Z

New page: {{TOCright}} = Problem = Consider the following grammar, where '''<tt>B</tt>''' is the initial symbol and '''<tt>{w,x,y,z}</tt>''' is the set of terminal symbols: A -> y B -> B x C | C...

New page

{{TOCright}}
= Problem =

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

A -> y
B -> B x C | C w A D | y
C -> C x | x B w
D -> w | z

# 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>yxxyw</tt>''' input sequence.

= Solution =

Something to keep in mind at all times: '''never eliminate the rules corresponding to the initial symbol'''

== Rewriting the Grammar ==

We start by noting the A and D singularities:

B -> B x C | C w y w | C w y z | y
C -> C x | x B w

Since mutual recursion does not exist, we will start by eliminating the left recursion on the B and C symbols.

B -> C w y w B' | C w y z B' | y B'
B' -> x C B' | (eps)
C -> x B w C'
C' -> x C' | (eps)

Eliminating the non-terminal left corner in B:

B -> x B w C' w y w B' | x B w C' w y z B' | y B'
B' -> x C B' | (eps)
C -> x B w C'
C' -> x C' | (eps)

Factoring:

B -> x B w C' w y B" | y B'
B' -> x C B' | (eps)
B" -> w B' | z B'
C -> x B w C'
C' -> x C' | (eps)

== FIRST and FOLLOW Sets ==

FIRST(B) = { x, y } FOLLOW(B) = { w }
FIRST(B') = { x, (eps) } FOLLOW(B') = FOLLOW(B) <amsmath>\cup</amsmath> FOLLOW(B") = { w }
FIRST(B") = { w, z } FOLLOW(B") = FOLLOW(B) { w }
FIRST(C) = { x } FOLLOW(C) = { $ } <amsmath>\cup</amsmath> FIRST(B') \ { (eps) } <amsmath>\cup</amsmath> FOLLOW(B') = { $, x, w }
FIRST(C') = { x, (eps) } FOLLOW(C') = { w } <amsmath>\cup</amsmath> FOLLOW(C) = { $, x, w }

== Parse Table ==

There is an ambiguity in C' on '''x'''.

| w | x | y | z | $ |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
B | | B -> x B w C' w y B" | B -> y B' | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
B' | B' -> (eps) | B' -> x C B' | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
B" | B" -> w B' | | | B" -> z B' | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
C | | C -> x B w C' | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
C' | C' -> (eps) | C' -> x C' | | | C' -> (eps) |
| | C' -> (eps) | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+

== Input Analysis ==

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

Top-Down Parsing/Exercise 4: Test 2010/04/17 - Revision history

Root at 14:41, 6 April 2015

Root: /* Parse Table */

Root: /* Computing the FIRST and FOLLOW Sets */

Root: /* Parse Table */

Root: /* Parse Table */

Root: /* Computing the FIRST and FOLLOW Sets */

Root: /* FIRST and FOLLOW Sets */

Root: New page: {{TOCright}} = Problem = Consider the following grammar, where '''B''' is the initial symbol and '''{w,x,y,z}''' is the set of terminal symbols: A -> y B -> B x C | C...

Root: New page: {{TOCright}} = Problem = Consider the following grammar, where '''`B`''' is the initial symbol and '''`{w,x,y,z}`''' is the set of terminal symbols: A -> y B -> B x C | C...