Re: SLR and LR(1) Differences: A Recap

Torben Ęgidius Mogensen wrote:


> LR(1) parse tables are much larger than SLR, whereas LALR(1) tables
> are no bigger. That makes LALR(1) popular for parser generators, and
> you can argue that this makes SLR uninteresting. I have, however,
> found that most people think in terms of FOLLOW when resolving
> conflicts in LALR(1) parsers, so they might as well be SLR.


But people also think in terms of left context, and find the inability
of SLR to make much use of it very disappointing. There is very nice
approach to LALR(1) that reuses the SLR algorithm on a derived
grammar:


M. E. Bermudez and G. Logothetis. Simple Computation of LALR(1)
Lookahead Sets. Information Processing Letters, 31:233--238, 1989.


This makes it very clear how LALR(1) takes left context into account
and as it reuses SLR, it explains why thinking in the terms of FOLLOW
often works.


> In short, I think the advantages of LALR(1) and LR(1) over SLR are
> overrated.




That is what I used to think, but I am now strongly convinced of the
practical merits of LALR(1). I have a parser generator that first
tries SLR and then tries LALR(1) if any conflicts remain. My test
suite includes grammars for Ada 95, C, Java 1.1 and Pascal. Here is an
extract from the test logs:


ada95.grm.log:LALR(1) lookahead sets resolved 42 conflicts
c.grm.log:LALR(1) lookahead sets resolved 12 conflicts
java11.grm.log:LALR(1) lookahead sets resolved 35 conflicts
pascal.grm.log:LALR(1) lookahead sets resolved 13 conflicts


(the only conflicts left are the usual dangling else conflict for C and
java).


The grammars in my test suite were adapted in a few hours work from grammars
that are readily available. Some years ago, I had to develop an SLR(1)
parser for (most of) Ada 83, and I know that it took many days to get a
working parser (which parses a wider language and then post-processes the
parse tree). The resulting parse is more difficult to maintain and has
poorer error reporting than I could now achieve with LALR(1).


A glance at the conflicts that SLR can't resolve makes me think that it
would be a real nightmare to parse C, for example, with SLR. Do you have
any evidence to the contrary?


Regards,


Rob.

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