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

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.


So far,
      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.
      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.
      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).


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.


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


Thank you.
            Joe

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