Re: What IS an LL/LR/SLR/LALR etc. grammar?

G'day all.


Joe Hotchkiss <joe.hotchkiss@gecm.com> writes:


>I have been writing a small recursive descent parser, mostly for my own
>amusement, and have been trying to document it for others to use. In
>doing so I have tried to give definitions of some terms, but I can't
>actually find a clear definition of the various types of grammar.


OK, here goes...


> LL(1) = scans input left-to-right, produces output for the
>left-most bits first, and looks ahead at most 1 symbol at a time.


LL(1) = scans input from left-to-right, produces a leftmost derivation
top-down, 1 symbol of lookahead


LL(k) is precisely the class of grammars which can be deterministically
parsed using a recursive descent parser where parsing decisions are based
on left context and k symbols of lookahead only.


> LR(1) = scans input left-to-right, produces output for the
>right-most bits first (but does so in reverse order for some reason!),
>and looks ahead at most 1 symbol at a time.


LR(1) = scans input from left-to-right, produces a rightmost derivation
in reverse bottom-up, 1 symbol of lookahead


LR(k) is precisely the class of grammars which can be deterministically
parsed using a shift-reduce (or recursive ascent) parser where parsing
decisions are based on left context and k symbols of lookahead only.


> LALR(1) = Look-Ahead LR(1), but the (1) indicates that it looks
>ahead 1 symbol anyway, so what is the difference? I have seen clear
>statements that LR(1) is NOT the same as LALR(1).


LALR(k) is not a simple class of grammars to reason about since its
definition is based on the kind of automaton used to parse it. LALR(k)
is, basically, what you get when you take an LR(k) parser and squish
it down to LR(0) size, possibly losing information along the way.


>Then there are SLR and SLALR grammars and quite possibly others that I
>have not come across yet.


SLR(k) is what you get when you start with an LR(0) parser and approximate
lookahead information by using follow sets. It's rarely used nowadays
since:


- People generally don't use k > 1
- LALR(1) is a superset of SLR(1)
- Modern LALR(1) generators are extremely efficient, and the
time saved generating SLR(1) parsers just isn't worth it.


Again, it's a bit hard to reason about SLR, because its definition is
based on the automaton which parses it. It's a bit easier than LALR,
though...


I don't know about SLALR.


As for a book, Nigel Chapman's "LR Parsing: Theory and Practice" is
a good one if you want to delve into the topic, and the definitions
are presented well.


Cheers,
Andrew Bromage

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