Re: Looking for formal definition of LALR(k)

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".

Return to the comp.compilers page.
Search the comp.compilers archives again.