lua-users home
lua-l archive

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

"Ryan Bright" <> writes:

> 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).

I recently posted to this list a grammar for Lua that is LALR(1),
which I know to be true because Bison accepts it.  I used the
precedence feature, so it is not strictly LALR(1) as written, but one
can easily transform it into a grammar that is.  I'll share the Bison
source if you really want to verify this fact.  I assume the LALR(1)
grammar defines the same language as accepted by the parser in the Lua
4.1 alpha release because no one has contradicted this assertion.

The Lua 4.1 alpha parser is a recursive decent parser of the form that
is often used to recognize languages defined by LL(1) grammars,
however, it is still not clear to me that there exists an LL(1)
grammar for Lua.  If you study the parser, you will find it makes
syntactic decisions for assignment and call statements by inspecting
the result of parsing a simpleexp.  This syntactic decision has no
obvious reflection in an LL(1) grammar.  I confess that once I found
an LALR(1) grammar, I have not made much of an effort to produce an
LL(1) grammar.  For the purposes of documentation, the LALR(1) grammar
is fine.

I would very much like to see an LL(1) for the Lua language.  
Please share one if you can generate one.