lua-users home
lua-l archive

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

spir wrote:

I'm new to Lua and the list. Jump on the opportunity to comment and ask about the following:

Roberto Ierusalimschy wrote:
Lua does not build an AST; it generates code on the fly.

I'm rather surprised to read this. Thought, actually, that I was the only one to use such an approach for big jobs like that. I have never read about the topic, but anyway my knowledge in computer science lies at the zeroth level ;-)

I'd like to know how the method used in Lua code generation compares to the following:
* Each pattern possibly assign a "post-parse node action" (or several) to each node they will generate.
* This action transforms the node (or rather its data), including possibly collapsing whole branches into what becomes a simple leaf.
* That way, each node is responsible to pass itself in the most convenient form to higher levels.

This method is incredibly easy and powerful. Usually, it will not only help converting or restructuring nodes or branches, instead directly produce the desired result, be it returning a computed value or performing an action such as writing xhtml from wiki lang. I call that "bottom-up processing", mirroring "top-down parsing".
In a personal parsing tool (in python), I use it intensively to generate parsers. The meta-grammar specifies such actions so that the meta-parser does all the job -- actually the generator itself is a func of ~ 15 lines mainly instantiating a result parser with proper params.


I think what you're describing is essentially an "attribute grammar", so you may find [1] interesting, or just google around for the term.

Before using this method, I long tried the hard way of walking parse trees, from outside and from the top.
Well, sorry if all of this is well-known to the ones of you possibly interested in the topic. The opportunity was too tempting. I'd really love pointers if any. But above all, I'm really curious about the method used in Lua to generate code while parsing.

If the language is fairly simple, you can do everything in one pass. Lua doesn't do any hoisting (e.g. in JavaScript you can call a function before it is declared), and the register allocation is more stack-like (so no graph colouring or linear scan algorithms, or similar, which require later analysis of variable lifetimes).

I haven't studied Lua's compiler code, so YMMV, but I'm going for the general principle here.

The basic strategy is to emit instructions when you've collected enough information during parsing to do so, simple statements and expressions like: local a = 41; a = a + 1, can have code generated for them at the end of the statement/expression (1 token lookahead is nice to have here), others require recursing down and then generating the opcodes a bit later.

I can imagine that there is also a certain amount of back patching of instructions and meta-data (variable life-time, upvalues, etc.) in the generated bytecode stream besides the usual forward jumps stuff for conditional branching.

It does mean that the parser and code generator are very tightly coupled, though, but it also makes for fast, small memory footprint compilation.

Richard Hundt