This week on my Parrot day, I hooked the tree grammar parser I wrote a couple weeks ago into the tree transformation engine I wrote last week. So, you can now write tree grammar rules in a nice sensible format like:
Leaf: min(.) = {
$P1 = getattribute node, 'value'
.return ($P1)
}
That rule says "When you're looking for the value of an attribute called min on a node called Leaf, it's the same value as the attribute value on the same node." Yes, that's PIR syntax inside the body of the block. With a little syntactic sugar: it provides you two named parameters node (the current node being operated on) and tree (the current tree being matched).
Ultimately there will be some prettier syntax there, but we haven't designed it yet. Using PIR in the mean-time gives lots of flexibility to experiment and figure out all the things we want tree grammars to be able to do.
Okay, that's cool, as far as it goes, but how is it useful? Well, to transform the tree, you just provide a rule for each node type to be transformed:
Leaf: result(.) = {
.local pmc newnode
newnode = new 'Leaf'
$P1 = tree._AG_VISIT('gmin', node)
setattribute newnode, 'value', $P1
.return(newnode)
}
This rule says "When I ask for the result attribute, what I actually want is a new node with the right shape for the transformed tree. In this case, when I start with a Leaf node, I want a Leaf node in the new tree, but instead of the original value, give me the global minimum (gmin) value calculated by the grammar." (_AG_VISIT is a particularly ugly name for get. Pardon the bones still sticking out, they'll be covered soon.)
When you've defined result rules for all the node types, requesting the result attribute for the top level node of the tree builds up the transformed tree for you. It's not magic, but it feels like magic.
If you check out the repository, you'll find a full test grammar in examples/branch_pir.g, and a test script that compiles the grammar and runs it against a sample tree in testtransform.pir.
So, how is all of that useful? This is where we get to the 'bootstrapping' part. The tree transformation engine uses itself to compile the tree grammar syntax. First it parses the source using a PGE grammar, then it uses a tree grammar to transform the match tree that PGE produces into another tree grammar. Really, it's not magic, but it is very cool. :) So, not only does the tree transformation engine work, but it's also the first test case for demonstrating that the engine is a useful compiler tool. Lots of refactoring left to do, but it's a good start. I'm happy. :)
this looks very nice. I'm almost tempted to take this and wrap it into a PIR backend for ANTLR. This way I could avoid learning Python for implementing 'Parrot bc'.
Re:Way cool
Allison on 2005-11-07T21:27:42
If you try it and find you need some features added, let me know. I'm looking for a few real-world applications to test and expand it on.
Re:Fun
Allison on 2005-11-07T16:31:29
Not surprising. XSLT is another tree transformation language.