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.

Documentation

• Automatic Code Generation Using Dynamic Programming Techniques
• Initial Project Specification
• HBURG presentation conveying underlying theory and some nice examples

Sources

• https://www.bytelabs.org/hburg/ (darcs repository)
  • darcs get https://www.bytelabs.org/hburg/ (darcs checkout)
• https://github.com/1g0rb0hm/hburg (github repository)
  • git clone https://github.com/1g0rb0hm/hburg.git (git checkout)
• hburg-1.1.3.tar.gz (source tarball)

HBURG is released under a BSD license and implemented in Haskell. Several Haskell extensions and GHC-specific 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 from its origin. A source tarball together with a GitHub repository exists as well.

HBURG Installation

Hackage Installation

Hackage is the Haskell community's central package archive of open source software. HBURG is available as a package on Hackage and can be installed as follows:

 $ cabal update
 $ cabal install hburg

Source Installation

The following steps are necessary if you would like to checkout the source code using darcs, configure, and build manually:

Checkout:

 $ darcs get https://www.bytelabs.org/hburg/ && cd hburg

If you are not using darcs you may want to download the source distribution: hburg-1.1.3.tar.gz.

Configure:

 $ runghc Setup.hs configure

Build:

 $ runghc Setup.hs build

Install:

 $ runghc Setup.hs install

Test:

 $ runghc Test.hs test 

Example

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.]
• iBurg
• JBurg
• OCamlBurg