Re: Ambiguity and LR(k)

Sylvain Schmitz wrote:
> Leonardo Teixeira Passos wrote:
>> I would like to know if a grammar is ambiguous then there isn't a
>> LR(k) syntax analyser that can be generated from it.
>
> Yes, this is true. You can find proofs of this for instance in Geller
> and Harrison, _On LR(k) Grammars and Languages_, TCS 4:245--276, 1977,
> or in most theory-oriented textbooks on parsing.
>
> Intuitively, you cannot generate a deterministic parser for an ambiguous
> grammar: if each parsing action done by the parser is chosen
> deterministically, then there is a unique way to recognize the entire
> input string, and the grammar is not ambiguous.


Well, just to be pedantic, "nondeterminism" isn't the same as
"ambiguity." For example, consider the language of palindromes,


        L = { ww^R | w \in {0,1}* }, where w^R denotes the reverse of w.


This language is generated by the following context-free grammar:


        S --> 0 S 0
        S --> 1 S 1
        S --> 0
        S --> 1
        S --> epsilon


This language can't be parsed by a deterministic parser, since for any
input string the parser has to "guess" when it has reached the midpoint
of the input. However, the grammar is not ambiguous: each string in the
language has exactly one parse tree (which is how "ambiguity" is defined).

Return to the comp.compilers page.
Search the comp.compilers archives again.