26 Oct 2006 00:29:34 -0400

Related articles |
---|

Grammar needed leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-10-24) |

Re: Grammar needed schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-10-26) |

Re: Grammar needed 148f3wg02@sneakemail.com (Karsten Nyblad) (2006-10-26) |

Re: Grammar needed pjj@cs.man.ac.uk (Pete Jinks) (2006-10-26) |

Re: Grammar needed cfc@shell01.TheWorld.com (Chris F Clark) (2006-10-26) |

Re: Grammar needed leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-11-01) |

From: | Sylvain Schmitz <schmitz@i3s.unice.fr> |

Newsgroups: | comp.compilers |

Date: | 26 Oct 2006 00:29:34 -0400 |

Organization: | Compilers Central |

References: | 06-10-101 |

Keywords: | parse, theory |

Posted-Date: | 26 Oct 2006 00:29:34 EDT |

X-Virus-Scanned: | amavisd-new at i3s.unice.fr |

Leonardo Teixeira Passos wrote:

*> I've been trying to obtain a grammar that meets two properties:*

*>*

*> (i) It represents an LR(k) language*

*> (ii) The grammar it self isn't LR(k) for any k, for there is at least*

*> one conflict. One or more of these conflicts does not indicate*

*> ambiguity in the grammar, but can't be solved with any k.*

You can consider for instance the grammar with rules

S -> A a | B b

A -> A c | c (G1)

B -> B c | c

(i) The language generated by this grammar is a deterministic language

`c+(a|b)', since it is also generated by the LR(0) grammar G2 with rules

S -> C a | C b (G2)

C -> C c | c

Or if you want to keep the two parts separated, by the SLR(1) grammar G3

with rules

S -> A a | B b

A -> c A | c (G3)

B -> c B | c

(ii) The grammar G1 is not LR(k) for any k but unambiguous: in order to

choose between the reduction of the first `c' to `A' or `B', the parser

needs the see the ending `a' or `b', which can be arbitrarily far away

after a sequence of `c's.

--

Hope that helps,

Sylvain

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.