About Me

My photo
Author of Groovy modules: GBench, GProf, Co-author of a Java book パーフェクトJava, Game Developer at GREE

Thursday, October 13, 2011

A way to write Groovy's AST easily

It is hard to write AST

Groovy provides a DSL to generate AST for implementation of AST transformation. But the DSL is complicated and hard to learn. Let's assume that you want to generate AST of GString:
"Hi, $name."
In this case, the DSL will be the following. Who can remember this stuff as many as the syntax?
gString 'Hi, $name.', {
    strings {
        constant 'Hi, '
        constant '.'
    }
    values {
        variable 'name'
    }
}

AST is also can be generated from code, but it does not benefit from the compiler checking (Joachim Baumann explains about it) and performance is less than the DSL. Please see the following benchmark:
@Grab('com.googlecode.gbench:gbench:0.2.2')
import gbench.BenchmarkBuilder
import org.codehaus.groovy.ast.builder.AstBuilder

def benchmarks = new BenchmarkBuilder().run {
    'DSL to AST' {
        new AstBuilder().buildFromSpec {
            gString 'Hi, $name.', {
                strings {
                    constant 'Hi, '
                    constant '.'
                }
                values {
                    variable 'name'
                }
            }
        }
    }
    'Code to AST' {
        new AstBuilder().buildFromString('"Hi, $name"')
    }
}
benchmarks.prettyPrint()

            user system cpu    real

DSL to AST     0      0   0  339918
Code to AST    0      0   0 2076590
So at the end of the day, you will cheat implementation code or test code of the DSL while writing AST. I believe that you can easily imagine it is a hard work.

How can we write the DSL easily?

I created a library that automatically generates the DSL from code to resolve the problem. The library, named AstSpecBuilder is now available here. The usage is very simple, just pass code to build method:
import astspecbuilder.*

def spec = new AstSpecBuilder().build('"Hi, $name."')

def expectedSpec =  '''\
block {
    returnStatement {
        gString 'Hi, $name.', {
            strings {
                constant 'Hi, '
                constant '.'
            }
            values {
                variable 'name'
            }
        }
    }
}
'''
assert expectedSpec == spec
It also can generate the DSL from AST, or rather the method in the above example is just a shortcut for the following code:
import astspecbuilder.*

def ast = new AstBuilder.buildFromString('"Hi, $name."')
def spec = new AstSpecBuilder().build(ast)

The indent string is 4 spaces by default but it has an option to change it. In the following example, the DSL will be indented with a tab:
def spec = new AstSpecBuilder(indent: '\t').build('"foo"')

def expectedSpec = '''\
block {
\treturnStatement {
\t\tconstant 'foo'
\t}
}
'''
assert expectedSpec == spec

2 comments:

  1. Hi Nagai Masato
    thanks for post. I have similar problem with AST generate. AstSpecBuilder is cool. Thanks

    ReplyDelete
    Replies
    1. Thank you Tom. Your comment game me power!

      Delete