1
$\begingroup$

I read that no LL(1) grammar can be ambiguous.

Can we just make a LL(1) predictive parser table for a grammar to determine whether it's ambiguous? If the grammar is not LL(1), can we say that grammar is ambiguous?

$\endgroup$
2
$\begingroup$

If the grammar is not LL(1), can we say that grammar is ambiguous?

Euh, no. A grammar is unambiguous if for every word in its language there exists exactly one derivation-tree for it in the grammar.

Parsing is a way to find that derivation, given the string, preferably in some efficient way. Several classes of grammars were defined that have efficient parsing methods, for example LL(1) grammars.

A grammar can be non-LL(1), and still be unambiguous. For instance when we reverse an LL(1) grammar (that is, take the mirror image of the RHS of every production) the result still is unambiguous: mirroring the original unique derivation trees. But it cannot be parsed in an LL fashion, rather its reverse...

$\endgroup$
3
  • $\begingroup$ Suppose we have a grammar $A -> aA / b$ . If we reverse it then grammar is $A -> Aa / b$ . Here the grammar is unambiguous but not LL(1) because we have left recursion after reversing. Did you mean this ? $\endgroup$ – Sagar P Nov 7 '17 at 6:50
  • 1
    $\begingroup$ exactly! Hope that helps. $\endgroup$ – Hendrik Jan Nov 7 '17 at 6:51
  • 1
    $\begingroup$ and by the way, thanks for the example. $\endgroup$ – Hendrik Jan Nov 7 '17 at 6:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.