22 Oct 1998 02:00:51 -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: | "Matt Timmermans" <matt@timmermans.no-spam-remove.org> |

Newsgroups: | comp.compilers |

Date: | 22 Oct 1998 02:00:51 -0400 |

Organization: | Bell Solutions |

References: | 98-10-109 |

Keywords: | parse, LALR |

X-MimeOLE: | Produced By Microsoft MimeOLE V4.72.3155.0 |

Ziemowit Laski wrote in message 98-10-109...

*>The dragon book, among others, defines LALR(k) operationally -- that*

*>is, a grammar is LALR(k) if the parser generator accepts it without*

*>any conflicts. In their article on LALR(1) lookahead sets (1982),*

*>DeRemer and Pennello claim they know of "no reasonable way" to define*

*>LALR(k) in a way that "does not involve the parser".*

The trouble is that LALR(k) is really defined with respect to a

particular generation algorithm:

LALR(k) parsers are generated by adding valid follow sets to an LR(0)

parser. An LR(k) parser, stripped of the lookahead information, is a

perfectly valid LR(0) parser, so if you say that a grammar is LALR(k)

iff all conflicts can be removed from some LR(0) parser for that

grammar by adding valid follow sets, then LALR(k)=LR(k).

If, however, you say that a grammar is LALR(k) iff all conflicts can

be removed from the canonical (minimal) LR(0) parser, then you get an

LALR(k) that can be simply defined, but it is smaller than that used

in practice, because the LR(0) parsers constructed by LALR(k) parser

generators have more states than are strictly necessary.

The set of LR(0) states generated by an LALR(k) parser generator can

be defined algebraically, but such definitions closely resemble the

operational descriptions of how those states are constructed -- you

can't make elegant and simple definitions using concepts like

"regularly separable".

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.