3 Oct 2006 18:20:26 -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: | Leonardo Teixeira Passos <leonardo@dcc.ufmg.br> |

Newsgroups: | comp.compilers |

Date: | 3 Oct 2006 18:20:26 -0400 |

Organization: | POP-MG/RNP |

Keywords: | LR(1), parse, theory |

Posted-Date: | 03 Oct 2006 18:20:26 EDT |

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. Is the other way

of thinking also true, i.e., if there isn't a k such that a LR(k)

syntax analyser can be automatically generated from a grammar G, then

G is definitly ambiguous?

Are there any hints or proofs for the given staments?

It seems to me that if a grammar is ambiguous, then there isn't a

LR(k) syntax analyser that can be generated for it. However, I cannot

prove or disprove this.

[As I recall, there are plenty of grammars that are unambiguous but cannot

be parsed by any technique that uses fixed lookahead. -John]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.