# Convert context free grammar to LL (1)

I have the following grammar:

```
S -> S+S|SS|S*|(S)|a
```

How do I convert it to LL (1) grammar?

I tried to eliminate left recursion, so I got

```
S->(S)S'|aS'
S'->+SS'|SS'|*S'|epsilon
```

I also tried to do the first factoring first and then eliminate the left recursion and I got something like:

```
S->(S)S"|aS"
S"->S'S"|epsilon
S'->+S|*|S
```

But I still don't get a perfect answer. I feel like the grammar is still not LL (1). Please, help.

source to share

It might help to try and write a grammar so that you read some complete term, and then maybe try to expand it in some way. For example, you can try something like this:

S → Term

Term → CoreTerm OptMore

CoreTerm → a | (Term)

OptMore → & Epsilon; | Term | + Deadline | * OptMore

For example, you should get (a + a) * a as

S

→ Term

→ CoreTerm OptMore

→ OptMore

→ term

→ CoreTerm OptMore

→ a (CoreTerm OptMore) OptMore

→ a (OptMore) OptMore

→ a (a + Term) OptMore

→ a (a + CoreTerm OptMore) OptMore

→ a (a + a OptMore) OptMore

→ a (a + a) OptMore

→ a (a + a) * OptMore

→ a (a + a) * Term

→ a (a + a) * CoreTerm OptMore

→ a (a + a) * a OptMore

→ a (a + a) * a

To see that this is an LL (1) grammar, here FIRST sets:

- FIRST (S) = {
- FIRST (Term) = {a, (}
- FIRST (CoreTerm) = {a, (}
- FIRST (OptMore) = {& epsilon ;, a, (, +, *}

Here FOLLOW sets:

- FOLLOW (S) = {$}
- FOLLOW (Term) = {$,)}
- FOLLOW (CoreTerm) = {a, (, +, *, $}
- FOLLOW (OptMore) = {$,)}

So now we can populate the parsing table:

```
| a | ( | + | * | ) | $
---------+------------------+------------------+--------+-----------+-----+------
S | Term | Term | | | |
Term | CoreTerm OptMore | CoreTerm OptMore | | | |
CoreTerm | a | (Term) | | | |
OptMore | Term | Term | + Term | * OptMore | eps | eps
```

So this grammar is indeed LL (1).

source to share