[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: bottom-up processing
- From: Richard Hundt <richardhundt@...>
- Date: Fri, 06 Nov 2009 15:27:49 +0100
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  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
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
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
It does mean that the parser and code generator are very tightly
coupled, though, but it also makes for fast, small memory footprint