Re: Ambiguity and LR(k)

"Saumya K. Debray" <debray@CS.Arizona.EDU> writes:


> 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).


This is kind of what I wanted to say: a grammar's ambiguity and its
being LL(n)/LR(n) are related issues but they're are not the same. If
a grammar is unambiguous, that just means that for each word in the
accepted language there is exactly one parse-tree. If OTOH a grammar
is LL(n)/LR(n) it means that for each word of the accepted language
you must be able to tell from the first/last n *tokens* (i. e.
terminals) which rule to choose. This is more strict than unambiguity
because for a grammar that is just unambiguous, n might not be fixed.
The palindrome grammar is one example.




Wolfram

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