Top-Down Parsing/Exercise 5: Test 2010/07/01 - Revision history

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

2019-04-08T16:50:17Z

Computing the FIRST and FOLLOW Sets

← Older revision		Revision as of 16:50, 8 April 2019
Line 52:		Line 52:

	FIRST(A) = { t, v } FOLLOW(A) = { $ }		FIRST(A) = { t, v } FOLLOW(A) = { $ }
	FIRST(B) = { t, (eps) } FOLLOW(B) = FOLLOW(B') ~~<math>\cup</math>~~ FIRST(D') \ { (eps) } = { v, x, $ }		FIRST(B) = { t, (eps) } FOLLOW(B) = FOLLOW(B') ∪ FIRST(D') \ { (eps) } = { v, x, $ }
	FIRST(B') = { w, u } FOLLOW(B') = FIRST(D) ~~<math>\cup</math>~~ FOLLOW(B) = { v, x, $ }		FIRST(B') = { w, u } FOLLOW(B') = FIRST(D) ∪ FOLLOW(B) = { v, x, $ }
	FIRST(D) = { v } FOLLOW(D) = FOLLOW(A) = { $ }		FIRST(D) = { v } FOLLOW(D) = FOLLOW(A) = { $ }
	FIRST(D') = { x, (eps) } FOLLOW(D') = FOLLOW(A) ~~<math>\cup</math>~~ FOLLOW(D) = { $ }		FIRST(D') = { x, (eps) } FOLLOW(D') = FOLLOW(A) ∪ FOLLOW(D) = { $ }

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

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

2019-04-08T16:48:34Z

Computing the FIRST and FOLLOW Sets

← Older revision		Revision as of 16:48, 8 April 2019
Line 52:		Line 52:

	FIRST(A) = { t, v } FOLLOW(A) = { $ }		FIRST(A) = { t, v } FOLLOW(A) = { $ }
	FIRST(B) = { t, (eps) } FOLLOW(B) = FOLLOW(B') <~~amsmath~~>\cup</~~amsmath~~> FIRST(D') \ { (eps) } = { v, x, $ }		FIRST(B) = { t, (eps) } FOLLOW(B) = FOLLOW(B') <math>\cup</math> FIRST(D') \ { (eps) } = { v, x, $ }
	FIRST(B') = { w, u } FOLLOW(B') = FIRST(D) <~~amsmath~~>\cup</~~amsmath~~> FOLLOW(B) = { v, x, $ }		FIRST(B') = { w, u } FOLLOW(B') = FIRST(D) <math>\cup</math> FOLLOW(B) = { v, x, $ }
	FIRST(D) = { v } FOLLOW(D) = FOLLOW(A) = { $ }		FIRST(D) = { v } FOLLOW(D) = FOLLOW(A) = { $ }
	FIRST(D') = { x, (eps) } FOLLOW(D') = FOLLOW(A) <~~amsmath~~>\cup</~~amsmath~~> FOLLOW(D) = { $ }		FIRST(D') = { x, (eps) } FOLLOW(D') = FOLLOW(A) <math>\cup</math> FOLLOW(D) = { $ }

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

Root at 14:41, 6 April 2015

2015-04-06T14:41:14Z

← 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 */

2010-07-02T10:34:52Z

Parse Table

← Older revision		Revision as of 10:34, 2 July 2010
Line 59:		Line 59:
	== Parse Table ==		== Parse Table ==

	\| w \| x ~~\| y \| z~~ \| $ \|		\| t \| u \| v \| w \| x \| $ \|
	---+----------------------+~~-----------~~-----------+~~-----------~~-----------+~~-----------~~-----------+~~------------~~-----------+		---+-----------+-----------+-----------+-----------+-----------+-----------+
	A \| \| \| \| \| \|		A \| t B' D \| \| v D' \| \| \| \|
	---+----------------------+~~-----------~~-----------+~~-----------~~-----------+~~-----------~~-----------+~~------------~~-----------+		---+-----------+-----------+-----------+-----------+-----------+-----------+
	B \| \| \| \| \| \|		B \| t B' \| \| (eps) \| \| (eps) \| (eps) \|
	---+----------------------+~~-----------~~-----------+~~-----------~~-----------+~~-----------~~-----------+~~------------~~-----------+		---+-----------+-----------+-----------+-----------+-----------+-----------+
	B' \| \| \| \| \| \|		B' \| \| u w B \| \| w B \| \| \|
	---+----------------------+~~-----------~~-----------+~~-----------~~-----------+~~-----------~~-----------+~~------------~~-----------+		---+-----------+-----------+-----------+-----------+-----------+-----------+
	D \| \| \| \| \| \|		D \| \| \| v D' \| \| \| \|
	---+----------------------+~~-----------~~-----------+~~-----------~~-----------+~~-----------~~-----------+~~------------~~-----------+		---+-----------+-----------+-----------+-----------+-----------+-----------+
	D' \| \| \| \| \| \|		D' \| \| \| \| \| x B D' \| (eps) \|
	---+----------------------+~~-----------~~-----------+~~-----------~~-----------+~~-----------~~-----------+~~------------~~-----------+		---+-----------+-----------+-----------+-----------+-----------+-----------+

	== Input Analysis ==		== Input Analysis ==

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

