I have a problem in reducing a grammar to LL(1)

33 Views Asked by At

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:

  1. 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 | ε

  1. 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 | ε

  1. 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?

0

There are 0 best solutions below