Re: Ambiguity and LR(k)

"Wolfram Fenske" <>
6 Oct 2006 17:10:39 -0400

          From comp.compilers

Related articles
Ambiguity and LR(k) (Leonardo Teixeira Passos) (2006-10-03)
Re: Ambiguity and LR(k) (Sylvain Schmitz) (2006-10-04)
Re: Ambiguity and LR(k) debray@CS.Arizona.EDU (Saumya K. Debray) (2006-10-04)
Re: Ambiguity and LR(k) (Wolfram Fenske) (2006-10-06)
| List of all articles for this month |

From: "Wolfram Fenske" <>
Newsgroups: comp.compilers
Date: 6 Oct 2006 17:10:39 -0400
References: 06-10-01306-10-017 06-10-020
Keywords: parse, LR(1)
Posted-Date: 06 Oct 2006 17:10:39 EDT

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


Post a followup to this message

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