JBurg Frequently Asked Questions

• What is JBurg?

  JBurg is a Bottom-Up Rewrite Machine Generator for Java.

  A bottom-up rewrite machine is a compiler construction tool that is often used in the compiler's back end to convert a tree-structured representation of a program into machine code -- or, in this case, bytecode.

  A very simple compiler tool chain is:

  source code -> JavaCC -> syntax tree -> JBurg-generated BURM -> BCEL -> Java class.

  This distribution includes a brief introduction to the theory.

• Help! My compiler fails with a "Unable to find a rule to process x(22){-1}" exception.

  Your BURM encountered a tree segment that didn't match any available pattern, or that could not satisfy a goal state required by a parent. See the debugging guide

• What are JBurg's system requirements?
  • JBurg is written in Java and generates Java code. JBurg itself, and the generated rewrite machine, both use inner classes.
  • JBurg uses the ANTLR parser generator to parse JBurg specifications. ANTLR is available from http://www.antlr.org.
    Note that the generated BURM does not depend on ANTLR in any way.

• Is JBurg related to the other "jburg" projects out on the 'Net?

  No. Unfortunately, "j" and "burg" have proven to be a very crowded namespace.

  JBurg's pattern-matching code and some parts of its dynamic programming engine were based on Fraser, Hanson, and Proebsting's paper on iburg, but aside from a close reading of the paper and its examples, all JBurg's code was developed independently.

• Do I have to deploy any JBurg components with my compiler?

  No. The bottom-up rewrite machine that JBurg generates is self-contained.

• How well do JBurg-generated rewrite machines scale?
  We have studied JBurg computations using theoretical analysis, runtime analysis using performance tools such as JProbe, and by measuring the elapsed time required to compile stress-test programs. JBurg generates a bottom-up rewrite machine that is O(N).

• Is JBurg like JJTree? What makes bottom-up rewrite worth the trouble of learning a new language?
  It is difficult to compare the two techniques precisely, because their theory is different: JJTree works from the top down, and it has hard-coded logic at choice points that guide it. JBurg works from the bottom-up, and finds patterns in the tree that satisfy goals. Goals can then be re-used as subgoals by a parent node, or they can be used at the same level of the tree to help satisfy additional goals. For example, consider this pattern, which derives an integer constant:
  int_value = INTEGER(void) { ... }

  This could be used as a subgoal by a parent PLUS:

  int_value = PLUS(int_value a, int_value b)
  {
      // implement PLUS
  }
  

  It can also be used to transform INTEGER into an object:

  object_value = int_value
  {
      //  Create a new Integer
  }
  

  So JBurg specifications look a little bit like the terminals and non-terminals of a JJTree grammar, but the "lines between the dots" aren't drawn in; they're sort of sketched in, and the dynamic programming engine finds an minimum-cost cover of the input tree.

• What's a "minimum-cost cover?"
  • Cover the tree means that all the nodes in the tree will be matched to an appropriate goal state. If any node does not match any appropriate goal state, then JBurg will throw an exception.
  • minimum-cost cover means that if there are multiple possible covers of the tree (which is usually the case), then JBurg will select the cover with the least overall cost.

• What's "Dynamic Programming?"

  The dynamic programming engine in a JBurg-generated rewrite machine works from the bottom of the tree upwards to find the minimum-cost cover. It is described in detail on the theory page.