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