Slash Boxes
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Allison (3003)

  (email not shown publicly)

Human (I think).

Journal of Allison (3003)

Thursday November 03, 2005
12:40 AM

bootstrapping tree transformation grammars

[ #27427 ]

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

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. :)

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
More | Login | Reply
Loading... please wait.
  • 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'.

    /* */
    • 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.
  • To my twisted brain this looks a lot like XSLT - basically providing templates and specifying what to generate on the output.