Lua Grammar

wiki

Lua 5.2/5.1 Grammars for OMeta

Lua 5.2 Grammar for javacc

Lua 5.2 Parser in Lua

Lua 5.1 Grammar for javacc

Lua 5.1 Grammar for Antlr

Lua 5.1 Grammar in the Reference Manual

"Section 8 - The Complete Syntax of Lua" of the Lua Reference Manual[1] provides an extended BNF grammar (without operator precedences) of Lua 5.1. For precedence, see [Section 2.5.6 - Precedence].

Lua 5.1 Grammar in Lemon format

This is essentially the same as Lemon[2] format, except that it permits quoted strings for literal terminals. See Listing 1 below.

Lua 5.1/5.0 Compiler in C

The original C parser of Lua, of course, exists in the source code of the Lua distribution, but it is hand-written in C and not easy to reuse.

Lua 5.1 Lexer and Parser in LPeg in Lua

LpegRecipes list Lua 5.1 lexers and parsers in Lua LPeg.

Lua 5.1 Parser in Lua

The mlp parser, included in MetaLua, can parse Lua (as well as Lua with syntax extensions) and convert it into an AST. mlp is built on top of the gg grammar generator, which can build extensible parsers with user-defined grammars. mlp and gg are written entirely in Lua, and its lexer is based on Yueliang (below). gg/mlp is used, for example, in MetaLua and LuaToCee.

Cheese[3] is a parser generator that uses Parsing Expression Grammars (PEG) as its description formalism and Lua itself as a description language for the parsers. It includes a parser that understands the complete syntax of Lua 5.1. (The PEG appears to be an effort that predates LPeg.)

LuaBalanced provides some functions that match delimited snippets of Lua code in a string. It avoids rigorously lexing and parsing the Lua grammar by assuming the Lua code is syntactically correct (which can be verified later using loadstring).

PenLight? provides a Lua lexer only [4][5] implemented in Lua.

Lua 5.1 Compiler in Lua

[Yueliang] implements a full Lua compiler in Lua. It is a fairly direct port of the Lua C code to Lua.

Lua 5.1 Compiler in Parrot

