Added llvmgcc version to allow tests to be xfailed by frontend version.

[llvm-complete.git] / utils / Burg / Doc / doc.tex

\documentstyle[11pt,fullpage]{article}
\begin{document}

\def\AddSpace#1{\ifcat#1a\ \fi#1} % if next is a letter, add a space
\def\YACC#1{{\sc Yacc}\AddSpace#1}
\def\TWIG#1{{\sc Twig}\AddSpace#1}
\def\PROG#1{{\sc Burg}\AddSpace#1}
\def\PARSER#1{{\sc Burm}\AddSpace#1}
\def\CODEGEN#1{{\sc Codegen}\AddSpace#1}

\title{{\sc Burg} --- Fast Optimal Instruction Selection and Tree Parsing}
\author{
Christopher W. Fraser \\
AT\&T Bell Laboratories \\
600 Mountain Avenue 2C-464 \\
Murray Hill, NJ 07974-0636 \\
{\tt cwf@research.att.com}
\and
Robert R. Henry \\
Tera Computer Company \\
400 N. 34th St., Suite 300 \\
Seattle, WA 98103-8600 \\
{\tt rrh@tera.com}
\and
Todd A. Proebsting \\
Dept. of Computer Sciences \\
University of Wisconsin \\
Madison, WI 53706 \\
{\tt todd@cs.wisc.edu}
}
\date{December 1991}

