# 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.

+3

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, (, +, *}

• 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).

0

source

All Articles