At uni I am studying formal languages and I was practicing with this exercise I had found on the Internet.
G:
S -> A B d | C d
A -> C d h | S e
C -> g B | h f
B -> g | ε
Source:https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php/Top-Down_Parsing/Example_2
I need to rewrite the grammar so that the language is LL(1). I tried to solve it like this:
- I noticed a left recursion S=>ABd=>SeBd and removed it with a substitution obtaining:
G:
S -> A B d | C d
A -> C d h | A B d e | C d e
C -> g B | h f
B -> g | ε
- I noticed an immediate left recursion on terminal A and removed it:
G:
S -> A B d | C d
A -> C d h A' | C d e A'
A' -> B d e A' | ε
C -> g B | h f
B -> g | ε
- I noticed a left factorization on terminal A and removed it, obtaining:
G:
S -> A B d | C d
A -> C d B'
B' -> h A' | e A'
A' -> B d e a | ε
C -> g B | h f
B -> g | ε
Now if I try to construct the parsing table and then calculate the first and follow you can immediately see that the grammar is not LL(1), since first(ABd)=first(Cd). Can someone explain why, since neither left recursion nor right factorization is present and it does not appear that the grammar is ambiguous. What did I do wrong?