bottom-up processing

[spir <denis.spir@...>]

Hello,

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.

A node action to write the line of code for a repetitive pattern may look like this (I write in python, for I don't know yet matching lua idioms):
def repetitionExpression(node):
    (pattern, min, max) = node.data
    params = "%s, %s, %s" % (pattern, min, max)
    node.data = "Repetition(%s)" % params
This works because the func can rely on the fact that child node have already transformed themselves as expected -- recursively. Using nearly the same expression, I can alternatively transform a whole grammar into a mega-pattern, a kind of giant regex, instead of a set of patterns, simply by inserting the expression of sub-patterns instead of a reference to them.

To be more concrete, a parser for (arbitrary complex) expression evaluation could directly yield results using node actions as complicated as:
def negate(node):
    node.data = - node.data
def doAdd(node):
    (op1,op2) = node.data
    node.data = op1 + op2
def writeVar(node):
    (name,value) = node.data
	state.vars[name] = value
def readVar(node):
    name = node.data
	node.data = state.vars[name]
...
Then the top node is a leaf containing the result... provided the source is correct.

There are a bunch of standard node actions to restructure a parse tree. Eg a 'negation' would yield a node that looks like negation:[NEG, op]. I get rid of NEG setting 'drop' on its pattern, and 'extract' unnests the operand, so as to return negation:op.
I also often use node actions to write metadata on a node itself, while the said data is still at hand.

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.

Denis
------
la vita e estrany