Re: Looking for formal definition of LALR(k)

"Matt Timmermans" <matt@timmermans.no-spam-remove.org>
22 Oct 1998 02:00:51 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.