24 Oct 1998 01:50:19 -0400

Related articles |
---|

Looking for formal definition of LALR(k) laski@ics.uci.edu (Ziemowit Laski) (1998-10-17) |

Re:Looking for formal definition of LALR(k) KPRASAD@us.oracle.com (KPRASAD.US.ORACLE.COM) (1998-10-21) |

Re: Looking for formal definition of LALR(k) matt@timmermans.no-spam-remove.org (Matt Timmermans) (1998-10-22) |

Re: Looking for formal definition of LALR(k) laski@ics.uci.edu (Ziemowit Laski) (1998-10-22) |

Re: Looking for formal definition of LALR(k) laski@ics.uci.edu (Ziemowit Laski) (1998-10-24) |

From: | Ziemowit Laski <laski@ics.uci.edu> |

Newsgroups: | comp.compilers |

Date: | 24 Oct 1998 01:50:19 -0400 |

Organization: | Compilers Central |

References: | <199810230525.WAA28269@mailsun2.us.oracle.com> |

Keywords: | parse, theory |

KPRASAD.US.ORACLE.COM wrote:

*> are you aware of a grammar that can be parsed by LR(k) and not LALR(k)?*

*> pl. provide examples*

*> thanks*

*> -kama*

I don't have my dragon book next to me :), but I'll try to reconstruct the

example they gave: S -> aAa | aBb | bAb | bAa A -> c

B -> c

The LR(k) parser will have two states {[A->c.|a],[B->c.|b]} and

{[A->c.|b],[B->c.|a]}, among others. When merged, they produce the LALR(k)

state {[A->c.|a,b],[B->c.|a,b]} with overlapping lookahead sets (i.e.,

reduce-reduce conflicts).

Zem

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.