# Problem

Consider the following grammar, where `G` is the initial symbol and `{a,b,c,d,e}` is the set of terminal symbols:

O -> a
G -> F c | O c d | (eps)
F -> G b | O c F e

- 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
`acbec` input sequence.

# Solution

Something to keep in mind at all times: **never eliminate the rules corresponding to the initial symbol**

### Elimination of Mutual Recursion: Expanding F in G

Initial grammar:

O -> a
G -> F c | O c d | (eps)
F -> G b | O c F e

Eliminating the singularity (O->a):

G -> F c | a c d | (eps)
F -> G b | a c F e

Expanding F in G:

G -> G b c | a c F e c | a c d | (eps)
F -> G b | a c F e

Eliminating left recursion in G:

G -> a c F e c G' | a c d G' | G'
G' -> b c G' | (eps)
F -> G b | a c F e

Factoring G prefixes:

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> F e c G' | d G'
F -> a c G" b | b c G' b | b | a c F e

Factoring F prefixes:

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> F e c G' | d G'
F -> a c F' | b F"
F' -> G" b | F e
F" -> c G' b | (eps)

Eliminating non-terminal left corners (note that F becomes unreachable):

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> a c F' e c G' | b F" e c G' | d G'
F' -> a c F' e c G' b | b F" e c G' b | d G' b | a c F' e | b F" e
F" -> c G' b | (eps)

Factoring F' prefixes, we get to the final version:

G -> a c G" | b c G' | (eps)
G' -> b c G' | (eps)
G" -> a c F' e c G' | b F" e c G' | d G'
F' -> a c F' e F" | b F" e F" | d G' b
F" -> c G' b | (eps)

### FIRST & FOLLOW sets

FIRST(G) = { a, b, (eps) } FOLLOW(G) = { $ }
FIRST(G') = { b, (eps) } FOLLOW(G') = { $, b }
FIRST(G") = { a, b, d } FOLLOW(G") = { $ }
FIRST(F') = { a, b, d } FOLLOW(F') = { e }
FIRST(F") = { c, (eps) } FOLLOW(F") = { e }