Re: Ambiguity and LR(k)

"Saumya K. Debray" <debray@CS.Arizona.EDU>
4 Oct 2006 16:47:14 -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: "Saumya K. Debray" <debray@CS.Arizona.EDU>
Newsgroups: comp.compilers
Date: 4 Oct 2006 16:47:14 -0400
Organization: University of Arizona Computer Science Department
References: 06-10-013 06-10-017
Keywords: LR(1), parse
Posted-Date: 04 Oct 2006 16:47:14 EDT

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

Post a followup to this message

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