2010-07-02T10:26:35Z

Computing the FIRST and FOLLOW Sets

← Older revision		Revision as of 10:26, 2 July 2010
Line 52:		Line 52:

	FIRST(A) = { t, v } FOLLOW(A) = { $ }		FIRST(A) = { t, v } FOLLOW(A) = { $ }
	FIRST(B) = { t, (eps) } FOLLOW(B) = FOLLOW(B') <amsmath>\cup</amsmath> FIRST(D') \ { (eps) } = { v, x, w }		FIRST(B) = { t, (eps) } FOLLOW(B) = FOLLOW(B') <amsmath>\cup</amsmath> FIRST(D') \ { (eps) } = { v, x, $ }
	FIRST(B') = { w, u } FOLLOW(B') = FIRST(D) <amsmath>\cup</amsmath> FOLLOW(B) = { v, x }		FIRST(B') = { w, u } FOLLOW(B') = FIRST(D) <amsmath>\cup</amsmath> FOLLOW(B) = { v, x, $ }
	FIRST(D) = { v } FOLLOW(D) = FOLLOW(A) = { $ }		FIRST(D) = { v } FOLLOW(D) = FOLLOW(A) = { $ }
	FIRST(D') = { x, (eps) } FOLLOW(D') = FOLLOW(A) <amsmath>\cup</amsmath> FOLLOW(D) = { $~~, x, w~~ }		FIRST(D') = { x, (eps) } FOLLOW(D') = FOLLOW(A) <amsmath>\cup</amsmath> FOLLOW(D) = { $ }

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

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

2010-07-01T19:01:07Z

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

New page

{{TOCright}}
= Problem =

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

A -> B D
B -> C w B | (eps)
D -> D x B | v
C -> t | t u

# 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>tuwvxtw</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 C singularities:

A -> B D
B -> t w B | t u w B | (eps)
D -> D x B | v

First we will eliminate left recursion in D and factoring "t" in B:

A -> B D
B -> t B' | (eps)
B' -> w B | u w B
D -> v D'
D' -> x B D' | (eps)

Eliminating the B left-corner in A:

A -> t B' D | D
B -> t B' | (eps)
B' -> w B | u w B
D -> v D'
D' -> x B D' | (eps)

Again:

A -> t B' D | v D'
B -> t B' | (eps)
B' -> w B | u w B
D -> v D'
D' -> x B D' | (eps)

== Computing the FIRST and FOLLOW Sets ==

FIRST(A) = { t, v } FOLLOW(A) = { $ }
FIRST(B) = { t, (eps) } FOLLOW(B) = FOLLOW(B') <amsmath>\cup</amsmath> FIRST(D') \ { (eps) } = { v, x, w }
FIRST(B') = { w, u } FOLLOW(B') = FIRST(D) <amsmath>\cup</amsmath> FOLLOW(B) = { v, x }
FIRST(D) = { v } FOLLOW(D) = FOLLOW(A) = { $ }
FIRST(D') = { x, (eps) } FOLLOW(D') = FOLLOW(A) <amsmath>\cup</amsmath> FOLLOW(D) = { $, x, w }

== Parse Table ==

| w | x | y | z | $ |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
A | | | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
B | | | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
B' | | | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
D | | | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
D' | | | | | |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+

== Input Analysis ==

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

Top-Down Parsing/Exercise 5: Test 2010/07/01 - Revision history

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

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

Root at 14:41, 6 April 2015

Root: /* Parse Table */

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

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

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