Top-Down Parsing/Example 2

Problem

Consider the following grammar, where S is the initial symbol and {d,e,f,g,h} is the set of terminal symbols:

 S -> A B d | C d
 A -> C d h | S e
 C -> g B | h f
 B -> g | ε

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 hfded input sequence.

Solution

The grammar can be parsed by an LL(1) parser if it does not have left recursion and no ambiguity is present (i.e., the LOOKAHEADs for all productions of each non-terminal are disjoint).

A simple inspection of the grammar shows that indirect left recursion is present in rules S and A. Also, there are left corners that may hide ambiguity (C).

The first step, then, is to rewrite the grammar so that multual recursion is eliminated (A becomes unreachable and can be removed from the grammar):

 S -> C d h B d | S e B d | C d
 A -> C d h | S e
 C -> g B | h f
 B -> g | ε

Now we handle the left corner (C in S) (C also becomes unreachable and can be removed from the grammar):

 S -> g B d h B d | h f d h B d | S e B d | g B d | h f d
 C -> g B | h f
 B -> g | ε

Now, left recursion can be eliminated:

 S  -> g B d h B d S' | h f d h B d S' | g B d S' | h f d S'
 S' -> e B d S' | ε
 B  -> g | ε

Factoring...

 S  -> g B d S" | h f d S"
 S' -> e B d S' | ε
 S" -> h B d S' | S'
 B  -> g | ε

Removing the left corner S' from S":

 S  -> g B d S" | h f d S"
 S' -> e B d S' | ε
 S" -> h B d S' | e B d S' | ε
 B  -> g | ε

The FIRST and FOLLOW sets are as follows:

 FIRST(S)  = FIRST(g B d S") ∪ FIRST(h f d S") = {g, h}
 FIRST(S') = FIRST(e B d S') ∪ {ε} = {e, ε}
 FIRST(S") = FIRST(h B d S') ∪ FIRST(e B d S') ∪ {ε} = {e, h, ε}
 FIRST(B)  = FIRST(g) ∪ {ε} = {g, ε}

 FOLLOW(S)  = {$}
 FOLLOW(S') ⊇ FOLLOW(S") ⊇ FOLLOW(S)
 FOLLOW(S') = FOLLOW(S") = FOLLOW(S) = {$}
 FOLLOW(B)  = {d}

For building the parse table, we will consider the FIRST and FOLLOW sets above.

	d	e	f	g	h	$
S				S -> g B d S"	S -> h f d S"
S'		S' -> e B d S'				S' -> ε
S"		S" -> e B d S'			S" -> h B d S'	S" -> ε
B	B -> ε			B -> g

The following table shows the parsing of the hfded input sequence.

STACK	INPUT	ACTION
S$	hfded$	S -> hfdS"
hfdS"$	hfded$	-> hfd
S"$	ed$	S" -> eBdS'
eBdS'$	ed$	-> e
BdS'$	d$	B -> ε
dS'$	d$	-> d
S'$	$	ACCEPT