HBURG (the acronym stands for Haskell Bottom Up Rewrite Generator) is a FREE and easy to use implementation of a code generator generator based upon Tree Pattern Matching and Dynamic Programming. HBURG is a program that generates tree parsers for cost-augmented tree grammars. It is useful for writing code generators for compilers. Given a mapping of a tree structured intermediate representation onto target machine instructions, HBURG generates a code generator that can be plugged into the instruction selection phase of a compiler.
- Automatic Code Generation Using Dynamic Programming Techniques
- Initial Project Specification
- HBURG presentation conveying underlying theory and some nice examples
HBURG is released under a BSD license and implemented in Haskell. Several Haskell extensions and GHC-spcific features are used. It is highly recommended to use the GHC compiler to build HBURG. You may also need darcs to checkout the source code, but a source tarball exists as well.
$ darcs get http://www.bytelabs.org/hburg/ && cd hburg
If you are not using darcs you may want to download the source distribution: hburg-1.1.2.tar.gz.
$ runghc Setup.hs configure
$ runghc Setup.hs build
$ runghc Setup.hs install </code></pre>
The best way to demonstrate how to use HBURG is by example. Below you find a link to a tarball which includes a compiler written in Java for a simple language. The compiler itself does not perform any optimizations, nor does it produce fully functional and executable assembly code. The following common stages found in almost all compilers are implemented:
- Lexing & Parsing via a LL(k) Coco/R attribute grammar specification (see src/sl/parser/SL.atg)
- Construction of an AST and simple context sensitive analysis
- RISC like code generation via an HBURG tree pattern matching grammar specification (see src/sl/code/risc/RISC.tpg)
Example programs of the simple language as well as an intermediate AST XML dump and the resulting assembly files can be found in the examples directory of the compiler (see below on how to build the compiler, the test ant target runs the examples through the compiler toolchain).
- Sources: java-compiler.tgz (Example compiler showing how to use HBURG)
- Building and running the example CISC compiler:
$ ant clean parser cisc build test
- Building and running the example RISC compiler:
$ ant clean parser risc build test
- For HBURG ant integration see the risc and cisc targets in the build.xml file.
References & Related Projects
- Code Generation using Tree Matching and Dynamic Programming [Alfred V. Aho, Mahadevan Ganapathi, Steven W.K Tjiang]
- Engineering a Simple and Efficient Code Generator Generator [Fraser, Ch.W., Hanson D.R., Proebsting T.A.]
- BEG - A Generator for Efficient Back Ends [Emmelmann, H., Schröer, F.-W., Landwehr, R.]
- Automating the Selection of Code Templates [Horspool, N.R.]
- Simple and Efficient BURS Table Generation [Proebsting, T.A.]
- BURS Automata Generation [Proebsting, T.A.]