Burg not needed any more now that SparcV9 is gone.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@27901 91177308-0d34-0410-b5e6-96231b3b80d8

38 files changed, 1 insertions, 6495 deletions

diff --git a/utils/Burg/.cvsignore b/utils/Burg/.cvsignore
deleted file mode 100644
index 9497b362f6..0000000000
--- a/utils/Burg/.cvsignore
+++ /dev/null
@@ -1,2 +0,0 @@
-gram.tab.c
-gram.tab.h
diff --git a/utils/Burg/COPYRIGHT b/utils/Burg/COPYRIGHT
deleted file mode 100644
index 1de0aad6f2..0000000000
--- a/utils/Burg/COPYRIGHT
+++ /dev/null
@@ -1,13 +0,0 @@
-Copyright (C) 1991 Todd A. Proebsting
-All Rights Reserved.
-
-This software is in the public domain.  You may use and copy this material
-freely. This privilege extends to modifications, although any modified
-version of this system given to a third party should clearly identify your
-modifications as well as the original source.
-
-The responsibility for the use of this material resides entirely with you.
-We make no warranty of any kind concerning this material, nor do we make
-any claim as to the suitability of BURG for any application.  This software
-is experimental in nature and there is no written or implied warranty.  Use
-it at your own risk.
diff --git a/utils/Burg/Doc/Makefile b/utils/Burg/Doc/Makefile
deleted file mode 100644
index 60e603f441..0000000000
--- a/utils/Burg/Doc/Makefile
+++ /dev/null
@@ -1,92 +0,0 @@
-##===- utils/Burg/Doc/Makefile ------------------------------*- Makefile -*-===##
-# 
-#                     The LLVM Compiler Infrastructure
-#
-# This file was developed by the LLVM research group and is distributed under
-# the University of Illinois Open Source License. See LICENSE.TXT for details.
-# 
-##===----------------------------------------------------------------------===##
-# $Id$
-
-#CFLAGS	=
-#CFLAGS	= -O
-#CFLAGS	= -O -DNOLEX
-CFLAGS	= -g -DDEBUG
-#CFLAGS	= -g -DNOLEX -DDEBUG
-
-SRCS = \
-	be.c \
-	burs.c \
-	closure.c \
-	delta.c \
-	fe.c \
-	item.c \
-	lex.c \
-	list.c \
-	main.c \
-	map.c \
-	nonterminal.c \
-	operator.c \
-	pattern.c \
-	plank.c \
-	queue.c \
-	rule.c \
-	string.c \
-	symtab.c \
-	table.c \
-	trim.c \
-	zalloc.c
-
-BU_OBJS = \
-	burs.o \
-	closure.o \
-	delta.o \
-	item.o \
-	list.o \
-	map.o \
-	nonterminal.o \
-	operator.o \
-	pattern.o \
-	queue.o \
-	rule.o \
-	table.o \
-	trim.o \
-	zalloc.o
-
-FE_OBJS = \
-	be.o \
-	fe.o \
-	lex.o \
-	main.o \
-	plank.o \
-	string.o \
-	symtab.o \
-	y.tab.o
-
-all: test
-
-burg: $(BU_OBJS) $(FE_OBJS)
-	$(CC) -o burg $(CFLAGS) $(BU_OBJS) $(FE_OBJS)
-
-y.tab.c y.tab.h: gram.y
-	yacc -d gram.y
-
-clean:
-	rm -f *.o y.tab.h y.tab.c core burg *.aux *.log *.dvi sample sample.c tmp
-
-$(FE_OBJS):	b.h
-$(BU_OBJS):	b.h
-$(FE_OBJS):	fe.h
-
-lex.o:	y.tab.h
-
-doc.dvi: doc.tex
-	latex doc; latex doc
-
-test: burg sample.gr
-	./burg -I     <sample.gr   >sample.c && cc $(CFLAGS) -o sample sample.c && ./sample
-	./burg -I      sample.gr   >tmp && cmp tmp sample.c
-	./burg -I     <sample.gr -o tmp && cmp tmp sample.c
-	./burg -I      sample.gr -o tmp && cmp tmp sample.c
-	./burg -I -O0 <sample.gr   >tmp && cmp tmp sample.c
-	./burg -I -=  <sample.gr   >tmp && cmp tmp sample.c
diff --git a/utils/Burg/Doc/doc.aux b/utils/Burg/Doc/doc.aux
deleted file mode 100644
index 0f7c13f020..0000000000
--- a/utils/Burg/Doc/doc.aux
+++ /dev/null
@@ -1,50 +0,0 @@
-\relax 
-\bibstyle{alpha}
-\citation{aho-twig-toplas}
-\citation{appel-87}
-\citation{balachandran-complang}
-\citation{kron-phd}
-\citation{hoffmann-jacm}
-\citation{hatcher-popl}
-\citation{chase-popl}
-\citation{pelegri-popl}
-\citation{pelegri-phd}
-\citation{wilhelm-tr}
-\citation{henry-budp}
-\citation{fraser-henry-spe-91}
-\citation{proebsting-91}
-\@writefile{toc}{\contentsline {section}{\numberline {1}Overview}{1}}
-\@writefile{toc}{\contentsline {section}{\numberline {2}Input}{1}}
-\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces A Sample Tree Grammar}}{2}}
-\newlabel{fig-tree-grammar}{{1}{2}}
-\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces EBNF Grammar for Tree Grammars for {\sc  Burg}\ }}{3}}
-\newlabel{fig-grammar-grammar}{{2}{3}}
-\@writefile{toc}{\contentsline {section}{\numberline {3}Output}{3}}
-\citation{aho-johnson-dp-classic}
-\citation{fraser-henry-spe-91}
-\citation{henry-budp}
-\citation{pelegri-phd}
-\@writefile{toc}{\contentsline {section}{\numberline {4}Debugging}{6}}
-\@writefile{toc}{\contentsline {section}{\numberline {5}Running {\sc  Burg}\ }{6}}
-\newlabel{sec-man-page}{{5}{6}}
-\citation{pelegri-popl}
-\citation{henry-budp}
-\citation{balachandran-complang}
-\citation{proebsting-91}
-\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces A Diverging Tree Grammar}}{7}}
-\newlabel{fig-diverge-grammar}{{3}{7}}
-\@writefile{toc}{\contentsline {section}{\numberline {6}Acknowledgements}{7}}
-\bibcite{aho-twig-toplas}{AGT89}
-\bibcite{aho-johnson-dp-classic}{AJ76}
-\bibcite{appel-87}{App87}
-\bibcite{balachandran-complang}{BDB90}
-\bibcite{wilhelm-tr}{BMW87}
-\bibcite{chase-popl}{Cha87}
-\bibcite{fraser-henry-spe-91}{FH91}
-\bibcite{hatcher-popl}{HC86}
-\bibcite{henry-budp}{Hen89}
-\bibcite{hoffmann-jacm}{HO82}
-\bibcite{kron-phd}{Kro75}
-\bibcite{pelegri-phd}{PL87}
-\bibcite{pelegri-popl}{PLG88}
-\bibcite{proebsting-91}{Pro91}
diff --git a/utils/Burg/Doc/doc.dvi b/utils/Burg/Doc/doc.dvi
deleted file mode 100644
index 3211f32c96..0000000000
--- a/utils/Burg/Doc/doc.dvi
+++ /dev/null
diff --git a/utils/Burg/Doc/doc.log b/utils/Burg/Doc/doc.log
deleted file mode 100644
index a224a4edf7..0000000000
--- a/utils/Burg/Doc/doc.log
+++ /dev/null
@@ -1,157 +0,0 @@
-This is TeX, Version 3.14159 (Web2C 7.3.2) (format=latex 2000.8.30)  4 JUN 2001 13:20
-**doc
-(doc.tex
-LaTeX2e <2000/06/01>
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latex209.def
-File: latex209.def 1998/05/13 v0.52 Standard LaTeX file
-
-
-          Entering LaTeX 2.09 COMPATIBILITY MODE
- *************************************************************
-    !!WARNING!!    !!WARNING!!    !!WARNING!!    !!WARNING!!   
- 
- This mode attempts to provide an emulation of the LaTeX 2.09
- author environment so that OLD documents can be successfully
- processed. It should NOT be used for NEW documents!
- 
- New documents should use Standard LaTeX conventions and start
- with the \documentclass command.
- 
- Compatibility mode is UNLIKELY TO WORK with LaTeX 2.09 style
- files that change any internal macros, especially not with
- those that change the FONT SELECTION or OUTPUT ROUTINES.
- 
- Therefore such style files MUST BE UPDATED to use
-          Current Standard LaTeX: LaTeX2e.
- If you suspect that you may be using such a style file, which
- is probably very, very old by now, then you should attempt to
- get it updated by sending a copy of this error message to the
- author of that file.
- *************************************************************
-
-\footheight=\dimen102
-\@maxsep=\dimen103
-\@dblmaxsep=\dimen104
-\@cla=\count79
-\@clb=\count80
-\mscount=\count81
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/tracefnt.sty
-Package: tracefnt 1997/05/29 v3.0j Standard LaTeX package (font tracing)
-\tracingfonts=\count82
-LaTeX Info: Redefining \selectfont on input line 96.
-)
-\symbold=\mathgroup4
-\symsans=\mathgroup5
-\symtypewriter=\mathgroup6
-\symitalic=\mathgroup7
-\symsmallcaps=\mathgroup8
-\symslanted=\mathgroup9
-LaTeX Font Info:    Redeclaring math alphabet \mathbf on input line 288.
-LaTeX Font Info:    Redeclaring math alphabet \mathsf on input line 289.
-LaTeX Font Info:    Redeclaring math alphabet \mathtt on input line 290.
-LaTeX Font Info:    Redeclaring math alphabet \mathit on input line 296.
-LaTeX Info: Redefining \em on input line 306.
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/latexsym.sty
-Package: latexsym 1998/08/17 v2.2e Standard LaTeX package (lasy symbols)
-\symlasy=\mathgroup10
-LaTeX Font Info:    Overwriting symbol font `lasy' in version `bold'
-(Font)                  U/lasy/m/n --> U/lasy/b/n on input line 42.
-)
-LaTeX Font Info:    Redeclaring math delimiter \lgroup on input line 370.
-LaTeX Font Info:    Redeclaring math delimiter \rgroup on input line 372.
-LaTeX Font Info:    Redeclaring math delimiter \bracevert on input line 374.
-
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/config/latex209.cf
-g
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/rawfonts.sty
-Compatibility mode: package `' requested, but `rawfonts' provided.
-Package: rawfonts 1994/05/08 Low-level LaTeX 2.09 font compatibility
-
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/tools/somedefs.sty
-Package: somedefs 1994/06/01 Toolkit for optional definitions
-)
-LaTeX Font Info:    Try loading font information for U+lasy on input line 44.
- (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/ulasy.fd
-File: ulasy.fd 1998/08/17 v2.2eLaTeX symbol font definitions
-)))) (/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/article.
-cls
-Document Class: article 2000/05/19 v1.4b Standard LaTeX document class
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/base/size11.clo
-File: size11.clo 2000/05/19 v1.4b Standard LaTeX file (size option)
-)
-\c@part=\count83
-\c@section=\count84
-\c@subsection=\count85
-\c@subsubsection=\count86
-\c@paragraph=\count87
-\c@subparagraph=\count88
-\c@figure=\count89
-\c@table=\count90
-\abovecaptionskip=\skip41
-\belowcaptionskip=\skip42
-Compatibility mode: definition of \rm ignored.
-Compatibility mode: definition of \sf ignored.
-Compatibility mode: definition of \tt ignored.
-Compatibility mode: definition of \bf ignored.
-Compatibility mode: definition of \it ignored.
-Compatibility mode: definition of \sl ignored.
-Compatibility mode: definition of \sc ignored.
-LaTeX Info: Redefining \cal on input line 501.
-LaTeX Info: Redefining \mit on input line 502.
-\bibindent=\dimen105
-)
-(/usr/dcs/software/supported/encap/TeX/share/texmf/tex/latex/pstex/fullpage.sty
-) (doc.aux)
-\openout1 = `doc.aux'.
-
-LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 2.
-LaTeX Font Info:    ... okay on input line 2.
-LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 2.
-LaTeX Font Info:    ... okay on input line 2.
-LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 2.
-LaTeX Font Info:    ... okay on input line 2.
-LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 2.
-LaTeX Font Info:    ... okay on input line 2.
-LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 2.
-LaTeX Font Info:    ... okay on input line 2.
-LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 2.
-LaTeX Font Info:    ... okay on input line 2.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <12> on input line 33.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <8> on input line 33.
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <6> on input line 33.
-LaTeX Font Info:    Try loading font information for OMS+cmtt on input line 100
-.
-LaTeX Font Info:    No file OMScmtt.fd. on input line 100.
-LaTeX Font Warning: Font shape `OMS/cmtt/m/n' undefined
-(Font)              using `OMS/cmsy/m/n' instead
-(Font)              for symbol `textbraceleft' on input line 100.
- [1
-
-]
-LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <10.95> on input line 150.
- [2] [3] [4] [5] [6]
-Overfull \hbox (1.38191pt too wide) in paragraph at lines 480--484
-[]\OT1/cmr/m/n/10.95 Emit code for \OT1/cmtt/m/n/10.95 burm[]arity\OT1/cmr/m/n/
-10.95 , \OT1/cmtt/m/n/10.95 burm[]child\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95
- burm[]cost\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.95 burm[]ntname\OT1/cmr/m/n/10
-.95 , \OT1/cmtt/m/n/10.95 burm[]op[]label\OT1/cmr/m/n/10.95 , \OT1/cmtt/m/n/10.
-95 burm[]opname\OT1/cmr/m/n/10.95 ,
- []
-
-[7] [8] [9] (doc.aux)
-LaTeX Font Warning: Some font shapes were not available, defaults substituted.
- ) 
-Here is how much of TeX's memory you used:
- 543 strings out of 12968
- 6147 string characters out of 289029
- 446019 words of memory out of 1453895
- 3433 multiletter control sequences out of 10000+10000
- 23403 words of font info for 87 fonts, out of 400000 for 2000
- 14 hyphenation exceptions out of 1000
- 21i,6n,20p,308b,283s stack positions out of 300i,100n,500p,50000b,4000s
-
-Output written on doc.dvi (9 pages, 29856 bytes).
diff --git a/utils/Burg/Doc/doc.tex b/utils/Burg/Doc/doc.tex
deleted file mode 100644
index 3dc67be317..0000000000
--- a/utils/Burg/Doc/doc.tex
+++ /dev/null
@@ -1,596 +0,0 @@
-\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(NODE