+++ /dev/null
-gram.tab.c
-gram.tab.h
+++ /dev/null
-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.
+++ /dev/null
-##===- 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
+++ /dev/null
-\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}
+++ /dev/null
-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).
+++ /dev/null
-\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}
-
+++ /dev/null
-Burg
-------------------------------------------------------------------------------
-Burg is licensed under the LLVM license. It has the following additional
-copyrights and restrictions:
-
-Copyright (C) 1991 Todd A. Proebsting
-All Rights Reserved.
-
-If you distribute a modified version of Burg, please document the changes you
-make in addition to redistributing our list of changes to the original Burg.
-
-See llvm/utils/Burg/LOG_CHANGES for a list of changes we have made to Burg.
-
-Burg is also located in llvm/test/Programs/MultiSource/Applications/Burg. The
-only modifications made to it are to allow it to compile.
-
-We originally downloaded Burg from the following URL:
-ftp://ftp.cs.arizona.edu/people/todd/burg.shar.Z
-
+++ /dev/null
-8/20/02 -- Vikram Adve
- be.c: Replaced "char*" with "const char*" to avoid compiler warnings.
-
-9/9/03 -- John Criswell
- b.h be.c fe.h gram.y lex.c main.c map.c nontermainl.c plan.c zalloc.c:
- A cursory look through our logs and comments indicates that these are
- the only modified files. No feature enhancements have been made;
- rather, all changes either fix minor programming errors, get rid of
- warnings, ANSI-ify the code, or integrate Burg into our build system.
-
+++ /dev/null
-##===- utils/Burg/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.
-#
-##===----------------------------------------------------------------------===##
-LEVEL = ../..
-TOOLNAME = burg
-BUILT_SOURCES = gram.tab.c gram.tab.h
-
-EXTRA_DIST = gram.yc gram.tab.c gram.tab.h sample.gr burg.shar.gz COPYRIGHT Doc
-
-include $(LEVEL)/Makefile.common
-
-gram.tab.c gram.tab.h: gram.yc
- $(Verb) $(BISON) -o gram.tab.c -d $<
-
-$(ObjDir)/lex.o : gram.tab.h
-
-clean::
- $(Verb) $(RM) -rf gram.tab.h gram.tab.c core* *.aux *.log *.dvi sample sample.c tmp
-
-doc.dvi: doc.tex
- $(Verb) latex doc; latex doc
-
-check:: $(ToolBuildPath) $(BUILD_SRC_DIR)/sample.gr
- $(ToolBuildPath) -I <$(BUILD_SRC_DIR)/sample.gr >sample.c \
- && $(CC) $(CFLAGS) -o sample sample.c && ./sample
- $(ToolBuildPath) -I $(BUILD_SRC_DIR)/sample.gr >tmp \
- && cmp tmp sample.c
- $(ToolBuildPath) -I <$(BUILD_SRC_DIR)/sample.gr -o tmp \
- && cmp tmp sample.c
- $(ToolBuildPath) -I $(BUILD_SRC_DIR)/sample.gr -o tmp \
- && cmp tmp sample.c
- $(ToolBuildPath) -I -O0 <$(BUILD_SRC_DIR)/sample.gr >tmp \
- && cmp tmp sample.c
- $(ToolBuildPath) -I -= <$(BUILD_SRC_DIR)/sample.gr >tmp \
- && cmp tmp sample.c
- $(RM) -f tmp sample.c
+++ /dev/null
-To format the documentation, type "make doc.dvi" and print the result.
-
-The length of the cost vectors is fixed at 4 for reasons that are
-primarily historical. To change it, edit the definition of DELTAWIDTH
-in b.h.
-
-Burg is compiled without optimization by default to avoid problems
-with initial installation. To improve burg's performance, add '-O' to
-CFLAGS in the Makefile and rebuild burg with a high quality optimizing
-compiler.
-
-To be added to the Burg mailing list, send your preferred electronic
-mail address to cwf@research.att.com.
-
+++ /dev/null
-/* $Id$ */
-
-#define MAX_ARITY 2
-
-typedef int ItemSetNum;
-typedef int OperatorNum;
-typedef int NonTerminalNum;
-typedef int RuleNum;
-typedef int ArityNum;
-typedef int ERuleNum;
-
-extern NonTerminalNum last_user_nonterminal;
-extern NonTerminalNum max_nonterminal;
-extern RuleNum max_rule;
-extern ERuleNum max_erule_num;
-extern int max_arity;
-
-#ifdef __STDC__
-#define ARGS(x) x
-#else
-#define ARGS(x) ()
-#endif
-
-#ifndef NOLEX
-#define DELTAWIDTH 4
-typedef short DeltaCost[DELTAWIDTH];
-typedef short *DeltaPtr;
-extern void ASSIGNCOST ARGS((DeltaPtr, DeltaPtr));
-extern void ADDCOST ARGS((DeltaPtr, DeltaPtr));
-extern void MINUSCOST ARGS((DeltaPtr, DeltaPtr));
-extern void ZEROCOST ARGS((DeltaPtr));
-extern int LESSCOST ARGS((DeltaPtr, DeltaPtr));
-extern int EQUALCOST ARGS((DeltaPtr, DeltaPtr));
-#define PRINCIPLECOST(x) (x[0])
-#else
-#define DELTAWIDTH 1
-typedef int DeltaCost;
-typedef int DeltaPtr;
-#define ASSIGNCOST(l, r) ((l) = (r))
-#define ADDCOST(l, r) ((l) += (r))
-#define MINUSCOST(l, r) ((l) -= (r))
-#define ZEROCOST(x) ((x) = 0)
-#define LESSCOST(l, r) ((l) < (r))
-#define EQUALCOST(l, r) ((l) == (r))
-#define PRINCIPLECOST(x) (x)
-#endif /* NOLEX */
-#define NODIVERGE(c,state,nt,base) if (prevent_divergence > 0) CHECKDIVERGE(c,state,nt,base);
-
-struct list {
- void *x;
- struct list *next;
-};
-typedef struct list *List;
-
-struct intlist {
- int x;
- struct intlist *next;
-};
-typedef struct intlist *IntList;
-
-struct operator {
- char *name;
- unsigned int ref:1;
- OperatorNum num;
- ItemSetNum baseNum;
- ItemSetNum stateCount;
- ArityNum arity;
- struct table *table;
-};
-typedef struct operator *Operator;
-
-struct nonterminal {
- char *name;
- NonTerminalNum num;
- ItemSetNum baseNum;
- ItemSetNum ruleCount;
- struct plankMap *pmap;
-
- struct rule *sampleRule; /* diagnostic---gives "a" rule that with this lhs */
-};
-typedef struct nonterminal *NonTerminal;
-
-struct pattern {
- NonTerminal normalizer;
- Operator op; /* NULL if NonTerm -> NonTerm */
- NonTerminal children[MAX_ARITY];
-};
-typedef struct pattern *Pattern;
-
-struct rule {
- DeltaCost delta;
- ERuleNum erulenum;
- RuleNum num;
- RuleNum newNum;
- NonTerminal lhs;
- Pattern pat;
- unsigned int used:1;
-};
-typedef struct rule *Rule;
-
-struct item {
- DeltaCost delta;
- Rule rule;
-};
-typedef struct item Item;
-
-typedef short *Relevant; /* relevant non-terminals */
-
-typedef Item *ItemArray;
-
-struct item_set { /* indexed by NonTerminal */
- ItemSetNum num;
- ItemSetNum newNum;
- Operator op;
- struct item_set *kids[2];
- struct item_set *representative;
- Relevant relevant;
- ItemArray virgin;
- ItemArray closed;
-};
-typedef struct item_set *Item_Set;
-
-#define DIM_MAP_SIZE (1 << 8)
-#define GLOBAL_MAP_SIZE (1 << 15)
-
-struct mapping { /* should be a hash table for TS -> int */
- List *hash;
- int hash_size;
- int max_size;
- ItemSetNum count;
- Item_Set *set; /* map: int <-> Item_Set */
-};
-typedef struct mapping *Mapping;
-
-struct index_map {
- ItemSetNum max_size;
- Item_Set *class;
-};
-typedef struct index_map Index_Map;
-
-struct dimension {
- Relevant relevant;
- Index_Map index_map;
- Mapping map;
- ItemSetNum max_size;
- struct plankMap *pmap;
-};
-typedef struct dimension *Dimension;
-
-
-struct table {
- Operator op;
- List rules;
- Relevant relevant;
- Dimension dimen[MAX_ARITY]; /* 1 for each dimension */
- Item_Set *transition; /* maps local indices to global
- itemsets */
-};
-typedef struct table *Table;
-
-struct relation {
- Rule rule;
- DeltaCost chain;
- NonTerminalNum nextchain;
- DeltaCost sibling;
- int sibFlag;
- int sibComputed;
-};
-typedef struct relation *Relation;
-
-struct queue {
- List head;
- List tail;
-};
-typedef struct queue *Queue;
-
-struct plank {
- char *name;
- List fields;
- int width;
-};
-typedef struct plank *Plank;
-
-struct except {
- short index;
- short value;
-};
-typedef struct except *Exception;
-
-struct plankMap {
- List exceptions;
- int offset;
- struct stateMap *values;
-};
-typedef struct plankMap *PlankMap;
-
-struct stateMap {
- char *fieldname;
- Plank plank;
- int width;
- short *value;
-};
-typedef struct stateMap *StateMap;
-
-struct stateMapTable {
- List maps;
-};
-
-extern void CHECKDIVERGE ARGS((DeltaPtr, Item_Set, int, int));
-extern void zero ARGS((Item_Set));
-extern ItemArray newItemArray ARGS((void));
-extern ItemArray itemArrayCopy ARGS((ItemArray));
-extern Item_Set newItem_Set ARGS((Relevant));
-extern void freeItem_Set ARGS((Item_Set));
-extern Mapping newMapping ARGS((int));
-extern NonTerminal newNonTerminal ARGS((char *));
-extern int nonTerminalName ARGS((char *, int));
-extern Operator newOperator ARGS((char *, OperatorNum, ArityNum));
-extern Pattern newPattern ARGS((Operator));
-extern Rule newRule ARGS((DeltaPtr, ERuleNum, NonTerminal, Pattern));
-extern List newList ARGS((void *, List));
-extern IntList newIntList ARGS((int, IntList));
-extern int length ARGS((List));
-extern List appendList ARGS((void *, List));
-extern Table newTable ARGS((Operator));
-extern Queue newQ ARGS((void));
-extern void addQ ARGS((Queue, Item_Set));
-extern Item_Set popQ ARGS((Queue));
-extern int equivSet ARGS((Item_Set, Item_Set));
-extern Item_Set decode ARGS((Mapping, ItemSetNum));
-extern Item_Set encode ARGS((Mapping, Item_Set, int *));
-extern void build ARGS((void));
-extern Item_Set *transLval ARGS((Table, int, int));
-
-typedef void * (*ListFn) ARGS((void *));
-extern void foreachList ARGS((ListFn, List));
-extern void reveachList ARGS((ListFn, List));
-
-extern void addToTable ARGS((Table, Item_Set));
-
-extern void closure ARGS((Item_Set));
-extern void trim ARGS((Item_Set));
-extern void findChainRules ARGS((void));
-extern void findAllPairs ARGS((void));
-extern void addRelevant ARGS((Relevant, NonTerminalNum));
-
-extern void *zalloc ARGS((unsigned int));
-extern void zfree ARGS((void *));
-
-extern NonTerminal start;
-extern List rules;
-extern List chainrules;
-extern List operators;
-extern List leaves;
-extern List nonterminals;
-extern List grammarNts;
-extern Queue globalQ;
-extern Mapping globalMap;
-extern int exceptionTolerance;
-extern int prevent_divergence;
-extern int principleCost;
-extern int lexical;
-extern struct rule stub_rule;
-extern Relation *allpairs;
-extern Item_Set *sortedStates;
-extern Item_Set errorState;
-
-extern void dumpRelevant ARGS((Relevant));
-extern void dumpOperator ARGS((Operator, int));
-extern void dumpOperator_s ARGS((Operator));
-extern void dumpOperator_l ARGS((Operator));
-extern void dumpNonTerminal ARGS((NonTerminal));
-extern void dumpRule ARGS((Rule));
-extern void dumpRuleList ARGS((List));
-extern void dumpItem ARGS((Item *));
-extern void dumpItem_Set ARGS((Item_Set));
-extern void dumpMapping ARGS((Mapping));
-extern void dumpQ ARGS((Queue));
-extern void dumpIndex_Map ARGS((Index_Map *));
-extern void dumpDimension ARGS((Dimension));
-extern void dumpPattern ARGS((Pattern));
-extern void dumpTable ARGS((Table, int));
-extern void dumpTransition ARGS((Table));
-extern void dumpCost ARGS((DeltaCost));
-extern void dumpAllPairs ARGS((void));
-extern void dumpRelation ARGS((Relation));
-extern void dumpSortedStates ARGS((void));
-extern void dumpSortedRules ARGS((void));
-extern int debugTrim;
-
-#ifdef DEBUG
-#define debug(a,b) if (a) b
-#else
-#define debug(a,b)
-#endif
-extern int debugTables;
-
-#define TABLE_INCR 8
-#define STATES_INCR 64
-
-#ifdef NDEBUG
-#define assert(c) ((void) 0)
-#else
-#define assert(c) ((void) ((c) || fatal(__FILE__,__LINE__)))
-#endif
-
-extern void doStart ARGS((char *));
-extern void exit ARGS((int));
-extern int fatal ARGS((const char *, int));
-extern void yyerror ARGS((const char *));
-extern void yyerror1 ARGS((const char *));
+++ /dev/null
-char rcsid_be[] = "$Id$";
-
-#include <stdio.h>
-#include <string.h>
-#include "b.h"
-#include "fe.h"
-
-#define ERROR_VAL 0
-
-FILE *outfile;
-const char *prefix = "burm";
-
-static void doKids ARGS((RuleAST));
-static void doLabel ARGS((Operator));
-static void doLayout ARGS((RuleAST));
-static void doMakeTable ARGS((Operator));
-static void doVector ARGS((RuleAST));
-static void layoutNts ARGS((PatternAST));
-static void makeIndex_Map ARGS((Dimension));
-static void makePvector ARGS((void));
-static void makeState ARGS((void));
-static void printPatternAST ARGS((PatternAST));
-static void printPatternAST_int ARGS((PatternAST));
-static void setVectors ARGS((PatternAST));
-static void trailing_zeroes ARGS((int));
-static int seminal ARGS((int from, int to));
-static void printRule ARGS((RuleAST, const char *));
-
-static void
-doLabel(op) Operator op;
-{
- fprintf(outfile, "\tcase %d:\n", op->num);
-
- switch (op->arity) {
- default:
- assert(0);
- break;
- case 0:
- fprintf(outfile, "\t\treturn %d;\n", op->table->transition[0]->num);
- break;
- case 1:
- if (op->table->rules) {
- fprintf(outfile, "\t\treturn %s_%s_transition[l];\n", prefix, op->name);
- } else {
- fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
- }
- break;
- case 2:
- if (op->table->rules) {
- fprintf(outfile, "\t\treturn %s_%s_transition[%s_%s_imap_1[l]][%s_%s_imap_2[r]];\n", prefix, op->name, prefix, op->name, prefix, op->name);
- } else {
- fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
- }
- break;
- }
-}
-
-int
-opsOfArity(arity) int arity;
-{
- int c;
- List l;
-
- c = 0;
- for (l = operators; l; l = l->next) {
- Operator op = (Operator) l->x;
- if (op->arity == arity) {
- fprintf(outfile, "\tcase %d:\n", op->num);
- c++;
- }
- }
- return c;
-}
-
-static void
-trailing_zeroes(z) int z;
-{
- int i;
-
- for (i = 0; i < z; i++) {
- fprintf(outfile, ", 0");
- }
-}
-
-void
-makeLabel()
-{
- int flag;
-
- fprintf(outfile, "#ifdef __STDC__\n");
- fprintf(outfile, "int %s_label(%s_NODEPTR_TYPE n) {\n", prefix, prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "int %s_label(n) %s_NODEPTR_TYPE n; {\n", prefix, prefix);
- fprintf(outfile, "#endif\n");
-
- fprintf(outfile,
- "\t%s_assert(n, %s_PANIC(\"NULL pointer passed to %s_label\\n\"));\n",
- prefix, prefix, prefix);
- fprintf(outfile, "\tswitch (%s_OP_LABEL(n)) {\n", prefix);
- fprintf(outfile, "\tdefault: %s_PANIC(\"Bad op %%d in %s_label\\n\", %s_OP_LABEL(n)); abort(); return 0;\n",
- prefix, prefix, prefix);
-
- flag = opsOfArity(0);
- if (flag > 0) {
- fprintf(outfile, "\t\treturn %s_STATE_LABEL(n) = %s_state(%s_OP_LABEL(n)",
- prefix, prefix, prefix);
- trailing_zeroes(max_arity);
- fprintf(outfile, ");\n");
- }
- flag = opsOfArity(1);
- if (flag > 0) {
- fprintf(outfile, "\t\treturn %s_STATE_LABEL(n) = %s_state(%s_OP_LABEL(n), %s_label(%s_LEFT_CHILD(n))",
- prefix, prefix, prefix, prefix, prefix);
- trailing_zeroes(max_arity-1);
- fprintf(outfile, ");\n");
- }
- flag = opsOfArity(2);
- if (flag > 0) {
- fprintf(outfile, "\t\treturn %s_STATE_LABEL(n) = %s_state(%s_OP_LABEL(n), %s_label(%s_LEFT_CHILD(n)), %s_label(%s_RIGHT_CHILD(n))",
- prefix, prefix, prefix, prefix, prefix, prefix, prefix);
- trailing_zeroes(max_arity-2);
- fprintf(outfile, ");\n");
-
- }
- fprintf(outfile, "\t}\n");
- fprintf(outfile, "}\n");
-}
-
-static void
-makeState()
-{
- fprintf(outfile, "int %s_state(int op, int l, int r) {\n", prefix);
- fprintf(outfile,
- "\t%s_assert(l >= 0 && l < %d, PANIC(\"Bad state %%d passed to %s_state\\n\", l));\n",
- prefix, globalMap->count, prefix);
- fprintf(outfile,
- "\t%s_assert(r >= 0 && r < %d, PANIC(\"Bad state %%d passed to %s_state\\n\", r));\n",
- prefix, globalMap->count, prefix);
- fprintf(outfile, "\tswitch (op) {\n");
- fprintf(outfile, "\tdefault: %s_PANIC(\"Bad op %%d in %s_state\\n\", op); abort(); return 0;\n", prefix, prefix);
-
- foreachList((ListFn) doLabel, operators);
-
- fprintf(outfile, "\t}\n");
- fprintf(outfile, "}\n");
-}
-
-static char cumBuf[4000];
-static int vecIndex;
-char vecBuf[4000];
-
-static void
-setVectors(ast) PatternAST ast;
-{
- char old[4000];
-
- switch (ast->sym->tag) {
- default:
- assert(0);
- break;
- case NONTERMINAL:
- sprintf(old, "\t\tkids[%d] = %s;\n", vecIndex, vecBuf);
- strcat(cumBuf, old);
- vecIndex++;
- return;
- case OPERATOR:
- switch (ast->sym->u.op->arity) {
- default:
- assert(0);
- break;
- case 0:
- return;
- case 1:
- strcpy(old, vecBuf);
- sprintf(vecBuf, "%s_LEFT_CHILD(%s)", prefix, old);
- setVectors((PatternAST) ast->children->x);
- strcpy(vecBuf, old);
- return;
- case 2:
- strcpy(old, vecBuf);
- sprintf(vecBuf, "%s_LEFT_CHILD(%s)", prefix, old);
- setVectors((PatternAST) ast->children->x);
-
- sprintf(vecBuf, "%s_RIGHT_CHILD(%s)", prefix, old);
- setVectors((PatternAST) ast->children->next->x);
- strcpy(vecBuf, old);
- return;
- }
- break;
- }
-}
-
-#define MAX_VECTOR 10
-
-void
-makeRuleTable()
-{
- int s,nt;
-
- fprintf(outfile, "static short %s_RuleNo[%d][%d] = {\n", prefix, globalMap->count, last_user_nonterminal-1);
- for (s = 0; s < globalMap->count; s++) {
- Item_Set ts = globalMap->set[s];
- if (s > 0) {
- fprintf(outfile, ",\n");
- }
- fprintf(outfile, "/* state %d */\n", s);
- fprintf(outfile, "{");
- for (nt = 1; nt < last_user_nonterminal; nt++) {
- if (nt > 1) {
- fprintf(outfile, ",");
- if (nt % 10 == 1) {
- fprintf(outfile, "\t/* state %d; Nonterminals %d-%d */\n", s, nt-10, nt-1);
- }
- }
- if (ts->closed[nt].rule) {
- ts->closed[nt].rule->used = 1;
- fprintf(outfile, "%5d", ts->closed[nt].rule->erulenum);
- } else {
- fprintf(outfile, "%5d", ERROR_VAL);
- }
- }
- fprintf(outfile, "}");
- }
- fprintf(outfile, "};\n");
-}
-
-static void
-makeIndex_Map(d) Dimension d;
-{
- int s;
-
- for (s = 0; s < globalMap->count; s++) {
- if (s > 0) {
- fprintf(outfile, ",");
- if (s % 10 == 0) {
- fprintf(outfile, "\t/* %d-%d */\n", s-10, s-1);
- }
- }
- fprintf(outfile, "%5d", d->map->set[d->index_map.class[s]->num]->num);
- }
- fprintf(outfile, "};\n");
-}
-
-static void
-doMakeTable(op) Operator op;
-{
- int s;
- int i,j;
- Dimension d;
-
- switch (op->arity) {
- default:
- assert(0);
- break;
- case 0:
- return;
- case 1:
- if (!op->table->rules) {
- return;
- }
- d = op->table->dimen[0];
- fprintf(outfile, "static short %s_%s_transition[%d] = {\n", prefix, op->name, globalMap->count);
- for (s = 0; s < globalMap->count; s++) {
- if (s > 0) {
- fprintf(outfile, ", ");
- if (s % 10 == 0) {
- fprintf(outfile, "\t/* %d-%d */\n", s-10, s-1);
- }
- }
- fprintf(outfile, "%5d", op->table->transition[d->map->set[d->index_map.class[s]->num]->num]->num);
- }
- fprintf(outfile, "};\n");
- break;
- case 2:
- if (!op->table->rules) {
- return;
- }
- fprintf(outfile, "static short %s_%s_imap_1[%d] = {\n", prefix, op->name, globalMap->count);
- makeIndex_Map(op->table->dimen[0]);
- fprintf(outfile, "static short %s_%s_imap_2[%d] = {\n", prefix, op->name, globalMap->count);
- makeIndex_Map(op->table->dimen[1]);
-
- fprintf(outfile, "static short %s_%s_transition[%d][%d] = {", prefix, op->name,
- op->table->dimen[0]->map->count,
- op->table->dimen[1]->map->count);
- for (i = 0; i < op->table->dimen[0]->map->count; i++) {
- if (i > 0) {
- fprintf(outfile, ",");
- }
- fprintf(outfile, "\n");
- fprintf(outfile, "{");
- for (j = 0; j < op->table->dimen[1]->map->count; j++) {
- Item_Set *ts = transLval(op->table, i, j);
- if (j > 0) {
- fprintf(outfile, ",");
- }
- fprintf(outfile, "%5d", (*ts)->num);
- }
- fprintf(outfile, "}\t/* row %d */", i);
- }
- fprintf(outfile, "\n};\n");
-
- break;
- }
-}
-
-void
-makeTables()
-{
- foreachList((ListFn) doMakeTable, operators);
-}
-
-RuleAST *pVector;
-
-void
-makeLHSmap()
-{
- int i;
-
- if (!pVector) {
- makePvector();
- }
-
- fprintf(outfile, "short %s_lhs[] = {\n", prefix);
- for (i = 0; i <= max_erule_num; i++) {
- if (pVector[i]) {
- fprintf(outfile, "\t%s_%s_NT,\n", prefix, pVector[i]->lhs);
- } else {
- fprintf(outfile, "\t0,\n");
- }
- }
- fprintf(outfile, "};\n\n");
-}
-
-static int seminal(int from, int to)
-{
- return allpairs[from][to].rule ? allpairs[from][to].rule->erulenum : 0;
-
- /*
- int tmp, last;
- tmp = 0;
- for (;;) {
- last = tmp;
- tmp = allpairs[to][from].rule ? allpairs[to][from].rule->erulenum : 0;
- if (!tmp) {
- break;
- }
- assert(pVector[tmp]);
- to = pVector[tmp]->rule->pat->children[0]->num;
- }
- return last;
- */
-}
-
-void
-makeClosureArray()
-{
- int i, j;
-
- if (!pVector) {
- makePvector();
- }
-
- fprintf(outfile, "short %s_closure[%d][%d] = {\n", prefix, last_user_nonterminal, last_user_nonterminal);
- for (i = 0; i < last_user_nonterminal; i++) {
- fprintf(outfile, "\t{");
- for (j = 0; j < last_user_nonterminal; j++) {
- if (j > 0 && j%10 == 0) {
- fprintf(outfile, "\n\t ");
- }
- fprintf(outfile, " %4d,", seminal(i,j));
- }
- fprintf(outfile, "},\n");
- }
- fprintf(outfile, "};\n");
-}
-
-void
-makeCostVector(z,d) int z; DeltaCost d;
-{
- fprintf(outfile, "\t{");
-#ifdef NOLEX
- if (z) {
- fprintf(outfile, "%5d", d);
- } else {
- fprintf(outfile, "%5d", 0);
- }
-#else
- {
- int j;
- for (j = 0; j < DELTAWIDTH; j++) {
- if (j > 0) {
- fprintf(outfile, ",");
- }
- if (z) {
- fprintf(outfile, "%5d", d[j]);
- } else {
- fprintf(outfile, "%5d", 0);
- }
- }
- }
-#endif /* NOLEX */
- fprintf(outfile, "}");
-}
-
-void
-makeCostArray()
-{
- int i;
-
- if (!pVector) {
- makePvector();
- }
-
- fprintf(outfile, "short %s_cost[][%d] = {\n", prefix, DELTAWIDTH);
- for (i = 0; i <= max_erule_num; i++) {
- makeCostVector(pVector[i] != 0, pVector[i] ? pVector[i]->rule->delta : 0);
- fprintf(outfile, ", /* ");
- printRule(pVector[i], "(none)");
- fprintf(outfile, " = %d */\n", i);
- }
- fprintf(outfile, "};\n");
-}
-
-void
-makeStateStringArray()
-{
- int s;
- int nt;
- int states;
-
- states = globalMap->count;
- fprintf(outfile, "\nconst char * %s_state_string[] = {\n", prefix);
- fprintf(outfile, "\" not a state\", /* state 0 */\n");
- for (s = 0; s < states-1; s++) {
- fprintf(outfile, "\t\"");
- printRepresentative(outfile, sortedStates[s]);
- fprintf(outfile, "\", /* state #%d */\n", s+1);
- }
- fprintf(outfile, "};\n");
-}
-
-void
-makeDeltaCostArray()
-{
- int s;
- int nt;
- int states;
-
- states = globalMap->count;
- fprintf(outfile, "\nshort %s_delta_cost[%d][%d][%d] = {\n", prefix, states, last_user_nonterminal, DELTAWIDTH);
- fprintf(outfile, "{{0}}, /* state 0 */\n");
- for (s = 0; s < states-1; s++) {
- fprintf(outfile, "{ /* state #%d: ", s+1);
- printRepresentative(outfile, sortedStates[s]);
- fprintf(outfile, " */\n");
- fprintf(outfile, "\t{0},\n");
- for (nt = 1; nt < last_user_nonterminal; nt++) {
- makeCostVector(1, sortedStates[s]->closed[nt].delta);
- fprintf(outfile, ", /* ");
- if (sortedStates[s]->closed[nt].rule) {
- int erulenum = sortedStates[s]->closed[nt].rule->erulenum;
- printRule(pVector[erulenum], "(none)");
- fprintf(outfile, " = %d */", erulenum);
- } else {
- fprintf(outfile, "(none) */");
- }
- fprintf(outfile, "\n");
- }
- fprintf(outfile, "},\n");
- }
- fprintf(outfile, "};\n");
-}
-
-static void
-printPatternAST_int(p) PatternAST p;
-{
- List l;
-
- if (p) {
- switch (p->sym->tag) {
- case NONTERMINAL:
- fprintf(outfile, "%5d,", -p->sym->u.nt->num);
- break;
- case OPERATOR:
- fprintf(outfile, "%5d,", p->sym->u.op->num);
- break;
- default:
- assert(0);
- }
- if (p->children) {
- for (l = p->children; l; l = l->next) {
- PatternAST pat = (PatternAST) l->x;
- printPatternAST_int(pat);
- }
- }
- }
-}
-
-static void
-printPatternAST(p) PatternAST p;
-{
- List l;
-
- if (p) {
- fprintf(outfile, "%s", p->op);
- if (p->children) {
- fprintf(outfile, "(");
- for (l = p->children; l; l = l->next) {
- PatternAST pat = (PatternAST) l->x;
- if (l != p->children) {
- fprintf(outfile, ", ");
- }
- printPatternAST(pat);
- }
- fprintf(outfile, ")");
- }
- }
-}
-
-static void
-layoutNts(ast) PatternAST ast;
-{
- char out[30];
-
- switch (ast->sym->tag) {
- default:
- assert(0);
- break;
- case NONTERMINAL:
- sprintf(out, "%d, ", ast->sym->u.nt->num);
- strcat(cumBuf, out);
- return;
- case OPERATOR:
- switch (ast->sym->u.op->arity) {
- default:
- assert(0);
- break;
- case 0:
- return;
- case 1:
- layoutNts((PatternAST) ast->children->x);
- return;
- case 2:
- layoutNts((PatternAST) ast->children->x);
- layoutNts((PatternAST) ast->children->next->x);
- return;
- }
- break;
- }
-}
-
-static void
-doVector(ast) RuleAST ast;
-{
- if (pVector[ast->rule->erulenum]) {
- fprintf(stderr, "ERROR: non-unique external rule number: (%d)\n", ast->rule->erulenum);
- exit(1);
- }
- pVector[ast->rule->erulenum] = ast;
-}
-
-static void
-makePvector()
-{
- pVector = (RuleAST*) zalloc((max_erule_num+1) * sizeof(RuleAST));
- foreachList((ListFn) doVector, ruleASTs);
-}
-
-static void
-doLayout(ast) RuleAST ast;
-{
- sprintf(cumBuf, "{ ");
- layoutNts(ast->pat);
- strcat(cumBuf, "0 }");
-}
-
-void
-makeNts()
-{
- int i;
- int new;
- StrTable nts;
-
- nts = newStrTable();
-
- if (!pVector) {
- makePvector();
- }
-
- for (i = 0; i <= max_erule_num; i++) {
- if (pVector[i]) {
- doLayout(pVector[i]);
- pVector[i]->nts = addString(nts, cumBuf, i, &new);
- if (new) {
- char ename[50];
-
- sprintf(ename, "%s_r%d_nts", prefix, i);
- pVector[i]->nts->ename = (char*) zalloc(strlen(ename)+1);
- strcpy(pVector[i]->nts->ename, ename);
- fprintf(outfile, "static short %s[] =", ename);
- fprintf(outfile, "%s;\n", cumBuf);
- }
- }
- }
-
- fprintf(outfile, "short *%s_nts[] = {\n", prefix);
- for (i = 0; i <= max_erule_num; i++) {
- if (pVector[i]) {
- fprintf(outfile, "\t%s,\n", pVector[i]->nts->ename);
- } else {
- fprintf(outfile, "\t0,\n");
- }
- }
- fprintf(outfile, "};\n");
-}
-
-static void
-printRule(RuleAST r, const char *d)
-{
- if (r) {
- fprintf(outfile, "%s: ", r->rule->lhs->name);
- printPatternAST(r->pat);
- } else {
- fprintf(outfile, "%s", d);
- }
-}
-
-void
-makeRuleDescArray()
-{
- int i;
-
- if (!pVector) {
- makePvector();
- }
-
- if (last_user_nonterminal != max_nonterminal) {
- /* not normal form */
- fprintf(outfile, "short %s_rule_descriptor_0[] = { 0, 0 };\n", prefix);
- } else {
- fprintf(outfile, "short %s_rule_descriptor_0[] = { 0, 1 };\n", prefix);
- }
- for (i = 1; i <= max_erule_num; i++) {
- if (pVector[i]) {
- Operator o;
- NonTerminal t;
-
- fprintf(outfile, "short %s_rule_descriptor_%d[] = {", prefix, i);
- fprintf(outfile, "%5d,", -pVector[i]->rule->lhs->num);
- printPatternAST_int(pVector[i]->pat);
- fprintf(outfile, " };\n");
- }
- }
-
- fprintf(outfile, "/* %s_rule_descriptors[0][1] = 1 iff grammar is normal form. */\n", prefix);
- fprintf(outfile, "short * %s_rule_descriptors[] = {\n", prefix);
- fprintf(outfile, "\t%s_rule_descriptor_0,\n", prefix);
- for (i = 1; i <= max_erule_num; i++) {
- if (pVector[i]) {
- fprintf(outfile, "\t%s_rule_descriptor_%d,\n", prefix, i);
- } else {
- fprintf(outfile, "\t%s_rule_descriptor_0,\n", prefix);
- }
- }
- fprintf(outfile, "};\n");
-}
-
-
-void
-makeRuleDescArray2()
-{
- int i;
-
- if (!pVector) {
- makePvector();
- }
-
- fprintf(outfile, "struct { int lhs, op, left, right; } %s_rule_struct[] = {\n", prefix);
- if (last_user_nonterminal != max_nonterminal) {
- /* not normal form */
- fprintf(outfile, "\t{-1},");
- } else {
- fprintf(outfile, "\t{0},");
- }
- fprintf(outfile, " /* 0 if normal form, -1 if not normal form */\n");
- for (i = 1; i <= max_erule_num; i++) {
- fprintf(outfile, "\t");
- if (pVector[i]) {
- Operator o;
- NonTerminal t1, t2;
-
- fprintf(outfile, "{");
- fprintf(outfile, "%5d, %5d, %5d, %5d",
- pVector[i]->rule->lhs->num,
- (o = pVector[i]->rule->pat->op) ? o->num : 0,
- (t1 = pVector[i]->rule->pat->children[0]) ? t1->num : 0,
- (t2 = pVector[i]->rule->pat->children[1]) ? t2->num : 0
- );
- fprintf(outfile, "} /* ");
- printRule(pVector[i], "0");
- fprintf(outfile, " = %d */", i);
- } else {
- fprintf(outfile, "{0}");
- }
- fprintf(outfile, ",\n");
- }
- fprintf(outfile, "};\n");
-}
-
-void
-makeStringArray()
-{
- int i;
-
- if (!pVector) {
- makePvector();
- }
-
- fprintf(outfile, "const char *%s_string[] = {\n", prefix);
- for (i = 0; i <= max_erule_num; i++) {
- fprintf(outfile, "\t");
- if (pVector[i]) {
- fprintf(outfile, "\"");
- printRule(pVector[i], "0");
- fprintf(outfile, "\"");
- } else {
- fprintf(outfile, "0");
- }
- fprintf(outfile, ",\n");
- }
- fprintf(outfile, "};\n");
- fprintf(outfile, "int %s_max_rule = %d;\n", prefix, max_erule_num);
- fprintf(outfile, "#define %s_Max_rule %d\n", prefix, max_erule_num);
-}
-
-void
-makeRule()
-{
- fprintf(outfile, "int %s_rule(int state, int goalnt) {\n", prefix);
- fprintf(outfile,
- "\t%s_assert(state >= 0 && state < %d, PANIC(\"Bad state %%d passed to %s_rule\\n\", state));\n",
- prefix, globalMap->count, prefix);
- fprintf(outfile,
- "\t%s_assert(goalnt >= 1 && goalnt < %d, PANIC(\"Bad goalnt %%d passed to %s_rule\\n\", state));\n",
- prefix, max_nonterminal, prefix);
- fprintf(outfile, "\treturn %s_RuleNo[state][goalnt-1];\n", prefix);
- fprintf(outfile, "};\n");
-}
-
-static StrTable kids;
-
-static void
-doKids(ast) RuleAST ast;
-{
- int new;
-
- vecIndex = 0;
- cumBuf[0] = 0;
- strcpy(vecBuf, "p");
- setVectors(ast->pat);
-
- ast->kids = addString(kids, cumBuf, ast->rule->erulenum, &new);
-
-}
-
-void
-makeKids()
-{
- List e;
- IntList r;
-
- kids = newStrTable();
-
- fprintf(outfile, "#ifdef __STDC__\n");
- fprintf(outfile, "%s_NODEPTR_TYPE * %s_kids(%s_NODEPTR_TYPE p, int rulenumber, %s_NODEPTR_TYPE *kids) {\n", prefix, prefix, prefix, prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "%s_NODEPTR_TYPE * %s_kids(p, rulenumber, kids) %s_NODEPTR_TYPE p; int rulenumber; %s_NODEPTR_TYPE *kids; {\n", prefix, prefix, prefix, prefix);
- fprintf(outfile, "#endif\n");
-
- fprintf(outfile,
- "\t%s_assert(p, %s_PANIC(\"NULL node pointer passed to %s_kids\\n\"));\n",
- prefix, prefix, prefix);
- fprintf(outfile,
- "\t%s_assert(kids, %s_PANIC(\"NULL kids pointer passed to %s_kids\\n\"));\n",
- prefix, prefix, prefix);
- fprintf(outfile, "\tswitch (rulenumber) {\n");
- fprintf(outfile, "\tdefault:\n");
- fprintf(outfile, "\t\t%s_PANIC(\"Unknown Rule %%d in %s_kids;\\n\", rulenumber);\n", prefix, prefix);
- fprintf(outfile, "\t\tabort();\n");
- fprintf(outfile, "\t\t/* NOTREACHED */\n");
-
- foreachList((ListFn) doKids, ruleASTs);
-
- for (e = kids->elems; e; e = e->next) {
- StrTableElement el = (StrTableElement) e->x;
- for (r = el->erulenos; r; r = r->next) {
- int i = r->x;
- fprintf(outfile, "\tcase %d:\n", i);
- }
- fprintf(outfile, "%s", el->str);
- fprintf(outfile, "\t\tbreak;\n");
- }
- fprintf(outfile, "\t}\n");
- fprintf(outfile, "\treturn kids;\n");
- fprintf(outfile, "}\n");
-}
-
-void
-makeOpLabel()
-{
- fprintf(outfile, "#ifdef __STDC__\n");
- fprintf(outfile, "int %s_op_label(%s_NODEPTR_TYPE p) {\n", prefix, prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "int %s_op_label(p) %s_NODEPTR_TYPE p; {\n", prefix, prefix);
- fprintf(outfile, "#endif\n");
- fprintf(outfile,
- "\t%s_assert(p, %s_PANIC(\"NULL pointer passed to %s_op_label\\n\"));\n",
- prefix, prefix, prefix);
- fprintf(outfile, "\treturn %s_OP_LABEL(p);\n", prefix);
- fprintf(outfile, "}\n");
-}
-
-void
-makeStateLabel()
-{
- fprintf(outfile, "#ifdef __STDC__\n");
- fprintf(outfile, "int %s_state_label(%s_NODEPTR_TYPE p) {\n", prefix, prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "int %s_state_label(p) %s_NODEPTR_TYPE p; {\n", prefix, prefix);
- fprintf(outfile, "#endif\n");
-
- fprintf(outfile,
- "\t%s_assert(p, %s_PANIC(\"NULL pointer passed to %s_state_label\\n\"));\n",
- prefix, prefix, prefix);
- fprintf(outfile, "\treturn %s_STATE_LABEL(p);\n", prefix);
- fprintf(outfile, "}\n");
-}
-
-void
-makeChild()
-{
- fprintf(outfile, "#ifdef __STDC__\n");
- fprintf(outfile, "%s_NODEPTR_TYPE %s_child(%s_NODEPTR_TYPE p, int index) {\n", prefix, prefix, prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "%s_NODEPTR_TYPE %s_child(p, index) %s_NODEPTR_TYPE p; int index; {\n", prefix, prefix, prefix);
- fprintf(outfile, "#endif\n");
-
- fprintf(outfile,
- "\t%s_assert(p, %s_PANIC(\"NULL pointer passed to %s_child\\n\"));\n",
- prefix, prefix, prefix);
- fprintf(outfile, "\tswitch (index) {\n");
- fprintf(outfile, "\tcase 0:\n");
- fprintf(outfile, "\t\treturn %s_LEFT_CHILD(p);\n", prefix);
- fprintf(outfile, "\tcase 1:\n");
- fprintf(outfile, "\t\treturn %s_RIGHT_CHILD(p);\n", prefix);
- fprintf(outfile, "\t}\n");
- fprintf(outfile, "\t%s_PANIC(\"Bad index %%d in %s_child;\\n\", index);\n", prefix, prefix);
- fprintf(outfile, "\tabort();\n");
- fprintf(outfile, "\treturn 0;\n");
- fprintf(outfile, "}\n");
-}
-
-static Operator *opVector;
-static int maxOperator;
-
-void
-makeOperatorVector()
-{
- List l;
-
- maxOperator = 0;
- for (l = operators; l; l = l->next) {
- Operator op = (Operator) l->x;
- if (op->num > maxOperator) {
- maxOperator = op->num;
- }
- }
- opVector = (Operator*) zalloc((maxOperator+1) * sizeof(*opVector));
- for (l = operators; l; l = l->next) {
- Operator op = (Operator) l->x;
- if (opVector[op->num]) {
- fprintf(stderr, "ERROR: Non-unique external symbol number (%d)\n", op->num);
- exit(1);
- }
- opVector[op->num] = op;
- }
-}
-
-void
-makeOperators()
-{
- int i;
-
- if (!opVector) {
- makeOperatorVector();
- }
- fprintf(outfile, "const char * %s_opname[] = {\n", prefix);
- for (i = 0; i <= maxOperator; i++) {
- if (i > 0) {
- fprintf(outfile, ", /* %d */\n", i-1);
- }
- if (opVector[i]) {
- fprintf(outfile, "\t\"%s\"", opVector[i]->name);
- } else {
- fprintf(outfile, "\t0");
- }
- }
- fprintf(outfile, "\n};\n");
- fprintf(outfile, "char %s_arity[] = {\n", prefix);
- for (i = 0; i <= maxOperator; i++) {
- if (i > 0) {
- fprintf(outfile, ", /* %d */\n", i-1);
- }
- fprintf(outfile, "\t%d", opVector[i] ? opVector[i]->arity : -1);
- }
- fprintf(outfile, "\n};\n");
- fprintf(outfile, "int %s_max_op = %d;\n", prefix, maxOperator);
- fprintf(outfile, "int %s_max_state = %d;\n", prefix, globalMap->count-1);
- fprintf(outfile, "#define %s_Max_state %d\n", prefix, globalMap->count-1);
-}
-
-void
-makeDebug()
-{
- fprintf(outfile, "#ifdef DEBUG\n");
- fprintf(outfile, "int %s_debug;\n", prefix);
- fprintf(outfile, "#endif /* DEBUG */\n");
-}
-
-void
-makeSimple()
-{
- makeRuleTable();
- makeTables();
- makeRule();
- makeState();
-}
-
-void
-startOptional()
-{
- fprintf(outfile, "#ifdef %s_STATE_LABEL\n", prefix);
- fprintf(outfile, "#define %s_INCLUDE_EXTRA\n", prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "#ifdef STATE_LABEL\n");
- fprintf(outfile, "#define %s_INCLUDE_EXTRA\n", prefix);
- fprintf(outfile, "#define %s_STATE_LABEL \tSTATE_LABEL\n", prefix);
- fprintf(outfile, "#define %s_NODEPTR_TYPE\tNODEPTR_TYPE\n", prefix);
- fprintf(outfile, "#define %s_LEFT_CHILD \tLEFT_CHILD\n", prefix);
- fprintf(outfile, "#define %s_OP_LABEL \tOP_LABEL\n", prefix);
- fprintf(outfile, "#define %s_RIGHT_CHILD \tRIGHT_CHILD\n", prefix);
- fprintf(outfile, "#endif /* STATE_LABEL */\n");
- fprintf(outfile, "#endif /* %s_STATE_LABEL */\n\n", prefix);
-
- fprintf(outfile, "#ifdef %s_INCLUDE_EXTRA\n\n", prefix);
-
-}
-
-void
-makeNonterminals()
-{
- List l;
-
- for (l = nonterminals; l; l = l->next) {
- NonTerminal nt = (NonTerminal) l->x;
- if (nt->num < last_user_nonterminal) {
- fprintf(outfile, "#define %s_%s_NT %d\n", prefix, nt->name, nt->num);
- }
- }
- fprintf(outfile, "#define %s_NT %d\n", prefix, last_user_nonterminal-1);
-}
-
-void
-makeNonterminalArray()
-{
- int i;
- List l;
- NonTerminal *nta;
-
- nta = (NonTerminal *) zalloc(sizeof(*nta) * last_user_nonterminal);
-
- for (l = nonterminals; l; l = l->next) {
- NonTerminal nt = (NonTerminal) l->x;
- if (nt->num < last_user_nonterminal) {
- nta[nt->num] = nt;
- }
- }
-
- fprintf(outfile, "const char *%s_ntname[] = {\n", prefix);
- fprintf(outfile, "\t\"Error: Nonterminals are > 0\",\n");
- for (i = 1; i < last_user_nonterminal; i++) {
- fprintf(outfile, "\t\"%s\",\n", nta[i]->name);
- }
- fprintf(outfile, "\t0\n");
- fprintf(outfile, "};\n\n");
-
- zfree(nta);
-}
-
-void
-endOptional()
-{
- fprintf(outfile, "#endif /* %s_INCLUDE_EXTRA */\n", prefix);
-}
-
-void
-startBurm()
-{
- fprintf(outfile, "#ifndef %s_PANIC\n", prefix);
- fprintf(outfile, "#define %s_PANIC\tPANIC\n", prefix);
- fprintf(outfile, "#endif /* %s_PANIC */\n", prefix);
- fprintf(outfile, "#ifdef __STDC__\n");
- fprintf(outfile, "extern void abort(void);\n");
- fprintf(outfile, "#else\n");
- fprintf(outfile, "extern void abort();\n");
- fprintf(outfile, "#endif\n");
- fprintf(outfile, "#ifdef NDEBUG\n");
- fprintf(outfile, "#define %s_assert(x,y)\t;\n", prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "#define %s_assert(x,y)\tif(!(x)) {y; abort();}\n", prefix);
- fprintf(outfile, "#endif\n");
-}
-
-void
-reportDiagnostics()
-{
- List l;
-
- for (l = operators; l; l = l->next) {
- Operator op = (Operator) l->x;
- if (!op->ref) {
- fprintf(stderr, "warning: Unreferenced Operator: %s\n", op->name);
- }
- }
- for (l = rules; l; l = l->next) {
- Rule r = (Rule) l->x;
- if (!r->used && r->num < max_ruleAST) {
- fprintf(stderr, "warning: Unused Rule: #%d\n", r->erulenum);
- }
- }
- if (!start->pmap) {
- fprintf(stderr, "warning: Start Nonterminal (%s) does not appear on LHS.\n", start->name);
- }
-
- fprintf(stderr, "start symbol = \"%s\"\n", start->name);
- fprintf(stderr, "# of states = %d\n", globalMap->count-1);
- fprintf(stderr, "# of nonterminals = %d\n", max_nonterminal-1);
- fprintf(stderr, "# of user nonterminals = %d\n", last_user_nonterminal-1);
- fprintf(stderr, "# of rules = %d\n", max_rule);
- fprintf(stderr, "# of user rules = %d\n", max_ruleAST);
-}
+++ /dev/null
-char rcsid_burs[] = "$Id$";
-
-#include "b.h"
-
-Item_Set errorState;
-
-static void doLeaf ARGS((Operator));
-
-static void
-doLeaf(leaf) Operator leaf;
-{
- int new;
- List pl;
- Item_Set ts;
- Item_Set tmp;
-
- assert(leaf->arity == 0);
-
- ts = newItem_Set(leaf->table->relevant);
-
- for (pl = rules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- if (p->pat->op == leaf) {
- if (!ts->virgin[p->lhs->num].rule || p->delta < ts->virgin[p->lhs->num].delta) {
- ts->virgin[p->lhs->num].rule = p;
- ASSIGNCOST(ts->virgin[p->lhs->num].delta, p->delta);
- ts->op = leaf;
- }
- }
- }
- trim(ts);
- zero(ts);
- tmp = encode(globalMap, ts, &new);
- if (new) {
- closure(ts);
- leaf->table->transition[0] = ts;
- addQ(globalQ, ts);
- } else {
- leaf->table->transition[0] = tmp;
- freeItem_Set(ts);
- }
-}
-
-void
-build()
-{
- int new;
- List ol;
- Item_Set ts;
-
- globalQ = newQ();
- globalMap = newMapping(GLOBAL_MAP_SIZE);
-
- ts = newItem_Set(0);
- errorState = encode(globalMap, ts, &new);
- ts->closed = ts->virgin;
- addQ(globalQ, ts);
-
- foreachList((ListFn) doLeaf, leaves);
-
- debug(debugTables, printf("---initial set of states ---\n"));
- debug(debugTables, dumpMapping(globalMap));
- debug(debugTables, foreachList((ListFn) dumpItem_Set, globalQ->head));
-
- for (ts = popQ(globalQ); ts; ts = popQ(globalQ)) {
- for (ol = operators; ol; ol = ol->next) {
- Operator op = (Operator) ol->x;
- addToTable(op->table, ts);
- }
- }
-}
+++ /dev/null
-char rcsid_closure[] = "$Id$";
-
-#include <stdio.h>
-#include "b.h"
-
-int prevent_divergence = 0;
-
-List chainrules;
-
-void
-findChainRules()
-{
- List pl;
-
- assert(!chainrules);
-
- for (pl = rules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- if (!p->pat->op) {
- chainrules = newList(p, chainrules);
- } else {
- p->pat->op->table->rules = newList(p, p->pat->op->table->rules);
- addRelevant(p->pat->op->table->relevant, p->lhs->num);
- }
- }
-}
-
-void
-zero(t) Item_Set t;
-{
- int i;
- DeltaCost base;
- int exists;
- int base_nt = 0;
-
- assert(!t->closed);
-
- ZEROCOST(base);
- exists = 0;
- for (i = 0; i < max_nonterminal; i++) {
- if (t->virgin[i].rule) {
- if (exists) {
- if (LESSCOST(t->virgin[i].delta, base)) {
- ASSIGNCOST(base, t->virgin[i].delta);
- base_nt = i;
- }
- } else {
- ASSIGNCOST(base, t->virgin[i].delta);
- exists = 1;
- base_nt = i;
- }
- }
- }
- if (!exists) {
- return;
- }
- for (i = 0; i < max_nonterminal; i++) {
- if (t->virgin[i].rule) {
- MINUSCOST(t->virgin[i].delta, base);
- }
- NODIVERGE(t->virgin[i].delta, t, i, base_nt);
- }
-}
-
-void
-closure(t) Item_Set t;
-{
- int changes;
- List pl;
-
- assert(!t->closed);
- t->closed = itemArrayCopy(t->virgin);
-
- changes = 1;
- while (changes) {
- changes = 0;
- for (pl = chainrules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- register Item *rhs_item = &t->closed[p->pat->children[0]->num];
-
- if (rhs_item->rule) { /* rhs is active */
- DeltaCost dc;
- register Item *lhs_item = &t->closed[p->lhs->num];
-
- ASSIGNCOST(dc, rhs_item->delta);
- ADDCOST(dc, p->delta);
- if (LESSCOST(dc, lhs_item->delta) || !lhs_item->rule) {
- ASSIGNCOST(lhs_item->delta, dc);
- lhs_item->rule = p;
- changes = 1;
- }
- }
- }
- }
-}
+++ /dev/null
-char rcsid_delta[] = "$Id$";
-
-#include <stdio.h>
-#include "b.h"
-#include "fe.h"
-
-int principleCost = 0;
-int lexical = 0;
-
-#ifndef NOLEX
-void
-ASSIGNCOST(l, r) DeltaPtr l; DeltaPtr r;
-{
- int i;
-
- if (lexical) {
- for (i = 0; i < DELTAWIDTH; i++) {
- l[i] = r[i];
- }
- } else {
- l[0] = r[0];
- }
-}
-
-void
-ADDCOST(l, r) DeltaPtr l; DeltaPtr r;
-{
- int i;
-
- if (lexical) {
- for (i = 0; i < DELTAWIDTH; i++) {
- l[i] += r[i];
- }
- } else {
- l[0] += r[0];
- }
-}
-
-void
-MINUSCOST(l, r) DeltaPtr l; DeltaPtr r;
-{
- int i;
-
- if (lexical) {
- for (i = 0; i < DELTAWIDTH; i++) {
- l[i] -= r[i];
- }
- } else {
- l[0] -= r[0];
- }
-}
-
-void
-ZEROCOST(x) DeltaPtr x;
-{
- int i;
-
- if (lexical) {
- for (i = 0; i < DELTAWIDTH; i++) {
- x[i] = 0;
- }
- } else {
- x[0] = 0;
- }
-}
-
-int
-LESSCOST(l, r) DeltaPtr l; DeltaPtr r;
-{
- int i;
-
- if (lexical) {
- for (i = 0; i < DELTAWIDTH; i++) {
- if (l[i] < r[i]) {
- return 1;
- } else if (l[i] > r[i]) {
- return 0;
- }
- }
- return 0;
- } else {
- return l[0] < r[0];
- }
-}
-
-int
-EQUALCOST(l, r) DeltaPtr l; DeltaPtr r;
-{
- int i;
-
- if (lexical) {
- for (i = 0; i < DELTAWIDTH; i++) {
- if (l[i] != r[i]) {
- return 0;
- }
- }
- return 1;
- } else {
- return l[0] == r[0];
- }
-}
-#endif /* NOLEX */
-
-void
-CHECKDIVERGE(c, its, nt, base) DeltaPtr c; Item_Set its; int nt; int base;
-{
- int i;
-
- if (prevent_divergence <= 0) {
- return;
- }
- if (lexical) {
-#ifndef NOLEX
- for (i = 0; i < DELTAWIDTH; i++) {
- if (c[i] > prevent_divergence) {
- char ntname[100];
- char basename[100];
- nonTerminalName(ntname, nt);
- nonTerminalName(basename, base);
- fprintf(stderr, "ERROR: The grammar appears to diverge\n");
- fprintf(stderr, "\tRelative Costs: %s(0), %s(%d)\n", basename, ntname, c[i]);
- fprintf(stderr, "\tOffending Operator: %s\n", its->op->name);
- fprintf(stderr, "\tOffending Tree: ");
- printRepresentative(stderr, its);
- fprintf(stderr, "\n");
- exit(1);
- }
- }
-#endif /*NOLEX*/
- } else if (PRINCIPLECOST(c) > prevent_divergence) {
- char ntname[100];
- char basename[100];
- nonTerminalName(ntname, nt);
- nonTerminalName(basename, base);
- fprintf(stderr, "ERROR: The grammar appears to diverge\n");
- fprintf(stderr, "\tRelative Costs: %s(0), %s(%d)\n", basename, ntname, PRINCIPLECOST(c));
- fprintf(stderr, "\tOffending Operator: %s\n", its->op->name);
- fprintf(stderr, "\tOffending Tree: ");
- printRepresentative(stderr, its);
- fprintf(stderr, "\n");
- exit(1);
- }
-}
+++ /dev/null
-char rcsid_fe[] = "$Id$";
-
-#include <stdio.h>
-#include <string.h>
-#include "b.h"
-#include "fe.h"
-
-int grammarflag;
-
-static int arity;
-
-List ruleASTs;
-List grammarNts;
-
-static void doBinding ARGS((Binding));
-static void doDecl ARGS((Arity));
-static NonTerminal lookup ARGS((Pattern));
-static NonTerminal normalize ARGS((PatternAST, NonTerminal, Pattern *));
-static void doEnterNonTerm ARGS((RuleAST));
-static void doRule ARGS((RuleAST));
-static void doTable ARGS((Operator));
-
-static void
-doBinding(b) Binding b;
-{
- int new;
- Symbol s;
-
- s = enter(b->name, &new);
- if (!new) {
- fprintf(stderr, "Non-unique name: %s\n", b->name);
- exit(1);
- }
- s->tag = OPERATOR;
- s->u.op = newOperator(b->name, b->opnum, arity);
- if (arity == 0) {
- leaves = newList(s->u.op, leaves);
- }
-}
-
-static void
-doDecl(a) Arity a;
-{
- if (!a) {
- return;
- }
- arity = a->arity;
- foreachList((ListFn) doBinding, a->bindings);
-}
-
-
-static List xpatterns;
-static int tcount;
-
-static NonTerminal
-lookup(p) Pattern p;
-{
- char buf[10];
- char *s;
- List l;
- NonTerminal n;
- DeltaCost dummy;
-
- for (l = xpatterns; l; l = l->next) {
- Pattern x = (Pattern) l->x;
- if (x->op == p->op
- && x->children[0] == p->children[0]
- && x->children[1] == p->children[1]) {
- return x->normalizer;
- }
- }
- sprintf(buf, "n%%%d", tcount++);
- s = (char *) zalloc(strlen(buf)+1);
- strcpy(s, buf);
- n = newNonTerminal(s);
- p->normalizer = n;
- xpatterns = newList(p, xpatterns);
- ZEROCOST(dummy);
- (void) newRule(dummy, 0, n, p);
- return n;
-}
-
-static NonTerminal
-normalize(ast, nt, patt) PatternAST ast; NonTerminal nt; Pattern *patt;
-{
- Symbol s;
- int new;
- Pattern dummy;
-
- s = enter(ast->op, &new);
- ast->sym = s;
- if (new) {
- fprintf(stderr, "Illegal use of %s --- undefined symbol\n", s->name);
- exit(1);
- return 0; /* shut up compilers */
- } else if (s->tag == NONTERMINAL) {
- if (ast->children) {
- fprintf(stderr, "Illegal use of %s, a non-terminal, as a terminal\n", s->name);
- exit(1);
- }
- *patt = newPattern(0);
- (*patt)->children[0] = s->u.nt;
- return s->u.nt;
- } else {
- s->u.op->ref = 1;
- *patt = newPattern(s->u.op);
- if (s->u.op->arity == -1) {
- if (!ast->children) {
- s->u.op->arity = 0;
- leaves = newList(s->u.op, leaves);
- } else if (!ast->children->next) {
- s->u.op->arity = 1;
- } else if (!ast->children->next->next) {
- s->u.op->arity = 2;
- } else {
- fprintf(stderr, "ERROR: Too many children (max = 2) for \"%s\"\n", s->name);
- exit(1);
- }
- if (s->u.op->arity > max_arity) {
- max_arity = s->u.op->arity;
- }
- }
- switch (s->u.op->arity) {
- default:
- assert(0);
- break;
- case 0:
- if (ast->children) {
- fprintf(stderr, "ERROR: Incorrect number of children for leaf operator, \"%s\"\n", s->name);
- exit(1);
- }
- break;
- case 1:
- if (!ast->children || ast->children->next) {
- fprintf(stderr, "ERROR: Incorrect number of children for unary operator, \"%s\"\n", s->name);
- exit(1);
- }
- (*patt)->children[0] = normalize((PatternAST) ast->children->x, 0, &dummy);
- break;
- case 2:
- if (!ast->children || !ast->children->next) {
- fprintf(stderr, "ERROR: Incorrect number of children for binary operator, \"%s\"\n", s->name);
- exit(1);
- }
- (*patt)->children[0] = normalize((PatternAST) ast->children->x, 0, &dummy);
- (*patt)->children[1] = normalize((PatternAST) ast->children->next->x, 0, &dummy);
- break;
- }
- if (nt) {
- (*patt)->normalizer = nt;
- return nt;
- } else {
- return lookup(*patt);
- }
- }
-}
-
-static void
-doEnterNonTerm(ast) RuleAST ast;
-{
- int new;
- Symbol s;
- DeltaCost delta;
- int i;
- IntList p;
-
-
- s = enter(ast->lhs, &new);
- if (new) {
- s->u.nt = newNonTerminal(s->name);
- s->tag = NONTERMINAL;
- } else {
- if (s->tag != NONTERMINAL) {
- fprintf(stderr, "Illegal use of %s as a non-terminal\n", s->name);
- exit(1);
- }
- }
- ZEROCOST(delta);
- for (p = ast->cost, i = 0; p; p = p->next, i++) {
- int x = p->x;
-#ifndef NOLEX
- if (lexical) {
- if (i < DELTAWIDTH) {
- delta[i] = x;
- }
- } else
-#endif /* NOLEX */
- {
- if (i == principleCost) {
- PRINCIPLECOST(delta) = x;
- }
- }
- }
- ast->rule = newRule(delta, ast->erulenum, s->u.nt, 0);
-}
-
-static void
-doRule(ast) RuleAST ast;
-{
- Pattern pat;
-
- (void) normalize(ast->pat, ast->rule->lhs, &pat);
- ast->rule->pat = pat;
-}
-
-static void
-doTable(op) Operator op;
-{
- op->table = newTable(op);
-}
-
-void
-doSpec(decls, rules) List decls; List rules;
-{
- foreachList((ListFn) doDecl, decls);
- debug(debugTables, foreachList((ListFn) dumpOperator_l, operators));
-
- ruleASTs = rules;
- reveachList((ListFn) doEnterNonTerm, rules);
-
- last_user_nonterminal = max_nonterminal;
-
- reveachList((ListFn) doRule, rules);
- debug(debugTables, foreachList((ListFn) dumpRule, rules));
-
- foreachList((ListFn) doTable, operators);
-}
-
-void
-doStart(name) char *name;
-{
- Symbol s;
- int new;
-
- if (start) {
- yyerror1("Redeclaration of start symbol to be ");
- fprintf(stderr, "\"%s\"\n", name);
- exit(1);
- }
- s = enter(name, &new);
- if (new) {
- s->u.nt = newNonTerminal(s->name);
- s->tag = NONTERMINAL;
- } else {
- if (s->tag != NONTERMINAL) {
- fprintf(stderr, "Illegal use of %s as a non-terminal\n", s->name);
- exit(1);
- }
- }
-}
-
-void
-doGrammarNts()
-{
- List l;
- int new;
-
- for (l = grammarNts; l; l = l->next) {
- char *n = (char*) l->x;
- Symbol s;
-
- s = enter(n, &new);
- if (new) {
- fprintf(stderr, "ERROR: %%gram, unused non-terminal: \"%s\"\n", n);
- exit(1);
- }
- if (s->tag != NONTERMINAL) {
- fprintf(stderr, "ERROR: %%gram, Not a non-terminal: \"%s\"\n", n);
- exit(1);
- }
- l->x = s;
- }
-}
-
-void
-doGram(nts) List nts;
-{
- if (grammarNts) {
- yyerror1("Redeclaration of %%gram\n");
- exit(1);
- }
- grammarNts = nts;
-}
-
-Arity
-newArity(ar, b) int ar; List b;
-{
- Arity a = (Arity) zalloc(sizeof(struct arity));
- a->arity = ar;
- a->bindings = b;
- return a;
-}
-
-Binding
-newBinding(name, opnum) char *name; int opnum;
-{
- Binding b = (Binding) zalloc(sizeof(struct binding));
- if (opnum == 0) {
- yyerror1("ERROR: Non-positive external symbol number, ");
- fprintf(stderr, "%d", opnum);
- exit(1);
- }
- b->name = name;
- b->opnum = opnum;
- return b;
-}
-
-PatternAST
-newPatternAST(op, children) char *op; List children;
-{
- PatternAST p = (PatternAST) zalloc(sizeof(struct patternAST));
- p->op = op;
- p->children = children;
- return p;
-}
-
-int max_ruleAST;
-
-RuleAST
-newRuleAST(lhs, pat, erulenum, cost) char *lhs; PatternAST pat; int erulenum; IntList cost;
-{
- RuleAST p = (RuleAST) zalloc(sizeof(struct ruleAST));
- p->lhs = lhs;
- p->pat = pat;
- if (erulenum <= 0) {
- yyerror1("External Rulenumber ");
- fprintf(stderr, "(%d) <= 0\n", erulenum);
- exit(1);
- }
- p->erulenum = erulenum;
- p->cost = cost;
- max_ruleAST++;
- return p;
-}
-
-void
-dumpBinding(b) Binding b;
-{
- printf("%s=%d ", b->name, b->opnum);
-}
-
-void
-dumpArity(a) Arity a;
-{
- List l;
-
- printf("Arity(%d) ", a->arity);
- for (l = a->bindings; l; l = l->next) {
- Binding b = (Binding) l->x;
- dumpBinding(b);
- }
- printf("\n");
-}
-
-void
-dumpPatternAST(p) PatternAST p;
-{
- List l;
-
- printf("%s", p->op);
- if (p->children) {
- printf("(");
- for (l = p->children; l; l = l->next) {
- PatternAST past = (PatternAST) l->x;
- dumpPatternAST(past);
- if (l->next) {
- printf(", ");
- }
- }
- printf(")");
- }
-}
-
-void
-dumpRuleAST(p) RuleAST p;
-{
- printf("%s : ", p->lhs);
- dumpPatternAST(p->pat);
- printf(" = %d (%ld)\n", p->erulenum, (long) p->cost);
-}
-
-void
-dumpDecls(decls) List decls;
-{
- List l;
-
- for (l = decls; l; l = l->next) {
- Arity a = (Arity) l->x;
- dumpArity(a);
- }
-}
-
-void
-dumpRules(rules) List rules;
-{
- List l;
-
- for (l = rules; l; l = l->next) {
- RuleAST p = (RuleAST) l->x;
- dumpRuleAST(p);
- }
-}
-
+++ /dev/null
-/* $Id$ */
-
-struct binding {
- char *name;
- int opnum;
-};
-typedef struct binding *Binding;
-
-struct arity {
- int arity;
- List bindings;
-};
-typedef struct arity *Arity;
-
-struct patternAST {
- struct symbol *sym;
- char *op;
- List children;
-};
-typedef struct patternAST *PatternAST;
-
-struct ruleAST {
- char *lhs;
- PatternAST pat;
- int erulenum;
- IntList cost;
- struct rule *rule;
- struct strTableElement *kids;
- struct strTableElement *nts;
-};
-typedef struct ruleAST *RuleAST;
-
-typedef enum {
- UNKNOWN,
- OPERATOR,
- NONTERMINAL
-} TagType;
-
-struct symbol {
- char *name;
- TagType tag;
- union {
- NonTerminal nt;
- Operator op;
- } u;
-};
-typedef struct symbol *Symbol;
-
-struct strTableElement {
- char *str;
- IntList erulenos;
- char *ename;
-};
-typedef struct strTableElement *StrTableElement;
-
-struct strTable {
- List elems;
-};
-typedef struct strTable *StrTable;
-
-extern void doGrammarNts ARGS((void));
-void makeRuleDescArray ARGS((void));
-void makeDeltaCostArray ARGS((void));
-void makeStateStringArray ARGS((void));
-
-extern StrTable newStrTable ARGS((void));
-extern StrTableElement addString ARGS((StrTable, char *, int, int *));
-
-extern void doSpec ARGS((List, List));
-extern Arity newArity ARGS((int, List));
-extern Binding newBinding ARGS((char *, int));
-extern PatternAST newPatternAST ARGS((char *, List));
-extern RuleAST newRuleAST ARGS((char *, PatternAST, int, IntList));
-extern Symbol enter ARGS((char *, int *));
-extern Symbol newSymbol ARGS((char *));
-
-extern void makeDebug ARGS((void));
-extern void makeSimple ARGS((void));
-extern void makePlanks ARGS((void));
-extern void makeOpLabel ARGS((void));
-extern void makeChild ARGS((void));
-extern void makeOperators ARGS((void));
-extern void makeLabel ARGS((void));
-extern void makeString ARGS((void));
-extern void makeString ARGS((void));
-extern void makeReduce ARGS((void));
-extern void makeRuleTable ARGS((void));
-extern void makeTables ARGS((void));
-extern void makeTreecost ARGS((void));
-extern void makePrint ARGS((void));
-extern void makeRule ARGS((void));
-extern void makeNts ARGS((void));
-extern void makeKids ARGS((void));
-extern void startBurm ARGS((void));
-extern void startOptional ARGS((void));
-extern void makePlankLabel ARGS((void));
-extern void makeStateLabel ARGS((void));
-extern void makeStringArray ARGS((void));
-extern void makeNonterminalArray ARGS((void));
-extern void makeCostArray ARGS((void));
-extern void makeLHSmap ARGS((void));
-extern void makeClosureArray ARGS((void));
-extern void makeOperatorVector ARGS((void));
-extern void endOptional ARGS((void));
-extern void reportDiagnostics ARGS((void));
-extern void makeNonterminals ARGS((void));
-extern int opsOfArity ARGS((int));
-
-extern void yypurge ARGS((void));
-extern void yyfinished ARGS((void));
-
-extern void printRepresentative ARGS((FILE *, Item_Set));
-
-extern void dumpRules ARGS((List));
-extern void dumpDecls ARGS((List));
-extern void dumpRuleAST ARGS((RuleAST));
-extern void dumpPatternAST ARGS((PatternAST));
-extern void dumpArity ARGS((Arity));
-extern void dumpBinding ARGS((Binding));
-extern void dumpStrTable ARGS((StrTable));
-
-extern int yylex ARGS((void));
-extern int yyparse ARGS((void));
-
-extern int max_ruleAST;
-extern List ruleASTs;
-
-extern FILE *outfile;
-extern const char *prefix;
-extern int trimflag;
-extern int speedflag;
-extern int grammarflag;
+++ /dev/null
-%{
-char rcsid_gram[] = "$Id$";
-
-#include <stdio.h>
-#include "b.h"
-#include "fe.h"
-void doGram(List);
-%}
-
-%union {
- int y_int;
- char *y_string;
- Arity y_arity;
- Binding y_binding;
- PatternAST y_patternAST;
- RuleAST y_ruleAST;
- List y_list;
- IntList y_intlist;
-}
-
-%start full
-
-%term ERROR
-%term K_TERM
-%term K_GRAM
-%term K_START
-%term K_PPERCENT
-%term INT
-%term ID
-
-%token <y_string> ID
-%token <y_int> INT
-
-%type <y_arity> decl
-%type <y_binding> binding
-%type <y_intlist> cost costtail
-%type <y_ruleAST> rule
-%type <y_patternAST> pattern
-%type <y_list> decls rules bindinglist grammarlist
-%%
-
-
-full : spec
- | spec K_PPERCENT
- { yyfinished(); }
- ;
-
-spec : decls K_PPERCENT rules
- { doSpec($1, $3); }
- ;
-
-decls : /* lambda */ { $$ = 0; }
- | decls decl { $$ = newList($2, $1); }
- ;
-
-decl : K_TERM bindinglist { $$ = newArity(-1, $2); }
- | K_GRAM grammarlist { $$ = 0; doGram($2); }
- | K_START ID { $$ = 0; doStart($2); } /* kludge */
- ;
-
-grammarlist : /* lambda */ { $$ = 0; }
- | grammarlist ID { $$ = newList($2, $1); }
- ;
-
-bindinglist : /* lambda */ { $$ = 0; }
- | bindinglist binding { $$ = newList($2, $1); }
- ;
-
-binding : ID '=' INT { $$ = newBinding($1, $3); }
- ;
-
-rules : /* lambda */ { $$ = 0; }
- | rules rule { $$ = newList($2, $1); }
- ;
-
-rule : ID ':' pattern '=' INT cost ';' { $$ = newRuleAST($1, $3, $5, $6); }
- ;
-
-pattern : ID { $$ = newPatternAST($1, 0); }
- | ID '(' pattern ')' { $$ = newPatternAST($1, newList($3,0)); }
- | ID '(' pattern ',' pattern ')' { $$ = newPatternAST($1, newList($3, newList($5, 0))); }
- ;
-
-cost : /* lambda */ { $$ = 0; }
- | '(' INT costtail ')' { $$ = newIntList($2, $3); }
- ;
-
-costtail : /* lambda */ { $$ = 0; }
- | ',' INT costtail { $$ = newIntList($2, $3); }
- | INT costtail { $$ = newIntList($1, $2); }
- ;
+++ /dev/null
-char rcsid_item[] = "$Id$";
-
-#include "b.h"
-#include <stdio.h>
-#include <string.h>
-#include "fe.h"
-
-static Item_Set fptr;
-
-ItemArray
-newItemArray()
-{
- ItemArray ia;
- ia = (ItemArray) zalloc(max_nonterminal *sizeof(*ia));
- return ia;
-}
-
-ItemArray
-itemArrayCopy(src) ItemArray src;
-{
- ItemArray dst;
-
- dst = newItemArray();
- memcpy(dst, src, max_nonterminal * sizeof(*dst));
- return dst;
-}
-
-Item_Set
-newItem_Set(relevant) Relevant relevant;
-{
- Item_Set ts;
-
- if (fptr) {
- ts = fptr;
- fptr = 0;
- memset(ts->virgin, 0, max_nonterminal * sizeof(struct item));
- if (ts->closed) {
- zfree(ts->closed);
- ts->closed = 0;
- }
- ts->num = 0;
- ts->op = 0;
- } else {
- ts = (Item_Set) zalloc(sizeof(struct item_set));
- ts->virgin = newItemArray();
- }
- ts->relevant = relevant;
- return ts;
-}
-
-void
-freeItem_Set(ts) Item_Set ts;
-{
- assert(!fptr);
- fptr = ts;
-}
-
-int
-equivSet(a, b) Item_Set a; Item_Set b;
-{
- register Relevant r;
- register int nt;
- register Item *aa = a->virgin;
- register Item *ba = b->virgin;
-
- /*
- return !bcmp(a->virgin, b->virgin, max_nonterminal * sizeof(Item));
- */
-
- r = a->relevant ? a->relevant : b->relevant;
- assert(r);
-
- if (a->op && b->op && a->op != b->op) {
- return 0;
- }
- for (; (nt = *r) != 0; r++) {
- if (aa[nt].rule != ba[nt].rule || !EQUALCOST(aa[nt].delta, ba[nt].delta)) {
- return 0;
- }
- }
- return 1;
-}
-
-void
-printRepresentative(f, s) FILE *f; Item_Set s;
-{
- if (!s) {
- return;
- }
- fprintf(f, "%s", s->op->name);
- switch (s->op->arity) {
- case 1:
- fprintf(f, "(");
- printRepresentative(f, s->kids[0]);
- fprintf(f, ")");
- break;
- case 2:
- fprintf(f, "(");
- printRepresentative(f, s->kids[0]);
- fprintf(f, ", ");
- printRepresentative(f, s->kids[1]);
- fprintf(f, ")");
- break;
- }
-}
-
-void
-dumpItem(t) Item *t;
-{
- printf("[%s #%d]", t->rule->lhs->name, t->rule->num);
- dumpCost(t->delta);
-}
-
-void
-dumpItem_Set(ts) Item_Set ts;
-{
- int i;
-
- printf("Item_Set #%d: [", ts->num);
- for (i = 1; i < max_nonterminal; i++) {
- if (ts->virgin[i].rule) {
- printf(" %d", i);
- dumpCost(ts->virgin[i].delta);
- }
- }
- printf(" ]\n");
-}
-
-void
-dumpCost(dc) DeltaCost dc;
-{
- printf("(%ld)", (long) dc);
-}
+++ /dev/null
-char rcsid_lex[] = "$Id$";
-
-#include <ctype.h>
-#include <stdio.h>
-#include <string.h>
-#include "b.h"
-#include "fe.h"
-#include "gram.tab.h"
-
-static char buf[BUFSIZ];
-
-static int yyline = 1;
-
-typedef int (*ReadFn) ARGS((void));
-
-static char *StrCopy ARGS((char *));
-static int code_get ARGS((void));
-static int simple_get ARGS((void));
-static void ReadCharString ARGS((ReadFn, int));
-static void ReadCodeBlock ARGS((void));
-static void ReadOldComment ARGS((ReadFn));
-
-static char *
-StrCopy(s) char *s;
-{
- char *t = (char *)zalloc(strlen(s) + 1);
- strcpy(t,s);
- return t;
-}
-
-static int
-simple_get()
-{
- int ch;
- if ((ch = getchar()) == '\n') {
- yyline++;
- }
- return ch;
-}
-
-static int
-code_get()
-{
- int ch;
- if ((ch = getchar()) == '\n') {
- yyline++;
- }
- if (ch != EOF) {
- fputc(ch, outfile);
- }
- return ch;
-}
-
-void
-yypurge()
-{
- while (code_get() != EOF) ;
-}
-
-
-static void
-ReadCharString(rdfn, which) ReadFn rdfn; int which;
-{
- int ch;
- int backslash = 0;
- int firstline = yyline;
-
- while ((ch = rdfn()) != EOF) {
- if (ch == which && !backslash) {
- return;
- }
- if (ch == '\\' && !backslash) {
- backslash = 1;
- } else {
- backslash = 0;
- }
- }
- yyerror1("Unexpected EOF in string on line ");
- fprintf(stderr, "%d\n", firstline);
- exit(1);
-}
-
-static void
-ReadOldComment(rdfn) ReadFn rdfn;
-{
- /* will not work for comments delimiter in string */
-
- int ch;
- int starred = 0;
- int firstline = yyline;
-
- while ((ch = rdfn()) != EOF) {
- if (ch == '*') {
- starred = 1;
- } else if (ch == '/' && starred) {
- return;
- } else {
- starred = 0;
- }
- }
- yyerror1("Unexpected EOF in comment on line ");
- fprintf(stderr, "%d\n", firstline);
- exit(1);
-}
-
-static void
-ReadCodeBlock()
-{
- int ch;
- int firstline = yyline;
-
- while ((ch = getchar()) != EOF) {
- if (ch == '%') {
- ch = getchar();
- if (ch != '}') {
- yyerror("bad %%");
- }
- return;
- }
- fputc(ch, outfile);
- if (ch == '\n') {
- yyline++;
- }
- if (ch == '"' || ch == '\'') {
- ReadCharString(code_get, ch);
- } else if (ch == '/') {
- ch = getchar();
- if (ch == '*') {
- fputc(ch, outfile);
- ReadOldComment(code_get);
- continue;
- } else {
- ungetc(ch, stdin);
- }
- }
- }
- yyerror1("Unclosed block of C code started on line ");
- fprintf(stderr, "%d\n", firstline);
- exit(1);
-}
-
-static int done;
-void
-yyfinished()
-{
- done = 1;
-}
-
-int
-yylex()
-{
- int ch;
- char *ptr = buf;
-
- if (done) return 0;
- while ((ch = getchar()) != EOF) {
- switch (ch) {
- case ' ':
- case '\f':
- case '\t':
- continue;
- case '\n':
- yyline++;
- continue;
- case '(':
- case ')':
- case ',':
- case ':':
- case ';':
- case '=':
- return(ch);
- case '/':
- ch = getchar();
- if (ch == '*') {
- ReadOldComment(simple_get);
- continue;
- } else {
- ungetc(ch, stdin);
- yyerror("illegal char /");
- continue;
- }
- case '%':
- ch = getchar();
- switch (ch) {
- case '%':
- return (K_PPERCENT);
- case '{':
- ReadCodeBlock();
- continue;
- case 's':
- case 'g':
- case 't':
- do {
- if (ptr >= &buf[BUFSIZ]) {
- yyerror("ID too long");
- return(ERROR);
- } else {
- *ptr++ = ch;
- }
- ch = getchar();
- } while (isalpha(ch) || isdigit(ch) || ch == '_');
- ungetc(ch, stdin);
- *ptr = '\0';
- if (!strcmp(buf, "term")) return K_TERM;
- if (!strcmp(buf, "start")) return K_START;
- if (!strcmp(buf, "gram")) return K_GRAM;
- yyerror("illegal character after %%");
- continue;
- default:
- yyerror("illegal character after %%");
- continue;
- }
- default:
- if (isalpha(ch) ) {
- do {
- if (ptr >= &buf[BUFSIZ]) {
- yyerror("ID too long");
- return(ERROR);
- } else {
- *ptr++ = ch;
- }
- ch = getchar();
- } while (isalpha(ch) || isdigit(ch) || ch == '_');
- ungetc(ch, stdin);
- *ptr = '\0';
- yylval.y_string = StrCopy(buf);
- return(ID);
- }
- if (isdigit(ch)) {
- int val=0;
- do {
- val *= 10;
- val += (ch - '0');
- ch = getchar();
- } while (isdigit(ch));
- ungetc(ch, stdin);
- yylval.y_int = val;
- return(INT);
- }
- yyerror1("illegal char ");
- fprintf(stderr, "(\\%03o)\n", ch);
- exit(1);
- }
- }
- return(0);
-}
-
-void yyerror1(const char *str)
-{
- fprintf(stderr, "line %d: %s", yyline, str);
-}
-
-void
-yyerror(const char *str)
-{
- yyerror1(str);
- fprintf(stderr, "\n");
- exit(1);
-}
+++ /dev/null
-char rcsid_list[] = "$Id$";
-
-#include "b.h"
-
-IntList
-newIntList(x, next) int x; IntList next;
-{
- IntList l;
-
- l = (IntList) zalloc(sizeof(*l));
- assert(l);
- l->x = x;
- l->next = next;
-
- return l;
-}
-
-List
-newList(x, next) void *x; List next;
-{
- List l;
-
- l = (List) zalloc(sizeof(*l));
- assert(l);
- l->x = x;
- l->next = next;
-
- return l;
-}
-
-List
-appendList(x, l) void *x; List l;
-{
- List last;
- List p;
-
- last = 0;
- for (p = l; p; p = p->next) {
- last = p;
- }
- if (last) {
- last->next = newList(x, 0);
- return l;
- } else {
- return newList(x, 0);
- }
-}
-
-void
-foreachList(f, l) ListFn f; List l;
-{
- for (; l; l = l->next) {
- (*f)(l->x);
- }
-}
-
-void
-reveachList(f, l) ListFn f; List l;
-{
- if (l) {
- reveachList(f, l->next);
- (*f)(l->x);
- }
-}
-
-int
-length(l) List l;
-{
- int c = 0;
-
- for(; l; l = l->next) {
- c++;
- }
- return c;
-}
+++ /dev/null
-char rcsid_main[] = "$Id$";
-
-#include <math.h>
-#include <stdio.h>
-#include "b.h"
-#include "fe.h"
-
-int debugTables = 0;
-static int simpleTables = 0;
-static int internals = 0;
-static int diagnostics = 0;
-
-static char *inFileName;
-static char *outFileName;
-
-static char version[] = "BURG, Version 1.0";
-
-extern int main ARGS((int argc, char **argv));
-
-int
-main(argc, argv) int argc; char **argv;
-{
- int i;
- extern int atoi ARGS((const char *));
-
- for (i = 1; argv[i]; i++) {
- char **needStr = 0;
- int *needInt = 0;
-
- if (argv[i][0] == '-') {
- switch (argv[i][1]) {
- case 'V':
- fprintf(stderr, "%s\n", version);
- break;
- case 'p':
- needStr = (char**)&prefix;
- break;
- case 'o':
- needStr = &outFileName;
- break;
- case 'I':
- internals = 1;
- break;
- case 'T':
- simpleTables = 1;
- break;
- case '=':
-#ifdef NOLEX
- fprintf(stderr, "'%s' was not compiled to support lexicographic ordering\n", argv[0]);
-#else
- lexical = 1;
-#endif /* NOLEX */
- break;
- case 'O':
- needInt = &principleCost;
- break;
- case 'c':
- needInt = &prevent_divergence;
- break;
- case 'e':
- needInt = &exceptionTolerance;
- break;
- case 'd':
- diagnostics = 1;
- break;
- case 'S':
- speedflag = 1;
- break;
- case 't':
- trimflag = 1;
- break;
- case 'G':
- grammarflag = 1;
- break;
- default:
- fprintf(stderr, "Bad option (%s)\n", argv[i]);
- exit(1);
- }
- } else {
- if (inFileName) {
- fprintf(stderr, "Unexpected Filename (%s) after (%s)\n", argv[i], inFileName);
- exit(1);
- }
- inFileName = argv[i];
- }
- if (needInt || needStr) {
- char *v;
- char *opt = argv[i];
-
- if (argv[i][2]) {
- v = &argv[i][2];
- } else {
- v = argv[++i];
- if (!v) {
- fprintf(stderr, "Expection argument after %s\n", opt);
- exit(1);
- }
- }
- if (needInt) {
- *needInt = atoi(v);
- } else if (needStr) {
- *needStr = v;
- }
- }
- }
-
- if (inFileName) {
- if(freopen(inFileName, "r", stdin)==NULL) {
- fprintf(stderr, "Failed opening (%s)", inFileName);
- exit(1);
- }
- }
-
- if (outFileName) {
- if ((outfile = fopen(outFileName, "w")) == NULL) {
- fprintf(stderr, "Failed opening (%s)", outFileName);
- exit(1);
- }
- } else {
- outfile = stdout;
- }
-
-
- yyparse();
-
- if (!rules) {
- fprintf(stderr, "ERROR: No rules present\n");
- exit(1);
- }
-
- findChainRules();
- findAllPairs();
- doGrammarNts();
- build();
-
- debug(debugTables, foreachList((ListFn) dumpOperator_l, operators));
- debug(debugTables, printf("---final set of states ---\n"));
- debug(debugTables, dumpMapping(globalMap));
-
-
- startBurm();
- makeNts();
- if (simpleTables) {
- makeSimple();
- } else {
- makePlanks();
- }
-
- startOptional();
- makeLabel();
- makeKids();
-
- if (internals) {
- makeChild();
- makeOpLabel();
- makeStateLabel();
- }
- endOptional();
-
- makeOperatorVector();
- makeNonterminals();
- if (internals) {
- makeOperators();
- makeStringArray();
- makeRuleDescArray();
- makeCostArray();
- makeDeltaCostArray();
- makeStateStringArray();
- makeNonterminalArray();
- /*
- makeLHSmap();
- */
- }
- makeClosureArray();
-
- if (diagnostics) {
- reportDiagnostics();
- }
-
- yypurge();
- exit(0);
-}
+++ /dev/null
-char rcsid_map[] = "$Id$";
-
-#include <stdio.h>
-#include <string.h>
-#include "b.h"
-#include "fe.h"
-
-Mapping globalMap;
-
-static void growMapping ARGS((Mapping));
-static int hash ARGS((Item_Set, int));
-
-Mapping
-newMapping(size) int size;
-{
- Mapping m;
-
- m = (Mapping) zalloc(sizeof(struct mapping));
- assert(m);
-
- m->count = 0;
- m->hash = (List*) zalloc(size * sizeof(List));
- m->hash_size = size;
- m->max_size = STATES_INCR;
- m->set = (Item_Set*) zalloc(m->max_size * sizeof(Item_Set));
- assert(m->set);
-
- return m;
-}
-
-static void
-growMapping(m) Mapping m;
-{
- Item_Set *tmp;
-
- m->max_size += STATES_INCR;
- tmp = (Item_Set*) zalloc(m->max_size * sizeof(Item_Set));
- memcpy(tmp, m->set, m->count * sizeof(Item_Set));
- zfree(m->set);
- m->set = tmp;
-}
-
-static int
-hash(ts, mod) Item_Set ts; int mod;
-{
- register Item *p = ts->virgin;
- register int v;
- register Relevant r = ts->relevant;
- register int nt;
-
- if (!ts->op) {
- return 0;
- }
-
- v = 0;
- for (; (nt = *r) != 0; r++) {
- v ^= ((long)p[nt].rule) + (PRINCIPLECOST(p[nt].delta)<<4);
- }
- v >>= 4;
- v &= (mod-1);
- return v;
-}
-
-Item_Set
-encode(m, ts, new) Mapping m; Item_Set ts; int *new;
-{
- int h;
- List l;
-
- assert(m);
- assert(ts);
- assert(m->count <= m->max_size);
-
- if (grammarNts && errorState && m == globalMap) {
- List l;
- int found;
-
- found = 0;
- for (l = grammarNts; l; l = l->next) {
- Symbol s;
- s = (Symbol) l->x;
-
- if (ts->virgin[s->u.nt->num].rule) {
- found = 1;
- break;
- }
- }
- if (!found) {
- *new = 0;
- return errorState;
- }
- }
-
- *new = 0;
- h = hash(ts, m->hash_size);
- for (l = m->hash[h]; l; l = l->next) {
- Item_Set s = (Item_Set) l->x;
- if (ts->op == s->op && equivSet(ts, s)) {
- ts->num = s->num;
- return s;
- }
- }
- if (m->count >= m->max_size) {
- growMapping(m);
- }
- assert(m->count < m->max_size);
- m->set[m->count] = ts;
- ts->num = m->count++;
- *new = 1;
- m->hash[h] = newList(ts, m->hash[h]);
- return ts;
-}
-
-Item_Set
-decode(m, t) Mapping m; ItemSetNum t;
-{
- assert(m);
- assert(t);
- assert(m->count < m->max_size);
- assert(t < m->count);
-
- return m->set[t];
-}
-
-void
-dumpMapping(m) Mapping m;
-{
- int i;
-
- printf("BEGIN Mapping: Size=%d\n", m->count);
- for (i = 0; i < m->count; i++) {
- dumpItem_Set(m->set[i]);
- }
- printf("END Mapping\n");
-}
+++ /dev/null
-char rcsid_nonterminal[] = "$Id$";
-
-#include "b.h"
-#include <stdio.h>
-#include <string.h>
-
-NonTerminal start;
-NonTerminalNum max_nonterminal = 1;
-NonTerminalNum last_user_nonterminal;
-List nonterminals;
-
-NonTerminal
-newNonTerminal(name) char *name;
-{
- NonTerminal nt;
-
- nt = (NonTerminal) zalloc(sizeof(struct nonterminal));
- assert(nt);
- if (max_nonterminal == 1) {
- start = nt;
- }
- nt->name = name;
- nt->num = max_nonterminal++;
- nonterminals = newList(nt, nonterminals);
-
- return nt;
-}
-
-int
-nonTerminalName(buf, i) char *buf; int i;
-{
- List l;
-
- for (l = nonterminals; l; l = l->next) {
- NonTerminal nt = (NonTerminal) l->x;
- if (nt->num == i) {
- strcpy(buf, nt->name);
- return 1;
- }
- }
- strcpy(buf, "(Unknown NonTerminal)");
- return 0;
-}
-
-void
-dumpNonTerminal(n) NonTerminal n;
-{
- printf("%s(%d)", n->name, n->num);
-}
+++ /dev/null
-char rcsid_operator[] = "$Id$";
-
-#include "b.h"
-#include <stdio.h>
-
-int max_arity = -1;
-
-List operators;
-List leaves;
-
-Operator
-newOperator(name, num, arity) char *name; OperatorNum num; ArityNum arity;
-{
- Operator op;
-
- assert(arity <= MAX_ARITY);
- op = (Operator) zalloc(sizeof(struct operator));
- assert(op);
- op->name = name;
- op->num = num;
- op->arity = arity;
-
- operators = newList(op, operators);
-
- return op;
-}
-
-void
-dumpOperator_s(op) Operator op;
-{
- printf("Op: %s(%d)=%d\n", op->name, op->arity, op->num);
-}
-
-void
-dumpOperator(op, full) Operator op; int full;
-{
- dumpOperator_s(op);
- if (full) {
- dumpTable(op->table, 0);
- }
-}
-
-void
-dumpOperator_l(op) Operator op;
-{
- dumpOperator(op, 1);
-}
-
+++ /dev/null
-char rcsid_pattern[] = "$Id$";
-
-#include <stdio.h>
-#include "b.h"
-
-Pattern
-newPattern(op) Operator op;
-{
- Pattern p;
-
- p = (Pattern) zalloc(sizeof(struct pattern));
- p->op = op;
- return p;
-}
-
-void
-dumpPattern(p) Pattern p;
-{
- int i;
-
- if (!p) {
- printf("[no-pattern]");
- return;
- }
-
- if (p->op) {
- printf("%s", p->op->name);
- if (p->op->arity > 0) {
- printf("(");
- for (i = 0; i < p->op->arity; i++) {
- printf("%s ", p->children[i]->name);
- }
- printf(")");
- }
- } else {
- printf("%s", p->children[0]->name);
- }
-}
+++ /dev/null
-char rcsid_plank[] = "$Id$";
-
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-#include "b.h"
-#include "fe.h"
-
-#define ERROR_VAL 0
-
-int speedflag = 0;
-
-Item_Set *sortedStates;
-static struct stateMapTable smt;
-int exceptionTolerance = 0;
-static int plankSize = 32;
-
-static Plank newPlank ARGS((void));
-static PlankMap newPlankMap ARGS((int));
-static StateMap newStateMap ARGS((void));
-static Exception newException ARGS((int, int));
-static void enterStateMap ARGS((PlankMap, short *, int, int *));
-static List assemblePlanks ARGS((void));
-static void assignRules ARGS((RuleAST));
-static int stateCompare ARGS((Item_Set *, Item_Set *));
-static int ruleCompare ARGS((RuleAST *, RuleAST *));
-static void renumber ARGS((void));
-static short * newVector ARGS((void));
-static int width ARGS((int));
-static PlankMap mapToPmap ARGS((Dimension));
-static void doDimPmaps ARGS((Operator));
-static void doNonTermPmaps ARGS((NonTerminal));
-static void makePmaps ARGS((void));
-static void outPlank ARGS((Plank));
-static void purgePlanks ARGS((List));
-static void inToEx ARGS((void));
-static void makePlankRuleMacros ARGS((void));
-static void makePlankRule ARGS((void));
-static void exceptionSwitch ARGS((List, const char *, const char *, const char *, int, const char *));
-static void doPlankLabel ARGS((Operator));
-static void doPlankLabelSafely ARGS((Operator));
-static void doPlankLabelMacrosSafely ARGS((Operator));
-static void makePlankState ARGS((void));
-
-static Plank
-newPlank()
-{
- Plank p;
- char buf[50];
- static int num = 0;
-
- p = (Plank) zalloc(sizeof(struct plank));
- sprintf(buf, "%s_plank_%d", prefix, num++);
- p->name = (char *) zalloc(strlen(buf)+1);
- strcpy(p->name, buf);
- return p;
-}
-
-static PlankMap
-newPlankMap(offset) int offset;
-{
- PlankMap im;
-
- im = (PlankMap) zalloc(sizeof(struct plankMap));
- im->offset = offset;
- return im;
-}
-
-static StateMap
-newStateMap()
-{
- char buf[50];
- static int num = 0;
-
- StateMap sm;
-
- sm = (StateMap) zalloc(sizeof(struct stateMap));
- sprintf(buf, "f%d", num++);
- sm->fieldname = (char *) zalloc(strlen(buf)+1);
- strcpy(sm->fieldname, buf);
- return sm;
-}
-
-static Exception
-newException(index, value) int index; int value;
-{
- Exception e;
-
- e = (Exception) zalloc(sizeof(struct except));
- e->index = index;
- e->value = value;
- return e;
-}
-
-static void
-enterStateMap(im, v, width, new) PlankMap im; short * v; int width; int *new;
-{
- int i;
- StateMap sm;
- List l;
- int size;
-
- assert(im);
- assert(v);
- assert(width > 0);
- size = globalMap->count;
-
- for (l = smt.maps; l; l = l->next) {
- int ecount;
-
- sm = (StateMap) l->x;
- ecount = 0;
- for (i = 0; i < size; i++) {
- if (v[i] != -1 && sm->value[i] != -1 && v[i] != sm->value[i]) {
- if (++ecount > exceptionTolerance) {
- goto again;
- }
- }
- }
- for (i = 0; i < size; i++) {
- assert(v[i] >= 0);
- assert(sm->value[i] >= 0);
- if (v[i] == -1) {
- continue;
- }
- if (sm->value[i] == -1) {
- sm->value[i] = v[i];
- } else if (v[i] != sm->value[i]) {
- im->exceptions = newList(newException(i,v[i]), im->exceptions);
- }
- }
- im->values = sm;
- if (width > sm->width) {
- sm->width = width;
- }
- *new = 0;
- return;
- again: ;
- }
- sm = newStateMap();
- im->values = sm;
- sm->value = v;
- sm->width = width;
- *new = 1;
- smt.maps = newList(sm, smt.maps);
-}
-
-static List
-assemblePlanks()
-{
- List planks = 0;
- Plank pl;
- List p;
- List s;
-
- for (s = smt.maps; s; s = s->next) {
- StateMap sm = (StateMap) s->x;
- for (p = planks; p; p = p->next) {
- pl = (Plank) p->x;
- if (sm->width <= plankSize - pl->width) {
- pl->width += sm->width;
- pl->fields = newList(sm, pl->fields);
- sm->plank = pl;
- goto next;
- }
- }
- pl = newPlank();
- pl->width = sm->width;
- pl->fields = newList(sm, 0);
- sm->plank = pl;
- planks = appendList(pl, planks);
- next: ;
- }
- return planks;
-}
-
-RuleAST *sortedRules;
-
-static int count;
-
-static void
-assignRules(ast) RuleAST ast;
-{
- sortedRules[count++] = ast;
-}
-
-static int
-stateCompare(s, t) Item_Set *s; Item_Set *t;
-{
- return strcmp((*s)->op->name, (*t)->op->name);
-}
-
-static int
-ruleCompare(s, t) RuleAST *s; RuleAST *t;
-{
- return strcmp((*s)->lhs, (*t)->lhs);
-}
-
-void
-dumpSortedStates()
-{
- int i;
-
- printf("dump Sorted States: ");
- for (i = 0; i < globalMap->count; i++) {
- printf("%d ", sortedStates[i]->num);
- }
- printf("\n");
-}
-
-void
-dumpSortedRules()
-{
- int i;
-
- printf("dump Sorted Rules: ");
- for (i = 0; i < max_ruleAST; i++) {
- printf("%d ", sortedRules[i]->rule->erulenum);
- }
- printf("\n");
-}
-
-static void
-renumber()
-{
- int i;
- Operator previousOp;
- NonTerminal previousLHS;
- int base_counter;
-
- sortedStates = (Item_Set*) zalloc(globalMap->count * sizeof(Item_Set));
- for (i = 1; i < globalMap->count; i++) {
- sortedStates[i-1] = globalMap->set[i];
- }
- qsort(sortedStates, globalMap->count-1, sizeof(Item_Set), (int(*)(const void *, const void *))stateCompare);
- previousOp = 0;
- for (i = 0; i < globalMap->count-1; i++) {
- sortedStates[i]->newNum = i;
- sortedStates[i]->op->stateCount++;
- if (previousOp != sortedStates[i]->op) {
- sortedStates[i]->op->baseNum = i;
- previousOp = sortedStates[i]->op;
- }
- }
-
- sortedRules = (RuleAST*) zalloc(max_ruleAST * sizeof(RuleAST));
- count = 0;
- foreachList((ListFn) assignRules, ruleASTs);
- qsort(sortedRules, max_ruleAST, sizeof(RuleAST), (int(*)(const void *, const void *))ruleCompare);
- previousLHS = 0;
- base_counter = 0;
- for (i = 0; i < max_ruleAST; i++) {
- if (previousLHS != sortedRules[i]->rule->lhs) {
- sortedRules[i]->rule->lhs->baseNum = base_counter;
- previousLHS = sortedRules[i]->rule->lhs;
- base_counter++; /* make space for 0 */
- }
- sortedRules[i]->rule->newNum = base_counter;
- sortedRules[i]->rule->lhs->ruleCount++;
- sortedRules[i]->rule->lhs->sampleRule = sortedRules[i]->rule; /* kludge for diagnostics */
- base_counter++;
- }
-}
-
-static short *
-newVector()
-{
- short *p;
- p = (short *) zalloc(globalMap->count* sizeof(short));
- return p;
-}
-
-static int
-width(v) int v;
-{
- int c;
-
- for (c = 0; v; v >>= 1) {
- c++;
- }
- return c;
-
-}
-
-static PlankMap
-mapToPmap(d) Dimension d;
-{
- PlankMap im;
- short *v;
- int i;
- int new;
-
- if (d->map->count == 1) {
- return 0;
- }
- assert(d->map->count > 1);
- im = newPlankMap(0);
- v = newVector();
- for (i = 0; i < globalMap->count-1; i++) {
- int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
- assert(index >= 0);
- v[i+1] = index;
- }
- v[0] = 0;
- enterStateMap(im, v, width(d->map->count), &new);
- if (!new) {
- zfree(v);
- }
- return im;
-}
-
-static void
-doDimPmaps(op) Operator op;
-{
- int i, j;
- Dimension d;
- short *v;
- PlankMap im;
- int new;
-
- if (!op->table->rules) {
- return;
- }
- switch (op->arity) {
- case 0:
- break;
- case 1:
- d = op->table->dimen[0];
- if (d->map->count > 1) {
- v = newVector();
- im = newPlankMap(op->baseNum);
- for (i = 0; i < globalMap->count-1; i++) {
- int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
- if (index) {
- Item_Set *ts = transLval(op->table, index, 0);
- v[i+1] = (*ts)->newNum - op->baseNum+1;
- assert(v[i+1] >= 0);
- }
- }
- enterStateMap(im, v, width(d->map->count-1), &new);
- if (!new) {
- zfree(v);
- }
- d->pmap = im;
- }
- break;
- case 2:
- if (op->table->dimen[0]->map->count == 1 && op->table->dimen[1]->map->count == 1) {
- op->table->dimen[0]->pmap = 0;
- op->table->dimen[1]->pmap = 0;
- } else if (op->table->dimen[0]->map->count == 1) {
- v = newVector();
- im = newPlankMap(op->baseNum);
- d = op->table->dimen[1];
- for (i = 0; i < globalMap->count-1; i++) {
- int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
- if (index) {
- Item_Set *ts = transLval(op->table, 1, index);
- v[i+1] = (*ts)->newNum - op->baseNum+1;
- assert(v[i+1] >= 0);
- }
- }
- enterStateMap(im, v, width(d->map->count-1), &new);
- if (!new) {
- zfree(v);
- }
- d->pmap = im;
- } else if (op->table->dimen[1]->map->count == 1) {
- v = newVector();
- im = newPlankMap(op->baseNum);
- d = op->table->dimen[0];
- for (i = 0; i < globalMap->count-1; i++) {
- int index = d->map->set[d->index_map.class[sortedStates[i]->num]->num]->num;
- if (index) {
- Item_Set *ts = transLval(op->table, index, 1);
- v[i +1] = (*ts)->newNum - op->baseNum +1;
- assert(v[i +1] >= 0);
- }
- }
- enterStateMap(im, v, width(d->map->count-1), &new);
- if (!new) {
- zfree(v);
- }
- d->pmap = im;
- } else {
- op->table->dimen[0]->pmap = mapToPmap(op->table->dimen[0]);
- op->table->dimen[1]->pmap = mapToPmap(op->table->dimen[1]);
- /* output table */
- fprintf(outfile, "static unsigned %s %s_%s_transition[%d][%d] = {",
- op->stateCount <= 255 ? "char" : "short",
- prefix,
- op->name,
- op->table->dimen[0]->map->count,
- op->table->dimen[1]->map->count);
- for (i = 0; i < op->table->dimen[0]->map->count; i++) {
- if (i > 0) {
- fprintf(outfile, ",");
- }
- fprintf(outfile, "\n{");
- for (j = 0; j < op->table->dimen[1]->map->count; j++) {
- Item_Set *ts = transLval(op->table, i, j);
- short diff;
- if (j > 0) {
- fprintf(outfile, ",");
- if (j % 10 == 0) {
- fprintf(outfile, "\t/* row %d, cols %d-%d*/\n",
- i,
- j-10,
- j-1);
- }
- }
- if ((*ts)->num > 0) {
- diff = (*ts)->newNum - op->baseNum +1;
- } else {
- diff = 0;
- }
- fprintf(outfile, "%5d", diff);
- }
- fprintf(outfile, "}\t/* row %d */", i);
- }
- fprintf(outfile, "\n};\n");
- }
- break;
- default:
- assert(0);
- }
-}
-
-static NonTerminal *ntVector;
-
-static void
-doNonTermPmaps(n) NonTerminal n;
-{
- short *v;
- PlankMap im;
- int new;
- int i;
-
- ntVector[n->num] = n;
- if (n->num >= last_user_nonterminal) {
- return;
- }
- if (n->ruleCount <= 0) {
- return;
- }
- im = newPlankMap(n->baseNum);
- v = newVector();
- for (i = 0; i < globalMap->count-1; i++) {
- Rule r = globalMap->set[sortedStates[i]->num]->closed[n->num].rule;
- if (r) {
- r->used = 1;
- v[i+1] = r->newNum - n->baseNum /*safely*/;
- assert(v[i+1] >= 0);
- }
- }
- enterStateMap(im, v, width(n->ruleCount+1), &new);
- if (!new) {
- zfree(v);
- }
- n->pmap = im;
-}
-
-static void
-makePmaps()
-{
- foreachList((ListFn) doDimPmaps, operators);
- ntVector = (NonTerminal*) zalloc((max_nonterminal) * sizeof(NonTerminal));
- foreachList((ListFn) doNonTermPmaps, nonterminals);
-}
-
-static void
-outPlank(p) Plank p;
-{
- List f;
- int i;
-
- fprintf(outfile, "static struct {\n");
-
- for (f = p->fields; f; f = f->next) {
- StateMap sm = (StateMap) f->x;
- fprintf(outfile, "\tunsigned int %s:%d;\n", sm->fieldname, sm->width);
- }
-
- fprintf(outfile, "} %s[] = {\n", p->name);
-
- for (i = 0; i < globalMap->count; i++) {
- fprintf(outfile, "\t{");
- for (f = p->fields; f; f = f->next) {
- StateMap sm = (StateMap) f->x;
- fprintf(outfile, "%4d,", sm->value[i] == -1 ? ERROR_VAL : sm->value[i]);
- }
- fprintf(outfile, "},\t/* row %d */\n", i);
- }
-
- fprintf(outfile, "};\n");
-}
-
-static void
-purgePlanks(planks) List planks;
-{
- List p;
-
- for (p = planks; p; p = p->next) {
- Plank x = (Plank) p->x;
- outPlank(x);
- }
-}
-
-static void
-inToEx()
-{
- int i;
- int counter;
-
- fprintf(outfile, "static short %s_eruleMap[] = {\n", prefix);
- counter = 0;
- for (i = 0; i < max_ruleAST; i++) {
- if (counter > 0) {
- fprintf(outfile, ",");
- if (counter % 10 == 0) {
- fprintf(outfile, "\t/* %d-%d */\n", counter-10, counter-1);
- }
- }
- if (counter < sortedRules[i]->rule->newNum) {
- assert(counter == sortedRules[i]->rule->newNum-1);
- fprintf(outfile, "%5d", 0);
- counter++;
- if (counter > 0) {
- fprintf(outfile, ",");
- if (counter % 10 == 0) {
- fprintf(outfile, "\t/* %d-%d */\n", counter-10, counter-1);
- }
- }
- }
- fprintf(outfile, "%5d", sortedRules[i]->rule->erulenum);
- counter++;
- }
- fprintf(outfile, "\n};\n");
-}
-
-static void
-makePlankRuleMacros()
-{
- int i;
-
- for (i = 1; i < last_user_nonterminal; i++) {
- List es;
- PlankMap im = ntVector[i]->pmap;
- fprintf(outfile, "#define %s_%s_rule(state)\t", prefix, ntVector[i]->name);
- if (im) {
- fprintf(outfile, "%s_eruleMap[", prefix);
- for (es = im->exceptions; es; es = es->next) {
- Exception e = (Exception) es->x;
- fprintf(outfile, "((state) == %d ? %d :",
- e->index, e->value);
- }
- fprintf(outfile, "%s[state].%s",
- im->values->plank->name,
- im->values->fieldname);
- for (es = im->exceptions; es; es = es->next) {
- fprintf(outfile, ")");
- }
- fprintf(outfile, " +%d]", im->offset);
-
- } else {
- /* nonterminal never appears on LHS. */
- assert(ntVector[i] == start);
- fprintf(outfile, "0");
- }
- fprintf(outfile, "\n");
- }
- fprintf(outfile, "\n");
-}
-
-static void
-makePlankRule()
-{
- int i;
-
- makePlankRuleMacros();
-
- fprintf(outfile, "#ifdef __STDC__\n");
- fprintf(outfile, "int %s_rule(int state, int goalnt) {\n", prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "int %s_rule(state, goalnt) int state; int goalnt; {\n", prefix);
- fprintf(outfile, "#endif\n");
-
- fprintf(outfile,
- "\t%s_assert(state >= 0 && state < %d, %s_PANIC(\"Bad state %%d passed to %s_rule\\n\", state));\n",
- prefix, globalMap->count, prefix, prefix);
- fprintf(outfile, "\tswitch(goalnt) {\n");
-
- for (i = 1; i < last_user_nonterminal; i++) {
- fprintf(outfile, "\tcase %d:\n", i);
- fprintf(outfile, "\t\treturn %s_%s_rule(state);\n", prefix, ntVector[i]->name);
- }
- fprintf(outfile, "\tdefault:\n");
- fprintf(outfile, "\t\t%s_PANIC(\"Unknown nonterminal %%d in %s_rule;\\n\", goalnt);\n", prefix, prefix);
- fprintf(outfile, "\t\tabort();\n");
- fprintf(outfile, "\t\treturn 0;\n");
- fprintf(outfile, "\t}\n");
- fprintf(outfile, "}\n");
-}
-
-static void
-exceptionSwitch(es, sw, pre, post, offset, def) List es; const char *sw; const char *pre; const char *post; int offset; const char *def;
-{
- if (es) {
- fprintf(outfile, "\t\tswitch (%s) {\n", sw);
- for (; es; es = es->next) {
- Exception e = (Exception) es->x;
- fprintf(outfile, "\t\tcase %d: %s %d; %s\n", e->index, pre, e->value+offset, post);
- }
- if (def) {
- fprintf(outfile, "\t\tdefault: %s;\n", def);
- }
- fprintf(outfile, "\t\t}\n");
- } else {
- if (def) {
- fprintf(outfile, "\t\t%s;\n", def);
- }
- }
-}
-
-static void
-doPlankLabel(op) Operator op;
-{
- PlankMap im0;
- PlankMap im1;
- char buf[100];
-
- fprintf(outfile, "\tcase %d:\n", op->num);
- switch (op->arity) {
- case 0:
- fprintf(outfile, "\t\treturn %d;\n", op->table->transition[0]->newNum);
- break;
- case 1:
- im0 = op->table->dimen[0]->pmap;
- if (im0) {
- exceptionSwitch(im0->exceptions, "l", "return ", "", im0->offset, 0);
- fprintf(outfile, "\t\treturn %s[l].%s + %d;\n",
- im0->values->plank->name, im0->values->fieldname, im0->offset);
- } else {
- Item_Set *ts = transLval(op->table, 1, 0);
- if (*ts) {
- fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum);
- } else {
- fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
- }
- }
- break;
- case 2:
- im0 = op->table->dimen[0]->pmap;
- im1 = op->table->dimen[1]->pmap;
- if (!im0 && !im1) {
- Item_Set *ts = transLval(op->table, 1, 1);
- if (*ts) {
- fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum);
- } else {
- fprintf(outfile, "\t\treturn %d;\n", ERROR_VAL);
- }
- } else if (!im0) {
- exceptionSwitch(im1->exceptions, "r", "return ", "", im1->offset, 0);
- fprintf(outfile, "\t\treturn %s[r].%s + %d;\n",
- im1->values->plank->name, im1->values->fieldname, im1->offset);
- } else if (!im1) {
- exceptionSwitch(im0->exceptions, "l", "return ", "", im0->offset, 0);
- fprintf(outfile, "\t\treturn %s[l].%s + %d;\n",
- im0->values->plank->name, im0->values->fieldname, im0->offset);
- } else {
- assert(im0->offset == 0);
- assert(im1->offset == 0);
- sprintf(buf, "l = %s[l].%s",
- im0->values->plank->name, im0->values->fieldname);
- exceptionSwitch(im0->exceptions, "l", "l =", "break;", 0, buf);
- sprintf(buf, "r = %s[r].%s",
- im1->values->plank->name, im1->values->fieldname);
- exceptionSwitch(im1->exceptions, "r", "r =", "break;", 0, buf);
-
- fprintf(outfile, "\t\treturn %s_%s_transition[l][r] + %d;\n",
- prefix,
- op->name,
- op->baseNum);
- }
- break;
- default:
- assert(0);
- }
-}
-
-static void
-doPlankLabelMacrosSafely(op) Operator op;
-{
- PlankMap im0;
- PlankMap im1;
-
- switch (op->arity) {
- case -1:
- fprintf(outfile, "#define %s_%s_state\t0\n", prefix, op->name);
- break;
- case 0:
- fprintf(outfile, "#define %s_%s_state", prefix, op->name);
- fprintf(outfile, "\t%d\n", op->table->transition[0]->newNum+1);
- break;
- case 1:
- fprintf(outfile, "#define %s_%s_state(l)", prefix, op->name);
- im0 = op->table->dimen[0]->pmap;
- if (im0) {
- if (im0->exceptions) {
- List es = im0->exceptions;
- assert(0);
- fprintf(outfile, "\t\tswitch (l) {\n");
- for (; es; es = es->next) {
- Exception e = (Exception) es->x;
- fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im0->offset : 0);
- }
- fprintf(outfile, "\t\t}\n");
- }
- if (speedflag) {
- fprintf(outfile, "\t( %s[l].%s + %d )\n",
- im0->values->plank->name, im0->values->fieldname,
- im0->offset);
- } else {
- fprintf(outfile, "\t( (%s_TEMP = %s[l].%s) ? %s_TEMP + %d : 0 )\n",
- prefix,
- im0->values->plank->name, im0->values->fieldname,
- prefix,
- im0->offset);
- }
- } else {
- Item_Set *ts = transLval(op->table, 1, 0);
- if (*ts) {
- fprintf(outfile, "\t%d\n", (*ts)->newNum+1);
- } else {
- fprintf(outfile, "\t%d\n", 0);
- }
- }
- break;
- case 2:
- fprintf(outfile, "#define %s_%s_state(l,r)", prefix, op->name);
-
- im0 = op->table->dimen[0]->pmap;
- im1 = op->table->dimen[1]->pmap;
- if (!im0 && !im1) {
- Item_Set *ts = transLval(op->table, 1, 1);
- assert(0);
- if (*ts) {
- fprintf(outfile, "\t\treturn %d;\n", (*ts)->newNum+1);
- } else {
- fprintf(outfile, "\t\treturn %d;\n", 0);
- }
- } else if (!im0) {
- assert(0);
- if (im1->exceptions) {
- List es = im1->exceptions;
- fprintf(outfile, "\t\tswitch (r) {\n");
- for (; es; es = es->next) {
- Exception e = (Exception) es->x;
- fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im1->offset : 0);
- }
- fprintf(outfile, "\t\t}\n");
- }
- fprintf(outfile, "\t\tstate = %s[r].%s; offset = %d;\n",
- im1->values->plank->name, im1->values->fieldname, im1->offset);
- fprintf(outfile, "\t\tbreak;\n");
- } else if (!im1) {
- assert(0);
- if (im0->exceptions) {
- List es = im0->exceptions;
- fprintf(outfile, "\t\tswitch (l) {\n");
- for (; es; es = es->next) {
- Exception e = (Exception) es->x;
- fprintf(outfile, "\t\tcase %d: return %d;\n", e->index, e->value ? e->value+im0->offset : 0);
- }
- fprintf(outfile, "\t\t}\n");
- }
- fprintf(outfile, "\t\tstate = %s[l].%s; offset = %d;\n",
- im0->values->plank->name, im0->values->fieldname, im0->offset);
- fprintf(outfile, "\t\tbreak;\n");
- } else {
- assert(im0->offset == 0);
- assert(im1->offset == 0);
- /*
- sprintf(buf, "l = %s[l].%s",
- im0->values->plank->name, im0->values->fieldname);
- exceptionSwitch(im0->exceptions, "l", "l =", "break;", 0, buf);
- sprintf(buf, "r = %s[r].%s",
- im1->values->plank->name, im1->values->fieldname);
- exceptionSwitch(im1->exceptions, "r", "r =", "break;", 0, buf);
-
- fprintf(outfile, "\t\tstate = %s_%s_transition[l][r]; offset = %d;\n",
- prefix,
- op->name,
- op->baseNum);
- fprintf(outfile, "\t\tbreak;\n");
- */
-
- if (speedflag) {
- fprintf(outfile, "\t( %s_%s_transition[%s[l].%s][%s[r].%s] + %d)\n",
- prefix,
- op->name,
- im0->values->plank->name, im0->values->fieldname,
- im1->values->plank->name, im1->values->fieldname,
- op->baseNum);
- } else {
- fprintf(outfile, "\t( (%s_TEMP = %s_%s_transition[%s[l].%s][%s[r].%s]) ? ",
- prefix,
- prefix,
- op->name,
- im0->values->plank->name, im0->values->fieldname,
- im1->values->plank->name, im1->values->fieldname);
- fprintf(outfile, "%s_TEMP + %d : 0 )\n",
- prefix,
- op->baseNum);
- }
- }
- break;
- default:
- assert(0);
- }
-}
-static void
-doPlankLabelSafely(op) Operator op;
-{
- fprintf(outfile, "\tcase %d:\n", op->num);
- switch (op->arity) {
- case -1:
- fprintf(outfile, "\t\treturn 0;\n");
- break;
- case 0:
- fprintf(outfile, "\t\treturn %s_%s_state;\n", prefix, op->name);
- break;
- case 1:
- fprintf(outfile, "\t\treturn %s_%s_state(l);\n", prefix, op->name);
- break;
- case 2:
- fprintf(outfile, "\t\treturn %s_%s_state(l,r);\n", prefix, op->name);
- break;
- default:
- assert(0);
- }
-}
-
-static void
-makePlankState()
-{
- fprintf(outfile, "\n");
- fprintf(outfile, "int %s_TEMP;\n", prefix);
- foreachList((ListFn) doPlankLabelMacrosSafely, operators);
- fprintf(outfile, "\n");
-
- fprintf(outfile, "#ifdef __STDC__\n");
- switch (max_arity) {
- case -1:
- fprintf(stderr, "ERROR: no terminals in grammar.\n");
- exit(1);
- case 0:
- fprintf(outfile, "int %s_state(int op) {\n", prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "int %s_state(op) int op; {\n", prefix);
- break;
- case 1:
- fprintf(outfile, "int %s_state(int op, int l) {\n", prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "int %s_state(op, l) int op; int l; {\n", prefix);
- break;
- case 2:
- fprintf(outfile, "int %s_state(int op, int l, int r) {\n", prefix);
- fprintf(outfile, "#else\n");
- fprintf(outfile, "int %s_state(op, l, r) int op; int l; int r; {\n", prefix);
- break;
- default:
- assert(0);
- }
- fprintf(outfile, "#endif\n");
-
- fprintf(outfile, "\tregister int %s_TEMP;\n", prefix);
-
- fprintf(outfile, "#ifndef NDEBUG\n");
-
- fprintf(outfile, "\tswitch (op) {\n");
- opsOfArity(2);
- if (max_arity >= 2) {
- fprintf(outfile,
- "\t\t%s_assert(r >= 0 && r < %d, %s_PANIC(\"Bad state %%d passed to %s_state\\n\", r));\n",
- prefix, globalMap->count, prefix, prefix);
- fprintf(outfile, "\t\t/*FALLTHROUGH*/\n");
- }
- opsOfArity(1);
- if (max_arity > 1) {
- fprintf(outfile,
- "\t\t%s_assert(l >= 0 && l < %d, %s_PANIC(\"Bad state %%d passed to %s_state\\n\", l));\n",
- prefix, globalMap->count, prefix, prefix);
- fprintf(outfile, "\t\t/*FALLTHROUGH*/\n");
- }
- opsOfArity(0);
- fprintf(outfile, "\t\tbreak;\n");
- fprintf(outfile, "\t}\n");
- fprintf(outfile, "#endif\n");
-
- fprintf(outfile, "\tswitch (op) {\n");
- fprintf(outfile,"\tdefault: %s_PANIC(\"Unknown op %%d in %s_state\\n\", op); abort(); return 0;\n",
- prefix, prefix);
- foreachList((ListFn) doPlankLabelSafely, operators);
- fprintf(outfile, "\t}\n");
-
- fprintf(outfile, "}\n");
-}
-
-void
-makePlanks()
-{
- List planks;
- renumber();
- makePmaps();
- planks = assemblePlanks();
- purgePlanks(planks);
- inToEx();
- makePlankRule();
- makePlankState();
-}
+++ /dev/null
-char rcsid_queue[] = "$Id$";
-
-#include "b.h"
-#include <stdio.h>
-
-Queue globalQ;
-
-Queue
-newQ()
-{
- Queue q;
-
- q = (Queue) zalloc(sizeof(struct queue));
- assert(q);
- q->head = 0;
- q->tail = 0;
-
- return q;
-}
-
-void
-addQ(q, ts) Queue q; Item_Set ts;
-{
- List qe;
-
- assert(q);
- assert(ts);
-
- qe = newList(ts, 0);
- if (q->head) {
- assert(q->tail);
- q->tail->next = qe;
- q->tail = qe;
- } else {
- q->head = q->tail = qe;
- }
-}
-
-Item_Set
-popQ(q) Queue q;
-{
- List qe;
- Item_Set ts;
-
- assert(q);
-
- if (q->head) {
- qe = q->head;
- q->head = q->head->next;
- ts = (Item_Set) qe->x;
- zfree(qe);
- return ts;
- } else {
- return 0;
- }
-}
-
-void
-dumpQ(q) Queue q;
-{
- printf("Begin Queue\n");
- foreachList((ListFn)dumpItem_Set, q->head);
- printf("End Queue\n");
-}
+++ /dev/null
-char rcsid_rule[] = "$Id$";
-
-#include "b.h"
-#include <stdio.h>
-
-RuleNum max_rule;
-int max_erule_num;
-
-struct rule stub_rule;
-
-List rules;
-
-Rule
-newRule(delta, erulenum, lhs, pat) DeltaPtr delta; ERuleNum erulenum; NonTerminal lhs; Pattern pat;
-{
- Rule p;
-
- p = (Rule) zalloc(sizeof(struct rule));
- assert(p);
- ASSIGNCOST(p->delta, delta);
- p->erulenum = erulenum;
- if (erulenum > max_erule_num) {
- max_erule_num = erulenum;
- }
- p->num = max_rule++;
- p->lhs = lhs;
- p->pat = pat;
-
- rules = newList(p, rules);
-
- return p;
-}
-
-void
-dumpRule(p) Rule p;
-{
- dumpNonTerminal(p->lhs);
- printf(" : ");
- dumpPattern(p->pat);
- printf(" ");
- dumpCost(p->delta);
- printf("\n");
-}
-
-void
-dumpRuleList(l) List l;
-{
- foreachList((ListFn)dumpRule, l);
-}
+++ /dev/null
-%{
-#include <stdio.h>
-
-typedef struct node *NODEPTR_TYPE;
-
-struct node {
- int op, state_label;
- NODEPTR_TYPE left, right;
-};
-
-#define OP_LABEL(p) ((p)->op)
-#define STATE_LABEL(p) ((p)->state_label)
-#define LEFT_CHILD(p) ((p)->left)
-#define RIGHT_CHILD(p) ((p)->right)
-#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);
-
-%%
-
-#define Assign 1
-#define Constant 2
-#define Fetch 3
-#define Four 4
-#define Mul 5
-#define Plus 6
-
-#ifdef __STDC__
-#define ARGS(x) x
-#else
-#define ARGS(x) ()
-#endif
-
-NODEPTR_TYPE buildtree ARGS((int, NODEPTR_TYPE, NODEPTR_TYPE));
-void printcover ARGS((NODEPTR_TYPE, int, int));
-void printtree ARGS((NODEPTR_TYPE));
-int treecost ARGS((NODEPTR_TYPE, int, int));
-void printMatches ARGS((NODEPTR_TYPE));
-int main ARGS((void));
-
-NODEPTR_TYPE buildtree(op, left, right) int op; NODEPTR_TYPE left; NODEPTR_TYPE right; {
- NODEPTR_TYPE p;
- extern void *malloc ARGS((unsigned));
-
- p = (NODEPTR_TYPE) malloc(sizeof *p);
- p->op = op;
- p->left = left;
- p->right = right;
- return p;
-}
-
-void printcover(p, goalnt, indent) NODEPTR_TYPE p; int goalnt; int indent; {
- int eruleno = burm_rule(STATE_LABEL(p), goalnt);
- short *nts = burm_nts[eruleno];
- NODEPTR_TYPE kids[10];
- int i;
-
- if (eruleno == 0) {
- printf("no cover\n");
- return;
- }
- for (i = 0; i < indent; i++)
- printf(".");
- printf("%s\n", burm_string[eruleno]);
- burm_kids(p, eruleno, kids);
- for (i = 0; nts[i]; i++)
- printcover(kids[i], nts[i], indent+1);
-}
-
-void printtree(p) NODEPTR_TYPE p; {
- int op = burm_op_label(p);
-
- printf("%s", burm_opname[op]);
- switch (burm_arity[op]) {
- case 0:
- break;
- case 1:
- printf("(");
- printtree(burm_child(p, 0));
- printf(")");
- break;
- case 2:
- printf("(");
- printtree(burm_child(p, 0));
- printf(", ");
- printtree(burm_child(p, 1));
- printf(")");
- break;
- }
-}
-
-int treecost(p, goalnt, costindex) NODEPTR_TYPE p; int goalnt; int costindex; {
- int eruleno = burm_rule(STATE_LABEL(p), goalnt);
- int cost = burm_cost[eruleno][costindex], i;
- short *nts = burm_nts[eruleno];
- NODEPTR_TYPE kids[10];
-
- burm_kids(p, eruleno, kids);
- for (i = 0; nts[i]; i++)
- cost += treecost(kids[i], nts[i], costindex);
- return cost;
-}
-
-void printMatches(p) NODEPTR_TYPE p; {
- int nt;
- int eruleno;
-
- printf("Node 0x%lx= ", (unsigned long)p);
- printtree(p);
- printf(" matched rules:\n");
- for (nt = 1; burm_ntname[nt] != (char*)NULL; nt++)
- if ((eruleno = burm_rule(STATE_LABEL(p), nt)) != 0)
- printf("\t%s\n", burm_string[eruleno]);
-}
-
-main() {
- NODEPTR_TYPE p;
-
- p = buildtree(Assign,
- buildtree(Constant, 0, 0),
- buildtree(Fetch,
- buildtree(Plus,
- buildtree(Constant, 0, 0),
- buildtree(Mul,
- buildtree(Four, 0, 0),
- buildtree(Fetch, buildtree(Constant, 0, 0), 0)
- )
- ),
- 0
- )
- );
- printtree(p);
- printf("\n\n");
- burm_label(p);
- printcover(p, 1, 0);
- printf("\nCover cost == %d\n\n", treecost(p, 1, 0));
- printMatches(p);
- return 0;
-}
-
+++ /dev/null
-char rcsid_string[] = "$Id$";
-
-#include <stdio.h>
-#include <string.h>
-#include "b.h"
-#include "fe.h"
-
-static StrTableElement newStrTableElement ARGS((void));
-
-StrTable
-newStrTable()
-{
- return (StrTable) zalloc(sizeof(struct strTable));
-}
-
-static StrTableElement
-newStrTableElement()
-{
- return (StrTableElement) zalloc(sizeof(struct strTableElement));
-}
-
-void
-dumpStrTable(t) StrTable t;
-{
- List e;
- IntList r;
-
- printf("Begin StrTable\n");
- for (e = t->elems; e; e = e->next) {
- StrTableElement el = (StrTableElement) e->x;
- printf("%s: ", el->str);
- for (r = el->erulenos; r; r = r->next) {
- int i = r->x;
- printf("(%d)", i);
- }
- printf("\n");
- }
- printf("End StrTable\n");
-}
-
-StrTableElement
-addString(t, s, eruleno, new) StrTable t; char *s; int eruleno; int *new;
-{
- List l;
- StrTableElement ste;
-
- assert(t);
- for (l = t->elems; l; l = l->next) {
- StrTableElement e = (StrTableElement) l->x;
-
- assert(e);
- if (!strcmp(s, e->str)) {
- e->erulenos = newIntList(eruleno, e->erulenos);
- *new = 0;
- return e;
- }
- }
- ste = newStrTableElement();
- ste->erulenos = newIntList(eruleno, 0);
- ste->str = (char *) zalloc(strlen(s) + 1);
- strcpy(ste->str, s);
- t->elems = newList(ste, t->elems);
- *new = 1;
- return ste;
-}
+++ /dev/null
-char rcsid_symtab[] = "$Id$";
-
-#include <stdio.h>
-#include <string.h>
-#include "b.h"
-#include "fe.h"
-
-static List symtab;
-
-Symbol
-newSymbol(name) char *name;
-{
- Symbol s;
-
- s = (Symbol) zalloc(sizeof(struct symbol));
- assert(s);
- s->name = name;
- return s;
-}
-
-Symbol
-enter(name, new) char *name; int *new;
-{
- List l;
- Symbol s;
-
- *new = 0;
- for (l = symtab; l; l = l->next) {
- s = (Symbol) l->x;
- if (!strcmp(name, s->name)) {
- return s;
- }
- }
- *new = 1;
- s = newSymbol(name);
- symtab = newList(s, symtab);
- return s;
-}
+++ /dev/null
-char rcsid_table[] = "$Id$";
-
-#include "b.h"
-#include <string.h>
-#include <stdio.h>
-
-static void growIndex_Map ARGS((Index_Map *));
-static Relevant newRelevant ARGS((void));
-static Dimension newDimension ARGS((Operator, int));
-static void GT_1 ARGS((Table));
-static void GT_2_0 ARGS((Table));
-static void GT_2_1 ARGS((Table));
-static void growTransition ARGS((Table, int));
-static Item_Set restrict ARGS((Dimension, Item_Set));
-static void addHP_1 ARGS((Table, Item_Set));
-static void addHP_2_0 ARGS((Table, Item_Set));
-static void addHP_2_1 ARGS((Table, Item_Set));
-static void addHyperPlane ARGS((Table, int, Item_Set));
-
-static void
-growIndex_Map(r) Index_Map *r;
-{
- Index_Map new;
-
- new.max_size = r->max_size + STATES_INCR;
- new.class = (Item_Set*) zalloc(new.max_size * sizeof(Item_Set));
- assert(new.class);
- memcpy(new.class, r->class, r->max_size * sizeof(Item_Set));
- zfree(r->class);
- *r = new;
-}
-
-static Relevant
-newRelevant()
-{
- Relevant r = (Relevant) zalloc(max_nonterminal * sizeof(*r));
- return r;
-}
-
-void
-addRelevant(r, nt) Relevant r; NonTerminalNum nt;
-{
- int i;
-
- for (i = 0; r[i]; i++) {
- if (r[i] == nt) {
- break;
- }
- }
- if (!r[i]) {
- r[i] = nt;
- }
-}
-
-static Dimension
-newDimension(op, index) Operator op; ArityNum index;
-{
- Dimension d;
- List pl;
- Relevant r;
-
- assert(op);
- assert(index >= 0 && index < op->arity);
- d = (Dimension) zalloc(sizeof(struct dimension));
- assert(d);
-
- r = d->relevant = newRelevant();
- for (pl = rules; pl; pl = pl->next) {
- Rule pr = (Rule) pl->x;
- if (pr->pat->op == op) {
- addRelevant(r, pr->pat->children[index]->num);
- }
- }
-
- d->index_map.max_size = STATES_INCR;
- d->index_map.class = (Item_Set*)
- zalloc(d->index_map.max_size * sizeof(Item_Set));
- d->map = newMapping(DIM_MAP_SIZE);
- d->max_size = TABLE_INCR;
-
- return d;
-}
-
-Table
-newTable(op) Operator op;
-{
- Table t;
- int i, size;
-
- assert(op);
-
- t = (Table) zalloc(sizeof(struct table));
- assert(t);
-
- t->op = op;
-
- for (i = 0; i < op->arity; i++) {
- t->dimen[i] = newDimension(op, i);
- }
-
- size = 1;
- for (i = 0; i < op->arity; i++) {
- size *= t->dimen[i]->max_size;
- }
- t->transition = (Item_Set*) zalloc(size * sizeof(Item_Set));
- t->relevant = newRelevant();
- assert(t->transition);
-
- return t;
-}
-
-static void
-GT_1(t) Table t;
-{
- Item_Set *ts;
- ItemSetNum oldsize = t->dimen[0]->max_size;
- ItemSetNum newsize = t->dimen[0]->max_size + TABLE_INCR;
-
- t->dimen[0]->max_size = newsize;
-
- ts = (Item_Set*) zalloc(newsize * sizeof(Item_Set));
- assert(ts);
- memcpy(ts, t->transition, oldsize * sizeof(Item_Set));
- zfree(t->transition);
- t->transition = ts;
-}
-
-static void
-GT_2_0(t) Table t;
-{
- Item_Set *ts;
- ItemSetNum oldsize = t->dimen[0]->max_size;
- ItemSetNum newsize = t->dimen[0]->max_size + TABLE_INCR;
- int size;
-
- t->dimen[0]->max_size = newsize;
-
- size = newsize * t->dimen[1]->max_size;
-
- ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
- assert(ts);
- memcpy(ts, t->transition, oldsize*t->dimen[1]->max_size * sizeof(Item_Set));
- zfree(t->transition);
- t->transition = ts;
-}
-
-static void
-GT_2_1(t) Table t;
-{
- Item_Set *ts;
- ItemSetNum oldsize = t->dimen[1]->max_size;
- ItemSetNum newsize = t->dimen[1]->max_size + TABLE_INCR;
- int size;
- Item_Set *from;
- Item_Set *to;
- int i1, i2;
-
- t->dimen[1]->max_size = newsize;
-
- size = newsize * t->dimen[0]->max_size;
-
- ts = (Item_Set*) zalloc(size * sizeof(Item_Set));
- assert(ts);
-
- from = t->transition;
- to = ts;
- for (i1 = 0; i1 < t->dimen[0]->max_size; i1++) {
- for (i2 = 0; i2 < oldsize; i2++) {
- to[i2] = from[i2];
- }
- to += newsize;
- from += oldsize;
- }
- zfree(t->transition);
- t->transition = ts;
-}
-
-static void
-growTransition(t, dim) Table t; ArityNum dim;
-{
-
- assert(t);
- assert(t->op);
- assert(dim < t->op->arity);
-
- switch (t->op->arity) {
- default:
- assert(0);
- break;
- case 1:
- GT_1(t);
- return;
- case 2:
- switch (dim) {
- default:
- assert(0);
- break;
- case 0:
- GT_2_0(t);
- return;
- case 1:
- GT_2_1(t);
- return;
- }
- }
-}
-
-static Item_Set
-restrict(d, ts) Dimension d; Item_Set ts;
-{
- DeltaCost base;
- Item_Set r;
- int found;
- register Relevant r_ptr = d->relevant;
- register Item *ts_current = ts->closed;
- register Item *r_current;
- register int i;
- register int nt;
-
- ZEROCOST(base);
- found = 0;
- r = newItem_Set(d->relevant);
- r_current = r->virgin;
- for (i = 0; (nt = r_ptr[i]) != 0; i++) {
- if (ts_current[nt].rule) {
- r_current[nt].rule = &stub_rule;
- if (!found) {
- found = 1;
- ASSIGNCOST(base, ts_current[nt].delta);
- } else {
- if (LESSCOST(ts_current[nt].delta, base)) {
- ASSIGNCOST(base, ts_current[nt].delta);
- }
- }
- }
- }
-
- /* zero align */
- for (i = 0; (nt = r_ptr[i]) != 0; i++) {
- if (r_current[nt].rule) {
- ASSIGNCOST(r_current[nt].delta, ts_current[nt].delta);
- MINUSCOST(r_current[nt].delta, base);
- }
- }
- assert(!r->closed);
- r->representative = ts;
- return r;
-}
-
-static void
-addHP_1(t, ts) Table t; Item_Set ts;
-{
- List pl;
- Item_Set e;
- Item_Set tmp;
- int new;
-
- e = newItem_Set(t->relevant);
- assert(e);
- e->kids[0] = ts->representative;
- for (pl = t->rules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- if (t->op == p->pat->op && ts->virgin[p->pat->children[0]->num].rule) {
- DeltaCost dc;
- ASSIGNCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
- ADDCOST(dc, p->delta);
- if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
- e->virgin[p->lhs->num].rule = p;
- ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
- e->op = t->op;
- }
- }
- }
- trim(e);
- zero(e);
- tmp = encode(globalMap, e, &new);
- assert(ts->num < t->dimen[0]->map->max_size);
- t->transition[ts->num] = tmp;
- if (new) {
- closure(e);
- addQ(globalQ, tmp);
- } else {
- freeItem_Set(e);
- }
-}
-
-static void
-addHP_2_0(t, ts) Table t; Item_Set ts;
-{
- List pl;
- register Item_Set e;
- Item_Set tmp;
- int new;
- int i2;
-
- assert(t->dimen[1]->map->count <= t->dimen[1]->map->max_size);
- for (i2 = 0; i2 < t->dimen[1]->map->count; i2++) {
- e = newItem_Set(t->relevant);
- assert(e);
- e->kids[0] = ts->representative;
- e->kids[1] = t->dimen[1]->map->set[i2]->representative;
- for (pl = t->rules; pl; pl = pl->next) {
- register Rule p = (Rule) pl->x;
-
- if (t->op == p->pat->op
- && ts->virgin[p->pat->children[0]->num].rule
- && t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].rule){
- DeltaCost dc;
- ASSIGNCOST(dc, p->delta);
- ADDCOST(dc, ts->virgin[p->pat->children[0]->num].delta);
- ADDCOST(dc, t->dimen[1]->map->set[i2]->virgin[p->pat->children[1]->num].delta);
-
- if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
- e->virgin[p->lhs->num].rule = p;
- ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
- e->op = t->op;
- }
- }
- }
- trim(e);
- zero(e);
- tmp = encode(globalMap, e, &new);
- assert(ts->num < t->dimen[0]->map->max_size);
- t->transition[ts->num * t->dimen[1]->max_size + i2] = tmp;
- if (new) {
- closure(e);
- addQ(globalQ, tmp);
- } else {
- freeItem_Set(e);
- }
- }
-}
-
-static void
-addHP_2_1(t, ts) Table t; Item_Set ts;
-{
- List pl;
- register Item_Set e;
- Item_Set tmp;
- int new;
- int i1;
-
- assert(t->dimen[0]->map->count <= t->dimen[0]->map->max_size);
- for (i1 = 0; i1 < t->dimen[0]->map->count; i1++) {
- e = newItem_Set(t->relevant);
- assert(e);
- e->kids[0] = t->dimen[0]->map->set[i1]->representative;
- e->kids[1] = ts->representative;
- for (pl = t->rules; pl; pl = pl->next) {
- register Rule p = (Rule) pl->x;
-
- if (t->op == p->pat->op
- && ts->virgin[p->pat->children[1]->num].rule
- && t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].rule){
- DeltaCost dc;
- ASSIGNCOST(dc, p->delta );
- ADDCOST(dc, ts->virgin[p->pat->children[1]->num].delta);
- ADDCOST(dc, t->dimen[0]->map->set[i1]->virgin[p->pat->children[0]->num].delta);
- if (!e->virgin[p->lhs->num].rule || LESSCOST(dc, e->virgin[p->lhs->num].delta)) {
- e->virgin[p->lhs->num].rule = p;
- ASSIGNCOST(e->virgin[p->lhs->num].delta, dc);
- e->op = t->op;
- }
- }
- }
- trim(e);
- zero(e);
- tmp = encode(globalMap, e, &new);
- assert(ts->num < t->dimen[1]->map->max_size);
- t->transition[i1 * t->dimen[1]->max_size + ts->num] = tmp;
- if (new) {
- closure(e);
- addQ(globalQ, tmp);
- } else {
- freeItem_Set(e);
- }
- }
-}
-
-static void
-addHyperPlane(t, i, ts) Table t; ArityNum i; Item_Set ts;
-{
- switch (t->op->arity) {
- default:
- assert(0);
- break;
- case 1:
- addHP_1(t, ts);
- return;
- case 2:
- switch (i) {
- default:
- assert(0);
- break;
- case 0:
- addHP_2_0(t, ts);
- return;
- case 1:
- addHP_2_1(t, ts);
- return;
- }
- }
-}
-
-void
-addToTable(t, ts) Table t; Item_Set ts;
-{
- ArityNum i;
-
- assert(t);
- assert(ts);
- assert(t->op);
-
- for (i = 0; i < t->op->arity; i++) {
- Item_Set r;
- Item_Set tmp;
- int new;
-
- r = restrict(t->dimen[i], ts);
- tmp = encode(t->dimen[i]->map, r, &new);
- if (t->dimen[i]->index_map.max_size <= ts->num) {
- growIndex_Map(&t->dimen[i]->index_map);
- }
- assert(ts->num < t->dimen[i]->index_map.max_size);
- t->dimen[i]->index_map.class[ts->num] = tmp;
- if (new) {
- if (t->dimen[i]->max_size <= r->num) {
- growTransition(t, i);
- }
- addHyperPlane(t, i, r);
- } else {
- freeItem_Set(r);
- }
- }
-}
-
-Item_Set *
-transLval(t, row, col) Table t; int row; int col;
-{
- switch (t->op->arity) {
- case 0:
- assert(row == 0);
- assert(col == 0);
- return t->transition;
- case 1:
- assert(col == 0);
- return t->transition + row;
- case 2:
- return t->transition + row * t->dimen[1]->max_size + col;
- default:
- assert(0);
- }
- return 0;
-}
-
-void
-dumpRelevant(r) Relevant r;
-{
- for (; *r; r++) {
- printf("%4d", *r);
- }
-}
-
-void
-dumpIndex_Map(r) Index_Map *r;
-{
- int i;
-
- printf("BEGIN Index_Map: MaxSize (%d)\n", r->max_size);
- for (i = 0; i < globalMap->count; i++) {
- printf("\t#%d: -> %d\n", i, r->class[i]->num);
- }
- printf("END Index_Map:\n");
-}
-
-void
-dumpDimension(d) Dimension d;
-{
- printf("BEGIN Dimension:\n");
- printf("Relevant: ");
- dumpRelevant(d->relevant);
- printf("\n");
- dumpIndex_Map(&d->index_map);
- dumpMapping(d->map);
- printf("MaxSize of dimension = %d\n", d->max_size);
- printf("END Dimension\n");
-}
-
-void
-dumpTable(t, full) Table t; int full;
-{
- int i;
-
- if (!t) {
- printf("NO Table yet.\n");
- return;
- }
- printf("BEGIN Table:\n");
- if (full) {
- dumpOperator(t->op, 0);
- }
- for (i = 0; i < t->op->arity; i++) {
- printf("BEGIN dimension(%d)\n", i);
- dumpDimension(t->dimen[i]);
- printf("END dimension(%d)\n", i);
- }
- dumpTransition(t);
- printf("END Table:\n");
-}
-
-void
-dumpTransition(t) Table t;
-{
- int i,j;
-
- switch (t->op->arity) {
- case 0:
- printf("{ %d }", t->transition[0]->num);
- break;
- case 1:
- printf("{");
- for (i = 0; i < t->dimen[0]->map->count; i++) {
- if (i > 0) {
- printf(",");
- }
- printf("%5d", t->transition[i]->num);
- }
- printf("}");
- break;
- case 2:
- printf("{");
- for (i = 0; i < t->dimen[0]->map->count; i++) {
- if (i > 0) {
- printf(",");
- }
- printf("\n");
- printf("{");
- for (j = 0; j < t->dimen[1]->map->count; j++) {
- Item_Set *ts = transLval(t, i, j);
- if (j > 0) {
- printf(",");
- }
- printf("%5d", (*ts)->num);
- }
- printf("}");
- }
- printf("\n}\n");
- break;
- default:
- assert(0);
- }
-}
+++ /dev/null
-char rcsid_trim[] = "$Id$";
-
-#include <stdio.h>
-#include "b.h"
-#include "fe.h"
-
-Relation *allpairs;
-
-int trimflag = 0;
-int debugTrim = 0;
-
-static void siblings ARGS((int, int));
-static void findAllNexts ARGS((void));
-static Relation *newAllPairs ARGS((void));
-
-static void
-siblings(i, j) int i; int j;
-{
- int k;
- List pl;
- DeltaCost Max;
- int foundmax;
-
- allpairs[i][j].sibComputed = 1;
-
- if (i == 1) {
- return; /* never trim start symbol */
- }
- if (i==j) {
- return;
- }
-
- ZEROCOST(Max);
- foundmax = 0;
-
- for (k = 1; k < max_nonterminal; k++) {
- DeltaCost tmp;
-
- if (k==i || k==j) {
- continue;
- }
- if (!allpairs[k][i].rule) {
- continue;
- }
- if (!allpairs[k][j].rule) {
- return;
- }
- ASSIGNCOST(tmp, allpairs[k][j].chain);
- MINUSCOST(tmp, allpairs[k][i].chain);
- if (foundmax) {
- if (LESSCOST(Max, tmp)) {
- ASSIGNCOST(Max, tmp);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, tmp);
- }
- }
-
- for (pl = rules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- Operator op = p->pat->op;
- List oprule;
- DeltaCost Min;
- int foundmin;
-
- if (!op) {
- continue;
- }
- switch (op->arity) {
- case 0:
- continue;
- case 1:
- if (!allpairs[p->pat->children[0]->num ][ i].rule) {
- continue;
- }
- foundmin = 0;
- for (oprule = op->table->rules; oprule; oprule = oprule->next) {
- Rule s = (Rule) oprule->x;
- DeltaPtr Cx;
- DeltaPtr Csj;
- DeltaPtr Cpi;
- DeltaCost tmp;
-
- if (!allpairs[p->lhs->num ][ s->lhs->num].rule
- || !allpairs[s->pat->children[0]->num ][ j].rule) {
- continue;
- }
- Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
- Csj= allpairs[s->pat->children[0]->num ][ j].chain;
- Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
- ASSIGNCOST(tmp, Cx);
- ADDCOST(tmp, s->delta);
- ADDCOST(tmp, Csj);
- MINUSCOST(tmp, Cpi);
- MINUSCOST(tmp, p->delta);
- if (foundmin) {
- if (LESSCOST(tmp, Min)) {
- ASSIGNCOST(Min, tmp);
- }
- } else {
- foundmin = 1;
- ASSIGNCOST(Min, tmp);
- }
- }
- if (!foundmin) {
- return;
- }
- if (foundmax) {
- if (LESSCOST(Max, Min)) {
- ASSIGNCOST(Max, Min);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, Min);
- }
- break;
- case 2:
- /* do first dimension */
- if (allpairs[p->pat->children[0]->num ][ i].rule) {
- foundmin = 0;
- for (oprule = op->table->rules; oprule; oprule = oprule->next) {
- Rule s = (Rule) oprule->x;
- DeltaPtr Cx;
- DeltaPtr Cb;
- DeltaPtr Csj;
- DeltaPtr Cpi;
- DeltaCost tmp;
-
- if (allpairs[p->lhs->num ][ s->lhs->num].rule
- && allpairs[s->pat->children[0]->num ][ j].rule
- && allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].rule) {
- Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
- Csj= allpairs[s->pat->children[0]->num ][ j].chain;
- Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
- Cb = allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].chain;
- ASSIGNCOST(tmp, Cx);
- ADDCOST(tmp, s->delta);
- ADDCOST(tmp, Csj);
- ADDCOST(tmp, Cb);
- MINUSCOST(tmp, Cpi);
- MINUSCOST(tmp, p->delta);
- if (foundmin) {
- if (LESSCOST(tmp, Min)) {
- ASSIGNCOST(Min, tmp);
- }
- } else {
- foundmin = 1;
- ASSIGNCOST(Min, tmp);
- }
- }
- }
- if (!foundmin) {
- return;
- }
- if (foundmax) {
- if (LESSCOST(Max, Min)) {
- ASSIGNCOST(Max, Min);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, Min);
- }
- }
- /* do second dimension */
- if (allpairs[p->pat->children[1]->num ][ i].rule) {
- foundmin = 0;
- for (oprule = op->table->rules; oprule; oprule = oprule->next) {
- Rule s = (Rule) oprule->x;
- DeltaPtr Cx;
- DeltaPtr Cb;
- DeltaPtr Csj;
- DeltaPtr Cpi;
- DeltaCost tmp;
-
- if (allpairs[p->lhs->num ][ s->lhs->num].rule
- && allpairs[s->pat->children[1]->num ][ j].rule
- && allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].rule) {
- Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
- Csj= allpairs[s->pat->children[1]->num ][ j].chain;
- Cpi= allpairs[p->pat->children[1]->num ][ i].chain;
- Cb = allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].chain;
- ASSIGNCOST(tmp, Cx);
- ADDCOST(tmp, s->delta);
- ADDCOST(tmp, Csj);
- ADDCOST(tmp, Cb);
- MINUSCOST(tmp, Cpi);
- MINUSCOST(tmp, p->delta);
- if (foundmin) {
- if (LESSCOST(tmp, Min)) {
- ASSIGNCOST(Min, tmp);
- }
- } else {
- foundmin = 1;
- ASSIGNCOST(Min, tmp);
- }
- }
- }
- if (!foundmin) {
- return;
- }
- if (foundmax) {
- if (LESSCOST(Max, Min)) {
- ASSIGNCOST(Max, Min);
- }
- } else {
- foundmax = 1;
- ASSIGNCOST(Max, Min);
- }
- }
- break;
- default:
- assert(0);
- }
- }
- allpairs[i ][ j].sibFlag = foundmax;
- ASSIGNCOST(allpairs[i ][ j].sibling, Max);
-}
-
-static void
-findAllNexts()
-{
- int i,j;
- int last;
-
- for (i = 1; i < max_nonterminal; i++) {
- last = 0;
- for (j = 1; j < max_nonterminal; j++) {
- if (allpairs[i ][j].rule) {
- allpairs[i ][ last].nextchain = j;
- last = j;
- }
- }
- }
- /*
- for (i = 1; i < max_nonterminal; i++) {
- last = 0;
- for (j = 1; j < max_nonterminal; j++) {
- if (allpairs[i ][j].sibFlag) {
- allpairs[i ][ last].nextsibling = j;
- last = j;
- }
- }
- }
- */
-}
-
-static Relation *
-newAllPairs()
-{
- int i;
- Relation *rv;
-
- rv = (Relation*) zalloc(max_nonterminal * sizeof(Relation));
- for (i = 0; i < max_nonterminal; i++) {
- rv[i] = (Relation) zalloc(max_nonterminal * sizeof(struct relation));
- }
- return rv;
-}
-
-void
-findAllPairs()
-{
- List pl;
- int changes;
- int j;
-
- allpairs = newAllPairs();
- for (pl = chainrules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- NonTerminalNum rhs = p->pat->children[0]->num;
- NonTerminalNum lhs = p->lhs->num;
- Relation r = &allpairs[lhs ][ rhs];
-
- if (LESSCOST(p->delta, r->chain)) {
- ASSIGNCOST(r->chain, p->delta);
- r->rule = p;
- }
- }
- for (j = 1; j < max_nonterminal; j++) {
- Relation r = &allpairs[j ][ j];
- ZEROCOST(r->chain);
- r->rule = &stub_rule;
- }
- changes = 1;
- while (changes) {
- changes = 0;
- for (pl = chainrules; pl; pl = pl->next) {
- Rule p = (Rule) pl->x;
- NonTerminalNum rhs = p->pat->children[0]->num;
- NonTerminalNum lhs = p->lhs->num;
- int i;
-
- for (i = 1; i < max_nonterminal; i++) {
- Relation r = &allpairs[rhs ][ i];
- Relation s = &allpairs[lhs ][ i];
- DeltaCost dc;
- if (!r->rule) {
- continue;
- }
- ASSIGNCOST(dc, p->delta);
- ADDCOST(dc, r->chain);
- if (!s->rule || LESSCOST(dc, s->chain)) {
- s->rule = p;
- ASSIGNCOST(s->chain, dc);
- changes = 1;
- }
- }
- }
- }
- findAllNexts();
-}
-
-void
-trim(t) Item_Set t;
-{
- int m,n;
- static short *vec = 0;
- int last;
-
- assert(!t->closed);
- debug(debugTrim, printf("Begin Trim\n"));
- debug(debugTrim, dumpItem_Set(t));
-
- last = 0;
- if (!vec) {
- vec = (short*) zalloc(max_nonterminal * sizeof(*vec));
- }
- for (m = 1; m < max_nonterminal; m++) {
- if (t->virgin[m].rule) {
- vec[last++] = m;
- }
- }
- for (m = 0; m < last; m++) {
- DeltaCost tmp;
- int j;
- int i;
-
- i = vec[m];
-
- for (j = allpairs[i ][ 0].nextchain; j; j = allpairs[i ][ j].nextchain) {
-
- if (i == j) {
- continue;
- }
- if (!t->virgin[j].rule) {
- continue;
- }
- ASSIGNCOST(tmp, t->virgin[j].delta);
- ADDCOST(tmp, allpairs[i ][ j].chain);
- if (!LESSCOST(t->virgin[i].delta, tmp)) {
- t->virgin[i].rule = 0;
- ZEROCOST(t->virgin[i].delta);
- debug(debugTrim, printf("Trimmed Chain (%d,%d)\n", i,j));
- goto outer;
- }
-
- }
- if (!trimflag) {
- continue;
- }
- for (n = 0; n < last; n++) {
- j = vec[n];
- if (i == j) {
- continue;
- }
-
- if (!t->virgin[j].rule) {
- continue;
- }
-
- if (!allpairs[i][j].sibComputed) {
- siblings(i,j);
- }
- if (!allpairs[i][j].sibFlag) {
- continue;
- }
- ASSIGNCOST(tmp, t->virgin[j].delta);
- ADDCOST(tmp, allpairs[i ][ j].sibling);
- if (!LESSCOST(t->virgin[i].delta, tmp)) {
- t->virgin[i].rule = 0;
- ZEROCOST(t->virgin[i].delta);
- goto outer;
- }
- }
-
- outer: ;
- }
-
- debug(debugTrim, dumpItem_Set(t));
- debug(debugTrim, printf("End Trim\n"));
-}
-
-void
-dumpRelation(r) Relation r;
-{
- printf("{ %d %ld %d %ld }", r->rule->erulenum, (long) r->chain, r->sibFlag, (long) r->sibling);
-}
-
-void
-dumpAllPairs()
-{
- int i,j;
-
- printf("Dumping AllPairs\n");
- for (i = 1; i < max_nonterminal; i++) {
- for (j = 1; j < max_nonterminal; j++) {
- dumpRelation(&allpairs[i ][j]);
- }
- printf("\n");
- }
-}
+++ /dev/null
-char rcsid_zalloc[] = "$Id$";
-
-#include <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-#include "b.h"
-
-int
-fatal(const char *name, int line)
-{
- fprintf(stderr, "assertion failed: file %s, line %d\n", name, line);
- exit(1);
- return 0;
-}
-
-void *
-zalloc(size) unsigned int size;
-{
- void *t = (void *) malloc(size);
- if (!t) {
- fprintf(stderr, "Malloc failed---PROGRAM ABORTED\n");
- exit(1);
- }
- memset(t, 0, size);
- return t;
-}
-
-void
-zfree(p) void *p;
-{
- free(p);
-}
##===----------------------------------------------------------------------===##
LEVEL = ..
-DIRS = Burg TableGen fpcmp PerfectShuffle
+DIRS = TableGen fpcmp PerfectShuffle
EXTRA_DIST := cgiplotNLT.pl check-each-file codegen-diff countloc.sh cvsupdate \
DSAclean.py DSAextract.py emacs findsym.pl GenLibDeps.pl \
projects / oota-llvm.git / commitdiff