# Is this grammar ambiguous?

I have the grammar:

\qquad \begin{align} S &\to S = P \mid S \neq P \mid P \\ P &\to NUM \end{align}

This grammar suffers from left recursion. To eliminate left recursion, I got:

\qquad \begin{align} S &\to PS' \\ S' &\to\, = PS' \mid\, \neq PS' \mid \varepsilon \\ P &\to NUM \end{align}

However when constructing the LL(1) parsing table, it turns out the grammar is ambiguous. Is there a way to disambiguate the grammar without changing the generated language, or did I make a mistake somewhere?

This is my work so far:

Non-terminal Nullable First            Follow
S            False    NUM              $S' True !=, ==, epsilon$
P            False    NUM              $, ==, != Parse Table != == NUM$
S                   ->PS'
S'  ->!=PS'  ->==PS'        ->epsilon
P                   ->NUM

• Are my workings correct then?
– barq
May 17, 2012 at 23:01
• I don't see how the grammar is ambiguous. Can you give a case where it is? May 17, 2012 at 23:03
• Look up refactoring ambiguous grammars. There should be enough material on google to get you started.
– Eric
May 17, 2012 at 23:03
• If there are multiply defined entries in the table, it's not LL(1). It could be due to left-recursion, the need for a left-factored grammar, or ambiguity (even after resolving the previous conditions). A parse table isn't going to necessarily tell you whether your grammar is ambiguous, although a multiply defined entry may hint that it is. As mentioned, if the grammar is ambiguous, it's ambiguous, but from what I can tell the grammar isn't ambiguous. Also, your follow sets are incomplete. FOLLOW(S') = FOLLOW(S) = {$}. – blackcompe May 18, 2012 at 3:28 • The grammar is not ambiguous. This is demonstrated by your parsing table: each table cell has at most one production in it. – ibid May 24, 2012 at 7:40 ## 1 Answer We can consider$NUM$and therewith$P$a terminal symbol. Furthermore,$S$does only occur once in every derivation. Therefore, if there is any ambiguity, it has to stem from$\qquad \displaystyle S' \to\, = PS' \mid\, \neq PS' \mid \varepsilon$Now, that fragment is a right-regular grammar with only one non-terminal whose right-hand sides do not share any prefixes. So clearly every term has only derivation, given by its length and permutation of$=$and$\neq$. In total, your grammar is unambiguous. Above observations also suggest that the grammar can be parsed in one pass from left to right with one token lookahead (distinguish$=$and$\neq$). In fact, the grammar is basically a deterministic (no shared prefixes) and right-regular (replace all$P$with$NUM\$) grammar, so it's certainly an LL(1) grammar.

So I suggest you revisit the construction of the parsing table (your favorite textbook or Wikipedia) -- you must have made a mistake.