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

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 w A D | y
C -> C x | x B w
D -> w | z

1. Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.
2. Compute the FIRST and FOLLOW sets for all non-terminal symbols in the new grammar and build the parse table.
3. Show the analysis table (stack, input, and actions) for the parsing process of the yxxyw 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)          |                      |                      |                       |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+