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

On 18 Feb 1999 10:47:30 -0500, Joe Hotchkiss <joe.hotchkiss@gecm.com>
wrote:


> 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) - what you can parse when you're using a top-down parser
generator like RDP. Kind of like recursive descent in power.


> 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) - what you can parse when you're using a really good commercial
bottom-up parser generator like Yacc++. Not seen much in the real
world otherwise, because the internal tables tend to get too big.


> 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(1) - what you can parse when you're using Yacc and its children.
Like LR(1), but with some additional restrictions on things that you
can parse. In practice these restriction don't get in your way much,
and LALR(1) grammars can express most normal programming-language
features. (C++ is, of course, abnormal in this area.) Most real-
world compilers are either LALR(1) using something like Yacc, or
hand-coded recursive-descent.


>Then there are SLR and SLALR grammars and quite possibly others that I
>have not come across yet. All the books I have read use at least some
>of these terms but I can find no systematic attempt to say what the
>differences are.


Not of much use, because LALR(1) is more general than SLR and LALR(1)
tools are widely available.


>Can anyone help or at least suggest a book with clear definitions?


You don't really want clear definitions, would be my guess, because
exact specs of these involve learning language and parsing theory.
You'd need to sludge through the swamp like the rest of here have
done: if you really really want to, then get the dragon book
(Compilers: Principles, Techniques, and Tools, by Aho, Sethi, and
Ullman) and allocate a few months to get up to speed. It's fun,
but I only did it because I couldn't not do it.


The other, gentler approach is to get John's book (lex & yacc, by
John Levine) and a copy of byacc and flex off the net and learn
how to write parsers by going through his examples.


Or, you can go get RDP


http://www.cs.rhbnc.ac.uk/research/languages/rdp.shtml


which is a lot easier to learn, and generates C code that you can
understand, instead of a lot of unfathomable tables.


Have fun!


Dwight

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