View source for Top-Down Parsing/Exercise 4: Test 2010/04/17

{{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)

== Computing the FIRST and FOLLOW Sets ==

 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") = { 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, (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' -> (eps)           |
 ---+----------------------+----------------------+----------------------+----------------------+-----------------------+
 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]]