![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to README CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / twig|
Return to README CVS log | Up to [Research Unix] / researchv10no / cmd / twig |
1.1 root 1: Installation Procedure
2: ----------------------
3: To install twig, you must decide in which directories to place:
4:
5: (1) the twig compiler binary, and
6: (2) the twig template files.
7:
8: Once you have made these two decisions, you should edit the makefile and
9: set the variable INSTALL to the value of (1), and the variable TEMPLATES to
10: (2). The definitions of INSTALL and TEMPLATES should be near the beginning
11: of the makefile. The installation can then be completed by typing:
12:
13: make install
14:
15: Once a user has written a twig specification, the command twig is used to
16: compile it. The compilation creates two files called walker.c,
17: containing several subroutines, and symbols.h, containing definitions.
18: Walker.c is compiled and linked with the rest of the user program, and
19: tree matching occurs when the user's program calls a subroutine called _match.
20: More details about twig specifications, and how to interface to the
21: subroutines in walker.c is given in the ``Twig Reference Manual'', AT&T Bell
22: Laboratories, Computing Science Technical Report #120.
23:
24: Addendum to the ``Twig Reference Manual''
25: -----------------------------------------
26:
27: 1. In a node declaration, the user can override the automatic numbering
28: of a node id by expliciting assigning a number using the ``= int''
29: construct. However, the user must then assign a number to all
30: of the node ids. In other words, the user must either assign
31: numbers to each of the node ids, or to none of them. The ids must
32: have unique numbers.
33:
34: 2. The default action of executing the labelled leaves from
35: right to left is inadequate. ``Execution,'' as used here, is in
36: the sense as described in the ``Twig Reference Manual.'' Although
37: one could simulate any execution order by using a top-down rule, and
38: explicitly requesting the execution of labelled leaves with the tDO
39: macro, it is tedious to do so. For example, implementing a Sethi-Ullman
40: style register allocator in such a fashion is extremely awkward.
41: To alleviate this tedium, reordering scheme has been proposed, and
42: implemented by Andrew Appel of Princeton University. It is included
43: in this version of twig.
44:
45: A function, ``_do'' performs the execution of the matches. This
46: function is part of the walker.c file generated by twig. In versions
47: of the walker without reordering, _do performs the call:
48:
49: _evalleaves(winner->lleaves);
50:
51: where winner->lleaves are the labelled leaves of the winning match.
52: Lleaves has type ``__match *[], '' and is a NULL terminated sequence
53: of matches for the labelled leaves in left to right order. Calling
54: tDO with an element of lleaves executes the match associated with
55: the labelled leaf.
56:
57: Reordering is accomplished by changing the call to _evalleaves with
58: the statement:
59:
60: REORDER(winner->lleaves);
61:
62: REORDER is a macro, or function defined by the user that may execute
63: the leaves in any order. If the user does not define REORDER then
64: twig will generate a default, which is to call _evalleaves.
65:
66: For example, if the user wishes to execute the leaves in the order of
67: decreasing cost, the following definition could be used.
68:
69: prologue {
70: ...
71: #define REORDER(list) reorder(list)
72: ...
73: }
74:
75: ...
76:
77: insert {
78:
79: reorder(list)
80: __match **list;
81: {
82: int i, j, n;
83: __match *index[16];
84:
85: /* copy list into index */
86: for(n=0; list[n]; n++) index[n] = list[n];
87:
88: /* insertion sort */
89: for(j=0;j<n;j++)
90: for(i=j; i>0; i--)
91: if(index[i]->cost > index[i-1]->cost) {
92: /* swap them */
93: __match *temp = index[i];
94: index[i] = index[i-1]; index[i-1] = p;
95: }
96:
97: /* now execute */
98: for(j=0;j<n;j++)
99: tDO(index[j]);
100: }
101:
102: }
103:
104:
105: 3. In a top-down rule, there is often a desire to execute all the
106: labelled leaves after performing some preparatory actions. This
107: could be done by saying
108:
109: tDO($%1$); tDO($%2$); ...
110:
111: However, the short hand notation, ``EVAL;'' provides the same function.
112:
113: 4. In the previous version of twig, Walker.c had a reference to
114: walker.h. Hence the user had to compile walker.c with the command:
115:
116: cc -Iinclude_dir -c walker.c
117:
118: where include_dir was the directory containing walker.h.
119: The reference to walker.h has been eliminated by inserting walker.h
120: into all the template files that could generate walker.c.
121: Therefore the new compile command is:
122:
123: cc -c walker.c
124:
125: 5. Twig assigns numbers to the node symbols, which are used to identify
126: nodes to the tree matcher. In the previous version of twig, the
127: tree matcher actually recognized ``M_NODE|number'' as the value
128: assigned to the node symbol rather than just plain ``number.''
129: This was completely undocumented. The current version fixed the
130: tree matcher to recognize ``number'' as the correct value associated
131: with a node symbol.
132:
133: 6. Twig now uses dynamic initialization of costs rather than static
134: initialization. This permits the user to declare COST as structure.
135:
136: 7. Many cost metrics used in twig programs are additive. That is,
137: the cost of a match is some constant cost plus the sum of the
138: costs of the matches at the labelled leaves. The macros ZEROCOST, and
139: ADDCOST provide an easy way to implement this. For example, if costs
140: are integers, then the definition
141:
142: #define ZEROCOST 1
143: #define ADDCOST(accum,y) (accum) += (y)
144:
145: would cause twig to generate, for rules without a cost part, code that
146: calculate the default cost as one plus the sum of the costs of the
147: matches at the labelled leaves.
148:
149: ZEROCOST, and ADDCOST must both be defined, if the above facility is
150: to be used. DEFAULT_COST must not be defined when ADDCOST is defined.
151:
152: 8. Changes made by Keutzer (allegra!keutzer) and Appel (research!appel)
153:
154: modifications by keutzer:
155:
156: char c ->int c
157: all over lex.c
158:
159: varargs added in _mtG in walker.c
160: may be too expensive for some people.
161: code is not portable to a SUN4 without it however.
162:
163: "short int"'s were changed to "short"'s for UTS compatability.
164:
165: The NODE struct pointed to by a NODEPTR now needs a "mark" field.
166:
167: A printTree(NODEPTR n) routine must also be supplied by the user.
168:
169: If you were using the values of nodes in your symbols.h file
170: then the command
171: cc -g -c -DDUMPNAMES sym.c
172: should be used to compile sym.c.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.