View source for Top-Down Parsing/Exercise 5: Test 2010/07/01

{{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, $ }
 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) = { $ }

== Parse Table ==

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

== Input Analysis ==


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