6 Oct 2006 17:10:39 -0400

Related articles |
---|

Ambiguity and LR(k) leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-10-03) |

Re: Ambiguity and LR(k) schmitz@i3s.unice.fr (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) int2k@gmx.net (Wolfram Fenske) (2006-10-06) |

From: | "Wolfram Fenske" <int2k@gmx.net> |

Newsgroups: | comp.compilers |

Date: | 6 Oct 2006 17:10:39 -0400 |

Organization: | http://groups.google.com |

References: | 06-10-01306-10-017 06-10-020 |

Keywords: | parse, LR(1) |

"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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.