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

migrated from stackoverflow.com Jul 17 '12 at 19:27

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Are my workings correct then? $\endgroup$ – barq May 17 '12 at 23:01
  • $\begingroup$ I don't see how the grammar is ambiguous. Can you give a case where it is? $\endgroup$ – ninjagecko May 17 '12 at 23:03
  • $\begingroup$ Look up refactoring ambiguous grammars. There should be enough material on google to get you started. $\endgroup$ – Eric May 17 '12 at 23:03
  • 1
    $\begingroup$ 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) = {$}. $\endgroup$ – blackcompe May 18 '12 at 3:28
  • 1
    $\begingroup$ The grammar is not ambiguous. This is demonstrated by your parsing table: each table cell has at most one production in it. $\endgroup$ – ibid May 24 '12 at 7:40

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy