# 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)  = { \$ } WikiTeX: unable to set permissions on working directory. { w }
FIRST(B') = { x, (eps) }       FOLLOW(B') = FOLLOW(B) WikiTeX: unable to set permissions on working directory. FOLLOW(B") = { \$, w }
FIRST(B") = { w, z }           FOLLOW(B") = FOLLOW(B) = { \$, w }
FIRST(C)  = { x }              FOLLOW(C)  = FIRST(B') \ { (eps) } WikiTeX: unable to set permissions on working directory. FOLLOW(B') = { \$, x, w }
FIRST(C') = { x, (eps) }       FOLLOW(C') = { w } WikiTeX: unable to set permissions on working directory. 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)          |                      |                      |                       |
---+----------------------+----------------------+----------------------+----------------------+-----------------------+
```