Re: Operator-precedence parsers in Lua

[Hugo Musso Gualandi <hgualandi@...>]

> Hi list,
> 
> anyone knows implementations of operator-precedence parsers in Lua?
> 
> I am (sort of) sure that I can write one myself, but I am so bad at
> choosing names of variables, functions, classes, fields, etc, that I
> would prefer to start by looking at what people have already done...
For parsing stuff, I'm a fan of using a top-down recursive descent
parsers. They can handle prefix and postfix operators and it also
generalizes well to parsing other kinds of things. But the best part is
that it doesn't depend on any libraries. Once you learn how to do it in
one language you can do it in any language.

The lovely Crafting Interpreters book has an excellent explanation of
how to do it, including the tricks for parsing left-associative binary
operators:
https://craftinginterpreters.com/parsing-expressions.html

If you look at the solution presented in the book you'll notice that it
creates a series of mutually recursive functions, one for each
precedence level. For example if you had a language with just the + and
* operators you would say that an expression is a sum of factors, and
that a factor is a product of elementary expressions such as numbers.

As an exercise to the reader, the book suggests that instead of having
separate functions for each precedence level (term, factor, etc) you
can create a helper function that receives the precedence level as a
parameter. This happens to be exactly what Lua's own parser does. Check
out the "subexpr" function in lparser.c:
https://github.com/lua/lua/blob/master/lparser.c

If you're looking for some Lua code as an inspiration, you could also
take a look at the parser we wrote for Pallene. It's basically the same
algorithm as Lua's parser, except that we rewrote it in Lua and that we
output an abstract syntax tree.
https://github.com/pallene-lang/pallene/blob/master/pallene/parser.lua

-- Hugo