Ambiguous grammar with LL(1) parse

Question

I'm having problems to solve this. I have to rewrite the following grammar to make it works with an LL(1) parse

S → noun | noun and noun | M, noun, and noun

M → M, noun | noun

The first problem that I noticed was that the grammar was recursive in the production with header M and I fix it like this

M → noun NewPro

NewPro → , noun NewPro

But then I noticed that the production with header S is ambiguous but I don't know how to fix it, I tried to "factorize" the noun but I am not actually sure.

Can you help me please?

Thank you for your answers.

Answer 1

Your left-recursion elimination of M is incomplete -- you forgot the rule NewPro → ε

Once you add that, you're left with the problem of S, which is not ambiguous, but needs left factoring. Since FIRST(M) ⊆ FIRST(S), you need to first substitute M into S:

S → noun | noun and noun | noun NewPro, noun, and noun

and then you can left-factor that simply, into

S → noun S'
S' → ε | and noun | NewPro, noun, and noun

Now you have the problem that this grammar is LL(4) but not LL(1), as you need 4 token lookahead to find the end of a sequence of NewPros. This is a much harder problem to deal with, but it can be fixed. First you need to pull the , noun, into NewPro:

S' → ε | and noun | NewPro and noun
NewPro → , noun, | , noun NewPro

and then left-factor NewPro:

NewPro → , noun NewPro'
NewPro' → , | NewPro

and then substitute into NewPro':

NewPro' → , | , noun NewPro'

and the left factor it too:

NewPro' → , NewPro'' NewPro'' → ε | noun NewPro'

Giving the final grammar:

S → noun S'
S' → ε | and noun | NewPro and noun
NewPro → , noun NewPro'
NewPro' → , NewPro''
NewPro'' → ε | noun NewPro'

Which is LL(1) and can be used directly or simplified a bit by substituting NewPro back into S' and renaming the rules to get rid of the '-suffixes:

S → noun A
A → ε | and noun | , noun B and noun
B → , C
C → ε | noun B