Jan 1, 2008

HBURG - Haskell Bottom Up Rewrite Generator

Overview

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

Source

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. 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 git, configure, and build manually:

Checkout:

 $ git clone https://github.com/1g0rb0hm/hburg && cd hburg

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.