4 Oct 2006 16:47:14 -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: | "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.