lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

> From:
> Hi everyone,

> I understand the lexing and parsing part of the process (I think
> at least, Lua is a LR(1) parser right? Left->right, one lookahead
> token?
First of all, you generally wouldn't describe a parser as being LR(1).  The
terms LL, SLR, LR, and LALR are used describe grammars, which, in turn,
define languages.  A parser accepts a string and then determines whether
that string is in the a given language.

I'm no expert on Lua, but it looks like it uses a pretty straight forward
top-down, predictive parsing method (as most hand-written parsers do).  This
method will accept LL grammars (ie, Left-to-right scan, Left-most
derivation), but not LR (Left-to-right scan, Right-most derivation).  LL is
a subset of LR.

> That is what I got from looking at the code and given my
> understanding of that kind of parser. Lua on the other hand
> doesn't seem to use the shift/reduce methodology, or I am just
> missing something entirely, but anyways, this is off on a tangent ;).
Shift/reduce is related to bottom-up parsing methods.  These methods are
usually more powerful (in terms of dealing with a wider range of grammars,
usually LR(1) or LALR(1)), and can be found implemented in most
compiler-compilers, like Yacc or Bison.  I believe Lua recently switched
from using a Yacc definition to a hand-crafted parser in the interests of
compilation speed.

> I really need a decent book on the parsing -> code generation ->
> VM part of it all, or at least some good resources on the net to
> read.
Other than the VM part, the definitive work is The Dragon Book, or Aho,
Sethi, and Ullman's Compilers: Principles, Techniques, and Tools.  I've
found it to be indispensible.  Check out the comp.compilers FAQ for more
book reviews:

If you're interested in a Hand-Written Parsers for Dummies type of approach,
however, Jack Crenshaw's Let's Build a Compiler is a fairly popular series,
but unfinished:

> Thanks in advance guys, and thanks for tolerating my odd ramblings :)
No problem.  Good luck.

Ryan Bright