\maketitle
\bibliographystyle{alpha}
\newcommand\term[1]{{\it #1}}
\newcommand\secref[1]{\S\ref{#1}}
\newcommand\figref[1]{Figure~\ref{#1}}
%
% rationale table making
%
{\catcode`\^^M=13 \gdef\Obeycr{\catcode`\^^M=13 \def^^M{\\}}%
\gdef\Restorecr{\catcode`\^^M=5 }} %

%
% for printing out options
%
\newcommand\option[1]{% #1=option character
{\tt -#1}%
}
\newcommand\var[1]{%
{\tt #1}%
}
\section{Overview}

\PROG is a program that generates a fast tree parser using BURS
(Bottom-Up Rewrite System) technology.  It accepts a cost-augmented
tree grammar and emits a C program that discovers in linear time an
optimal parse of trees in the language described by the grammar.  \PROG
has been used to construct fast optimal instruction selectors for use
in code generation.  \PROG addresses many of the problems addressed by
{\sc Twig}~\cite{aho-twig-toplas,appel-87}, but it is somewhat less flexible and
much faster.  \PROG is available via anonymous \var{ftp} from
\var{kaese.cs.wisc.edu}.  The compressed \var{shar} file
\var{pub/burg.shar.Z} holds the complete distribution.

This document describes only that fraction of the BURS model that is
required to use \PROG.  Readers interested in more detail might start
with Reference~\cite{balachandran-complang}.  Other relevant documents
include References~\cite{kron-phd,hoffmann-jacm,hatcher-popl,chase-popl,pelegri-popl,pelegri-phd,wilhelm-tr,henry-budp,fraser-henry-spe-91,proebsting-91}.

\section{Input}

\PROG accepts a tree grammar and emits a BURS tree parser.
\figref{fig-tree-grammar} shows a sample grammar that implements a very
simple instruction selector.
\begin{figure}
\begin{verbatim}
%{
#define NODEPTR_TYPE treepointer
#define OP_LABEL(p) ((p)->op)
#define LEFT_CHILD(p) ((p)->left)
#define RIGHT_CHILD(p) ((p)->right)
#define STATE_LABEL(p) ((p)->state_label)
#define PANIC printf
%}
%start reg
%term Assign=1 Constant=2 Fetch=3 Four=4 Mul=5 Plus=6
%%
con:  Constant                = 1 (0);
con:  Four                    = 2 (0);
addr: con                     = 3 (0);
addr: Plus(con,reg)           = 4 (0);
addr: Plus(con,Mul(Four,reg)) = 5 (0);
reg:  Fetch(addr)             = 6 (1);
reg:  Assign(addr,reg)        = 7 (1);
\end{verbatim}
\caption{A Sample Tree Grammar\label{fig-tree-grammar}}
\end{figure}
\PROG grammars are structurally similar to \YACC's.  Comments follow C
conventions.  Text between ``\var{\%\{}'' and ``\var{\%\}}'' is called
the \term{configuration section};  there may be several such segments.
All are concatenated and copied verbatim into the head of the generated
parser, which is called \PARSER.  Text after the second ``\var{\%\%}'',
if any, is also copied verbatim into \PARSER, at the end.

The configuration section configures \PARSER for the trees being parsed
and the client's environment.  This section must define
\var{NODEPTR\_TYPE} to be a visible typedef symbol for a pointer to a
node in the subject tree.  \PARSER invokes \var{OP\_LABEL(p)},
\var{LEFT\_CHILD(p)}, and \var{RIGHT\_CHILD(p)} to read the operator
and children from the node pointed to by \var{p}.  It invokes
\var{PANIC} when it detects an error.  If the configuration section
defines these operations as macros, they are implemented in-line;
otherwise, they must be implemented as functions.  The section on
diagnostics elaborates on \var{PANIC}.

\PARSER computes and stores a single integral \term{state} in each node
of the subject tree.  The configuration section must define a macro
\var{STATE\_LABEL(p)} to access the state field of the node pointed to
by \var{p}.  A macro is required because \PROG uses it as an lvalue.  A
C \var{short} is usually the right choice; typical code generation
grammars require 100--1000 distinct state labels.

The tree grammar follows the configuration section.
\figref{fig-grammar-grammar} gives an EBNF grammar for \PROG tree
grammars.
\begin{figure}
\begin{verbatim}
grammar:  {dcl} '%%' {rule}

dcl:      '%start' Nonterminal
dcl:      '%term' { Identifier '=' Integer }

rule:     Nonterminal ':' tree '=' Integer cost ';'
cost:     /* empty */
cost:     '(' Integer { ',' Integer } ')'

tree:     Term '(' tree ',' tree ')'
tree:     Term '(' tree ')'
tree:     Term
tree:     Nonterminal
\end{verbatim}
\caption{EBNF Grammar for Tree Grammars for \PROG\ \label{fig-grammar-grammar}}
\end{figure}
Comments, the text between ``\var{\%\{}'' and ``\var{\%\}}'', and the
text after the optional second ``\var{\%\%}'' are treated lexically, so
the figure omits them.  In the EBNF grammar, quoted text must appear
literally, \var{Nonterminal} and \var{Integer} are self-explanatory,
and \var{Term} denotes an identifier previously declared as a
terminal.  {\tt\{$X$\}} denotes zero or more instances of $X$.

Text before the first ``\var{\%\%}'' declares the start symbol and the
terminals or operators in subject trees.  All terminals must be
declared; each line of such declarations begins with \var{\%term}.
Each terminal has fixed arity, which \PROG infers from the rules using that terminal.
\PROG restricts terminals to have at most two children.  Each terminal
is declared with a positive, unique, integral \term{external symbol
number} after a ``\var{=}''.  \var{OP\_LABEL(p)} must return the valid
external symbol number for \var{p}.  Ideally, external symbol numbers
form a dense enumeration.  Non-terminals are not declared, but the
start symbol may be declared with a line that begins with
\var{\%start}.

Text after the first ``\var{\%\%}'' declares the rules.  A tree grammar
is like a context-free grammar:  it has rules, non-terminals,
terminals, and a special start non-terminal.  The right-hand side of a
rule, called the \term{pattern}, is a tree.  Tree patterns appear in
prefix parenthesized form.  Every non-terminal denotes a tree.  A chain
rule is a rule whose pattern is another non-terminal.  If no start
symbol is declared, \PROG uses the non-terminal defined by the first
rule.  \PROG needs a single start symbol;  grammars for which it is
natural to use multiple start symbols must be augmented with an
artificial start symbol that derives, with zero cost, the grammar's
natural start symbols.  \PARSER will automatically select one
that costs least for any given tree.

\PROG accepts no embedded semantic actions like \YACC's, because no one
format suited all intended applications.  Instead, each rule has a
positive, unique, integral \term{external rule number}, after the
pattern and preceded by a ``\var{=}''.  Ideally, external rule numbers
form a dense enumeration.  \PARSER uses these numbers to report the
matching rule to a user-supplied routine, which must implement any
desired semantic action;  see below.  Humans may select these integers
by hand, but \PROG is intended as a \term{server} for building BURS
tree parsers.  Thus some \PROG clients will consume a richer
description and translate it into \PROG's simpler input.

Rules end with a vector of non-negative, integer costs, in parentheses
and separated by commas.  If the cost vector is omitted, then all
elements are assumed to be zero.  \PROG retains only the first four
elements of the list.  The cost of a derivation is the sum of the costs
for all rules applied in the derivation.  Arithmetic on cost vectors
treats each member of the vector independently.  The tree parser finds
the cheapest parse of the subject tree.  It breaks ties arbitrarily.
By default, \PROG uses only the \term{principal cost} of each cost
vector, which defaults to the first element, but options described
below provide alternatives.

\section{Output}

\PARSER traverses the subject tree twice.  The first pass or
\term{labeller} runs bottom-up and left-to-right, visiting each node
exactly once.  Each node is labeled with a state, a single number that
encodes all full and partial optimal pattern matches viable at that
node.  The second pass or \term{reducer} traverses the subject tree
top-down.  The reducer accepts a tree node's state label and a
\term{goal} non-terminal --- initially the root's state label and the
start symbol --- which combine to determine the rule to be applied at
that node.  By construction, the rule has the given goal non-terminal
as its left-hand side.  The rule's pattern identifies the subject
subtrees and goal non-terminals for all recursive visits.  Here, a
``subtree'' is not necessarily an immediate child of the current node.
Patterns with interior operators cause the reducer to skip the
corresponding subject nodes, so the reducer may proceed directly to
grandchildren, great-grandchildren, and so on.  On the other hand,
chain rules cause the reducer to revisit the current subject node, with
a new goal
non-terminal, so \term{x} is also regarded as a subtree of \term{x}.

As the reducer visits (and possibly revisits) each node, user-supplied
code implements semantic action side effects and controls the order in
which subtrees are visited.  The labeller is self-contained, but the
reducer combines code from \PROG with code from the user, so \PARSER
does not stand alone.

The \PARSER that is generated by \PROG provides primitives for
labelling and reducing trees.  These mechanisms are a compromise
between expressibility, abstraction, simplicity, flexibility and
efficiency.  Clients may combine primitives into labellers and reducers
that can traverse trees in arbitrary ways, and they may call semantic
routines when and how they wish during traversal.  Also, \PROG
generates a few higher level routines that implement common
combinations of primitives, and it generates mechanisms that help debug
the tree parse.

\PROG generates the labeller as a function named \var{burm\_label} with
the signature
\begin{verbatim}
extern int burm_label(NODEPTR_TYPE p);
\end{verbatim}
It labels the entire subject tree pointed to by \var{p} and returns the
root's state label.  State zero labels unmatched trees.  The trees may
be corrupt or merely inconsistent with the grammar.

The simpler \var{burm\_state} is \var{burm\_label} without the
code to traverse the tree and to read and write its fields.  It may be
used to integrate labelling into user-supplied traversal code.  A
typical signature is
\begin{verbatim}
extern int burm_state(int op, int leftstate, int rightstate);
\end{verbatim}
It accepts an external symbol number for a node and the labels for the
node's left and right children.  It returns the state label to assign
to that node.  For unary operators, the last argument is ignored; for
leaves, the last two arguments are ignored.  In general, \PROG
generates a \var{burm\_state} that accepts the maximum number of child
states required by the input grammar.  For example, if the grammar
includes no binary operators, then \var{burm\_state} will have the
signature
\begin{verbatim}
extern int burm_state(int op, int leftstate);
\end{verbatim}
This feature is included to permit future expansion to operators with
more than two children.

The user must write the reducer, but \PARSER writes code and data that
help.  Primary is
\begin{verbatim}
extern int burm_rule(int state, int goalnt);
\end{verbatim}
which accepts a tree's state label and a goal non-terminal and returns the
external rule number of a rule.  The rule will have matched the tree
and have the goal non-terminal on the left-hand side; \var{burm\_rule}
returns zero when the tree labelled with the given state did not match
the goal non-terminal.  For the initial, root-level call, \var{goalnt}
must be one, and \PARSER exports an array that identifies the values
for nested calls:
\begin{verbatim}
extern short *burm_nts[] = { ... };
\end{verbatim}
is an array indexed by external rule numbers.  Each element points to a
zero-terminated vector of short integers, which encode the goal
non-terminals for that rule's pattern, left-to-right.  The user needs
only these two externals to write a complete reducer, but a third
external simplifies some applications:
\begin{verbatim}
extern NODEPTR_TYPE *burm_kids(NODEPTR_TYPE p, int eruleno, NODEPTR_TYPE kids[]);
\end{verbatim}
accepts the address of a tree \var{p}, an external rule number, and an
empty vector of pointers to trees.  The procedure assumes that \var{p}
matched the given rule, and it fills in the vector with the subtrees (in
the sense described above) of \var{p} that must be reduced recursively.
\var{kids} is returned.  It is not zero-terminated.

The simple user code below labels and then fully reduces a subject tree;
the reducer prints the tree cover.  \var{burm\_string} is defined below.
\begin{verbatim}
parse(NODEPTR_TYPE p) {
  burm_label(p);   /* label the tree */
  reduce(p, 1, 0);  /* and reduce it */
}

reduce(NODEPTR_TYPE p, int goalnt, int indent) {
  int eruleno = burm_rule(STATE_LABEL(p), goalnt);  /* matching rule number */
  short *nts = burm_nts[eruleno];             /* subtree goal non-terminals */
  NODEPTR_TYPE kids[10];                                /* subtree pointers */
  int i;
  
  for (i = 0; i < indent; i++)
    printf(".");                                      /* print indented ... */
  printf("%s\n", burm_string[eruleno]);                 /* ... text of rule */
  burm_kids(p, eruleno, kids);               /* initialize subtree pointers */
  for (i = 0; nts[i]; i++)               /* traverse subtrees left-to-right */
    reduce(kids[i], nts[i], indent+1);        /* and print them recursively */
}
\end{verbatim}
The reducer may recursively traverse subtrees in any order, and it may
interleave arbitrary semantic actions with recursive traversals.
Multiple reducers may be written, to implement multi-pass algorithms
or independent single-pass algorithms.

For each non-terminal $x$, \PROG emits a preprocessor directive to
equate \var{burm\_}$x$\var{\_NT} with $x$'s integral encoding.  It also
defines a macro \var{burm\_}$x$\var{\_rule(a)} that is equivalent to
\var{burm\_rule(a,}$x$\var{)}.  For the grammar in
\figref{fig-tree-grammar}, \PROG emits
\begin{verbatim}
#define burm_reg_NT 1
#define burm_con_NT 2
#define burm_addr_NT 3
#define burm_reg_rule(a) ...
#define burm_con_rule(a) ...
#define burm_addr_rule(a) ...
\end{verbatim}
Such symbols are visible only to the code after the second
``\var{\%\%}''.  If the symbols \var{burm\_}$x$\var{\_NT} are needed
elsewhere, extract them from the \PARSER source.

The \option{I} option directs \PROG to emit an encoding of the input
that may help the user produce diagnostics.  The vectors
\begin{verbatim}
extern char *burm_opname[];
extern char burm_arity[];
\end{verbatim}
hold the name and number of children, respectively, for each terminal.
They are indexed by the terminal's external symbol number.  The vectors
\begin{verbatim}
extern char *burm_string[];
extern short burm_cost[][4];
\end{verbatim}
hold the text and cost vector for each rule.  They are indexed by the
external rule number.  The zero-terminated vector
\begin{verbatim}
extern char *burm_ntname[];
\end{verbatim}
is indexed by \var{burm\_}$x$\var{\_NT} and holds the name of
non-terminal $x$.  Finally, the procedures
\begin{verbatim}
extern int burm_op_label(NODEPTR_TYPE p);
extern int burm_state_label(NODEPTR_TYPE p);
extern NODEPTR_TYPE burm_child(NODEPTR_TYPE p, int index);
\end{verbatim}
are callable versions of the configuration macros.
\var{burm\_child(p,0)} implements \var{LEFT\_CHILD(p)}, and
\var{burm\_child(p,1)} implements \var{RIGHT\_CHILD(p)}.  A sample use
is the grammar-independent expression
\var{burm\_opname[burm\_op\_label(p)]}, which yields the textual name
for the operator in the tree node pointed to by \var{p}.

A complete tree parser can be assembled from just \var{burm\_state},
\var{burm\_rule}, and \var{burm\_nts}, which use none of the
configuration section except \var{PANIC}.  The generated routines that
use the rest of the configuration section are compiled only if the
configuration section defines \var{STATE\_LABEL}, so they can be
omitted if the user prefers to hide the tree structure from \PARSER.
This course may be wise if, say, the tree structure is defined in a
large header file with symbols that might collide with \PARSER's.

\PARSER selects an optimal parse without dynamic programming at compile
time~\cite{aho-johnson-dp-classic}.  Instead, \PROG does the dynamic
programming at compile-compile time, as it builds \PARSER.
Consequently, \PARSER parses quickly.  Similar labellers have taken as
few as 15 instructions per node, and reducers as few as 35 per node
visited~\cite{fraser-henry-spe-91}.

\section{Debugging}

\PARSER invokes \var{PANIC} when an error prevents it from proceeding.
\var{PANIC} has the same signature as \var{printf}.  It should pass its
arguments to \var{printf} if diagnostics are desired and then either
abort (say via \var{exit}) or recover (say via \var{longjmp}).  If it
returns, \PARSER aborts.  Some errors are not caught.

\PROG assumes a robust preprocessor, so it omits full consistency
checking and error recovery.  \PROG constructs a set of states using a
closure algorithm like that used in LR table construction.  \PROG
considers all possible trees generated by the tree grammar and
summarizes infinite sets of trees with finite sets.  The summary
records the cost of those trees but actually manipulates the
differences in costs between viable alternatives using a dynamic
programming algorithm.  Reference~\cite{henry-budp} elaborates.

Some grammars derive trees whose optimal parses depend on arbitrarily
distant data.  When this happens, \PROG and the tree grammar
\term{cost diverge}, and \PROG attempts to build an infinite
set of states; it first thrashes and ultimately exhausts
memory and exits.  For example, the tree grammar in
\figref{fig-diverge-grammar}
\begin{figure}
\begin{verbatim}
%term Const=17 RedFetch=20 GreenFetch=21 Plus=22
%%
reg: GreenFetch(green_reg) = 10 (0);
reg: RedFetch(red_reg) = 11 (0);

green_reg: Const = 20 (0);
green_reg: Plus(green_reg,green_reg) = 21 (1);

red_reg: Const = 30 (0);
red_reg: Plus(red_reg,red_reg) = 31 (2);
\end{verbatim}
\caption{A Diverging Tree Grammar\label{fig-diverge-grammar}}
\end{figure}
diverges, since non-terminals \var{green\_reg} and \var{red\_reg}
derive identical infinite trees with different costs.  If the cost of
rule 31 is changed to 1, then the grammar does not diverge.

Practical tree grammars describing instruction selection do not
cost-diverge because infinite trees are derived from non-terminals
that model temporary registers.  Machines can move data between
different types of registers for a small bounded cost, and the rules
for these instructions prevent divergence.  For example, if
\figref{fig-diverge-grammar} included rules to move data between red
and green registers, the grammar would not diverge.  If a bonafide
machine grammar appears to make \PROG loop, try a host with more
memory.  To apply \PROG to problems other than instruction selection,
be prepared to consult the literature on
cost-divergence~\cite{pelegri-phd}.

\section{Running \PROG\ }\label{sec-man-page}

\PROG reads a tree grammar and writes a \PARSER in C.  \PARSER can be
compiled by itself or included in another file.  When suitably named
with the \option{p} option, disjoint instances of \PARSER should link
together without name conflicts.  The command:
\begin{flushleft}
\var{burg} [ {\it arguments} ] [ {\it file} ]
\end{flushleft}
invokes \PROG.  If a {\it file} is named, \PROG expects its grammar
there; otherwise it reads the standard input.  The options include:
\def\Empty{}
%
\newcommand\odescr[2]{% #1=option character, #2=optional argument
\gdef\Arg2{#2}%
\item[\option{#1}\ifx\Arg2\Empty\else{{\it #2}}\fi]
}
\begin{description}
%
\odescr{c}{} $N$
Abort if any relative cost exceeds $N$, which keeps \PROG from looping on
diverging grammars.  Several
references~\cite{pelegri-popl,henry-budp,balachandran-complang,proebsting-91}
explain relative costs.
%
\odescr{d}{}
Report a few statistics and flag unused rules and terminals.
%
\odescr{o}{} {\it file}
Write parser into {\it file}.  Otherwise it writes to the standard output.
%
\odescr{p}{} {\it prefix}
Start exported names with {\it prefix}.  The default is \var{burm}.
%
\odescr{t}{}
Generates smaller tables faster, but all goal non-terminals passed to
\var{burm\_rule} must come from an appropriate \var{burm\_nts}.  Using
\var{burm\_}$x$\var{\_NT} instead may give unpredictable results.
%
\odescr{I}{}
Emit code for \var{burm\_arity}, \var{burm\_child}, \var{burm\_cost},
\var{burm\_ntname}, \var{burm\_op\_label}, \var{burm\_opname},
\var{burm\_state\_label}, and \var{burm\_string}.
%
\odescr{O}{} $N$
Change the principal cost to $N$.  Elements of each cost vector are
numbered from zero.
%
\odescr{=}{}
Compare costs lexicographically, using all costs in the given order.
This option slows \PROG and may produce a larger parser.  Increases
range from small to astronomical.
\end{description}

\section{Acknowledgements}

The first \PROG was adapted by the second author from his \CODEGEN
package, which was developed at the University of Washington with
partial support from NSF Grant CCR-88-01806.  It was unbundled from
\CODEGEN with the support of Tera Computer.  The current \PROG was
written by the third author with the support of NSF grant
CCR-8908355.  The interface, documentation, and testing involved
all three authors.

Comments from a large group at the 1991 Dagstuhl Seminar on Code
Generation improved \PROG's interface.  Robert Giegerich and Susan
Graham organized the workshop, and the International Conference and
Research Center for Computer Science, Schloss Dagstuhl, provided an
ideal environment for such collaboration.  Beta-testers included Helmut
Emmelmann, Dave Hanson, John Hauser, Hugh Redelmeier, and Bill Waite.

\begin{thebibliography}{BMW87}

\bibitem[AGT89]{aho-twig-toplas}
Alfred~V. Aho, Mahadevan Ganapathi, and Steven W.~K. Tjiang.
\newblock Code generation using tree matching and dynamic programming.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  11(4):491--516, October 1989.

\bibitem[AJ76]{aho-johnson-dp-classic}
Alfred~V. Aho and Steven~C. Johnson.
\newblock Optimal code generation for expression trees.
\newblock {\em Journal of the ACM}, 23(3):458--501, July 1976.

\bibitem[App87]{appel-87}
Andrew~W. Appel.
\newblock Concise specification of locally optimal code generators.
\newblock Technical report CS-TR-080-87, Princeton University, 1987.

\bibitem[BDB90]{balachandran-complang}
A.~Balachandran, D.~M. Dhamdhere, and S.~Biswas.
\newblock Efficient retargetable code generation using bottom-up tree pattern
  matching.
\newblock {\em Computer Languages}, 15(3):127--140, 1990.

\bibitem[BMW87]{wilhelm-tr}
J\"{u}rgen B\"{o}rstler, Ulrich M\"{o}nche, and Reinhard Wilhelm.
\newblock Table compression for tree automata.
\newblock Technical Report Aachener Informatik-Berichte No. 87-12, RWTH Aachen,
  Fachgruppe Informatik, Aachen, Fed. Rep. of Germany, 1987.

\bibitem[Cha87]{chase-popl}
David~R. Chase.
\newblock An improvement to bottom up tree pattern matching.
\newblock {\em Fourteenth Annual ACM Symposium on Principles of Programming
  Languages}, pages 168--177, January 1987.

\bibitem[FH91]{fraser-henry-spe-91}
Christopher~W. Fraser and Robert~R. Henry.
\newblock Hard-coding bottom-up code generation tables to save time and space.
\newblock {\em Software---Practice\&Experience}, 21(1):1--12, January 1991.

\bibitem[HC86]{hatcher-popl}
Philip~J. Hatcher and Thomas~W. Christopher.
\newblock High-quality code generation via bottom-up tree pattern matching.
\newblock {\em Thirteenth Annual ACM Symposium on Principles of Programming
  Languages}, pages 119--130, January 1986.

\bibitem[Hen89]{henry-budp}
Robert~R. Henry.
\newblock Encoding optimal pattern selection in a table-driven bottom-up
  tree-pattern matcher.
\newblock Technical Report 89-02-04, University of Washington Computer Science
  Department, Seattle, WA, February 1989.

\bibitem[HO82]{hoffmann-jacm}
Christoph Hoffmann and Michael~J. O'Donnell.
\newblock Pattern matching in trees.
\newblock {\em Journal of the ACM}, 29(1):68--95, January 1982.

\bibitem[Kro75]{kron-phd}
H.~H. Kron.
\newblock {\em Tree Templates and Subtree Transformational Grammars}.
\newblock PhD thesis, UC Santa Cruz, December 1975.

\bibitem[PL87]{pelegri-phd}
Eduardo Pelegri-Llopart.
\newblock {\em Tree Transformations in Compiler Systems}.
\newblock PhD thesis, UC Berkeley, December 1987.

\bibitem[PLG88]{pelegri-popl}
Eduardo Pelegri-Llopart and Susan~L. Graham.
\newblock Optimal code generation for expression trees: An application of
  {BURS} theory.
\newblock {\em Fifteenth Annual ACM Symposium on Principles of Programming
  Languages}, pages 294--308, January 1988.

\bibitem[Pro91]{proebsting-91}
Todd~A. Proebsting.
\newblock Simple and efficient {BURS} table generation.
\newblock Technical report, Department of Computer Sciences, University of
  Wisconsin, 1991.

\end{thebibliography}

\end{document}