V10/cmd/twig/README
Installation Procedure
----------------------
To install twig, you must decide in which directories to place:
(1) the twig compiler binary, and
(2) the twig template files.
Once you have made these two decisions, you should edit the makefile and
set the variable INSTALL to the value of (1), and the variable TEMPLATES to
(2). The definitions of INSTALL and TEMPLATES should be near the beginning
of the makefile. The installation can then be completed by typing:
make install
Once a user has written a twig specification, the command twig is used to
compile it. The compilation creates two files called walker.c,
containing several subroutines, and symbols.h, containing definitions.
Walker.c is compiled and linked with the rest of the user program, and
tree matching occurs when the user's program calls a subroutine called _match.
More details about twig specifications, and how to interface to the
subroutines in walker.c is given in the ``Twig Reference Manual'', AT&T Bell
Laboratories, Computing Science Technical Report #120.
Addendum to the ``Twig Reference Manual''
-----------------------------------------
1. In a node declaration, the user can override the automatic numbering
of a node id by expliciting assigning a number using the ``= int''
construct. However, the user must then assign a number to all
of the node ids. In other words, the user must either assign
numbers to each of the node ids, or to none of them. The ids must
have unique numbers.
2. The default action of executing the labelled leaves from
right to left is inadequate. ``Execution,'' as used here, is in
the sense as described in the ``Twig Reference Manual.'' Although
one could simulate any execution order by using a top-down rule, and
explicitly requesting the execution of labelled leaves with the tDO
macro, it is tedious to do so. For example, implementing a Sethi-Ullman
style register allocator in such a fashion is extremely awkward.
To alleviate this tedium, reordering scheme has been proposed, and
implemented by Andrew Appel of Princeton University. It is included
in this version of twig.
A function, ``_do'' performs the execution of the matches. This
function is part of the walker.c file generated by twig. In versions
of the walker without reordering, _do performs the call:
_evalleaves(winner->lleaves);
where winner->lleaves are the labelled leaves of the winning match.
Lleaves has type ``__match *[], '' and is a NULL terminated sequence
of matches for the labelled leaves in left to right order. Calling
tDO with an element of lleaves executes the match associated with
the labelled leaf.
Reordering is accomplished by changing the call to _evalleaves with
the statement:
REORDER(winner->lleaves);
REORDER is a macro, or function defined by the user that may execute
the leaves in any order. If the user does not define REORDER then
twig will generate a default, which is to call _evalleaves.
For example, if the user wishes to execute the leaves in the order of
decreasing cost, the following definition could be used.
prologue {
...
#define REORDER(list) reorder(list)
...
}
...
insert {
reorder(list)
__match **list;
{
int i, j, n;
__match *index[16];
/* copy list into index */
for(n=0; list[n]; n++) index[n] = list[n];
/* insertion sort */
for(j=0;j<n;j++)
for(i=j; i>0; i--)
if(index[i]->cost > index[i-1]->cost) {
/* swap them */
__match *temp = index[i];
index[i] = index[i-1]; index[i-1] = p;
}
/* now execute */
for(j=0;j<n;j++)
tDO(index[j]);
}
}
3. In a top-down rule, there is often a desire to execute all the
labelled leaves after performing some preparatory actions. This
could be done by saying
tDO($%1$); tDO($%2$); ...
However, the short hand notation, ``EVAL;'' provides the same function.
4. In the previous version of twig, Walker.c had a reference to
walker.h. Hence the user had to compile walker.c with the command:
cc -Iinclude_dir -c walker.c
where include_dir was the directory containing walker.h.
The reference to walker.h has been eliminated by inserting walker.h
into all the template files that could generate walker.c.
Therefore the new compile command is:
cc -c walker.c
5. Twig assigns numbers to the node symbols, which are used to identify
nodes to the tree matcher. In the previous version of twig, the
tree matcher actually recognized ``M_NODE|number'' as the value
assigned to the node symbol rather than just plain ``number.''
This was completely undocumented. The current version fixed the
tree matcher to recognize ``number'' as the correct value associated
with a node symbol.
6. Twig now uses dynamic initialization of costs rather than static
initialization. This permits the user to declare COST as structure.
7. Many cost metrics used in twig programs are additive. That is,
the cost of a match is some constant cost plus the sum of the
costs of the matches at the labelled leaves. The macros ZEROCOST, and
ADDCOST provide an easy way to implement this. For example, if costs
are integers, then the definition
#define ZEROCOST 1
#define ADDCOST(accum,y) (accum) += (y)
would cause twig to generate, for rules without a cost part, code that
calculate the default cost as one plus the sum of the costs of the
matches at the labelled leaves.
ZEROCOST, and ADDCOST must both be defined, if the above facility is
to be used. DEFAULT_COST must not be defined when ADDCOST is defined.
8. Changes made by Keutzer (allegra!keutzer) and Appel (research!appel)
modifications by keutzer:
char c ->int c
all over lex.c
varargs added in _mtG in walker.c
may be too expensive for some people.
code is not portable to a SUN4 without it however.
"short int"'s were changed to "short"'s for UTS compatability.
The NODE struct pointed to by a NODEPTR now needs a "mark" field.
A printTree(NODEPTR n) routine must also be supplied by the user.
If you were using the values of nodes in your symbols.h file
then the command
cc -g -c -DDUMPNAMES sym.c
should be used to compile sym.c.