31 Mar 2005 23:32:46 -0500

Related articles |
---|

Examples of LR(k) grammars (k > 1) sought zlaski@ziemas.net (Ziemowit Laski) (2005-03-27) |

Re: Examples of LR(k) grammars (k > 1) sought nospam@nospam.nospam (Karsten Nyblad) (2005-03-31) |

Re: Examples of LR(k) grammars (k > 1) sought schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-03-31) |

Re: Examples of LR(k) grammars (k > 1) sought zlaski@ziemas.net (Ziemowit Laski) (2005-03-31) |

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

Newsgroups: | comp.compilers |

Date: | 31 Mar 2005 23:32:46 -0500 |

Organization: | Compilers Central |

References: | 05-03-115 |

Keywords: | LR(1), parse |

Posted-Date: | 31 Mar 2005 23:32:46 EST |

Ziemowit Laski wrote:

*> I was wondering if anyone could point me to actual examples of*

*> grammars that are LR(k) but _not_ LALR(k), for k > 1, and/or to an*

*> algorithm for generating such grammars.*

The usual example of an LR(1) grammar which is not LALR is:

S -> aAa | bAb | aBb | bBa

A -> c

B -> c

The LR(0) state reached when reading "ac" or "bc" allows both the

reductions of "c" to "A" and to "B". The lookahead possible for each

reduction contains "a" and "b", for the LR(0) state merge has lost the

information of which token---"a" or "b"---has been read first.

Increasing the value of k will not change anything.

If you also need your grammar to be non-LR(1), just put the end context

further as in:

S -> aADa | bADb | aBDb | bBDa

A -> c

B -> c

D -> d^{k-1}

If you were looking for more real life examples, I remember there is one

in the bison manual [http://www.gnu.org/software/bison/manual], which

you can probably adapt in order to have k > 1.

--

Hope that helps,

Sylvain

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.