Parrot [6] contains a compiler, written in Perl5, that compiles Lua 5.1 down to Parrot VM bytecodes (though it's a work in progress). There is also a web interface to the subversion repository [7].

See also related efforts:

• [Monkey] - an implementation of Lua on Parrot - A Lua to PIR compiler implemented in C
• [lua2pir] - A Lua bytecode to PIR compiler

Lua 5.1/5.0 Test Suite

Those reimplementing Lua may be interested in the test suite for 5.1 LuaList:2006-03/msg00716.html and 5.0 LuaList:2005-12/msg00312.html.

Lua 5.0 Parser in Lua - LuaParse

In August 2004, Rici Lake announced a new Lua 5.0 parser on the lua mailing list, implemented in Lua: [LuaParse].

A Lua 5.0 Grammar in Gentle

[Lua2js] contains a complete grammar for Lua 5.0 done with the Gentle[8] compiler construction kit.

Lua 5.0 in Parser in Haskell/Parsec

The lua-xgettext tool includes a parser in Haskell/Parsec: LuaList:2006-10/msg00609.html

Lua 5.0 Parser in C++ Spirit

A mostly complete C++ parser of Lua 5.0, which is using Spirit from Boost: http://article.gmane.org/gmane.comp.parsers.spirit.general/4846

This seems like a nice start for reusing in your own things that need a Lua interpreter in C++. The author has abandoned the project, and the above is the latest version as of February 2004. In February 2005, I looked at this grammar closer to try to use it. There are a number of problems with it:

• id's can start with _. Easy to fix.
• Escaped ' and " inside strings are not working. Easy to fix.
• Comments can only appear at statement level. A work-around is to add it to expressions and fields rules, which improves things a lot. Make sure to do *( comment ) instead of just comment to handle comments after each other.
• Long comments --[[ ]] are not supported. Easy to fix by changing comment to shortcomment and longcomment. Make sure to put longcomment first, because spirit is eager.
• a[b] = 2 does not parse. Some function calls are not parsed correctly, i.e. a(b)(). It seems that the refactoring of the left recursion with prefixexp is not done correctly. I have failed to fix this.

The last point is a show-stopper for me. Thus I have failed to make Spirit parse Lua correctly.

-- Asger Ottar Alstrup (aalstrup at laerdal.dk)

There is another spirit parser that I wrote for SZARP SCADA system. It is tested mostly for simple cases when we can bypass actual lua and execute statments without resorting to vm, but generally it seems to be doing all right. It should not suffer from deficiencies mentioned above and is written using latest spirit API. It may be a little difficult to use right away because it is a part of larger system but still its dependencies are rather minimal.

The parser files can be reached here: http://szarp.git.sourceforge.net/git/gitweb.cgi?p=szarp/szarp;a=tree;f=libSzarp2;hb=master It is split among four files: include/lua_syntax.h and szbase/lua_parser.cc, szbase/lua_parser_extra.cc, szbase/lua_parser_extra.h

In case of any questions, drop me an e-mail: Darek Marcinkiewicz (reksio at newterm.pl)

Lua 5.0 Lexer in re2c

LexicalAnalysis

Lua 4.1 Grammar

Moved to LuaFourOneGrammar

Lua 4 Interpreter in Java - JLua

An incomplete interpreter of Lua 4 implemented in Java: http://www.hetland.org/jlua/ (broken link)

Lua 2.5 Interpreter in OCaml - Lua-ml

[Lua-ml] is an implementation of Lua 2.5 in OCaml. The parser is constructed with some OCaml parser generator, wrapped up in some literate programming system.

Listing 1

Lua 5.1 grammar in Lemon--RiciLake [Implemented in LJS]

%fallback  OPEN '(' .

chunk      ::= block .

semi       ::= ';' .
semi       ::= .

block      ::= scope statlist .
block      ::= scope statlist laststat semi .
ublock     ::= block 'until' exp .

scope      ::= .
scope      ::= scope statlist binding semi.
           
statlist   ::= .
statlist   ::= statlist stat semi .

stat       ::= 'do' block 'end' .
stat       ::= 'while' exp 'do' block 'end' .
stat       ::= repetition 'do' block 'end' .
stat       ::= 'repeat' ublock .
stat       ::= 'if' conds 'end' .
stat       ::= 'function' funcname funcbody .
stat       ::= setlist '=' explist1 .
stat       ::= functioncall .

repetition ::= 'for' NAME '=' explist23 .
repetition ::= 'for' namelist 'in' explist1 .
           
conds      ::= condlist .
conds      ::= condlist 'else' block .
condlist   ::= cond .
condlist   ::= condlist 'elseif' cond .
cond       ::= exp 'then' block .
           
laststat   ::= 'break' .
laststat   ::= 'return' .
laststat   ::= 'return' explist1 .

binding    ::= 'local' namelist .
binding    ::= 'local' namelist '=' explist1 .
binding    ::= 'local' 'function' NAME funcbody .

funcname   ::= dottedname .
funcname   ::= dottedname ':' NAME .

dottedname ::= NAME .
dottedname ::= dottedname '.' NAME .

namelist   ::= NAME .
namelist   ::= namelist ',' NAME .

explist1   ::= exp .
explist1   ::= explist1 ',' exp .
explist23  ::= exp ',' exp .
explist23  ::= exp ',' exp ',' exp .

%left      'or' .
%left      'and' .
%left      '<' '<=' '>' '>=' '==' '~=' .
%right     '..' .
%left      '+' '-' .
%left      '*' '/' '%' .
%right     'not' '#' .
%right     '^' .

exp        ::= 'nil'|'true'|'false'|NUMBER|STRING|'...' .
exp        ::= function .
exp        ::= prefixexp .
exp        ::= tableconstructor .
exp        ::= 'not'|'#'|'-' exp .         ['not']
exp        ::= exp 'or' exp .
exp        ::= exp 'and' exp .
exp        ::= exp '<'|'<='|'>'|'>='|'=='|'~=' exp .
exp        ::= exp '..' exp .
exp        ::= exp '+'|'-' exp .
exp        ::= exp '*'|'/'|'%' exp .
exp        ::= exp '^' exp .
           
setlist    ::= var .
setlist    ::= setlist ',' var .

var        ::= NAME .
var        ::= prefixexp '[' exp ']' .
var        ::= prefixexp '.' NAME .

prefixexp  ::= var .
prefixexp  ::= functioncall .
prefixexp  ::= OPEN exp ')' .

functioncall ::= prefixexp args .
functioncall ::= prefixexp ':' NAME args .

args        ::= '(' ')' .
args        ::= '(' explist1 ')' .
args        ::= tableconstructor .
args        ::= STRING .

function    ::= 'function' funcbody .

funcbody    ::= params block 'end' .

params      ::= '(' parlist ')' .

parlist     ::= .
parlist     ::= namelist .
parlist     ::= '...' .
parlist     ::= namelist ',' '...' .

tableconstructor ::= '{' '}' .
tableconstructor ::= '{' fieldlist '}' .
tableconstructor ::= '{' fieldlist ','|';' '}' .

fieldlist   ::= field .
fieldlist   ::= fieldlist ','|';' field .
            
field       ::= exp .
field       ::= NAME '=' exp .
field       ::= '[' exp ']' '=' exp .