Return to twig0.tex CVS log

Up to [Research Unix] / researchv10no / cmd / twig / doc / manual

Annotation of researchv10no/cmd/twig/doc/manual/twig0.tex, revision 1.1

1.1     ! root        1: \documentstyle[titlepage,fullpage,12pt,clbiba]{article}
        !             2: \begin{document}
        !             3: \newcommand{\twigcomp}{{\tt twig}}
        !             4: \newcommand{\Twigcomp}{{\tt Twig}}
        !             5: \newcommand{\twiglang}{{\it twig}}
        !             6: \newcommand{\Twiglang}{{\it Twig}}
        !             7: \title{Twig Reference Manual}
        !             8: 
        !             9: \date{
        !            10: \begin{minipage}{.8\textwidth}
        !            11: \normalsize
        !            12: \noindent
        !            13: \Twiglang{} is a language for manipulating trees.  A \twiglang{}
        !            14: program consists of a set
        !            15: of pattern-action rules together with associated declarations.  Patterns
        !            16: describe trees to be matched.  Actions calculate costs, perform tree
        !            17: manipulations and other functions such as emitting code.  A \twiglang{} program is
        !            18: translated by the \twigcomp{} compiler into subroutines and tables in a host
        !            19: language.  In the current implementation, the host language is C.\\[6pt]
        !            20: A \twiglang{} program manipulates trees by first finding a minimum cost covering of
        !            21: the input tree.  The actions of the rules whose pattern parts composes the
        !            22: covering is then executed. The minimum cost covering is determined using
        !            23: dynamic programming.  This technique naturally resolves many ambiguities that
        !            24: may be in the specifications.\\[6pt]
        !            25: The prime purpose of \twiglang{} is to create tree manipulation programs.
        !            26: One interesting application of tree manipulation is code generation and
        !            27: \twiglang{} has been used to implement a code generator for the 
        !            28: pcc2 compiler on the VAX.
        !            29: \end{minipage}}
        !            30: 
        !            31: \author{Steven W.K. Tjiang}
        !            32: 
        !            33: \maketitle
        !            34: \tableofcontents\newpage
        !            35: \section{Introduction}
        !            36: 
        !            37: \Twiglang{} is a language for writing tree manipulation programs.
        !            38: A \twiglang{} program does this by using a matcher to find a minimal
        !            39: cost covering of a tree.
        !            40: The covering is composed of
        !            41: user supplied templates.
        !            42: Trees are manipulated by
        !            43: executing the actions associated with the templates of their coverings.
        !            44: These actions may rewrite the tree, update other data structures, or
        !            45: generate output.
        !            46: 
        !            47: Figure~\ref{overview} gives an overview of the \twiglang{} system.
        !            48: The round boxes in the figure indicates files and the sharp cornered boxes
        !            49: are processing programs.
        !            50: The user writes the \twiglang{} specification file.
        !            51: This file is then compiled by the \twigcomp{} compiler into
        !            52: host language files.
        !            53: In the current version of \twiglang{}, the host language is C.
        !            54: The host language files are then compiled and linked with
        !            55: other user supplied files.
        !            56: The resulting program represented by the large box at the bottom
        !            57: of figure~\ref{overview} is the tree manipulation program.
        !            58: \begin{figure}[hp]
        !            59: \input{pic}
        !            60: \caption{The {\bf Twig } system}
        !            61: \label{overview}
        !            62: \end{figure}
        !            63: The details of this box will be discussed later.
        !            64: 
        !            65: \section{Motivation}
        !            66: 
        !            67: Although \Twiglang{} is a language for manipulating trees
        !            68: it was originally motivated by
        !            69: pattern directed code generation.  In many compilers, the typical
        !            70: structure is a {\sl front end} and a {\sl back end}.  The front end reads
        !            71: the input source program, checks its syntax and contextual conditions,
        !            72: and builds an intermediate representation of the program.
        !            73: The language used to do this representation is often called the
        !            74: {\it intermediate representation} and will be abbreviated as IR.
        !            75: The back end
        !            76: takes the IR and translates it into the target machine code.
        !            77: 
        !            78: That isn't the whole story but it's close.  Both ends may be 
        !            79: sets of programs rather than one
        !            80: program.  There may also be a
        !            81: {\it middle} that performs transformations on the
        !            82: IR.  The intention of these
        !            83: transformations is to improve the target code that comes out of the compiler.
        !            84: For this discussion, we can ignore the middle.
        !            85: 
        !            86: IRs can vary greatly from compiler to compiler.
        !            87: However the IRs are implemented, they are encodings of graphs.
        !            88: Usually three types of graphs are evident\cite{dragon}.
        !            89: There is a flowgraph whose nodes are {\sl basic blocks} and
        !            90: the edges corresponds to transfer of control between the basic blocks.
        !            91: Basic blocks are not featureless.  They are graphs themselves.
        !            92: Some compilers will represent them as a forest of
        !            93: {\it directed acyclic graphs} or DAGs.
        !            94: The nodes are data values and operations.
        !            95: Since operations yields values, one can think of nodes as
        !            96: corresponding to values.  An edge exists from node $a$ to
        !            97: node $b$ if and only if the value corresponding to $a$ depends on the
        !            98: value corresponding to $b$.  Other compilers will use trees instead of DAGs.
        !            99: Trees are not
        !           100: as general as DAGs and these compilers overcome that by using some
        !           101: type of labelling or copying.
        !           102: 
        !           103: Writing a front end usually
        !           104: involves writing a recognizer
        !           105: for the source language, designing a symbol table,
        !           106: and determining an error recovery strategy.  What has made this process easy
        !           107: are parser generators like YACC\cite{yacc}.
        !           108: They separate out the task of recognizing the
        !           109: source language from the other details.  This makes the task
        !           110: intellectually more manageable.
        !           111: The compiler implementor now specifies the source language via grammar
        !           112: productions.  Symbol table manipulations,
        !           113: and IR construction rules are attached to productions and activated
        !           114: when a source language construct is recognized.
        !           115: The front end is then {\it automatically} generated by processing the
        !           116: specification with a parser generator.
        !           117: The result is
        !           118: a high quality front end whose performance is close to that of a
        !           119: hand-crafted front end.
        !           120: 
        !           121: Providing the same type of facilities for automatically building back
        !           122: ends has been much more difficult.  Extending current front end
        !           123: parsers to do back ends
        !           124: has been workable but not entirely successful.  The basic idea is that
        !           125: the back end implementor writes a {\it machine grammar}
        !           126: for the IR and code generation
        !           127: occurs as actions that are executed when patterns are found
        !           128: in the IR\cite{gana,henry}.
        !           129: Unfortunately, these grammars are large and ambiguous.  Using
        !           130: parsers to handle them have usually met with many combinatorial problems
        !           131: \cite{henry}.  Furthermore, these code generators are slow
        !           132: although their output is often of high quality.
        !           133: The software engineering advantages one see with parsers in the front end
        !           134: are not so evident in this circumstance.  Instead of having to deal with
        !           135: the complexities of code generation, the implementor now has to deal with
        !           136: the complexities of the very large machine grammar.
        !           137: 
        !           138: Another approach at automatically building back ends is to start with
        !           139: known good algorithms for generating code.  From these algorithms, we
        !           140: can build an abstract interpreter and then specifications can be written
        !           141: to drive them.  We hope that by doing this we can derive a much more natural
        !           142: code generation specification technique.
        !           143: \Twiglang{} is one possible result of this approach.  The algorithms
        !           144: that form the basis of \twiglang{} are presented in \cite{optimalcode} and
        !           145: \cite{treematch}.  \Twiglang{}
        !           146: specifications are much less complex than parser based
        !           147: specifications.  Ambiguities are handled naturally and do not complicate
        !           148: the specifications.
        !           149: 
        !           150: In \cite{optimalcode}, it is shown how optimal code can be generated
        !           151: for an expression tree
        !           152: given a description of a machine's instruction set.
        !           153: This description is in term of tree templates.
        !           154: The algorithm first determines a minimal cost covering of
        !           155: an expression tree using dynamic programming.
        !           156: The covering is composed from the templates in the
        !           157: description.  The code generated is then the instructions
        !           158: represented by the templates in the covering.
        !           159: This algorithm was shown to generate the shortest code sequences for an
        !           160: abstract machine and
        !           161: its running time was shown to be linear in the number of nodes in the
        !           162: expression tree in \cite{optimalcode}.
        !           163: 
        !           164: This is all very well in theory but what about in practice.
        !           165: Code length is  not always the quantity that one wishes to minimize.
        !           166: One might wish to minimize the number of memory accesses or machine cycles
        !           167: executed by the generated code.
        !           168: Fortunately, the algorithm can also minimize these quantities.
        !           169: In fact, it can minimize any strictly increasing cost function.
        !           170: Let $I$ denote a machine instruction and
        !           171: $I_0I_1I_2...I_n$ denote a sequence of instructions.
        !           172: Then a cost function $f$ is strictly increasing if and only if
        !           173: $f(I_0I_1I_2...I_n) < f(I_0I_1I_2...I_nI_{n+1})$ for all
        !           174: instruction sequences $I_0I_1I_2...I_n$ and instruction
        !           175: $I_{n+1}$.  Another shortcoming in \cite{optimalcode}
        !           176: is that no efficient algorithm is given for matching the templates
        !           177: in the tree.  This is where \cite{treematch} comes in.  In that paper,
        !           178: two algorithms are presented for tree matching.  \Twiglang{} combines
        !           179: the work presented in the two papers.
        !           180: 
        !           181: \Twiglang{} differs from the algorithm as presented in \cite{optimalcode} in
        !           182: the following ways:
        !           183: \begin{itemize}
        !           184: \item
        !           185: It provides a convenient specification language for the templates.
        !           186: \item
        !           187: Tree templates in \cite{optimalcode} were labelled with either {\sl Register} or
        !           188: {\sl Memory}.  This label being the storage class that the instruction corresponding
        !           189: to the template would put a result.
        !           190: \Twiglang{} generalize tree labels so that
        !           191: they can be any symbol.
        !           192: \item
        !           193: Instead of associating an instruction with each template, \twiglang{} associates
        !           194: an action.
        !           195: \item
        !           196: In \cite{optimalcode}, code is generated by a bottom up traversal of the
        !           197: minimum cost covering.  \Twiglang{} allows a top down traversal of the cover
        !           198: and also the ability for the actions to rewrite parts of the
        !           199: tree.
        !           200: \item
        !           201: The algorithm in \cite{optimalcode} determines the evaluation order
        !           202: which gives the optimal code.
        !           203: \Twiglang{} does not do this.
        !           204: The evaluation order determination was omitted based on the conjecture that
        !           205: most of the time, simple left to right evaluation of the leaves will yield
        !           206: near optimal results.
        !           207: In situations where a nonstandard evaluation order is required, a new
        !           208: \twiglang{} pattern could be added that codes the order explicitly
        !           209: (see Section~\ref{exec:phase}).
        !           210: \end{itemize}
        !           211: 
        !           212: In this manual, a brief discussion will be given of the \twiglang{} language
        !           213: and how \twiglang{} programs can be incorporated with C.
        !           214: 
        !           215: Many statements have been made in this manual without proof.
        !           216: If the reader wishes to pursue it further, more details about the algorithms
        !           217: will be presented in an upcoming paper,
        !           218: \cite{aho:gana:tjiang}.
        !           219: 
        !           220: \section{The \Twiglang{} Language}
        !           221: \subsection{Lexical Issues and Conventions}
        !           222: Currently the
        !           223: following identifiers are reserved keywords of \twiglang{}:
        !           224: 
        !           225: \begin{tabbing}
        !           226: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\kill
        !           227: action \> cost \> insert \\
        !           228: label \> node \> prologue
        !           229: \end{tabbing}
        !           230: 
        !           231: \noindent ;:(),= are special characters.  All blanks, tabs, formfeeds and
        !           232: newlines are ignored by \twiglang{} but they may not appear inside
        !           233: identifiers and numbers.  Identifiers are nonempty strings
        !           234: made of letters, digits or underscores and starting with a letter.
        !           235: Numbers are nonempty string of digits.  Code fragments or action parts
        !           236: are enclosed in braces.  Inside code fragments, C lexical rules must
        !           237: be obeyed except that strings of the form $\$...\$$ that are not inside C
        !           238: strings have special meaning to \twiglang{}.  In the following sections, $id$
        !           239: denotes an identifier; $int_1$, $int_2$ denotes numbers; $ccode$
        !           240: denotes C code fragments; $...$ indicates repetition of the previous
        !           241: item; $[...]$ indicates that $...$ is optional.
        !           242: 
        !           243: The input to the \twiglang{} program will be referred to as the subject tree.
        !           244: 
        !           245: \subsection{Rules}
        !           246: 
        !           247: The fundamental unit of a \twiglang{} program is a rule.
        !           248: 
        !           249: \begin{verse}
        !           250: $label\_id$ {\bf :} $tree\_pattern$\quad {\bf [} $cost$ {\bf ]}
        !           251: {\bf [ =} $action$ {\bf ]}
        !           252: \end{verse}
        !           253: 
        !           254: \noindent Intuitively, the pattern is used to match a subtree.
        !           255: The $cost$ code
        !           256: fragment is then evaluated.  The resulting cost is recorded by
        !           257: the matcher for use in dynamic programming.  The $action$ is executed
        !           258: if the rule is part of the least cost cover of the tree.
        !           259: The details of pattern matching will be discussed in Section~\ref{pattern}.
        !           260: 
        !           261: If the $cost$ part is missing, \twigcomp{} will insert default code
        !           262: that returns the special value, {\tt DEFAULT\_COST}.
        !           263: A missing $action$ part indicates that nothing will be done when a
        !           264: match is found.
        !           265: 
        !           266: \subsection{Tree Patterns}
        !           267: \label{TreePatterns}
        !           268: Tree patterns are specified
        !           269: in prefix parenthesized form and can be described by the
        !           270: following BNF:
        !           271: 
        !           272: \begin{verse}
        !           273: $tree\_pattern\to node\_id\;\vert\;label\_id$\\
        !           274: $tree\_pattern\to node\_id \;{\bf (}\; tree\_list \;{\bf )}$\\
        !           275: $tree\_list \to tree \;{\bf ,}\; tree\_list \;\vert\; tree$\\
        !           276: \end{verse}
        !           277: 
        !           278: \begin{figure}
        !           279: \unitlength 0.1in
        !           280: \begin{center}
        !           281: \begin{picture}(25,16)
        !           282: \put(7,0){\framebox(4,3){\tt id}}
        !           283: \put(20,0){\framebox(5,3){\tt const}}
        !           284: \put(13,6){\framebox(5,3){\tt plus}}
        !           285: \put(6,12){\framebox(5,3){\tt plus}}
        !           286: \put(0,6){\framebox(4,3){\tt id}}
        !           287: \put(11,3){\line(2,3){2}}
        !           288: \put(20,3){\line(-2,3){2}}
        !           289: \put(13,9){\line(-2,3){2}}
        !           290: \put(4,9){\line(2,3){2}}
        !           291: \end{picture}
        !           292: \end{center}
        !           293: \vspace{0.5in}
        !           294: \begin{verse}
        !           295: \begin{center}
        !           296: \tt plus(id, plus(id, const))
        !           297: \end{center}
        !           298: \end{verse}
        !           299: \caption{A Tree and its prefixed form}
        !           300: \label{treepattern}
        !           301: \end{figure}
        !           302: \noindent Figure~\ref{treepattern} gives an example of a tree pattern
        !           303: and its prefix parenthesized form.
        !           304: 
        !           305: There are two types of symbols: $node\_id$\/s and $label\_id$\/s.
        !           306: $Node\_id$\/s are used to denote internal nodes and leaves.
        !           307: $Label\_id$\/s label tree patterns and are analogous to
        !           308: nonterminals in context free grammars.
        !           309: For example, the following \twiglang{} rules without their action parts describe
        !           310: simple expression trees with the {\tt plus} operator.
        !           311: 
        !           312: \begin{verse}
        !           313: {\tt\begin{tabbing}
        !           314: expr: \= plus(expr, expr)\\
        !           315: expr: \> identifier\\
        !           316: expr: \> constant
        !           317: \end{tabbing}}
        !           318: \end{verse}
        !           319: 
        !           320: \noindent Here, {\tt identifier} and {\tt constant} are $node\_id$\/s
        !           321: representing leaves, and
        !           322: {\tt plus} is a $node\_id$ representing an internal node whereas
        !           323: {\tt expr} is a
        !           324: $label\_id$.  Pattern leaves that are $label\_id$\/s are called
        !           325: {\sl labelled leaves}.
        !           326: In the first rule, both leaves of the pattern are labelled.
        !           327: 
        !           328: \Twigcomp{} associates an integer with each node symbol and label symbol.  These
        !           329: integers are used by the \twiglang{} pattern matcher as encodings for the
        !           330: symbols.
        !           331: As the matcher traverses the
        !           332: tree, a user supplied subroutine is called to provide an integer
        !           333: corresponding to each node.
        !           334: 
        !           335: \subsection{Costs}
        !           336: 
        !           337: To increase the flexibility of representing costs, the tree matcher
        !           338: views costs as an {\sl abstract data type} or ADT.
        !           339: For example, costs may be represented as an integer or
        !           340: as a vector of integers with each element representing the cost of a specific
        !           341: resource.
        !           342: A cost ADT suitable for \twiglang{} must have the following four definitions:
        !           343: 
        !           344: \begin{itemize}
        !           345: \item {\tt COST} is a C type.
        !           346: Although the proper functioning of the tree matcher
        !           347: does not depend on the internal details of the {\tt COST} type, it must have
        !           348: the type information for storage allocation purposes.
        !           349: \item {\tt INFINITY} is the maximum attainable cost value.
        !           350: The matcher uses {\tt INFINITY} to initialize its data structures.
        !           351: \item {\tt DEFAULT\_COST} is the cost
        !           352: value returned by rules without a cost part.
        !           353: \item
        !           354: {\tt COSTLESS} is a function of
        !           355: two cost values.  It must return true if and only if the first argument is
        !           356: less than the second.
        !           357: \end{itemize}
        !           358: 
        !           359: \subsection{Trees}
        !           360: 
        !           361: As with costs, trees are treated as an ADT.  Here, using an ADT is
        !           362: even more important because trees come in a variety of shapes and
        !           363: representations.
        !           364: \Twiglang{} would be overly complicated if it had to
        !           365: know any more than the fundamental properties of trees.  Thus,
        !           366: \twiglang{} treats trees as an acyclic directed
        !           367: graph of almost featureless nodes with one
        !           368: distinguished node, the root.  Each node has only one feature and that
        !           369: is an integer corresponding to the $node\_id$\/s discussed above.
        !           370: To provide this
        !           371: view to \twiglang{}, the user must provide the following definitions and
        !           372: subroutines.
        !           373: 
        !           374: \begin{itemize}
        !           375: \item {\tt NODEPTR} is the type of a node.  The actual
        !           376: details of
        !           377: the {\tt NODEPTR}
        !           378: are irrelevant and \twigcomp{} uses this definition only for storage
        !           379: allocation and declaration purposes.
        !           380: \item
        !           381: {\tt NULL} is used to denote a null {\tt NODEPTR} value.
        !           382: In the current implementation this is the same {\tt NULL} used by the
        !           383: C standard I/O package and need not be defined by the user.
        !           384: This restricts the {\tt NODEPTR} representation to be a pointer.
        !           385: \item
        !           386: {\tt mtGetNodes$(r,n)$} returns the $n$th child of $r$ where $r$
        !           387: is a {\tt NODEPTR}.  The
        !           388: leftmost child is {\tt mtGetNodes}$(r,1)$.  If $n > \hbox{degree}(r)$
        !           389: then the function should return {\tt NULL}.  \Twigcomp{} expects the
        !           390: expression {\tt mtGetNodes}$({\tt NULL}, 0)$
        !           391: to denote the root node of
        !           392: the subject tree.
        !           393: \item
        !           394: {\tt mtValue$(r)$} returns the integer associated with $r$
        !           395: (See section~\ref{TreePatterns}).
        !           396: \item
        !           397: {\tt mtSetNodes$(r,n,c)$} replaces the $n$th child of $r$ with
        !           398: $c$.  This routine may be used to replace whole subtrees with others.
        !           399: {\tt mtSetNodes}$({\tt NULL},0,c)$ is used by \twigcomp{} to set the
        !           400: root of the subject tree to $c$.
        !           401: \end{itemize}
        !           402: 
        !           403: \subsection{Prologue and Inserts}
        !           404: 
        !           405: \begin{verse}
        !           406: {\tt prologue} $ccode$;
        !           407: \end{verse}
        !           408: 
        !           409: \noindent signals to \twigcomp{} that $ccode$ should be inserted at the
        !           410: beginning of the output source file.  $Ccode$ should contain
        !           411: definitions relevant to the C code in
        !           412: rules that are defined later in the \twiglang{} source file.
        !           413: 
        !           414: \begin{verse}
        !           415: {\tt insert} $ccode$;
        !           416: \end{verse}
        !           417: 
        !           418: \noindent causes $ccode$ to be placed into the source file.
        !           419: There can be multiple inserts and they will be placed into the source
        !           420: file
        !           421: in the order that they appear.
        !           422: 
        !           423: \subsection{Declarations}
        !           424: 
        !           425: All \twiglang{} identifiers are declared before they are used.
        !           426: 
        !           427: \begin{verse}
        !           428: {\tt node $id[(int_1)] [= int_2] ...$;\hfil}
        !           429: \end{verse}
        !           430: 
        !           431: \noindent A node declaration declares one or more identifier to be
        !           432: associated with nodes of the subject tree.  The identifiers are
        !           433: assigned numbers by \twigcomp{} but the user can overide the assigned number
        !           434: by specifying $int_2$.  The degree of the node identifer, the
        !           435: number of children, is assumed to be fixed.  Normally, \twigcomp{} will
        !           436: deduce the degree when $id$ is used in a rule.  However, the user may
        !           437: explicitly give the degree by specifying $int_1$.
        !           438: 
        !           439: \begin{verse}
        !           440: {\tt label $id ...$;}
        !           441: \end{verse}
        !           442: 
        !           443: A label declaration indicates that the following $id$'s are to be used
        !           444: as labels of rules.
        !           445: 
        !           446: \subsection{Costs and Action code}
        !           447: 
        !           448: Code fragments such as the $cost$ and $action$ clauses of a rule are
        !           449: specfied by enclosing C code in braces.  All legal C constructs are
        !           450: permitted in code fragments.  In addition, the following are provided
        !           451: for convenient access to the subject tree and internal data
        !           452: structures of the matcher.
        !           453: 
        !           454: \begin{itemize}
        !           455: \item $\$\%n\$$ denotes a pointer value to the matcher data
        !           456: structure for the $n$th labelled leaf.  Thus to access the cost value
        !           457: associated with that leaf, the notation $\$\%n\$\to${\tt cost} may be used.
        !           458: 
        !           459: \item $\$\$$ denotes a pointer value to the root of the subject
        !           460: tree.
        !           461: 
        !           462: \item $\$n_1.n_2.n_3.\, \hbox{...}\,.n_{k-1}.n_k\$$ denotes
        !           463: a pointer value to the $n_k$th child of the $n_{k-1}th$ child of the
        !           464: $n_{k-2}$th child of \hbox{...} of the $n_1$th child of the root of
        !           465: the subject tree.  Each $n_i$ is a positive non-zero integer.
        !           466: \end{itemize}
        !           467: 
        !           468: Some special constructs are available to code fragments in the cost
        !           469: part of the specification.  The
        !           470: statement ``{\tt ABORT;}'' when encountered during the execution of
        !           471: the cost code, signals to the matcher that this pattern is to be
        !           472: rejected.  When a ``{\tt REWRITE;}'' statement is encountered, control
        !           473: is returned to the matcher and the rule will become a {\sl rewrite}
        !           474: mode match.  When the end of the cost code fragment is reached,
        !           475: control is returned to the matcher and the rule becomes a {\sl defer}
        !           476: mode match.
        !           477: The statement ``{\tt TOPDOWN;}'' is like ``{\tt REWRITE;}'' except that
        !           478: the mode of the match becomes {\sl topdown}.  The meanings of these modes
        !           479: will be explained in Section~\ref{pattern}.
        !           480: 
        !           481: Cost values are returned to the matcher by assigning to
        !           482: the ``{\tt cost}'' variable in the cost clause.  If no assignment is
        !           483: made to the {\tt cost} variable then the returned cost will be {\tt
        !           484: DEFAULT\_COST}.
        !           485: 
        !           486: Action clauses are expected to return a new tree which will replace
        !           487: the subject tree.  This is done by returning using the
        !           488: ``{\tt return($new\_tree$);}'' statement.
        !           489: where {\tt $new\_tree$} is of type
        !           490: {\tt NODEPTR}.
        !           491: If execution reaches the end of the action clause, the
        !           492: matcher resumes execution and the subject tree is not modified.
        !           493: 
        !           494: \section{Pattern Matcher Operation}
        !           495: \label{pattern}
        !           496: 
        !           497: The
        !           498: pattern matcher operates in two phases: the costing phase and the execution
        !           499: phase.
        !           500: During
        !           501: the costing phase, a minimal cost covering of the subject tree is found.
        !           502: The execution phase invokes the actions that are associated with the patterns
        !           503: making up the covering.  Execution phases may begin during the costing phase
        !           504: to execute the covering of a subtree as described in Section~\ref{exec:phase}.
        !           505: 
        !           506: \subsection{The Costing Phase}
        !           507: \label{cost:phase}
        !           508: 
        !           509: Let the patterns of the \twiglang{} specifications be interpreted as grammar
        !           510: productions with {\sl label\_id}s as non-terminals and {\sl node\_id}s
        !           511: as terminals.
        !           512: If we add a production
        !           513: $S\,\to\,\hbox{\sl label\_id}$ for all {\sl label\_id}s where $S$ is the
        !           514: start symbol,
        !           515: then a covering for a tree is analogous to a derivation
        !           516: for the prefixed form of the tree.
        !           517: Figure~\ref{gram:interp} shows some patterns and its corresponding grammar.
        !           518: \begin{figure}
        !           519: \begin{center}
        !           520: \begin{verse}
        !           521: \tt
        !           522: e: plus(e,e)\\
        !           523: e: plus(e, plus(e,e))\\
        !           524: e: id\\
        !           525: e: const\\
        !           526: \end{verse}
        !           527: \end{center}
        !           528: \vspace{0.3in}
        !           529: \begin{center}\begin{verse}
        !           530: $S\to e$\\
        !           531: $e\to plus(e,e)$\\
        !           532: $e\to plus(e,plus(e,e)$\\
        !           533: $e\to id$\\
        !           534: $e\to const$\\
        !           535: \end{verse}\end{center}
        !           536: \caption{Pattern and Grammar}
        !           537: \label{gram:interp}
        !           538: \end{figure}
        !           539: The productions of the form $S\to\hbox{\sl label\_id}$ reflect the fact that
        !           540: any {\sl label\_id} may start a cover.
        !           541: 
        !           542: The matcher finds the least cost cover by doing a preorder traversal of
        !           543: the subject tree.
        !           544: At the same time, it
        !           545: builds a skeleton tree that is structurally isomorphic to the subject tree.
        !           546: When a match is discovered the cost clause of the pattern is invoked to
        !           547: calculate the cost.  Many patterns with different labels could match at any
        !           548: given node but only the lowest cost pattern for each label is recorded in
        !           549: the skeleton.
        !           550: 
        !           551: When a pattern is matched, its label is then used as input to the pattern
        !           552: matcher so that matching of patterns with labelled leaves can begin.
        !           553: This process
        !           554: is analogous to a reduce action in
        !           555: bottom up parsers.
        !           556: 
        !           557: \subsection{The Execution Phase}
        !           558: \label{exec:phase}
        !           559: 
        !           560: The execution phase starts when the costing phase is complete or when
        !           561: a sufficiently low cost {\sl rewrite} mode rule is encountered.
        !           562: Let $M$ be a matching
        !           563: rule and $L_1, L_2, L_3, ... ,L_n$ be
        !           564: the labelled leaves of the matching pattern.
        !           565: The following procedure is used to execute the action parts of $M$.
        !           566: 
        !           567: \vbox{
        !           568: \vspace{2ex}
        !           569: \noindent {\bf Procedure \it Execute}
        !           570: 
        !           571: \begin{itemize}
        !           572: \item If $M$ is a {\sl deferred} mode match then
        !           573: execution occurs by first applying {\it Execute} to the $L_i$s
        !           574: from left to right.  That is, in the order that they appear in
        !           575: the prefix form of the tree.
        !           576: When all the $L_i$s are executed, the action part of $M$ is
        !           577: invoked.
        !           578: 
        !           579: \item If $M$ is a {\sl rewrite } mode match then
        !           580: just the action part of $M$ is executed.  When the action part returns
        !           581: the matcher deletes the skeleton corresponding to the subtree that
        !           582: $M$ matched and rescans the new subtree that may have been substituted
        !           583: by executing $M$.
        !           584: 
        !           585: \item If $M$ is a {\sl topdown} mode match then only
        !           586: the action part of $M$ is executed.  To execute a
        !           587: labelled leaves, $L_i$, $M$'s action part may do so explicitly
        !           588: by using the {\tt tDO($\$\%i\$$)} macro.  This allows
        !           589: the user to arbitrary order the execution of the labelled leaves.
        !           590: \end{itemize}
        !           591: }
        !           592: 
        !           593: \noindent When the costing phase is over, the execution phase is started
        !           594: by picking the lowest cost match at the root of the subject tree.
        !           595: This will be the root of the minimum cost cover.
        !           596: The match is executed as described above.
        !           597: 
        !           598: The execution phase may begin before the costing phase is over.
        !           599: This occurs when a rewrite rule matches and its cost is lower than
        !           600: all other matches at that subtree.  In this situation the rewrite rule
        !           601: is executed immediately and the new rewritten subtree is scanned once more.
        !           602: The prescence of rewrite rules throws a wrench in the theoretical niceties
        !           603: of the matching algorithm.  For example, there is now no guarantee
        !           604: that the algorithm will terminate because the tree can
        !           605: be repeatedly enlarged.
        !           606: Rewrite rules can be dangerous.  They can
        !           607: be triggered unintentionally if the user is not careful to abort them
        !           608: in situations where they are not wanted.
        !           609: However, if used with care they can help to reduce the size of the \twiglang{}
        !           610: specification.
        !           611: 
        !           612: \section{Some Examples}
        !           613: 
        !           614: \subsection{Expression Trees to Prefix}
        !           615: A \twiglang{} program to print out the prefix form of expression
        !           616: parse trees
        !           617: is shown in Figure~\ref{trees:prefix}.
        !           618: 
        !           619: \begin{itemize}
        !           620: 
        !           621: \item The rules do not have cost calculations.
        !           622: Since there are no
        !           623: ambiguities costs are not necessary.
        !           624: 
        !           625: \item The second rule is a topdown mode rule.  This is essential in printing
        !           626: the prefix form.  If it was omitted the postfix form would be printed.
        !           627: 
        !           628: \item Before any matching can begin {\tt \_matchinit} must be called.
        !           629: Trees can then be processed by calling {\tt \_match} after arranging that
        !           630: the call
        !           631: {\tt mtGetNodes}$({\tt NULL},0)$ returns the root of the subject tree.
        !           632: \end{itemize}
        !           633: 
        !           634: \begin{figure}[tp]
        !           635: \begin{tabbing}
        !           636: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=
        !           637: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\kill
        !           638: prologue \> $\{$\\[4pt]
        !           639: typedef \> struct node $*$\>\>{\tt NODEPTR};\\
        !           640: \#define \> {\tt COST} \>\> int\\
        !           641: \#define \> {\tt INFINITY}\>\>  100000\\
        !           642: \#define \> {\tt DEFAULT\_COST} \>\> 0\\[4pt]
        !           643: {\tt NODEPTR} Root;\\
        !           644: struct code \> $\{$\\
        !           645: \> char op; \> \> $/*$ null if node is a leaf $*/$\\
        !           646: \> NODEPTR left, right;\\
        !           647: \> char $*$id;\\
        !           648: $\}$;\\[4pt]
        !           649: $\}$;\\[6pt]
        !           650: node \> nOp nIdent;\\
        !           651: label \> lExpr;\\[6pt]
        !           652: lExpr:\> nIdent\\
        !           653: \>= $\{$ printf(``$\%$s'', id); $\}$;\\[4pt]
        !           654: lExpr:\>nOp(lExpr,lExpr)\\
        !           655: \>$\{$ {\tt TOPDOWN};$\}$\\
        !           656: \>= $\{$\\
        !           657: \>\>putchar($\$\$\to$op);\\
        !           658: \>\>tDO($\$\%1\$$);\\
        !           659: \>\>tDO($\$\%2\$$);\\
        !           660: \>$\}$;\\[6pt]
        !           661: insert\>$\{$\\[4pt]
        !           662: mtValue(root)\\
        !           663: \>{\tt NODEPTR} root;\\
        !           664: $\{$\\
        !           665: \>if(root$\to$op==0)\\
        !           666: \>\>return(nIdent);\\
        !           667: \>else\\
        !           668: \>\>return(nOp);\\
        !           669: $\}$\\[4pt]
        !           670: \end{tabbing}
        !           671: \caption{Printing Expression trees to Prefix form}
        !           672: \end{figure}
        !           673: \addtocounter{figure}{-1}
        !           674: \begin{figure}[tp]
        !           675: \begin{tabbing}
        !           676: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=
        !           677: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\kill
        !           678: mtGetNodes(r,n)\\
        !           679: \>{\tt NODEPTR} r;\\
        !           680: \>int n;\\
        !           681: $\{$\\
        !           682: \>if(n==1)\\
        !           683: \>\>return(r$\to$left);\\
        !           684: \>else if(n==1)\\
        !           685: \>\>return(r$\to$right);\\
        !           686: \>else if(n==0 $\&\&$ r=={\tt NULL})\\
        !           687: \>\>return(Root);\\
        !           688: \>else return({\tt NULL});\\
        !           689: $\}$\\[4pt]
        !           690: mtSetNodes(r,n, c)\\
        !           691: \>{\tt NODEPTR} r, c;\\
        !           692: \>int n;\\
        !           693: $\{$\\
        !           694: \>if(n==1)\\
        !           695: \>\>r$\to$left = c;\\
        !           696: \>else if(n==2)\\
        !           697: \>\>r$\to$right = c;\\
        !           698: \>else if(n==0)\\
        !           699: \>\>Root = c;\\
        !           700: $\}$\\[4pt]
        !           701: main(argc,argv)\>\>\>$/*$ called by user only $*/$\\
        !           702: \>char $**$argv;\\
        !           703: $\{$\\
        !           704: \>\_matchinit();\>\>$/*$ initialize the matcher $*/$\\
        !           705: \>$...$ {\sl get a tree and set Root to it}\\
        !           706: \>\_match();\>\>$/*$ do the match $*/$\\
        !           707: $\}$\\
        !           708: $\}$\\
        !           709: \end{tabbing}
        !           710: \caption{(cont.) Printing Expression trees to Prefix form}
        !           711: \label{trees:prefix}
        !           712: \end{figure}
        !           713: 
        !           714: \subsection{Short Circuited Boolean Evaluation}
        !           715: 
        !           716: Short circuited boolean evaluation is naturally topdown.
        !           717: A fragment of \twiglang{} program that implements this
        !           718: is shown in Figure~\ref{short:circuit}.
        !           719: 
        !           720: \begin{itemize}
        !           721: 
        !           722: \item Labels for true and false branches are passed down to
        !           723: rules below by putting them into the nodes.  Another way of
        !           724: accomplishing this is to use an auxillary argument stack.
        !           725: 
        !           726: \item The rules assume that every test generates a branch to both
        !           727: the false and true label.  On conventional machines, extra branches
        !           728: can be eliminated by recognizing that one could generate code that
        !           729: falls through to its true or false labels.  This can be done by
        !           730: separating {\sl lTest} into {\sl lTrueTest} and {\sl lFalseTest} which
        !           731: branches only when true and false respectively.  Rules can then be
        !           732: written to take advantage of this.
        !           733: \end{itemize}
        !           734: 
        !           735: \begin{figure}
        !           736: \begin{tabbing}
        !           737: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=
        !           738: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\kill
        !           739: prologue \> $\{$\\[4pt]
        !           740: \#include\>``otherdefs.h''\\
        !           741: union node $\{$\\
        !           742: \> $...$ \>\>$/*$ definition of other node types $*/$\\
        !           743: \> union $\{$\\
        !           744: \>\> int operation;\\
        !           745: \>\> {\tt NODEPTR} left, right;\\
        !           746: \>\> {\tt LABEL} falselab, truelab;\>\>$/*$ {\tt LABEL} will defined
        !           747: elsewhere $*/$\\
        !           748: \>\> $...$ \>\> $/*$ other definitions relevant to {\sl test nodes} $*/$\\
        !           749: \> $\}$ test;
        !           750: \> $...$ \>\>$/*$ definition of other node types $*/$\\
        !           751: $\}$;\\[4pt]
        !           752: $\}$;\\[6pt]
        !           753: node\>nAnd nOr nNot nLess;\\
        !           754: label\>lTest lExpr;\\[6pt]
        !           755: lTest:\>nAnd(lTest,lTest)\\
        !           756: \>$\{$ {\tt TOPDOWN}; $\}$\\
        !           757: \>=$\{$\\
        !           758: \>\>$\$1\$\to$test.falselab = $\$\$\to$test.falselab;\\
        !           759: \>\>$\$1\$\to$test.truelab = getlabel();\\
        !           760: \>\>tDO($\$\%1\$$);\\
        !           761: \>\>printlab($\$1\$\to$test.truelab);\\
        !           762: \>\>$\$2\$\to$test.falselab = $\$\$\to$test.falselab;\\
        !           763: \>\>$\$2\$\to$test.truelab = $\$\$\to$test.truelab;\\
        !           764: \>\>tDO($\$\%2\$$);\\
        !           765: \>$\}$;\\[4pt]
        !           766: lTest:\>nOr(lTest,lTest)\\
        !           767: \>$\{$ {\tt TOPDOWN}; $\}$\\
        !           768: \>=$\{$\\
        !           769: \>\>$\$1\$\to$test.falselab = getlabel();\\
        !           770: \>\>$\$1\$\to$test.truelab = $\$\$\to$test.truelab;\\
        !           771: \>\>tDO($\$\%1\$$);\\
        !           772: \>\>$\$2\$\to$test.truelab = $\$\$\to$test.truelab;\\
        !           773: \>\>$\$2\$\to$test.falselab = $\$\$\to$test.falselab;\\
        !           774: \>\>tDO($\$\%2\$$);\\
        !           775: \>$\}$;\\
        !           776: \end{tabbing}
        !           777: \caption{Short circuited Boolean Evaluation}
        !           778: \label{short:circuit}
        !           779: \end{figure}
        !           780: \addtocounter{figure}{-1}
        !           781: \begin{figure}[tp]
        !           782: \begin{tabbing}
        !           783: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=
        !           784: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\kill
        !           785: lTest:\>nNot(lTest)\\
        !           786: \>$\{$ {\tt TOPDOWN}; $\}$\\
        !           787: \>=$\{$\\
        !           788: \>\>$\$1\$\to$test.truelab = $\$\$\to$test.falselab;\\
        !           789: \>\>$\$1\$\to$test.falselab = $\$\$\to$test.truelab;\\
        !           790: \>\>tDO($\$\%1\$$);\\
        !           791: \>$\}$;\\[4pt]
        !           792: lTest:\>nLess(lExpr,lExpr)\>\>$/*$ {\sl not topdown anymore } $*/$\\
        !           793: \>=$\{$ $...$ {\sl generate code for comparison } $...$ $\}$;\\
        !           794: \end{tabbing}
        !           795: \caption{(cont.) Short circuited Boolean Evaluation}
        !           796: \end{figure}
        !           797: 
        !           798: \subsection{Code Generation}
        !           799: 
        !           800: Figure~\ref{example} is an 
        !           801: example of \twiglang{} program that
        !           802: can be used to generate VAX code for
        !           803: the subtract instruction:
        !           804: 
        !           805: \begin{figure}
        !           806: \begin{tabbing}
        !           807: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=
        !           808: \hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\hspace{1in}\=\kill
        !           809: prologue \> $\{$\\
        !           810: $/*$ otherdefs.h will have a type definition for {\tt NODEPTR} $*/$\\
        !           811: \#include\>``otherdefs.h''\\
        !           812: \#define\>{\tt TEMP\_COST}\>\>5\\
        !           813: \#define\>{\tt SUB\_COST}\>\>30\\
        !           814: \#define\>{\tt DEC\_COST}\>\>10\\
        !           815: NODEPTR \> gettemp();\\
        !           816: $\}$;\\[4pt]
        !           817: node \> long constant sub;\\
        !           818: label \> operand temp;\\[4pt]
        !           819: operand: \> long;\>\>\>$/*$ rule 1 $*/$\\
        !           820: operand:\>constant;\>\>\>$/*$ rule 2 $*/$\\
        !           821: operand:\>temp;\>\>\>$/*$ rule 3 $*/$\\[4pt]
        !           822: temp:\>operand\>\>\>$/*$ rule 4 $*/$\\
        !           823: \>$\{$ cost = {\tt TEMP\_COST}+$\$\%1\$\to$cost;$\}$\\
        !           824: \>$=\{$\\
        !           825: \>\>NODEPTR t = gettemp();\\
        !           826: \>\> emit(``mov'', $\$\$$, t, 0);\\
        !           827: \>\>return(t);\\
        !           828: \>$\}$;\\[4pt]
        !           829: operand:\>sub(operand,operand)\>\>\>$/*$ rule 5 $*/$\\
        !           830: \>$\{$cost = $\$\%1\$\to$cost + $\$\%2\$\to$cost+{\tt SUB\_COST};$\}$\\
        !           831: \>=$\{$\\
        !           832: \>\>NODEPTR t = gettemp();\\
        !           833: \>\>emit(``sub'', $\$1\$$, $\$2\$$, t, 0);\\
        !           834: \>\>return(t);\\
        !           835: \>$\}$;\\[4pt]
        !           836: temp:\>sub(temp,constant)\>\>\>$/*$ rule 6 $*/$\\
        !           837: \>$\{$\\
        !           838: \>\>if(value($\$2\$$)==1)\\
        !           839: \>\>\>cost = $\$\%1\$\to$cost+{\tt DEC\_COST};\\
        !           840: \>\>else ABORT;\\
        !           841: \>$\}$=$\{$\\
        !           842: \>\>emit(``dec'', $\$1\$$, 0);\\
        !           843: \>\>return($\$1\$$);\\
        !           844: \>$\}$;
        !           845: \end{tabbing}
        !           846: \caption{Small Code Generation Example}
        !           847: \label{example}
        !           848: \end{figure}
        !           849: 
        !           850: \begin{itemize}
        !           851: \item Rules 3 and 4 form a loop.
        !           852: The potential loop: temp$\to$operand$\to$temp$\to$operand$...$ is
        !           853: broken
        !           854: by the matcher recognizing that the cost of the second match of temp
        !           855: does not cost less than the first match of temp.
        !           856: 
        !           857: \item In the cost clause of rule 5, the cost is the sum of the
        !           858: leaves plus the cost of the subtract instruction.
        !           859: The action clause emits code to add the two operands
        !           860: and leave the result in a temporary location.  The temporary is
        !           861: returned as a substitution for the subject tree.
        !           862: 
        !           863: \item Rule 6 handles a special case where the left operand is
        !           864: already in a temporary and the constant is one.  In this case, the
        !           865: temporary is directly decremented and returned as the new tree.
        !           866: \end{itemize}
        !           867: 
        !           868: \section{How to run \Twigcomp{}}
        !           869: 
        !           870: Once a user has written the specification, \twigcomp{} is used to compile it
        !           871: into a subroutine.
        !           872: Figure~\ref{overview} gives an overview of how \twigcomp{} does this.
        !           873: In Figure~\ref{overview}, rounded boxes indicate files and sharp
        !           874: cornered boxes
        !           875: are processing programs.  The user creates the \twiglang{} specification which
        !           876: is represented by the top box.  The specification file must have the
        !           877: suffix ``{\tt .mt}''.  Let's say we have one called {\tt arbor.mt}.
        !           878: To invoke the \twigcomp{} compiler we type:
        !           879: 
        !           880: \begin{verse}
        !           881: {\bf twig} [--{\bf w$xx$}] arbor.mt
        !           882: \end{verse}
        !           883: 
        !           884: The proprocessor reads {\tt arbor.mt} and if there are no errors
        !           885: will create two files: {\tt symbols.h} and {\tt walker.c}.
        !           886: To build {\tt walker.c}, \twigcomp{} uses a template file called {\tt walker.$xx$}
        !           887: where $xx$ is the argument of the optional --{\bf w} flag.
        !           888: If the flag is omitted then $xx$ defaults to ``{\tt c1}''.
        !           889: 
        !           890: {\tt Symbols.h} and {\tt walker.c}
        !           891: can then compiled and linked with the other modules of the
        !           892: user's program.  These other modules should provide the
        !           893: Tree and Cost ADTs described above.
        !           894: {\tt Walker.h} is an auxilliary include file that is referenced by {
        !           895: \tt walker.c}.
        !           896: A typical compile command is:
        !           897: 
        !           898: \begin{verse}
        !           899: {\bf cc} -- {\bf I\sl include\_dir} {\bf -c} walker.c
        !           900: \end{verse}
        !           901: 
        !           902: The --{\bf I\sl include\_dir} argument causes {\bf cc} to look for
        !           903: walker.h in {\sl include\_dir}.  The exact value of {\sl include\_dir}
        !           904: will depend on where the files are stored at your site.
        !           905: The tree matcher is initialized by calling {\tt \_matchinit} and matching
        !           906: can begin by calling {\tt \_match} from
        !           907: the user program.
        !           908: 
        !           909: \section{Organization of the \Twigcomp{} Compiler}
        !           910: The preprocessor is written completely in C and YACC.
        !           911: It can be roughly broken up into four modules:
        !           912: \begin{itemize}
        !           913: \item Lexer --- The lexer performs lexical analysis.
        !           914: The input is tokenized by this module and passed to the parser
        !           915: as required.  Identifiers are looked up in the symbol table
        !           916: and space is reserved for them if they have never been encountered.
        !           917: \item Parser --- This part is written in YACC and recognizes the
        !           918: \twiglang{} language.  When a language construct is recognized actions
        !           919: are invoked.  Declarations, prologues and inserts will invoke symbol
        !           920: table operations when recognized.  Rules are broken up and stored
        !           921: in the symbol table too.  The tree patterns in the rules are unflattened
        !           922: and passed to the machine builder.
        !           923: \item Machine Builder --- This module takes tree patterns and incrementally
        !           924: builds an internal representation of the matching automaton.
        !           925: The builder takes this
        !           926: tree and then enumerates each of the possible paths from the root to the
        !           927: leaves.  These paths are treated as strings and a string matching automaton
        !           928: is built as described in \cite{fgrep} and \cite{treematch}.
        !           929: 
        !           930: Inside the builder the partially built machine is kept in a linked list
        !           931: form.  Each machine state is a linked list and each node represents
        !           932: a state transition.  When the tables for the machine are written out into {
        !           933: \tt walker.c}, the linked list structure is
        !           934: translated into a table of sixteen bit integers.
        !           935: Each transistion is stored as two integers.  The first is
        !           936: the integer corresponding to the symbol that causes the transistion and the
        !           937: second is the index of the next state in the table.
        !           938: 
        !           939: \item Symbol Table ---  The central data structure in this symbol table is
        !           940: the hash table.
        !           941: Each entry in the hash table is a bucket --- a linked list of symbol table
        !           942: entries.  There is no rehashing.  All colliding items are placed
        !           943: in the linked list.
        !           944: This is a simple
        !           945: and adequately efficient arrangement.  Depending on the type of symbols, the
        !           946: entry may point to other data structures.  Entries for $label\_id$s point to
        !           947: lists of trees.  $Node\_id$ entries record the integers that have been
        !           948: associates with them.  Other entries may point to data structures holding a
        !           949: textual representation of C code that forms action and cost parts.
        !           950: \end{itemize}
        !           951: 
        !           952: Here is a list of the files that form the \twigcomp{} compiler's source
        !           953: and their approximate function.
        !           954: \begin{itemize}
        !           955: \item {\tt common.h} --- This file contains data definitions for how
        !           956: trees are represented in the parser.  It also contains type definitions for
        !           957: external functions.
        !           958: \item {\tt code.h} --- This file contains definitions for how code fragments
        !           959: are stored.
        !           960: \item {\tt sym.h} --- This file defines the major data structures in the
        !           961: symbol table.
        !           962: \item {\tt machine.h} ---  This file defines the how the matching automaton
        !           963: is represented internally.
        !           964: \item {\tt twig.y} --- This is the parser.
        !           965: \item {\tt sym.c} ---  This is the symbol table manager.
        !           966: \item {\tt path.c} --- The path string enumerator.
        !           967: \item {\tt machine.c} --- The machine builder.
        !           968: \item {\tt lex.c } --- The lexer.
        !           969: \item {\tt tree.c}, {\tt io.c}, and {\tt code.c} --- Miscellaneous
        !           970: routines for manipulating trees, performing I/O and manipulating
        !           971: code fragments.
        !           972: \end{itemize}
        !           973: 
        !           974: \section{Performance}
        !           975: 
        !           976: So far, the only experience we have with \twiglang{}
        !           977: is a VAX code generator written
        !           978: for the pcc2 compiler.  The \twiglang{} code generator is 25\% faster than
        !           979: the original code generator.
        !           980: The maintainability and modifiability of the code generator has
        !           981: improved.  For example adding the indexed addressing mode
        !           982: into the code generator took only a few hours.  The target code quality
        !           983: is just as good as the original code generator.
        !           984: 
        !           985: The \twigcomp{} table
        !           986: generation algorithm is fast.  For the VAX machine description which
        !           987: consist of 109 rules, the generation time was 4.2 seconds on a 780.
        !           988: The generation time could be increased
        !           989: by two orders of magnitude
        !           990: before other table driven system can compete with \twigcomp{} on this basis.
        !           991: Furthermore, the tables are small.  The VAX description is only 7.5K
        !           992: and the text space for the walker is 30K.
        !           993: Again this is much smaller than those of other table driven systems.
        !           994: 
        !           995: \Twiglang{} is currently a research tool.  Several things can be done to improve
        !           996: \twiglang{}'s performance.
        !           997: \begin{itemize}
        !           998: \item  \Twiglang{} does a lot of procedure calls.  Every machine transition
        !           999: require at least one procedure call.  Contrast this to YACC where a machine
        !          1000: transition is done in line.
        !          1001: \item \Twiglang{} performs a very expensive closure operation with respect to
        !          1002: unit rules.  A unit rule is the analogue of a unit production and has the
        !          1003: form:
        !          1004: 
        !          1005: \begin{verse}
        !          1006: $label_1$: $label_2$;
        !          1007: \end{verse}
        !          1008: 
        !          1009: \noindent This closure is done at run time.
        !          1010: It requires many procedure calls and manipulates complex data structures.
        !          1011: We are looking at ways of doing this
        !          1012: at table generation time or to hash the results of the closures so that
        !          1013: redundant calculations can be avoided.  The problem with doing them
        !          1014: in the table generator is the possible explosion in its
        !          1015: running time.
        !          1016: 
        !          1017: \item Many of the cost parts for the rules are similar and hence some
        !          1018: tests are performed and recalculated many times
        !          1019: on a node.  \Twigcomp{} should be clever
        !          1020: enough to factor out some of these tests and do them only once.
        !          1021: However, the information required for \twigcomp{} to do this is not easily
        !          1022: available.  It is hidden in the C code fragments.
        !          1023: 
        !          1024: \item The current compact
        !          1025: representation of the matching automaton
        !          1026: require linear searching except at the
        !          1027: start state where the large branching factor compelled us to use an
        !          1028: array scheme.  Using another representation would speed up the
        !          1029: matcher.  For example, implementing the VAX description as an array is
        !          1030: estimated to use about 50K bytes but may provide
        !          1031: performance improvement.
        !          1032: 
        !          1033: \end{itemize}
        !          1034: \bibliography{mybib}
        !          1035: \bibliographystyle{plain}
        !          1036: \end{document}

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.