![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to kindling 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 kindling CVS log | Up to [Research Unix] / researchv10no / cmd / twig |
1.1 root 1: # To unbundle, sh this file
2: echo README 1>&2
3: sed 's/.//' >README <<'//GO.SYSIN DD README'
4: -Installation Procedure
5: -----------------------
6: -To install twig, you must decide in which directories to place:
7: -
8: -(1) the twig compiler binary, and
9: -(2) the twig template files.
10: -
11: -Once you have made these two decisions, you should edit the makefile and
12: -set the variable INSTALL to the value of (1), and the variable TEMPLATES to
13: -(2). The definitions of INSTALL and TEMPLATES should be near the beginning
14: -of the makefile. The installation can then be completed by typing:
15: -
16: - make install
17: -
18: -Once a user has written a twig specification, the command twig is used to
19: -compile it. The compilation creates two files called walker.c,
20: -containing several subroutines, and symbols.h, containing definitions.
21: -Walker.c is compiled and linked with the rest of the user program, and
22: -tree matching occurs when the user's program calls a subroutine called _match.
23: -More details about twig specifications, and how to interface to the
24: -subroutines in walker.c is given in the ``Twig Reference Manual'', AT&T Bell
25: -Laboratories, Computing Science Technical Report #120.
26: -
27: -Addendum to the ``Twig Reference Manual''
28: ------------------------------------------
29: -
30: -1. In a node declaration, the user can override the automatic numbering
31: - of a node id by expliciting assigning a number using the ``= int''
32: - construct. However, the user must then assign a number to all
33: - of the node ids. In other words, the user must either assign
34: - numbers to each of the node ids, or to none of them. The ids must
35: - have unique numbers.
36: -
37: -2. The default action of executing the labelled leaves from
38: - right to left is inadequate. ``Execution,'' as used here, is in
39: - the sense as described in the ``Twig Reference Manual.'' Although
40: - one could simulate any execution order by using a top-down rule, and
41: - explicitly requesting the execution of labelled leaves with the tDO
42: - macro, it is tedious to do so. For example, implementing a Sethi-Ullman
43: - style register allocator in such a fashion is extremely awkward.
44: - To alleviate this tedium, reordering scheme has been proposed, and
45: - implemented by Andrew Appel of Princeton University. It is included
46: - in this version of twig.
47: -
48: - A function, ``_do'' performs the execution of the matches. This
49: - function is part of the walker.c file generated by twig. In versions
50: - of the walker without reordering, _do performs the call:
51: -
52: - _evalleaves(winner->lleaves);
53: -
54: - where winner->lleaves are the labelled leaves of the winning match.
55: - Lleaves has type ``__match *[], '' and is a NULL terminated sequence
56: - of matches for the labelled leaves in left to right order. Calling
57: - tDO with an element of lleaves executes the match associated with
58: - the labelled leaf.
59: -
60: - Reordering is accomplished by changing the call to _evalleaves with
61: - the statement:
62: -
63: - REORDER(winner->lleaves);
64: -
65: - REORDER is a macro, or function defined by the user that may execute
66: - the leaves in any order. If the user does not define REORDER then
67: - twig will generate a default, which is to call _evalleaves.
68: -
69: - For example, if the user wishes to execute the leaves in the order of
70: - decreasing cost, the following definition could be used.
71: -
72: - prologue {
73: - ...
74: - #define REORDER(list) reorder(list)
75: - ...
76: - }
77: -
78: - ...
79: -
80: - insert {
81: -
82: - reorder(list)
83: - __match **list;
84: - {
85: - int i, j, n;
86: - __match *index[16];
87: -
88: - /* copy list into index */
89: - for(n=0; list[n]; n++) index[n] = list[n];
90: -
91: - /* insertion sort */
92: - for(j=0;j<n;j++)
93: - for(i=j; i>0; i--)
94: - if(index[i]->cost > index[i-1]->cost) {
95: - /* swap them */
96: - __match *temp = index[i];
97: - index[i] = index[i-1]; index[i-1] = p;
98: - }
99: -
100: - /* now execute */
101: - for(j=0;j<n;j++)
102: - tDO(index[j]);
103: - }
104: -
105: - }
106: -
107: -
108: -3. In a top-down rule, there is often a desire to execute all the
109: - labelled leaves after performing some preparatory actions. This
110: - could be done by saying
111: -
112: - tDO($%1$); tDO($%2$); ...
113: -
114: - However, the short hand notation, ``EVAL;'' provides the same function.
115: -
116: -4. In the previous version of twig, Walker.c had a reference to
117: - walker.h. Hence the user had to compile walker.c with the command:
118: -
119: - cc -Iinclude_dir -c walker.c
120: -
121: - where include_dir was the directory containing walker.h.
122: - The reference to walker.h has been eliminated by inserting walker.h
123: - into all the template files that could generate walker.c.
124: - Therefore the new compile command is:
125: -
126: - cc -c walker.c
127: -
128: -5. Twig assigns numbers to the node symbols, which are used to identify
129: - nodes to the tree matcher. In the previous version of twig, the
130: - tree matcher actually recognized ``M_NODE|number'' as the value
131: - assigned to the node symbol rather than just plain ``number.''
132: - This was completely undocumented. The current version fixed the
133: - tree matcher to recognize ``number'' as the correct value associated
134: - with a node symbol.
135: -
136: -6. Twig now uses dynamic initialization of costs rather than static
137: - initialization. This permits the user to declare COST as structure.
138: -
139: -7. Many cost metrics used in twig programs are additive. That is,
140: - the cost of a match is some constant cost plus the sum of the
141: - costs of the matches at the labelled leaves. The macros ZEROCOST, and
142: - ADDCOST provide an easy way to implement this. For example, if costs
143: - are integers, then the definition
144: -
145: - #define ZEROCOST 1
146: - #define ADDCOST(accum,y) (accum) += (y)
147: -
148: - would cause twig to generate, for rules without a cost part, code that
149: - calculate the default cost as one plus the sum of the costs of the
150: - matches at the labelled leaves.
151: -
152: - ZEROCOST, and ADDCOST must both be defined, if the above facility is
153: - to be used. DEFAULT_COST must not be defined when ADDCOST is defined.
154: -
155: -8. Changes made by Keutzer (allegra!keutzer) and Appel (research!appel)
156: -
157: - modifications by keutzer:
158: -
159: - char c ->int c
160: - all over lex.c
161: -
162: - varargs added in _mtG in walker.c
163: - may be too expensive for some people.
164: - code is not portable to a SUN4 without it however.
165: -
166: - "short int"'s were changed to "short"'s for UTS compatability.
167: -
168: - The NODE struct pointed to by a NODEPTR now needs a "mark" field.
169: -
170: - A printTree(NODEPTR n) routine must also be supplied by the user.
171: -
172: - If you were using the values of nodes in your symbols.h file
173: - then the command
174: - cc -g -c -DDUMPNAMES sym.c
175: - should be used to compile sym.c.
176: //GO.SYSIN DD README
177: echo code.c 1>&2
178: sed 's/.//' >code.c <<'//GO.SYSIN DD code.c'
179: -#include "common.h"
180: -#include "code.h"
181: -#define BLOCKSIZE 10
182: -
183: -Code *cdfreep = NULL;
184: -
185: -Code *
186: -CodeGetBlock()
187: -{
188: - static int count = 0;
189: - static Code *blockp = NULL;
190: - Code *cp;
191: -
192: - if(cdfreep!=NULL) {
193: - cp = cdfreep;
194: - cdfreep = cdfreep->prev;
195: - } else {
196: - if(count==0) {
197: - blockp = (Code *) malloc (BLOCKSIZE*sizeof(Code));
198: - count = BLOCKSIZE;
199: - }
200: - cp = blockp++;
201: - count--;
202: - }
203: - cp->prev = NULL;
204: - cp->firstFree = cp->segment;
205: - return(cp);
206: -}
207: -
208: -void
209: -CodeFreeBlock(cd)
210: - Code *cd;
211: -{
212: - if (cd!=NULL) {
213: - cd->prev = cdfreep;
214: - cdfreep = cd;
215: - }
216: -}
217: -
218: -Code *
219: -CodeStoreChar(cd, c)
220: - Code *cd;
221: - char c;
222: -{
223: - if(cd->firstFree - cd->segment >= CSEGSIZE) {
224: - Code *ncd = CodeGetBlock();
225: - ncd->prev = cd;
226: - cd = ncd;
227: - }
228: - *cd->firstFree = c;
229: - cd->firstFree++;
230: - return(cd);
231: -}
232: -
233: -Code *
234: -CodeStoreString(cd, s)
235: - Code *cd;
236: - char *s;
237: -{
238: - while(*s!='\0') cd = CodeStoreChar(cd, *s++);
239: - return(cd);
240: -}
241: -
242: -Code *
243: -CodeAppend(cd1, cd2)
244: - Code *cd1, *cd2;
245: -{
246: - if(cd2==NULL) return(cd1);
247: - cd2->prev = CodeAppend(cd1, cd2->prev);
248: - return(cd2);
249: -}
250: -
251: -void
252: -CodeWrite(f, cd)
253: - FILE *f;
254: - Code *cd;
255: -{
256: - register char *cp;
257: -
258: - if (cd != NULL)
259: - {CodeWrite(outfile, cd->prev);
260: - for(cp=cd->segment; cp < cd->firstFree; cp++)
261: - putc(*cp, f);
262: - }
263: -}
264: -
265: -Code *
266: -CodeMarkLine(cd,lineno)
267: - Code *cd;
268: - int lineno;
269: -{
270: - char buf[100];
271: - sprintf(buf,"\n# line %d \"%s\"\n", lineno, inFileName);
272: - return(CodeStoreString(cd,buf));
273: -}
274: //GO.SYSIN DD code.c
275: echo code.h 1>&2
276: sed 's/.//' >code.h <<'//GO.SYSIN DD code.h'
277: -#define CSEGSIZE 512-2*sizeof(int)
278: -
279: -typedef struct Code {
280: - struct Code *prev;
281: - char *firstFree;
282: - char segment[CSEGSIZE];
283: - } Code;
284: -
285: -extern Code *CodeStoreChar();
286: -extern Code *CodeGetBlock();
287: -extern Code *CodeAppend();
288: -extern Code *CodeStoreString(), *CodeMarkLine();
289: //GO.SYSIN DD code.h
290: echo common.h 1>&2
291: sed 's/.//' >common.h <<'//GO.SYSIN DD common.h'
292: -#include <stdio.h>
293: -#include <assert.h>
294: -
295: -#define MAXIDSIZE 100
296: -#define HASHSIZE 1181
297: -#define MAXPATH 32
298: -#define MAXBRANCH 10
299: -#define MAXACCEPTS 100
300: -#define MAXSTATES 200
301: -/* type definitions */
302: -typedef char byte;
303: -
304: -/* forward and external type defs */
305: -extern struct node *GetNode();
306: -extern struct edges *GetEdge();
307: -extern struct augmented_edges *GetAugEdges();
308: -extern char *malloc();
309: -extern char *strrchr();
310: -extern FILE *outfile;
311: -extern FILE *symfile;
312: -
313: -extern int debug_flag;
314: -# define DB_LEX 1 /* print out lexical analyser debugging info */
315: -# define DB_MACH 2 /* print out machine information */
316: -# define DB_SYM 4 /* print out symbol debugging info */
317: -# define DB_TREE 8 /* print out trees */
318: -# define DB_MEM 16 /* check memory usage */
319: -extern int tflag; /* generate tables only */
320: -extern int ntrees;
321: -extern int unique;
322: -
323: -/* tree definitions */
324: -typedef struct node Node;
325: -typedef struct symbol_entry SymbolEntry;
326: -
327: -/* Nodes provide the backbone for the trees built by the parser */
328: -struct node {
329: - SymbolEntry *sym;
330: - int nlleaves; /* count of the labelled leaves */
331: - Node *children;
332: - Node *siblings;
333: -};
334: -
335: -extern Node *TreeBuild();
336: -
337: -/* path defintions */
338: -extern void path_setup();
339: -
340: -/* lexical analyser */
341: -extern int yyline;
342: -extern char *inFileName;
343: -extern char token_buffer[MAXIDSIZE+1];
344: -
345: -extern void LexInit();
346: -extern yylex();
347: //GO.SYSIN DD common.h
348: echo doc 1>&2
349: sed 's/.//' >doc <<'//GO.SYSIN DD doc'
350: //GO.SYSIN DD doc
351: echo examples 1>&2
352: sed 's/.//' >examples <<'//GO.SYSIN DD examples'
353: //GO.SYSIN DD examples
354: echo io.c 1>&2
355: sed 's/.//' >io.c <<'//GO.SYSIN DD io.c'
356: -#include "common.h"
357: -#define MAXINTONLINE 10
358: -static int intcnt, intonline, firstint;
359: -
360: -oreset()
361: -{
362: - intcnt = 0;
363: - intonline = 0;
364: - firstint = 1;
365: -}
366: -
367: -ointcnt() { return(intcnt); }
368: -
369: -oputint(i)
370: -{
371: - if(!firstint) putc(',', outfile);
372: - else firstint = 0;
373: - fprintf(outfile, "%d", i);
374: - intonline++;
375: - intcnt++;
376: - if(intonline >= MAXINTONLINE) { putc('\n', outfile); intonline = 0; }
377: -}
378: -
379: -oputoct(i)
380: -{
381: - if(!firstint) putc(',', outfile);
382: - else firstint = 0;
383: - fprintf(outfile, "0%o", i);
384: - intonline++;
385: - intcnt++;
386: - if(intonline >= MAXINTONLINE) { putc('\n', outfile); intonline = 0; }
387: -}
388: //GO.SYSIN DD io.c
389: echo lex.c 1>&2
390: sed 's/.//' >lex.c <<'//GO.SYSIN DD lex.c'
391: -#include <ctype.h>
392: -#include "common.h"
393: -#include "code.h"
394: -#include "sym.h"
395: -#include "y.tab.h"
396: -
397: -int yyline = 1;
398: -char token_buffer[MAXIDSIZE+1];
399: -extern YYSTYPE yylval;
400: -static void ScanCodeBlock();
401: -static void ScanComment();
402: -static Code *curCdBlock;
403: -static char get();
404: -
405: -yylex()
406: -{
407: - register c;
408: - register char *cp;
409: - int in_ident = 0;
410: - yylval.y_nodep = (struct node *) NULL;
411: - cp = token_buffer;
412: - while((c=getchar())!=EOF) {
413: - switch(c) {
414: - case ' ': case '\t': case '\f':
415: - continue;
416: - case '@': case '[': case ']': case ';': case ':':
417: - case '(': case ')': case ',': case '=':
418: - case '*':
419: - if(debug_flag&DB_LEX) {
420: - putc(c,stderr);
421: - putc('\n', stderr);
422: - }
423: - *cp++ = c;
424: - *cp = '\0';
425: - return(c);
426: -
427: - case '{':
428: - ScanCodeBlock();
429: - yylval.y_code = curCdBlock;
430: - curCdBlock = NULL;
431: - *cp++ = '{'; *cp++ = '}';
432: - return(CBLOCK);
433: -
434: - case '\n':
435: - yyline++;
436: - continue;
437: - case '/':
438: - if ((c=getchar())=='*') {
439: - ScanComment(get);
440: - continue;
441: - } else {
442: - ungetc(c, stdin);
443: - c = '/';
444: - }
445: - /* FALL THRU */
446: -
447: - default:
448: - if (isdigit(c)) {
449: - int errs = 0;
450: - do {
451: - if(cp > &token_buffer[MAXIDSIZE]) {
452: - token_buffer[MAXIDSIZE] = '\0';
453: - yyerror("number too long");
454: - errs++;
455: - } else *cp++ = c;
456: - c = getchar();
457: - } while (isdigit(c));
458: - if(isalpha(c))
459: - yyerror2("illegal digit '%c'", c);
460: - ungetc(c, stdin);
461: - if(errs)
462: - return(ERROR);
463: - yylval.y_int = atoi(token_buffer);
464: - return(NUMBER);
465: - }
466: - if (isalpha(c)) {
467: - SymbolEntry *sp;
468: - int errs = 0;
469: - do {
470: - if(cp > &token_buffer[MAXIDSIZE]) {
471: - token_buffer[MAXIDSIZE] = '\0';
472: - yyerror("ID too long");
473: - errs++;
474: - } else *cp++ = c;
475: - c = getchar();
476: - } while (isalpha(c)||isdigit(c)||c=='_');
477: - ungetc(c, stdin);
478: - if(errs)
479: - return(ERROR);
480: - *cp = '\0';
481: -
482: - sp = SymbolLookup (token_buffer);
483: - if (sp==NULL) {
484: - /* undefined */
485: - yylval.y_symp = SymbolAllocate(token_buffer);
486: - } else {
487: - /* already defined */
488: - if (sp->attr == A_KEYWORD)
489: - return (sp->sd.keyword);
490: - yylval.y_symp = sp;
491: - }
492: - if(debug_flag&DB_LEX)
493: - fprintf(stderr, "ID\n");
494: - return(ID);
495: - }
496: - yyerror2("illegal character (\\%03o)", c);
497: - }
498: - }
499: - strcpy(token_buffer, "EOF");
500: - return(0);
501: -}
502: -
503: -void
504: -LexInit()
505: -{
506: -}
507: -
508: -lexCleanup()
509: -{
510: -}
511: -
512: -/*
513: - * Beware: ungets of the characters from these routines may screw up the
514: - * line count
515: - */
516: -static char
517: -getput()
518: -{
519: - /* keutzer
520: - char c;
521: - */
522: - int c;
523: - c = getchar();
524: - if(c=='\n') yyline++;
525: - if(c!=EOF)
526: - curCdBlock = CodeStoreChar(curCdBlock, c);
527: - return(c);
528: -}
529: -
530: -static char
531: -get()
532: -{
533: - /* keutzer
534: - char c;
535: - */
536: - int c;
537: - c = getchar();
538: - if(c=='\n') yyline++;
539: - return(c);
540: -}
541: -
542: -extern int nerrors;
543: -
544: -static void
545: -ScanComment(rdfunc)
546: - char (*rdfunc)();
547: -{
548: - int startline = yyline;
549: - /* keutzer
550: - char c;
551: - */
552: - int c;
553: - int saw_star = 0;
554: - while ((c=rdfunc())!=EOF) {
555: - if (c=='*')
556: - saw_star++;
557: - else if(c=='/' && saw_star) {
558: - return;
559: - } else saw_star = 0;
560: - }
561: - yyerror2("unexpected EOF in comment beginning on line %d", startline);
562: - nerrors++;
563: - cleanup(1);
564: -}
565: -
566: -static
567: -ScanString(rdfunc)
568: - char (*rdfunc)();
569: -{
570: - int startline = yyline;
571: - /* keutzer
572: - char c;
573: - */
574: - int c;
575: - int saw_backsl = 0;
576: -
577: - while((c=rdfunc())!=EOF) {
578: - if (c=='"' && !saw_backsl)
579: - return;
580: - if (c=='\\' && !saw_backsl) {
581: - saw_backsl = 1;
582: - continue;
583: - }
584: - saw_backsl = 0;
585: - }
586: - /* fall thru due to EOF */
587: - yyerror2("unexpected EOF in string beginning on line %d", startline);
588: - nerrors++;
589: - cleanup(1);
590: -}
591: -
592: -static
593: -ScanChar()
594: -{
595: - int startline = yyline;
596: - /* keutzer
597: - char c;
598: - */
599: - int c;
600: - int saw_backsl = 0;
601: -
602: - while((c=getput(stdin))!=EOF) {
603: - if (c=='\'' && !saw_backsl)
604: - return;
605: - if (c=='\\' && !saw_backsl) {
606: - saw_backsl = 1;
607: - continue;
608: - }
609: - saw_backsl = 0;
610: - }
611: - /* fall thru due to EOF */
612: - yyerror2("unexpected EOF in character constant beginning on line %d",
613: - startline);
614: - nerrors++;
615: - cleanup(1);
616: -}
617: -
618: -static void
619: -ScanTreeReference()
620: -{
621: -
622: - /* keutzer
623: - char c;
624: - */
625: - int c;
626: - c = getchar();
627: - if(c=='%') {
628: - curCdBlock = CodeStoreString (curCdBlock, "_ll[(");
629: - while ((c=getchar())!=EOF && c!='$') {
630: - if(!isdigit(c)) {
631: - yyerror("unclosed $ reference");
632: - ungetc(c,stdin);
633: - break;
634: - }
635: - curCdBlock = CodeStoreChar(curCdBlock, c);
636: - }
637: - curCdBlock = CodeStoreString (curCdBlock, ")-1]");
638: - return;
639: - }
640: - else if(c=='$') {
641: - curCdBlock = CodeStoreString(curCdBlock, "root");
642: - return;
643: - } else curCdBlock = CodeStoreString(curCdBlock, "_mtG(root,");
644: - do {
645: - if(!isdigit(c) && c!='.') {
646: - yyerror("unclosed $ reference");
647: - ungetc(c,stdin);
648: - break;
649: - }
650: - curCdBlock = CodeStoreChar(curCdBlock, c=='.' ? ',' : c);
651: - } while((c=getchar())!=EOF && c!='$');
652: - curCdBlock = CodeStoreString(curCdBlock, ", -1)");
653: -}
654: -
655: -static void
656: -ScanCodeBlock()
657: -{
658: - int startline = yyline;
659: - /* keutzer
660: - char c;
661: - */
662: - int c;
663: - if(curCdBlock==NULL) {
664: - curCdBlock = CodeGetBlock();
665: - curCdBlock = CodeMarkLine(curCdBlock,yyline);
666: - }
667: - while((c=getc(stdin))!=EOF) {
668: - if (c=='}')
669: - return;
670: - else if (c=='$') ScanTreeReference();
671: - else curCdBlock = CodeStoreChar(curCdBlock, c);
672: - if (c=='\n') yyline++;
673: - if (c=='"') ScanString(getput);
674: - else if (c=='\'') ScanChar();
675: - else if (c=='/') {
676: - if ((c=getc(stdin))=='*') {
677: - curCdBlock = CodeStoreChar(curCdBlock, '*');
678: - ScanComment(getput);
679: - }
680: - else ungetc(c, stdin);
681: - }
682: - else if (c=='{') {
683: - ScanCodeBlock();
684: - curCdBlock = CodeStoreChar (curCdBlock, '}');
685: - }
686: - }
687: - yyerror2("{ on line %d has no closing }", startline);
688: - nerrors++;
689: -}
690: //GO.SYSIN DD lex.c
691: echo machcomm.h 1>&2
692: sed 's/.//' >machcomm.h <<'//GO.SYSIN DD machcomm.h'
693: -/*
694: - * The machine is laid out as a sequence of integers in the walker.
695: - * The form described above is only used inside the preprocessor.
696: - * Each machine state is one of the following sequence:
697: - *
698: - * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
699: - * or
700: - * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
701: - * or
702: - * ACCEPT <accept table index> -1
703: - *
704: - * The accept table is in the form:
705: - *
706: - * <tree index_1> ...<tree_index_m> -1
707: - *
708: - */
709: -
710: -#define FASTLIM 0
711: -#define TABLE 1
712: -#define FAIL 2
713: -#define ACCEPT 3
714: -#define TABLE2 4
715: -#define EOT -1
716: -
717: -/* special machine state */
718: -#define HANG -1
719: -
720: -/* used by the evaluator to interpret path table */
721: -#define eSTOP 0
722: -#define ePOP -1
723: -#define eEVAL -2
724: -#define eNEXT -3
725: -#define ePUSH -4
726: -
727: -/* Tags that indicate the type of a value */
728: -#define M_BRANCH 010000
729: -#define M_NODE 0
730: -#define M_LABEL 01000
731: -#define MAX_NODE_VALUE 00777
732: -#define MTAG_SHIFT 9
733: -#define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE))
734: -
735: -/* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */
736: -#define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0)
737: -#define MI_DEFINED(x) ((x)!=-1)
738: -#define MI_LABEL(x) (((x)&M_LABEL)!=0)
739: -#define MI_BRANCH(x) (((x)&M_BRANCH)!=0)
740: -
741: -/* build a tagged value */
742: -#define MV_NODE(x) (x)
743: -#define MV_BRANCH(x) ((x)|M_BRANCH)
744: -#define MV_LABEL(x) ((x)|M_LABEL)
745: -
746: //GO.SYSIN DD machcomm.h
747: echo machine.c 1>&2
748: sed 's/.//' >machine.c <<'//GO.SYSIN DD machine.c'
749: -#include "common.h"
750: -#include "code.h"
751: -#include "sym.h"
752: -#include "machine.h"
753: -
754: -int gen_table2; /* generate type two tables */
755: -struct machine_node *machine = NULL;
756: -static int depth;
757: -
758: -static struct machine_node *
759: -get_state()
760: -{
761: - struct machine_node *mp = (struct machine_node *)
762: - malloc (sizeof (struct machine_node));
763: - assert (mp!=NULL);
764: - mp->inp.value = -1;
765: - mp->nst = NULL;
766: - mp->link = NULL;
767: - mp->fail = NULL;
768: - mp->match = NULL;
769: - return(mp);
770: -}
771: -
772: -add_match(s, tp, depth)
773: - struct machine_node *s;
774: - LabelData *tp;
775: - int depth;
776: -{
777: - struct match *mp = (struct match *) malloc (sizeof (struct match));
778: -
779: - assert (mp!=NULL);
780: - mp->next = s->match;
781: - mp->depth = depth;
782: - mp->tree = tp;
783: - s->match = mp;
784: -}
785: -
786: -/*
787: - * Build a trie from the path strings. Failure transition are added later.
788: - */
789: -cgotofn(tp)
790: - LabelData *tp;
791: -{
792: - struct machine_input inp;
793: - int ret;
794: - register struct machine_node *s;
795: - register int quit = 0;
796: -
797: - if (machine==NULL) {
798: - /* first time thru */
799: - machine = get_state();
800: - }
801: - s = machine;
802: - depth = -1;
803: -
804: - assert (tp->tree!=NULL);
805: - path_setup (tp->tree);
806: -
807: - for(;;) {
808: - ret = path_getsym(&inp);
809: -
810: - /* no more paths */
811: - if (ret == EOF)
812: - break;
813: -
814: - if (ret == NULL) {
815: - /*
816: - * the end of the path. Add a match to the
817: - * accepting state.
818: - */
819: - assert ((depth&01)==0); /* make sure it's even */
820: - add_match(s, tp, depth >> 1);
821: - s = machine;
822: - depth = -1;
823: - ntrees++;
824: - continue;
825: - }
826: -
827: - while (!MI_EQUAL(s->inp, inp)) {
828: - if (!MI_DEFINED(s->inp.value) || s->link == NULL) {
829: - if (MI_DEFINED(s->inp.value)) {
830: - /*
831: - * The trie must be split here
832: - */
833: - s->link = get_state();
834: - s = s->link;
835: - }
836: - /*
837: - * Fill in the state
838: - */
839: - s->inp = inp;
840: - s->nst = get_state();
841: - s = s->nst;
842: - depth++;
843: - break;
844: - } else s = s->link;
845: - }
846: - if (MI_EQUAL(s->inp, inp)) {
847: - s = s->nst;
848: - depth++;
849: - }
850: - }
851: -}
852: -
853: -/* print out the machine for debugging */
854: -machine_print(mp)
855: - struct machine_node *mp;
856: -{
857: - register struct machine_node *mp2;
858: - struct machine_node *fail;
859: - struct match *match, *p;
860: -
861: - if (mp==NULL)
862: - return;
863: - printf("%x %d:", mp, mp->index);
864: - if((fail = mp->fail))
865: - printf("\tfail %x", fail);
866: - if((match = mp->match)) {
867: - printf("\taccept ");
868: - for(p = match; p!=NULL; p = p->next) {
869: - LabelData *tp = p->tree;
870: - printf("%s ", (tp->label)->name);
871: - }
872: - }
873: - putchar('\n');
874: - for(mp2=mp; mp2!=NULL; mp2 = mp2->link) {
875: - if (MI_DEFINED(mp2->inp.value)) {
876: - if (MI_BRANCH(mp->inp.value))
877: - printf(" %d -> ", mp2->inp.value);
878: - else
879: - printf(" [%s] -> ", (mp2->inp.sym)->name);
880: - printf("%x", mp2->nst);
881: - }
882: - assert(mp2->fail==fail);
883: - assert(mp2->match==match);
884: - }
885: - if(MI_DEFINED(mp->inp.value))
886: - putchar('\n');
887: - for (mp2 = mp; mp2!=NULL; mp2=mp2->link) {
888: - machine_print(mp2->nst);
889: - }
890: -}
891: -
892: -/*
893: - * This routine augments the machine with failure transition.
894: - * The trie is examined in breadth first order.
895: - * See Aho, Corasick Comm ACM 18:6 for details
896: - */
897: -cfail()
898: -{
899: - struct machine_node **stack, **stack2;
900: - struct machine_node **stackTop, **stack2Top, **temp;
901: - int stackCnt, stack2Cnt;
902: - struct machine_node *state;
903: - struct machine_input sym;
904: - register struct machine_node *s, *q;
905: -
906: - /* allocate stacks */
907: - stackTop = stack = (struct machine_node **) malloc
908: - (ntrees*sizeof (struct machine_node *));
909: - stack2 = stack2Top = (struct machine_node **) malloc
910: - (ntrees*sizeof (struct machine_node *));
911: - stackCnt = stack2Cnt = 0;
912: - s = machine;
913: - do {
914: - if (MI_DEFINED(s->inp.value)) {
915: - assert(++stackCnt <= ntrees);
916: - *stackTop++ = s->nst;
917: - }
918: - s = s->link;
919: - } while (s != NULL);
920: -
921: - for(;;) {
922: - if (stackCnt == 0) {
923: - /* swap stacks */
924: - if (stack2Cnt == 0)
925: - break;
926: - stackCnt = stack2Cnt; stack2Cnt = 0;
927: - stackTop = stack2Top;
928: - temp = stack; stack = stack2; stack2 = temp;
929: - stack2Top = stack2;
930: - }
931: - stackCnt--;
932: - s = *--stackTop;
933: - do {
934: - int startstate = 0;
935: - sym = s->inp;
936: - if (MI_DEFINED(sym.value)) { /* g(s,c) != 0 */
937: - assert (++stack2Cnt <= ntrees);
938: - *stack2Top++ = (q=s->nst);
939: - state = s->fail; /* state = f(s) */
940: - for(;;) {
941: - if (state == 0) {
942: - state = machine;
943: - startstate++;
944: - }
945: - if (MI_EQUAL(state->inp, sym)) {
946: - struct match *mp = NULL;
947: -
948: - /* append any accepting matches */
949: - for(mp=(state->nst)->match;mp;mp=mp->next)
950: - add_match(q,mp->tree, mp->depth);
951: - mp = q->match;
952: -
953: - do {
954: - /* f(q) = g(state,sym)
955: - * for all q links */
956: - q->fail = state->nst;
957: - q->match = mp;
958: - } while ((q = q->link) != 0);
959: - break;
960: - }
961: - else if (state->link != 0)
962: - state = state->link;
963: - else {
964: - state = state->fail;
965: - if (state==NULL&&startstate)
966: - break;
967: - }
968: - }
969: - }
970: - s = s->link;
971: - } while (s!=NULL);
972: - }
973: -}
974: -
975: -/*
976: - * Called from the YACC rule pattern_spec
977: - */
978: -void
979: -machine_build()
980: -{
981: - cfail();
982: - (void) MachineNumber(machine, 0);
983: - if(debug_flag&DB_MACH) {
984: - fputs("\n-------\n", stderr);
985: - machine_print(machine);
986: - }
987: -}
988: -
989: -struct match *acceptTable[MAXACCEPTS];
990: -struct match **acceptTableTop = acceptTable;
991: -static short int *arityTable;
992: -int nextAcceptIndex = 0;
993: -
994: -/*
995: - * This is the first pass of the process to generate the
996: - * flattened machine used in the walker. Called from machine_build
997: - */
998: -int
999: -MachineNumber(mach, index)
1000: - struct machine_node *mach;
1001: - int index;
1002: -{
1003: - struct machine_node *mp;
1004: -
1005: - for(mp=mach; mp!=NULL; mp = mp->link)
1006: - if(MI_DEFINED(mp->inp.value))
1007: - index = MachineNumber(mp->nst, index);
1008: -
1009: - mach->index = index;
1010: - if (mach->match!=NULL) index += 2;
1011: - if(mach->link!=NULL || mach->nst!=NULL) {
1012: - index += 2;
1013: - for(mp = mach; mp!=NULL; mp = mp->link)
1014: - if(mp->nst!=NULL)
1015: - index += 2;
1016: - }
1017: -
1018: - if (mach->fail!=NULL)
1019: - index += 2;
1020: - index++;
1021: - return(index);
1022: -}
1023: -
1024: -/*
1025: - * Build the flattened out machine used in the walker.
1026: - * See machine.h for description
1027: - */
1028: -MachineGen()
1029: -{
1030: - struct match **atp, *ap;
1031: - short int *sp;
1032: -
1033: - oreset();
1034: - fputs("short int mtTable[] = {\n", outfile);
1035: - machineGen2(machine);
1036: - fputs("};\n", outfile);
1037: -
1038: - fputs("short int mtAccept[] = {\n", outfile);
1039: -
1040: - oreset();
1041: - for(atp = acceptTable; atp < acceptTableTop; atp++) {
1042: - for(ap = *atp; ap!=NULL; ap = ap->next) {
1043: - register LabelData *tree = ap->tree;
1044: -
1045: - /* if you change any of the code below you must change
1046: - * the increment added to nextAcceptIndex in
1047: - * machineGen2
1048: - */
1049: - oputint(tree->treeIndex);
1050: - oputint(ap->depth);
1051: - }
1052: - oputint(-1);
1053: - }
1054: - fprintf(outfile, "};\nshort int mtStart = %d;\n", machine->index);
1055: -}
1056: -
1057: -machineGen2(mach)
1058: - struct machine_node *mach;
1059: -{
1060: - struct machine_node *mp;
1061: - struct match *ap;
1062: -
1063: - if (mach==NULL)
1064: - return;
1065: -
1066: - for(mp=mach; mp!=NULL; mp = mp->link)
1067: - if(MI_DEFINED(mp->inp.value))
1068: - machineGen2(mp->nst);
1069: -
1070: - assert(mach->index == ointcnt());
1071: - if (mach->match!=NULL) {
1072: - *acceptTableTop++ = mach->match;
1073: - oputint(ACCEPT); oputint(nextAcceptIndex);
1074: - for(ap = mach->match; ap!=NULL; ap = ap->next)
1075: - nextAcceptIndex += 2;
1076: - nextAcceptIndex++;
1077: - }
1078: - if(mach->link!=NULL || mach->nst!=NULL) {
1079: - if(MI_BRANCH(mp->inp.value)&&gen_table2) {
1080: - oputint (TABLE2);
1081: - for(mp = mach; mp!=NULL; mp = mp->link) {
1082: - if(mp->nst!=NULL) {
1083: - oputoct(mp->inp.value);
1084: - oputint((mp->nst)->index);
1085: - }
1086: - }
1087: - } else {
1088: - oputint (TABLE);
1089: - for(mp = mach; mp!=NULL; mp = mp->link) {
1090: - if(mp->nst!=NULL) {
1091: - oputoct(mp->inp.value);
1092: - oputint((mp->nst)->index);
1093: - }
1094: - }
1095: - }
1096: - oputint(-1);
1097: - }
1098: -
1099: - /* A failure transition or a -1 terminate every state */
1100: - if (mach->fail!=NULL) {
1101: - oputint(FAIL); oputint((mach->fail)->index);
1102: - }
1103: - oputint(-1);
1104: -}
1105: //GO.SYSIN DD machine.c
1106: echo machine.h 1>&2
1107: sed 's/.//' >machine.h <<'//GO.SYSIN DD machine.h'
1108: -/*
1109: - * The machine used here is the same as the one used in fgrep.
1110: - * Logically, it is a trie of all the strings to be recognized.
1111: - * In this case, the strings are the paths of tree patterns.
1112: - * The nodes of the trie are the states of the machine and leaves
1113: - * are accepting states. The trie is augmented by failure transitions.
1114: - *
1115: - * Each machine state is a linked list of machine_node's and referred to
1116: - * by pointing to the head of the list. The machine_node represents a
1117: - * transition. The nst field points to the next state when the current
1118: - * input is MI_EQUAL to the inp field. If the input is not MI_EQUAL to any
1119: - * of the inp fields in the list, the next state is the one that fail
1120: - * points to. The fail field must be the same for all machine_node's in
1121: - * a state. Accepting states have inp.value equal to -1, and the match
1122: - * field points to a list of match structures. The match structures record
1123: - * which trees have been partially matched.
1124: - *
1125: - * The index is used by the machine generator to convert the machine into
1126: - * a list of integers.
1127: - *
1128: - * Further details about the data structure and algorithms can be
1129: - * found in:
1130: - * Knuth, Morris, Pratt in SIAM J Computing 6:3
1131: - * Aho, Corasick in Comm ACM 18:6
1132: - * Hoffman, O'Donnell in JACM 29:1
1133: - */
1134: -struct machine_input {
1135: - short value;
1136: - struct symbol_entry *sym;
1137: -};
1138: -#define MI_EQUAL(x,y) ((x).value==(y).value)
1139: -
1140: -#include "machcomm.h"
1141: -
1142: -extern int path_getsym();
1143: -
1144: -struct machine_node {
1145: - struct machine_input inp;
1146: - struct machine_node *nst;
1147: - struct machine_node *link;
1148: - struct machine_node *fail;
1149: - struct match *match;
1150: - short int index;
1151: -};
1152: -
1153: -struct match {
1154: - struct match *next;
1155: - short int depth;
1156: - LabelData *tree;
1157: -};
1158: -
1159: -extern struct machine_node *machine;
1160: -
1161: -extern void machine_build();
1162: //GO.SYSIN DD machine.h
1163: echo makefile 1>&2
1164: sed 's/.//' >makefile <<'//GO.SYSIN DD makefile'
1165: -#
1166: -CC= cc
1167: -INSTALL= /usr/bin
1168: -TEMPLATES = /usr/lib/twig
1169: -SRCS= twig.y sym.c path.c machine.c trees.c lex.c code.c io.c mem.c
1170: -OBJS= y.tab.o sym.o path.o machine.o trees.o lex.o code.o io.o mem.o
1171: -HDRS= common.h code.h sym.h machine.h mem.h
1172: -PREFIX= \"$(TEMPLATES)/walker\"
1173: -
1174: -all: twig
1175: -
1176: -install: twig
1177: - mv twig $(INSTALL)
1178: - mv walker.c1 $(TEMPLATES)
1179: -
1180: -kindling:
1181: - bundle README makefile *.y *.c *.h rawwalker.* >kindling
1182: -
1183: -sym.h: code.h
1184: -machine.h: machcomm.h
1185: - touch machine.h
1186: -
1187: -machine.o: common.h sym.h machine.h machine.c
1188: - $(CC) -g -c machine.c
1189: -
1190: -path.o: common.h sym.h path.c
1191: - $(CC) -g -c path.c
1192: -
1193: -y.tab.h: common.h sym.h twig.y
1194: - yacc -d twig.y
1195: -
1196: -y.tab.c: y.tab.h common.h sym.h twig.y
1197: -y.tab.o: y.tab.c
1198: - $(CC) -DPREFIX_BASE=$(PREFIX) -g -c y.tab.c
1199: -
1200: -sym.o: common.h sym.h y.tab.h sym.c
1201: - $(CC) -g -c sym.c
1202: -
1203: -trees.o: common.h sym.h
1204: - $(CC) -g -c trees.c
1205: -
1206: -lex.o: common.h sym.h y.tab.h lex.c
1207: - $(CC) -g -c lex.c
1208: -
1209: -code.o: common.h code.h
1210: - $(CC) -g -c code.c
1211: -
1212: -io.o: common.h io.c
1213: - $(CC) -g -c io.c
1214: -
1215: -mem.o: common.h mem.c
1216: - $(CC) -g -c mem.c
1217: -
1218: -twig: $(OBJS)
1219: - $(CC) -g -o twig $(OBJS)
1220: -
1221: -# generate walker from templates
1222: -walker.c1: machcomm.h walker.h rawwalker.c1
1223: - cat machcomm.h walker.h rawwalker.c1 >walker.c1
1224: -
1225: -walker.ex: machcomm.h walker.h rawwalker.ex
1226: - cat machcomm.h walker.h rawwalker.ex >walker.ex
1227: -
1228: -# at bell labs only
1229: -print:
1230: - pr makefile $(HDRS) $(SRCS) | 4can
1231: -bell_print:
1232: - pp makefile $(HDRS) $(SRCS) | dcan
1233: -
1234: -# at stanford only
1235: -enscript:
1236: - enscript -Pbt -2r makefile $(HDRS) $(SRCS)
1237: -
1238: //GO.SYSIN DD makefile
1239: echo mem.c 1>&2
1240: sed 's/.//' >mem.c <<'//GO.SYSIN DD mem.c'
1241: -#include <stdio.h>
1242: -#include <assert.h>
1243: -#include "mem.h"
1244: -
1245: -#define BLKF 100
1246: -
1247: -static struct _mem *mlist;
1248: -
1249: -static void
1250: -zap(cp,size)
1251: - char *cp;
1252: - int size;
1253: -{
1254: - for(;size>0;size--) {
1255: - *cp = 0xff;
1256: - }
1257: -}
1258: -void
1259: -mem_init(mp, size)
1260: - struct _mem *mp;
1261: - int size;
1262: -{
1263: - int i, s;
1264: - assert(size>=4);
1265: - mp->size = s = size;
1266: - s *= BLKF;
1267: - for (i=1; i < s; i <<= 1);
1268: - mp->bsize = i;
1269: - mp->blkf = mp->bsize/size;
1270: - mp->cnt = 0;
1271: - mp->freelist = NULL;
1272: - mp->totelem = 0;
1273: - mp->freecnt = 0;
1274: - mp->next = mlist;
1275: - mlist = mp;
1276: -};
1277: -
1278: -char *
1279: -mem_get(mp)
1280: - struct _mem *mp;
1281: -{
1282: - char *cp;
1283: - if (mp->freelist!=NULL) {
1284: - cp = mp->freelist;
1285: - mp->freelist = *(char **) cp;
1286: - mp->freecnt--;
1287: - zap(cp,mp->size);
1288: - return(cp);
1289: - } else if (mp->cnt==0) {
1290: - mp->block = (char *)malloc(mp->bsize);
1291: - mp->cnt = mp->blkf;
1292: - mp->totelem += mp->blkf;
1293: - }
1294: - mp->cnt--;
1295: - cp = mp->block;
1296: - mp->block += mp->size;
1297: - zap(cp,mp->size);
1298: - return(cp);
1299: -}
1300: -
1301: -mem_free(mp, cp)
1302: - struct _mem *mp;
1303: - char *cp;{
1304: - *(char **)cp = mp->freelist;
1305: - mp->freelist = cp;
1306: - mp->freecnt++;
1307: -}
1308: -
1309: -mem_outstanding(mp)
1310: - struct _mem *mp;
1311: -{
1312: - /* returns elements that are outstanding..i.e. asked for
1313: - * but haven't yet been returned
1314: - */
1315: - return(mp->totelem - (mp->cnt+mp->freecnt));
1316: -}
1317: -
1318: -mem_epilogue()
1319: -{
1320: - struct _mem *mp;
1321: - /*
1322: - * if the following assertion fails then one of the following
1323: - * has happened:
1324: - * 1) somebody forgot to free something or
1325: - * 2) there is leakage.
1326: - */
1327: - for(mp=mlist; mp!=NULL; mp = mp->next) {
1328: - assert(mem_outstanding(mp)==0);
1329: - }
1330: -}
1331: //GO.SYSIN DD mem.c
1332: echo mem.h 1>&2
1333: sed 's/.//' >mem.h <<'//GO.SYSIN DD mem.h'
1334: -struct _mem {
1335: - struct _mem *next;
1336: - int size; /* size of individual elements in bytes */
1337: - int blkf; /* blocking factor */
1338: - int bsize; /* block size */
1339: - char *block; /* block */
1340: - int cnt; /* count of free elem in block */
1341: - char *freelist; /* free list */
1342: - int totelem; /* total number elements we have */
1343: - int freecnt; /* number of times mem_free was called */
1344: -};
1345: //GO.SYSIN DD mem.h
1346: echo path.c 1>&2
1347: sed 's/.//' >path.c <<'//GO.SYSIN DD path.c'
1348: -#include <stdio.h>
1349: -#include "common.h"
1350: -#include "code.h"
1351: -#include "sym.h"
1352: -#include "machine.h"
1353: -
1354: -/*
1355: - * Routines to enumerate paths of a tree. Firt call path_setup to
1356: - * initialize the internal data structure. Each component of the
1357: - * path may be consecutively retrieved by calling path_getsym.
1358: - */
1359: -
1360: -/*
1361: - * For trees, a path is defined to be the sequence of nodes and edges
1362: - * from the root to a leaf. A path is represented here as a list of
1363: - * path components. Each component is represented by the following
1364: - * strucutre and may either be a pointer to a node or an integer.
1365: - * If the integer is i then the next component is the ith child of the
1366: - * previous component in the list. For example, "a 3 b 1 c" is a path
1367: - * for the tree "a(x,y,b(c,k))". The tag field indicates whether the
1368: - * component is a node or a branch.
1369: - * When the component represents a node then the node field points
1370: - * the corresponding Node structure. When the component is a branch then
1371: - * branch is the index of the current branch followed (1 is leftmost...)
1372: - * and node is a list of all unexamined children.
1373: - */
1374: -struct path {
1375: - int tag;
1376: -#define P_NODE 0
1377: -#define P_BRANCH 1
1378: - int branch;
1379: - Node *node;
1380: -};
1381: -
1382: -/*
1383: - * The path component list is stored in the path array. Path_length
1384: - * is the length of the path. Path_ptr points to the first unread
1385: - * component of the path component list. (see path_getsym
1386: - * and path_build for details)
1387: - */
1388: -struct path path[2*MAXPATH];
1389: -static int path_length;
1390: -static struct path *path_ptr = NULL;
1391: -
1392: -/*
1393: - * Given a tree, path_setup updates the path array with the leftmost
1394: - * of a subtree starting at root. The leftmost path is produced by
1395: - * following the leftmost branch of every encountered interior node
1396: - * starting at the root. Note that this routine can be used to layout
1397: - * the leftmost branch of a subtree into part of the path array and for
1398: - * initializing the path array with the leftmost path of the whole tree.
1399: - */
1400: -void
1401: -path_setup(root)
1402: - Node *root;
1403: -{
1404: - for(;;) {
1405: - register struct path *pp = &path[path_length++];
1406: - Node *ep;
1407: - assert (root!=NULL);
1408: -
1409: - /* Place node in the component list */
1410: - pp->tag = P_NODE;
1411: - pp->node = root;
1412: -
1413: - /* If leaf encountered exit */
1414: - if ((ep=root->children)==NULL)
1415: - break;
1416: -
1417: - /*
1418: - * Mark that the left branch (i.e. 1st in our numbering
1419: - * scheme) was followed.
1420: - */
1421: - pp = &path[path_length++];
1422: - pp->tag = P_BRANCH;
1423: - pp->branch = 1;
1424: - pp->node = ep->siblings;
1425: - root = ep;
1426: - }
1427: - path_ptr = path;
1428: -}
1429: -
1430: -/*
1431: - * Path_build generates the next path of the tree and returns 0 if
1432: - * there are no more paths. Each path can be associated
1433: - * with exactly one leaf. Hence the ordering of paths generated by
1434: - * this routine is the same as a left to right ordering of the leaves.
1435: - */
1436: -path_build()
1437: -{
1438: - Node *np, *ep;
1439: - struct path *pp = &path[path_length-1];
1440: -
1441: - /*
1442: - * Assert that the end of the last path was indeed
1443: - * a leaf.
1444: - */
1445: - assert (pp->tag == P_NODE);
1446: - assert ((pp->node)->children == NULL);
1447: -
1448: - /*
1449: - * back up until we find a node that still has children
1450: - */
1451: - pp--;
1452: - while (pp >= &path[1] && pp->node==NULL) pp -= 2;
1453: -
1454: - /*
1455: - * If we hit the beginning of the path array, there are
1456: - * no more leaves and hence no more paths.
1457: - */
1458: - if (pp < &path[1]) {
1459: - /* reset path_length */
1460: - path_length = 0;
1461: - return(0);
1462: - }
1463: -
1464: - /*
1465: - * append the new leftmost branch onto the rest of
1466: - * the path component list.
1467: - */
1468: - pp->branch++;
1469: - np = pp->node;
1470: - pp->node = np->siblings;
1471: - path_length = pp-path+1;
1472: - path_setup(np);
1473: - return(1);
1474: -}
1475: -
1476: -/*
1477: - * Get the next component in the path component list.
1478: - * When the end of a path is reached, NULL is returned and
1479: - * the next call will retrieve the first component of the next path.
1480: - * EOF is returned if there are no more paths.
1481: - * A return value of 1 indicates that the value returned in mi is
1482: - * valid.
1483: - */
1484: -int
1485: -path_getsym(mi)
1486: - register struct machine_input *mi;
1487: -{
1488: - if(path_ptr > &path[path_length]) {
1489: - /*
1490: - * When the end of that path is passed, generate the
1491: - * next path.
1492: - */
1493: - if(!path_build())
1494: - return(EOF);
1495: - path_ptr = path;
1496: - }
1497: - if (path_ptr == &path[path_length]) {
1498: - /*
1499: - * Path_ptr just encountered the end of
1500: - * the path, return a marker value
1501: - * to notify caller.
1502: - */
1503: - mi->value = 0;
1504: - path_ptr++;
1505: - return(NULL);
1506: - } else if (path_ptr->tag != P_BRANCH) {
1507: - /*
1508: - * Translate the right machine input value
1509: - */
1510: - mi->sym = (path_ptr->node)->sym;
1511: - switch((mi->sym)->attr) {
1512: -
1513: - case A_NODE:
1514: - mi->value = MV_NODE((mi->sym)->unique);
1515: - break;
1516: -
1517: - case A_LABEL:
1518: - mi->value = MV_LABEL((mi->sym)->unique);
1519: - break;
1520: -
1521: - default:
1522: - assert(0);
1523: - }
1524: - } else {
1525: - mi->value = MV_BRANCH(path_ptr->branch);
1526: - }
1527: - path_ptr++;
1528: - return(1);
1529: -}
1530: -
1531: -/*
1532: - * Prints out path for debugging
1533: - */
1534: -void
1535: -prpath()
1536: -{
1537: - register int i;
1538: - for(i=0; i < path_length; i++) {
1539: - struct path *pp = &path[i];
1540: - if (pp->tag==P_NODE) {
1541: - struct node *np = pp->node;
1542: - printf("[%s]", (np->sym)->name);
1543: - } else {
1544: - assert (pp->tag == P_BRANCH);
1545: - printf("%d", pp->branch);
1546: - }
1547: - }
1548: - putchar('\n');
1549: -
1550: -}
1551: //GO.SYSIN DD path.c
1552: echo rawwalker.c1 1>&2
1553: sed 's/.//' >rawwalker.c1 <<'//GO.SYSIN DD rawwalker.c1'
1554: -/*
1555: - * See Aho, Corasick Comm ACM 18:6, and Hoffman and O'Donell JACM 29:1
1556: - * for detail of the matching algorithm
1557: - */
1558: -
1559: -/* turn this flag on if your machine has a fast byte string zero operation */
1560: -/*#define BZERO 1*/
1561: -int mtDebug = 0;
1562: -int treedebug = 0;
1563: -extern int _machstep();
1564: -extern short int mtStart;
1565: -extern short int mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
1566: -#ifdef LINE_XREF
1567: - extern short int mtLine[];
1568: -#endif
1569: -extern NODEPTR mtGetNodes(), mtAction();
1570: -extern skeleton *_allocskel();
1571: -extern __match *_allocmatch();
1572: -extern __partial *_allocpartial();
1573: -
1574: -#define MPBLOCKSIZ 3000
1575: -__match *_mpblock[MPBLOCKSIZ], **_mpbtop;
1576: -
1577: -/*
1578: - * See sym.h in the preprocessor for details
1579: - * Basically used to support eh $%n$ construct.
1580: - */
1581: -__match **
1582: -_getleaves (mp, skp)
1583: - register __match *mp; register skeleton *skp;
1584: -{
1585: - skeleton *stack[MAXDEPTH];
1586: - skeleton **stp = stack;
1587: - register short int *sip = &mtPaths[mtPathStart[mp->tree]];
1588: - register __match **mmp = _mpbtop;
1589: - __match **mmp2 = mmp;
1590: - if((_mpbtop += *sip++ + 1) > &_mpblock[MPBLOCKSIZ]) {
1591: - printf ("ich: %d\n", _mpbtop-_mpblock);
1592: - assert(0);
1593: - }
1594: -
1595: - for(;;)
1596: - switch(*sip++) {
1597: - case ePUSH:
1598: - *stp++ = skp;
1599: - skp = skp->leftchild;
1600: - break;
1601: -
1602: - case eNEXT:
1603: - skp = skp->sibling;
1604: - break;
1605: -
1606: - case eEVAL:
1607: - if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
1608: - *mmp++ = mp;
1609: - break;
1610: -
1611: - case ePOP:
1612: - skp = *--stp;
1613: - break;
1614: -
1615: - case eSTOP:
1616: - *mmp = NULL;
1617: - return (mmp2);
1618: - }
1619: -}
1620: -
1621: -_evalleaves (mpp)
1622: - register __match **mpp;
1623: -{
1624: - for (; *mpp!=NULL; mpp++) {
1625: - register __match *mp = *mpp;
1626: - _do (mp->skel, mp, 1);
1627: - }
1628: -}
1629: -
1630: -
1631: -_do(sp, winner, evalall)
1632: - skeleton *sp; register __match *winner; int evalall;
1633: -{
1634: - register __match **mpp;
1635: - register skeleton *skel = winner->skel;
1636: - if(winner==NULL) {
1637: - _prskel(sp, 0);
1638: - puts ("no winner");
1639: - return;
1640: - }
1641: - if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
1642: - REORDER (winner->lleaves);
1643: - mtSetNodes (skel->parent, skel->nson,
1644: - skel->root=mtAction (winner->tree, winner->lleaves, sp));
1645: -}
1646: -
1647: -skeleton *
1648: -_walk(sp, ostate)
1649: - register skeleton *sp;
1650: - int ostate;
1651: -{
1652: - int state, nstate, nson;
1653: - register __partial *pp;
1654: - register __match *mp, *mp2;
1655: - register skeleton *nsp, *lastchild = NULL;
1656: - NODEPTR son, root;
1657: -
1658: - root = sp->root;
1659: - nson = 1; sp->mincost = INFINITY;
1660: - state = _machstep (ostate, root, mtValue(root));
1661: -
1662: - while((son = mtGetNodes(root, nson))!=NULL) {
1663: - nstate = _machstep (state, NULL, MV_BRANCH(nson));
1664: - nsp = _allocskel();
1665: - nsp->root = son;
1666: - nsp->parent = root;
1667: - nsp->nson = nson;
1668: - _walk(nsp, nstate);
1669: - if(COSTLESS(nsp->mincost, INFINITY)) {
1670: - assert (nsp->winner->mode==xREWRITE);
1671: - if (mtDebug || treedebug) {
1672: - printf ("rewrite\n");
1673: - _prskel (nsp, 0);
1674: - }
1675: - _do(nsp, nsp->winner, 0);
1676: - _freeskel(nsp);
1677: - continue;
1678: - }
1679: - _merge (sp, nsp);
1680: - if (lastchild==NULL) sp->leftchild = nsp;
1681: - else lastchild->sibling = nsp;
1682: - lastchild = nsp;
1683: - nson++;
1684: - }
1685: -
1686: - for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
1687: - if (pp->bits&01==1) {
1688: - mp = _allocmatch();
1689: - mp->tree = pp->treeno;
1690: - _addmatches (ostate, sp, mp);
1691: - }
1692: - if(son==NULL && nson==1)
1693: - _closure (state, ostate, sp);
1694: -
1695: - sp->rightchild = lastchild;
1696: - if (root==NULL) {
1697: - COST c; __match *win; int i; nsp = sp->leftchild;
1698: - c = INFINITY;
1699: - win = NULL;
1700: - for (i = 0; i < MAXLABELS; i++) {
1701: - mp = nsp->succ[i];
1702: - if (mp!=NULL && COSTLESS (mp->cost, c))
1703: - { c = mp->cost; win = mp; }
1704: - }
1705: - if (mtDebug || treedebug)
1706: - _prskel (nsp, 0);
1707: - _do (nsp, win, 0);
1708: - }
1709: - if (mtDebug)
1710: - _prskel (sp, 0);
1711: - return(sp);
1712: -}
1713: -
1714: -static short int _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
1715: -
1716: -/*
1717: - * Convert the start state which has a large branching factor into
1718: - * a index table. This must be called before the matcher is used.
1719: - */
1720: -_matchinit()
1721: -{
1722: - short int *sp;
1723: - struct pair { short int val, where } *pp;
1724: - for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
1725: - for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
1726: - sp = &mtTable[mtStart];
1727: - assert (*sp==TABLE);
1728: - for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
1729: - if (MI_NODE(pp->val))
1730: - _nodetab[M_DETAG(pp->val)] = pp->where;
1731: - else if (MI_LABEL(pp->val))
1732: - _labeltab[M_DETAG(pp->val)] = pp->where;
1733: - }
1734: -}
1735: -
1736: -int
1737: -_machstep(state, root, input)
1738: - short int state, input;
1739: - NODEPTR root;
1740: -{
1741: - register short int *stp = &mtTable[state];
1742: - int start = 0;
1743: - if (state==HANG)
1744: - return (input==(MV_BRANCH(1)) ? mtStart : HANG);
1745: -rescan:
1746: - if (stp==&mtTable[mtStart]) {
1747: - if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
1748: - if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
1749: - }
1750: -
1751: - for(;;) {
1752: - if(*stp==ACCEPT) stp += 2;
1753: -
1754: - if(*stp==TABLE) {
1755: - stp++;
1756: - while(*stp!=EOT) {
1757: - if(input==*stp) {
1758: - return(*++stp);
1759: - }
1760: - stp += 2;
1761: - }
1762: - stp++;
1763: - }
1764: - if(*stp!=FAIL) {
1765: - if (start) return (HANG);
1766: - else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
1767: - } else {
1768: - stp++;
1769: - stp = &mtTable[*stp];
1770: - goto rescan;
1771: - }
1772: - }
1773: -}
1774: -
1775: -_addmatches(ostate, sp, np)
1776: - int ostate;
1777: - register skeleton *sp;
1778: - register __match *np;
1779: -{
1780: - int label;
1781: - int state;
1782: - register __match *mp;
1783: -
1784: - label = mtMap[np->tree];
1785: -
1786: - /*
1787: - * this is a very poor substitute for good design of the DFA.
1788: - * What we need is a special case that allows any label to be accepted
1789: - * by the start state but we don't want the start state to recognize
1790: - * them after a failure.
1791: - */
1792: - state = _machstep(ostate, NULL, MV_LABEL(label));
1793: - if (ostate!=mtStart && state==HANG) {
1794: - _freematch(np);
1795: - return;
1796: - }
1797: -
1798: - np->lleaves = _getleaves (np, sp);
1799: - np->skel = sp;
1800: - if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
1801: - {
1802: - _freematch(np);
1803: - return;
1804: - }
1805: -
1806: -/*
1807: - if(np->mode==xREWRITE && COSTLESS(np->cost, sp->mincost)) {
1808: - sp->mincost = np->cost;
1809: - sp->winner = np;
1810: - }
1811: -*/
1812: - if ((mp = sp->succ[label])!=NULL) {
1813: - if (!COSTLESS (np->cost, mp->cost))
1814: - { _freematch(np); return; }
1815: - else _freematch(mp);
1816: - }
1817: - if(COSTLESS(np->cost,sp->mincost)) {
1818: - if(np->mode==xREWRITE) {
1819: - sp->mincost = np->cost; sp->winner = np; }
1820: - else { sp->mincost = INFINITY; sp->winner = NULL; }
1821: - }
1822: - sp->succ[label] = np;
1823: - _closure(state, ostate, sp);
1824: -}
1825: -
1826: -_closure(state, ostate, skp)
1827: - int state, ostate;
1828: - skeleton *skp;
1829: -{
1830: - register struct ap { short int tree, depth; } *ap;
1831: - short int *sp = &mtTable[state];
1832: - register __match *mp;
1833: -
1834: - if(state==HANG || *sp!=ACCEPT) return(NULL);
1835: -
1836: - for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
1837: - if (ap->depth==0) {
1838: - mp = _allocmatch();
1839: - mp->tree = ap->tree;
1840: - _addmatches (ostate, skp, mp);
1841: - } else {
1842: - register __partial *pp, *lim = &skp->partial[skp->treecnt];
1843: - for(pp=skp->partial; pp < lim; pp++)
1844: - if(pp->treeno==ap->tree)
1845: - break;
1846: - if(pp==lim) {
1847: - skp->treecnt++;
1848: - pp->treeno = ap->tree;
1849: - pp->bits = (1<<(ap->depth));
1850: - } else pp->bits |= (1<<(ap->depth));
1851: - }
1852: -}
1853: -
1854: -_merge (old, new)
1855: - skeleton *old, *new;
1856: -{
1857: - register __partial *op = old->partial, *np = new->partial;
1858: - int nson = new->nson;
1859: - register __partial *lim = np + new->treecnt;
1860: - if (nson==1) {
1861: - old->treecnt = new->treecnt;
1862: - for(; np < lim; op++, np++) {
1863: - op->treeno = np->treeno;
1864: - op->bits = np->bits/2;
1865: - }
1866: - } else {
1867: - __partial *newer = _allocpartial();
1868: - register __partial *newerp = newer;
1869: - register int cnt;
1870: - lim = op+old->treecnt;
1871: - for(cnt=new->treecnt; cnt-- ; np++) {
1872: - for(op = old->partial; op < lim; op++)
1873: - if (op->treeno == np->treeno) {
1874: - newerp->treeno = op->treeno;
1875: - newerp++->bits = op->bits & (np->bits/2);
1876: - break;
1877: - }
1878: - }
1879: - _freepartial(old->partial);
1880: - old->partial = newer;
1881: - old->treecnt = newerp-newer;
1882: - }
1883: -}
1884: -
1885: -/* Save and Allocate Matches */
1886: -#define BLKF 100
1887: -__match *freep = NULL;
1888: -static int _count = 0;
1889: -static __match *_blockp = NULL;
1890: -#ifdef CHECKMEM
1891: -int x_matches, f_matches;
1892: -#endif
1893: -
1894: -__match *
1895: -_allocmatch()
1896: -{
1897: - __match *mp;
1898: -
1899: - if(freep!=NULL) {
1900: - mp = freep;
1901: - freep = ((__match *)((struct freeb *) freep)->next);
1902: -#ifdef CHECKMEM
1903: - f_matches--;
1904: -#endif
1905: - } else {
1906: - if(_count==0) {
1907: - _blockp = (__match *) malloc (BLKF*sizeof (__match));
1908: - _count = BLKF;
1909: -#ifdef CHECKMEM
1910: - x_matches += BLKF;
1911: -#endif
1912: - }
1913: - mp = _blockp++;
1914: - _count--;
1915: - }
1916: - return(mp);
1917: -}
1918: -
1919: -_freematch(mp)
1920: - __match *mp;
1921: -{
1922: - ((struct freeb *) mp)->next = (struct freeb *) freep;
1923: - freep = mp;
1924: -#ifdef CHECKMEM
1925: - f_matches++;
1926: -#endif
1927: -}
1928: -
1929: -static __partial *pfreep = NULL;
1930: -static int pcount = 0;
1931: -static __partial *pblock = NULL;
1932: -#ifdef CHECKMEM
1933: -static int x_partials, f_partials;
1934: -#endif
1935: -
1936: -__partial *
1937: -_allocpartial()
1938: -{
1939: - __partial *pp;
1940: - if (pfreep!=NULL) {
1941: - pp = pfreep;
1942: - pfreep = *(__partial **) pp;
1943: -#ifdef CHECKMEM
1944: - f_partials--;
1945: -#endif
1946: - } else {
1947: - if (pcount==0) {
1948: - pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
1949: - pcount = BLKF;
1950: -#ifdef CHECKMEM
1951: - x_partials += BLKF;
1952: -#endif
1953: - }
1954: - pp = pblock;
1955: - pblock += MAXTREES;
1956: - pcount--;
1957: - }
1958: - return(pp);
1959: -}
1960: -
1961: -_freepartial(pp)
1962: - __partial *pp;
1963: -{
1964: - * (__partial **)pp = pfreep;
1965: - pfreep = pp;
1966: -#ifdef CHECKMEM
1967: - f_partials++;
1968: -#endif
1969: -}
1970: -
1971: -
1972: -/* storage management */
1973: -static skeleton *sfreep = NULL;
1974: -static int scount = 0;
1975: -static skeleton * sblock = NULL;
1976: -
1977: -skeleton *
1978: -_allocskel()
1979: -{
1980: - skeleton *sp;
1981: - int i;
1982: - if(sfreep!=NULL) {
1983: - sp = sfreep;
1984: - sfreep = sp->sibling;
1985: - } else {
1986: - if(scount==0) {
1987: - sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
1988: - scount = BLKF;
1989: - }
1990: - sp = sblock++;
1991: - scount--;
1992: - }
1993: - sp->sibling = NULL; sp->leftchild = NULL;
1994: - for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
1995: - sp->treecnt = 0;
1996: - sp->partial = _allocpartial();
1997: - return(sp);
1998: -}
1999: -
2000: -_freeskel(sp)
2001: - skeleton *sp;
2002: -{
2003: - int i;
2004: - __match *mp;
2005: - if(sp==NULL)
2006: - return;
2007: - if(sp->leftchild)
2008: - _freeskel(sp->leftchild);
2009: - if(sp->sibling)
2010: - _freeskel(sp->sibling);
2011: - _freepartial (sp->partial);
2012: - for (i=0; i < MAXLABELS; i++)
2013: - if ((mp = sp->succ[i])!=NULL) _freematch (mp);
2014: - sp->sibling = sfreep;
2015: - sfreep = sp;
2016: -}
2017: -
2018: -_match()
2019: -{
2020: - skeleton *sp;
2021: - sp = _allocskel();
2022: - sp->root = NULL;
2023: - _mpbtop = _mpblock;
2024: - _freeskel(_walk(sp, HANG));
2025: -#ifdef CHECKMEM
2026: - if(f_matches+_count!=x_matches) {
2027: - printf(";#m %d %d %d\n", f_matches, _count, x_matches);
2028: - assert(0);
2029: - }
2030: - if(f_partials+pcount!=x_partials) {
2031: - printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
2032: - assert(0);
2033: - }
2034: -#endif
2035: -}
2036: -
2037: -NODEPTR
2038: -_mtG(root,i)
2039: - NODEPTR root;
2040: - int i;
2041: -{
2042: - int *p = &i;
2043: - while(*p!=-1)
2044: - root = mtGetNodes(root, *p++);
2045: - return(root);
2046: -}
2047: -
2048: -/* diagnostic routines */
2049: -
2050: -_prskel (skp, lvl)
2051: - skeleton *skp; int lvl;
2052: -{
2053: - int i; __match *mp;
2054: - __partial *pp;
2055: - if(skp==NULL) return;
2056: - for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
2057: - printf ("###\n");
2058: - for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
2059: - for (i = 0; i < MAXLABELS; i++)
2060: - if ((mp=skp->succ[i])!=NULL)
2061: -#ifdef LINE_XREF
2062: - printf ("[%d<%d> %d]", mp->tree,
2063: - mtLine[mp->tree], mp->cost);
2064: -#else
2065: - printf ("[%d %d]", mp->tree, mp->cost);
2066: -#endif
2067: - putchar('\n');
2068: - for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
2069: - for (i = 0, pp=skp->partial; i < skp->treecnt; i++, pp++)
2070: -#ifdef LINE_XREF
2071: - printf("(%d<%d> %x)", pp->treeno, mtLine[pp->treeno],
2072: - pp->bits);
2073: -#else
2074: - printf ("(%d %x)", pp->treeno, pp->bits);
2075: -#endif
2076: - putchar('\n');
2077: - fflush(stdout);
2078: - _prskel (skp->leftchild, lvl+2);
2079: - _prskel (skp->sibling, lvl);
2080: -}
2081: //GO.SYSIN DD rawwalker.c1
2082: echo rawwalker.ex 1>&2
2083: sed 's/.//' >rawwalker.ex <<'//GO.SYSIN DD rawwalker.ex'
2084: -/*
2085: - * See Aho, Corasick Comm ACM 18:6, and Hoffman and O'Donell JACM 29:1
2086: - * for detail of the matching algorithm
2087: - */
2088: -
2089: -/* turn this flag on if your machine has a fast byte string zero operation */
2090: -/*#define BZERO 1*/
2091: -int mtDebug = 0;
2092: -int treedebug = 0;
2093: -extern int _machstep();
2094: -extern short int mtStart;
2095: -extern short int mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
2096: -#ifdef LINE_XREF
2097: - extern short int mtLine[];
2098: -#endif
2099: -extern NODEPTR mtGetNodes(), mtAction();
2100: -extern skeleton *_allocskel();
2101: -extern __match *_allocmatch();
2102: -extern __partial *_allocpartial();
2103: -
2104: -#define MPBLOCKSIZ 3000
2105: -__match *_mpblock[MPBLOCKSIZ], **_mpbtop;
2106: -
2107: -/*
2108: - * See sym.h in the preprocessor for details
2109: - * Basically used to support eh $%n$ construct.
2110: - */
2111: -__match **
2112: -_getleaves (mp, skp)
2113: - register __match *mp; register skeleton *skp;
2114: -{
2115: - skeleton *stack[MAXDEPTH];
2116: - skeleton **stp = stack;
2117: - register short int *sip = &mtPaths[mtPathStart[mp->tree]];
2118: - register __match **mmp = _mpbtop;
2119: - __match **mmp2 = mmp;
2120: - if((_mpbtop += *sip++ + 1) > &_mpblock[MPBLOCKSIZ]) {
2121: - printf ("ich: %d\n", _mpbtop-_mpblock);
2122: - assert(0);
2123: - }
2124: -
2125: - for(;;)
2126: - switch(*sip++) {
2127: - case ePUSH:
2128: - *stp++ = skp;
2129: - skp = skp->leftchild;
2130: - break;
2131: -
2132: - case eNEXT:
2133: - skp = skp->sibling;
2134: - break;
2135: -
2136: - case eEVAL:
2137: - if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
2138: - *mmp++ = mp;
2139: - break;
2140: -
2141: - case ePOP:
2142: - skp = *--stp;
2143: - break;
2144: -
2145: - case eSTOP:
2146: - *mmp = NULL;
2147: - return (mmp2);
2148: - }
2149: -}
2150: -
2151: -_evalleaves (mpp)
2152: - register __match **mpp;
2153: -{
2154: - for (; *mpp!=NULL; mpp++) {
2155: - register __match *mp = *mpp;
2156: - _do (mp->skel, mp, 1);
2157: - }
2158: -}
2159: -
2160: -
2161: -_do(sp, winner, evalall)
2162: - skeleton *sp; register __match *winner; int evalall;
2163: -{
2164: - register __match **mpp;
2165: - register skeleton *skel = winner->skel;
2166: - if(winner==NULL) {
2167: - _prskel(sp, 0);
2168: - puts ("no winner");
2169: - return;
2170: - }
2171: - if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
2172: - REORDER (winner->lleaves);
2173: - mtSetNodes (skel->parent, skel->nson,
2174: - skel->root=mtAction (winner->tree, winner->lleaves, sp));
2175: -}
2176: -
2177: -skeleton *
2178: -_walk(sp, ostate)
2179: - register skeleton *sp;
2180: - int ostate;
2181: -{
2182: - int state, nstate, nson;
2183: - register __partial *pp;
2184: - register __match *mp, *mp2;
2185: - register skeleton *nsp, *lastchild = NULL;
2186: - NODEPTR son, root;
2187: -
2188: - root = sp->root;
2189: - nson = 1; sp->mincost = INFINITY;
2190: - state = _machstep (ostate, root, mtValue(root));
2191: -
2192: - while((son = mtGetNodes(root, nson))!=NULL) {
2193: - nstate = _machstep (state, NULL, MV_BRANCH(nson));
2194: - nsp = _allocskel();
2195: - nsp->root = son;
2196: - nsp->parent = root;
2197: - nsp->nson = nson;
2198: - _walk(nsp, nstate);
2199: - if(COSTLESS(nsp->mincost, INFINITY)) {
2200: - assert (nsp->winner->mode==xREWRITE);
2201: - if (mtDebug || treedebug) {
2202: - printf ("rewrite\n");
2203: - _prskel (nsp, 0);
2204: - }
2205: - _do(nsp, nsp->winner, 0);
2206: - _freeskel(nsp);
2207: - continue;
2208: - }
2209: - _merge (sp, nsp);
2210: - if (lastchild==NULL) sp->leftchild = nsp;
2211: - else lastchild->sibling = nsp;
2212: - lastchild = nsp;
2213: - nson++;
2214: - }
2215: -
2216: - for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
2217: - if (pp->bits&01==1) {
2218: - mp = _allocmatch();
2219: - mp->tree = pp->treeno;
2220: - _addmatches (ostate, sp, mp);
2221: - }
2222: - if(son==NULL && nson==1)
2223: - _closure (state, ostate, sp);
2224: -
2225: - sp->rightchild = lastchild;
2226: - if (root==NULL) {
2227: - COST c; __match *win; int i; nsp = sp->leftchild;
2228: - c = INFINITY;
2229: - win = NULL;
2230: - for (i = 0; i < MAXLABELS; i++) {
2231: - mp = nsp->succ[i];
2232: - if (mp!=NULL && COSTLESS (mp->cost, c))
2233: - { c = mp->cost; win = mp; }
2234: - }
2235: - if (mtDebug || treedebug)
2236: - _prskel (nsp, 0);
2237: - _do (nsp, win, 0);
2238: - }
2239: - if (mtDebug)
2240: - _prskel (sp, 0);
2241: - return(sp);
2242: -}
2243: -
2244: -static short int _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
2245: -
2246: -/*
2247: - * Convert the start state which has a large branching factor into
2248: - * a index table. This must be called before the matcher is used.
2249: - */
2250: -_matchinit()
2251: -{
2252: - short int *sp;
2253: - struct pair { short int val, where } *pp;
2254: - for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
2255: - for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
2256: - sp = &mtTable[mtStart];
2257: - assert (*sp==TABLE);
2258: - for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
2259: - if (MI_NODE(pp->val))
2260: - _nodetab[M_DETAG(pp->val)] = pp->where;
2261: - else if (MI_LABEL(pp->val))
2262: - _labeltab[M_DETAG(pp->val)] = pp->where;
2263: - }
2264: -}
2265: -
2266: -int
2267: -_machstep(state, root, input)
2268: - short int state, input;
2269: - NODEPTR root;
2270: -{
2271: - register short int *stp = &mtTable[state];
2272: - int start = 0;
2273: - if (state==HANG)
2274: - return (input==(MV_BRANCH(1)) ? mtStart : HANG);
2275: -rescan:
2276: - if (stp==&mtTable[mtStart]) {
2277: - if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
2278: - if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
2279: - }
2280: -
2281: - for(;;) {
2282: - if(*stp==ACCEPT) stp += 2;
2283: -
2284: - if(*stp==TABLE) {
2285: - stp++;
2286: - while(*stp!=EOT) {
2287: - if(input==*stp) {
2288: - return(*++stp);
2289: - }
2290: - stp += 2;
2291: - }
2292: - stp++;
2293: - }
2294: - if(*stp!=FAIL) {
2295: - if (start) return (HANG);
2296: - else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
2297: - } else {
2298: - stp++;
2299: - stp = &mtTable[*stp];
2300: - goto rescan;
2301: - }
2302: - }
2303: -}
2304: -
2305: -_addmatches(ostate, sp, np)
2306: - int ostate;
2307: - register skeleton *sp;
2308: - register __match *np;
2309: -{
2310: - int label;
2311: - int state, qstate;
2312: - register __match *mp;
2313: - static short int quick[128][MAXLABELS];
2314: - static short int qtag[128][MAXLABELS];
2315: -
2316: - label = mtMap[np->tree];
2317: -
2318: - /*
2319: - * The following lines replace the line:
2320: - *
2321: - * state = _machstep(ostate, NULL, MV_LABEL(label));
2322: - *
2323: - * Statistics show that a large percentage (approx 2/3) of calls to
2324: - * _machstep occur in this function. The lines below attempt
2325: - * to reduce the number of these calls by using an unsophisticated
2326: - * but apparently adequate caching scheme.
2327: - */
2328: - qstate = ((ostate>>2)+2)&0177;
2329: - if(ostate != qtag[qstate][label]) {
2330: - state = _machstep(ostate, NULL, MV_LABEL(label));
2331: - quick[qstate][label] = state;
2332: - qtag[qstate][label] = ostate;
2333: - } else state = quick[qstate][label];
2334: -
2335: - /*
2336: - * this is a very poor substitute for good design of the DFA.
2337: - * What we need is a special case that allows any label to be accepted
2338: - * by the start state but we don't want the start state to recognize
2339: - * them after a failure.
2340: - */
2341: - if (ostate!=mtStart && state==HANG) {
2342: - _freematch(np);
2343: - return;
2344: - }
2345: -
2346: - np->lleaves = _getleaves (np, sp);
2347: - np->skel = sp;
2348: - if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
2349: - {
2350: - _freematch(np);
2351: - return;
2352: - }
2353: -
2354: - if ((mp = sp->succ[label])!=NULL) {
2355: - if (!COSTLESS (np->cost, mp->cost))
2356: - { _freematch(np); return; }
2357: - else _freematch(mp);
2358: - }
2359: - if(COSTLESS(np->cost,sp->mincost)) {
2360: - if(np->mode==xREWRITE) {
2361: - sp->mincost = np->cost; sp->winner = np; }
2362: - else { sp->mincost = INFINITY; sp->winner = NULL; }
2363: - }
2364: - sp->succ[label] = np;
2365: - _closure(state, ostate, sp);
2366: -}
2367: -
2368: -_closure(state, ostate, skp)
2369: - int state, ostate;
2370: - skeleton *skp;
2371: -{
2372: - register struct ap { short int tree, depth; } *ap;
2373: - short int *sp = &mtTable[state];
2374: - register __match *mp;
2375: -
2376: - if(state==HANG || *sp!=ACCEPT) return(NULL);
2377: -
2378: - for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
2379: - if (ap->depth==0) {
2380: - mp = _allocmatch();
2381: - mp->tree = ap->tree;
2382: - _addmatches (ostate, skp, mp);
2383: - } else {
2384: - register __partial *pp, *lim = &skp->partial[skp->treecnt];
2385: - for(pp=skp->partial; pp < lim; pp++)
2386: - if(pp->treeno==ap->tree)
2387: - break;
2388: - if(pp==lim) {
2389: - skp->treecnt++;
2390: - pp->treeno = ap->tree;
2391: - pp->bits = (1<<(ap->depth));
2392: - } else pp->bits |= (1<<(ap->depth));
2393: - }
2394: -}
2395: -
2396: -_merge (old, new)
2397: - skeleton *old, *new;
2398: -{
2399: - register __partial *op = old->partial, *np = new->partial;
2400: - int nson = new->nson;
2401: - register __partial *lim = np + new->treecnt;
2402: - if (nson==1) {
2403: - old->treecnt = new->treecnt;
2404: - for(; np < lim; op++, np++) {
2405: - op->treeno = np->treeno;
2406: - op->bits = np->bits/2;
2407: - }
2408: - } else {
2409: - __partial *newer = _allocpartial();
2410: - register __partial *newerp = newer;
2411: - register int cnt;
2412: - lim = op+old->treecnt;
2413: - for(cnt=new->treecnt; cnt-- ; np++) {
2414: - for(op = old->partial; op < lim; op++)
2415: - if (op->treeno == np->treeno) {
2416: - newerp->treeno = op->treeno;
2417: - newerp++->bits = op->bits & (np->bits/2);
2418: - break;
2419: - }
2420: - }
2421: - _freepartial(old->partial);
2422: - old->partial = newer;
2423: - old->treecnt = newerp-newer;
2424: - }
2425: -}
2426: -
2427: -/* Save and Allocate Matches */
2428: -#define BLKF 100
2429: -__match *freep = NULL;
2430: -static int _count = 0;
2431: -static __match *_blockp = NULL;
2432: -#ifdef CHECKMEM
2433: -int x_matches, f_matches;
2434: -#endif
2435: -
2436: -__match *
2437: -_allocmatch()
2438: -{
2439: - __match *mp;
2440: -
2441: - if(freep!=NULL) {
2442: - mp = freep;
2443: - freep = ((__match *)((struct freeb *) freep)->next);
2444: -#ifdef CHECKMEM
2445: - f_matches--;
2446: -#endif
2447: - } else {
2448: - if(_count==0) {
2449: - _blockp = (__match *) malloc (BLKF*sizeof (__match));
2450: - _count = BLKF;
2451: -#ifdef CHECKMEM
2452: - x_matches += BLKF;
2453: -#endif
2454: - }
2455: - mp = _blockp++;
2456: - _count--;
2457: - }
2458: - return(mp);
2459: -}
2460: -
2461: -_freematch(mp)
2462: - __match *mp;
2463: -{
2464: - ((struct freeb *) mp)->next = (struct freeb *) freep;
2465: - freep = mp;
2466: -#ifdef CHECKMEM
2467: - f_matches++;
2468: -#endif
2469: -}
2470: -
2471: -static __partial *pfreep = NULL;
2472: -static int pcount = 0;
2473: -static __partial *pblock = NULL;
2474: -#ifdef CHECKMEM
2475: -static int x_partials, f_partials;
2476: -#endif
2477: -
2478: -__partial *
2479: -_allocpartial()
2480: -{
2481: - __partial *pp;
2482: - if (pfreep!=NULL) {
2483: - pp = pfreep;
2484: - pfreep = *(__partial **) pp;
2485: -#ifdef CHECKMEM
2486: - f_partials--;
2487: -#endif
2488: - } else {
2489: - if (pcount==0) {
2490: - pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
2491: - pcount = BLKF;
2492: -#ifdef CHECKMEM
2493: - x_partials += BLKF;
2494: -#endif
2495: - }
2496: - pp = pblock;
2497: - pblock += MAXTREES;
2498: - pcount--;
2499: - }
2500: - return(pp);
2501: -}
2502: -
2503: -_freepartial(pp)
2504: - __partial *pp;
2505: -{
2506: - * (__partial **)pp = pfreep;
2507: - pfreep = pp;
2508: -#ifdef CHECKMEM
2509: - f_partials++;
2510: -#endif
2511: -}
2512: -
2513: -
2514: -/* storage management */
2515: -static skeleton *sfreep = NULL;
2516: -static int scount = 0;
2517: -static skeleton * sblock = NULL;
2518: -
2519: -skeleton *
2520: -_allocskel()
2521: -{
2522: - skeleton *sp;
2523: - int i;
2524: - if(sfreep!=NULL) {
2525: - sp = sfreep;
2526: - sfreep = sp->sibling;
2527: - } else {
2528: - if(scount==0) {
2529: - sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
2530: - scount = BLKF;
2531: - }
2532: - sp = sblock++;
2533: - scount--;
2534: - }
2535: - sp->sibling = NULL; sp->leftchild = NULL;
2536: - for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
2537: - sp->treecnt = 0;
2538: - sp->partial = _allocpartial();
2539: - return(sp);
2540: -}
2541: -
2542: -_freeskel(sp)
2543: - skeleton *sp;
2544: -{
2545: - int i;
2546: - __match *mp;
2547: - if(sp==NULL)
2548: - return;
2549: - if(sp->leftchild)
2550: - _freeskel(sp->leftchild);
2551: - if(sp->sibling)
2552: - _freeskel(sp->sibling);
2553: - _freepartial (sp->partial);
2554: - for (i=0; i < MAXLABELS; i++)
2555: - if ((mp = sp->succ[i])!=NULL) _freematch (mp);
2556: - sp->sibling = sfreep;
2557: - sfreep = sp;
2558: -}
2559: -
2560: -_match()
2561: -{
2562: - skeleton *sp;
2563: - sp = _allocskel();
2564: - sp->root = NULL;
2565: - _mpbtop = _mpblock;
2566: - _freeskel(_walk(sp, HANG));
2567: -#ifdef CHECKMEM
2568: - if(f_matches+_count!=x_matches) {
2569: - printf(";#m %d %d %d\n", f_matches, _count, x_matches);
2570: - assert(0);
2571: - }
2572: - if(f_partials+pcount!=x_partials) {
2573: - printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
2574: - assert(0);
2575: - }
2576: -#endif
2577: -}
2578: -
2579: -NODEPTR
2580: -_mtG(root,i)
2581: - NODEPTR root;
2582: - int i;
2583: -{
2584: - int *p = &i;
2585: - while(*p!=-1)
2586: - root = mtGetNodes(root, *p++);
2587: - return(root);
2588: -}
2589: -
2590: -/* diagnostic routines */
2591: -
2592: -_prskel (skp, lvl)
2593: - skeleton *skp; int lvl;
2594: -{
2595: - int i; __match *mp;
2596: - __partial *pp;
2597: - if(skp==NULL) return;
2598: - for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
2599: - printf ("###\n");
2600: - for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
2601: - for (i = 0; i < MAXLABELS; i++)
2602: - if ((mp=skp->succ[i])!=NULL)
2603: -#ifdef LINE_XREF
2604: - printf ("[%d<%d> %d]", mp->tree,
2605: - mtLine[mp->tree], mp->cost);
2606: -#else
2607: - printf ("[%d %d]", mp->tree, mp->cost);
2608: -#endif
2609: - putchar('\n');
2610: - for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
2611: - for (i = 0, pp=skp->partial; i < skp->treecnt; i++, pp++)
2612: -#ifdef LINE_XREF
2613: - printf("(%d<%d> %x)", pp->treeno, mtLine[pp->treeno],
2614: - pp->bits);
2615: -#else
2616: - printf ("(%d %x)", pp->treeno, pp->bits);
2617: -#endif
2618: - putchar('\n');
2619: - fflush(stdout);
2620: - _prskel (skp->leftchild, lvl+2);
2621: - _prskel (skp->sibling, lvl);
2622: -}
2623: //GO.SYSIN DD rawwalker.ex
2624: echo sym.c 1>&2
2625: sed 's/.//' >sym.c <<'//GO.SYSIN DD sym.c'
2626: -/*
2627: - * Symbol manipulation routines
2628: - */
2629: -#include "common.h"
2630: -#include "code.h"
2631: -#include "sym.h"
2632: -#include "machine.h"
2633: -#include "y.tab.h"
2634: -#include "mem.h"
2635: -
2636: -#define SAFE 1 /* generates code to do redundant checks */
2637: -#define MAXSYMS 100
2638: -#define MAX_UNIQUE 255
2639: -
2640: -static void AppendToList();
2641: -typedef
2642: - struct SymbolList {
2643: - SymbolEntry *first, *last;
2644: - int count;
2645: - }
2646: - SymbolList;
2647: -
2648: -/*
2649: - * The range of the unique numbers assigned to each type of
2650: - * symbol is [min,max)
2651: - */
2652: -struct ranges {
2653: - int min,max;
2654: - int limit;
2655: -} uniques[] = {
2656: - {0, 0, MAX_UNIQUE}, /* A_UNDEFINED -- not used */
2657: - {0, 0, MAX_NODE_VALUE}, /* A_NODE */
2658: - {0, 0, MAX_UNIQUE}, /* A_LABEL */
2659: - {0, 0, MAX_UNIQUE}, /* A_COST */
2660: - {0, 0, MAX_UNIQUE}, /* A_ACTION */
2661: -};
2662: -
2663: -int treeIndex = 0;
2664: -
2665: -static SymbolList lists[] = {
2666: - { NULL, NULL, 0}, /* A_UNDEFINED -- never used */
2667: - { NULL, NULL, 0}, /* A_NODE */
2668: - { NULL, NULL, 0}, /* A_LABEL */
2669: - { NULL, NULL, 0}, /* A_COST */
2670: - { NULL, NULL, 0}, /* A_ACTION */
2671: - { NULL, NULL, 0}, /* A_CONST */
2672: -};
2673: -
2674: -struct _mem sym_mem, lab_mem, tree_mem;
2675: -SymbolEntry *hash_table[HASHSIZE];
2676: -SymbolEntry *startSymbol;
2677: -
2678: -static int
2679: -RawHash(s)
2680: - register char *s;
2681: -{
2682: - register int sum = 0;
2683: - register int i = 0;
2684: - while(*s)
2685: - sum += (++i)*(0377&*s++);
2686: - return(sum);
2687: -}
2688: -
2689: -
2690: -/*
2691: - * Allocate a new symbol_entry structure for the given structure and
2692: - * return it. There is no check of whether the symbol is already defined or
2693: - * not. The caller is expected to fill in the uninitialized fields.
2694: - */
2695: -SymbolEntry *
2696: -SymbolAllocate(s)
2697: - char *s;
2698: -{
2699: - SymbolEntry *sp;
2700: - sp = (SymbolEntry *) mem_get(&sym_mem);
2701: - assert(sp!=NULL);
2702: -
2703: -#ifdef SAFE
2704: - assert (SymbolLookup(s) == NULL);
2705: -#endif
2706: -
2707: - sp->name = malloc(strlen(s)+1);
2708: - assert(sp->name!=NULL);
2709: - strcpy (sp->name, s);
2710: - sp->hash = RawHash(s);
2711: - sp->next = NULL;
2712: - sp->attr = A_UNDEFINED;
2713: - sp->unique = -1;
2714: - return(sp);
2715: -}
2716: -
2717: -void
2718: -SymbolFree (symp)
2719: - SymbolEntry *symp;
2720: -{
2721: - assert (symp->next == NULL);
2722: - free(symp);
2723: -}
2724: -
2725: -SymbolEntry *
2726: -SymbolLookup(s)
2727: - char *s;
2728: -{
2729: - int hash_value = RawHash(s);
2730: - register SymbolEntry * hp = hash_table[hash_value%HASHSIZE];
2731: -
2732: - while(hp!=NULL) {
2733: - if(hp->hash == hash_value &&
2734: - strcmp (s, hp->name)==0) break;
2735: - hp = hp->next;
2736: - }
2737: - return(hp);
2738: -}
2739: -
2740: -/*
2741: - * enter the symbol into the symbol table. It believes everything in the
2742: - * symp argument.
2743: - */
2744: -void
2745: -SymbolEnter (symp, attr)
2746: - SymbolEntry *symp;
2747: - byte attr;
2748: -{
2749: - struct symbol_entry *hp;
2750: -
2751: -#ifdef SAFE
2752: - assert (symp!=NULL);
2753: - assert (symp->hash == RawHash(symp->name));
2754: - assert (symp->attr == A_UNDEFINED);
2755: -#endif
2756: -
2757: - hp = hash_table[symp->hash%HASHSIZE];
2758: - symp->next = hp;
2759: - hash_table[symp->hash%HASHSIZE] = symp;
2760: - symp->attr = attr;
2761: - if (HAS_UNIQUE(attr)){
2762: - struct ranges *rp = &uniques[attr];
2763: - int new_unique;
2764: - if(symp->unique==-1)
2765: - symp->unique = new_unique = rp->max++;
2766: - else {
2767: - new_unique = symp->unique;
2768: - if(new_unique>=rp->max)
2769: - rp->max = new_unique+1;
2770: - else if(new_unique < rp->min)
2771: - rp->min = new_unique;
2772: - }
2773: - if(new_unique>rp->limit)
2774: - sem_error("number assigned to %s (%d) out of range",
2775: - symp->name, new_unique);
2776: - if(new_unique<0)
2777: - sem_error("number assigned to %s (%d) is negative",
2778: - symp->name, new_unique);
2779: - assert(rp->max>=rp->min);
2780: - }
2781: - if (HAS_LIST(attr)) {
2782: - AppendToList(&lists[attr], symp);
2783: - }
2784: -}
2785: -
2786: -static void
2787: -AppendToList(list, sp)
2788: - SymbolList *list;
2789: - SymbolEntry *sp;
2790: -{
2791: - sp->link = NULL;
2792: - if(list->first==NULL)
2793: - list->first = sp;
2794: - else (list->last)->link = sp;
2795: - list->last = sp;
2796: - list->count++;
2797: -}
2798: -
2799: -SymbolCheckNodeValues()
2800: -{
2801: - SymbolList *slist;
2802: - SymbolEntry **stab, **spp, *sp;
2803: - struct ranges *rp;
2804: - int i, range;
2805: -
2806: - rp = &uniques[A_NODE];
2807: - slist = &lists[A_NODE];
2808: - range = rp->max - rp->min + 1;
2809: - stab = (SymbolEntry **) malloc(range*sizeof(SymbolEntry *));
2810: -
2811: - for(i=range, spp = stab; i-->0; spp++) *spp = NULL;
2812: -
2813: - for(sp = slist->first; sp; sp = sp->link) {
2814: - SymbolEntry *sp2 = stab[sp->unique];
2815: - if(sp2==NULL)
2816: - stab[sp->unique] = sp;
2817: - else
2818: - sem_error("%s and %s have the same node value",
2819: - sp2->name, sp->name);
2820: - }
2821: - free(stab);
2822: -}
2823: -
2824: -SymbolEntry *
2825: -SymbolEnterKeyword(s, value)
2826: - char *s;
2827: - int value;
2828: -{
2829: - SymbolEntry *sp = SymbolAllocate(s);
2830: - sp->sd.keyword = value;
2831: - SymbolEnter (sp, A_KEYWORD);
2832: - return(sp);
2833: -}
2834: -
2835: -void
2836: -SymbolInit()
2837: -{
2838: - SymbolEntry *sp;
2839: -
2840: - mem_init(&sym_mem,sizeof(SymbolEntry));
2841: - mem_init(&lab_mem,sizeof(LabelData));
2842: - mem_init(&tree_mem,sizeof(struct treeassoc));
2843: - SymbolEnterKeyword ("node", K_NODE);
2844: - SymbolEnterKeyword ("label", K_LABEL);
2845: - SymbolEnterKeyword ("prologue", K_PROLOGUE);
2846: - SymbolEnterKeyword ("const", K_CONST);
2847: - SymbolEnterKeyword ("insert", K_INSERT);
2848: - SymbolEnterKeyword ("cost", K_COST);
2849: - SymbolEnterKeyword ("action", K_ACTION);
2850: -}
2851: -
2852: -void
2853: -SymbolMap(f)
2854: - int (*f)();
2855: -{
2856: - SymbolEntry **spp, *sp;
2857: - for(spp = hash_table; spp < &hash_table[HASHSIZE]; spp++)
2858: - for(sp= *spp; sp!=NULL; sp = sp->next)
2859: - f(sp);
2860: -};
2861: -
2862: -static int symcnt, labcnt, nodecnt;
2863: -static
2864: -sym_count(sp)
2865: - SymbolEntry *sp;
2866: -{
2867: - symcnt++;
2868: - switch(sp->attr) {
2869: - case A_LABEL: {
2870: - LabelData *lp;
2871: - for(lp = sp->sd.lp;lp!=NULL;lp=lp->next) {
2872: - labcnt++;
2873: - nodecnt += cntnodes(lp->tree);
2874: - }
2875: - } break;
2876: - }
2877: -}
2878: -
2879: -void
2880: -SymbolFinish()
2881: -{
2882: - if(DB_MEM&debug_flag) {
2883: - extern struct _mem node_mem;
2884: - int symout = mem_outstanding(&sym_mem);
2885: - int labout = mem_outstanding(&lab_mem);
2886: - int nodeout = mem_outstanding(&node_mem);
2887: - SymbolMap(sym_count);
2888: - fprintf(stderr,"symbols defined=%d out=%d\n",symcnt, symout);
2889: - fprintf(stderr,"labdata def=%d out=%d\n",labcnt,labout);
2890: - fprintf(stderr,"node def=%d out=%d\n",nodecnt,nodeout);
2891: - assert(symcnt==symout);
2892: - assert(labcnt==labout);
2893: - assert(nodecnt==nodeout);
2894: - }
2895: -}
2896: -
2897: -void
2898: -SymbolEnterList (symp, attr)
2899: - SymbolEntry *symp;
2900: - int attr;
2901: -{
2902: - /*
2903: - * enter in reverse order because the list was built in reverse
2904: - * order by the parser
2905: - */
2906: -
2907: - if(symp==NULL)
2908: - return;
2909: - SymbolEnterList(symp->next, attr);
2910: - if(symp->attr!=A_UNDEFINED)
2911: - sem_error ("multiple declaration ignored: %s", symp->name);
2912: - SymbolEnter (symp, attr);
2913: -}
2914: -
2915: -LabelData *
2916: -SymbolEnterTreeIntoLabel(symp, tree, costfunc, action, lineno)
2917: - SymbolEntry *symp, *action, *costfunc;
2918: - struct node *tree;
2919: - int lineno;
2920: -{
2921: - LabelData *tp = (LabelData *) mem_get(&lab_mem);
2922: - struct treeassoc *ap;
2923: -
2924: - if (symp==&ErrorSymbol) return(NULL);
2925: -#ifdef SAFE
2926: - assert (tp!=NULL);
2927: - assert (symp->attr==A_LABEL);
2928: -#endif
2929: -
2930: - tp->tree = tree;
2931: - tp->treeIndex = treeIndex++;
2932: - tp->lineno = lineno;
2933: - tp->next = symp->sd.lp;
2934: - tp->label = symp;
2935: - symp->sd.lp = tp;
2936: -
2937: - if (action!=NULL) {
2938: - ap = (struct treeassoc *) mem_get(&tree_mem);
2939: - ap->tree = tp->treeIndex;
2940: - ap->next = action->sd.ca.assoc;
2941: - action->sd.ca.assoc = ap;
2942: - }
2943: -
2944: - if (costfunc!=NULL) {
2945: - ap = (struct treeassoc *) mem_get(&tree_mem);
2946: - ap->tree = tp->treeIndex;
2947: - ap->next = costfunc->sd.ca.assoc;
2948: - costfunc->sd.ca.assoc = ap;
2949: - }
2950: - return(tp);
2951: -}
2952: -
2953: -static void
2954: -WriteSymbols(sp, mask)
2955: - SymbolEntry *sp;
2956: - int mask;
2957: -{
2958: - for(;sp!=NULL; sp = sp->link)
2959: - fprintf(symfile, "#define %s\t0%o\n", sp->name, sp->unique|mask);
2960: -}
2961: -
2962: -void
2963: -SymbolDump()
2964: -{
2965: - WriteSymbols(lists[A_NODE].first, M_NODE);
2966: - WriteSymbols(lists[A_LABEL].first, 0);
2967: - WriteSymbols(lists[A_CONST].first, 0);
2968: - fprintf(symfile, "#define MAXLABELS %d\n", uniques[A_LABEL].max);
2969: - fprintf(symfile, "#define MAXTREES %d\n", treeIndex);
2970: - fprintf(symfile, "#define MAXNDVAL %d\n", uniques[A_NODE].max);
2971: -}
2972: -
2973: -void
2974: -SymbolGenerateWalkerCode()
2975: -{
2976: - register SymbolEntry *pp;
2977: - int i;
2978: - extern int line_xref_flag;
2979: - struct treeassoc *tap;
2980: - register LabelData *lp;
2981: - register short int *mapTab;
2982: -
2983: - /*
2984: - * Write out the table of tree index to label correspondence
2985: - */
2986: - mapTab = (short int *) malloc (treeIndex * sizeof(short int));
2987: - for(pp=lists[A_LABEL].first; pp!=NULL; pp=pp->link) {
2988: - lp = pp->sd.lp;
2989: - if(lp==NULL)
2990: - sem_error2("%s undefined\n", pp->name);
2991: - for(;lp!=NULL;lp=lp->next)
2992: - mapTab[lp->treeIndex] = pp->unique;
2993: - }
2994: - fputs("short int mtMap[] = {\n", outfile);
2995: - for(i=0, oreset(); i < treeIndex;)
2996: - oputoct(mapTab[i++]);
2997: - fputs("};\n", outfile);
2998: -
2999: - /* generate tree to line index table */
3000: - if(line_xref_flag) {
3001: - for(pp=lists[A_LABEL].first; pp!=NULL; pp=pp->link) {
3002: - lp = pp->sd.lp;
3003: - for(;lp!=NULL;lp=lp->next)
3004: - mapTab[lp->treeIndex] = lp->lineno;
3005: - }
3006: - fputs("short int mtLine[] = {\n", outfile);
3007: - for(i=0, oreset(); i<treeIndex;)
3008: - oputint(mapTab[i++]);
3009: - fputs("};\n", outfile);
3010: - }
3011: - /*
3012: - * Generate path table
3013: - */
3014: - fputs ("short int mtPaths[] = {\n", outfile);
3015: - for(pp=lists[A_LABEL].first, oreset(); pp!=NULL; pp=pp->link) {
3016: - lp = pp->sd.lp;
3017: - if(lp==NULL)
3018: - sem_error2("%s undefined\n", pp->name);
3019: - do {
3020: - mapTab[lp->treeIndex] = ointcnt();
3021: - oputint (lp->tree->nlleaves);
3022: - SymbolWritePath (lp->tree);
3023: - oputint (eSTOP);
3024: - lp = lp->next;
3025: - } while (lp!=NULL);
3026: - }
3027: - fputs(" };\nshort int mtPathStart[] = {\n", outfile);
3028: - for(i=0, oreset(); i < treeIndex;)
3029: - oputint (mapTab[i++]);
3030: - fputs("};\n", outfile);
3031: -
3032: - /*
3033: - * Code to perform the action of the trees
3034: - */
3035: - fputs("NODEPTR\nmtAction (_t, _ll, _s)\n", outfile);
3036: - fputs("int _t; __match **_ll; skeleton *_s;\n", outfile);
3037: - fputs("{ NODEPTR root = _s->root;\n", outfile);
3038: - fputs("switch (_t) {\n", outfile);
3039: - for (pp=lists[A_ACTION].first; pp!=NULL; pp=pp->link) {
3040: - if ((tap=pp->sd.ca.assoc)==NULL) {
3041: - sem_error2 ("%s not used", pp->name);
3042: - continue;
3043: - }
3044: - for (; tap!=NULL; tap=tap->next)
3045: - fprintf (outfile, "case %d:", tap->tree);
3046: - fputs ("{\n", outfile);
3047: - CodeWrite (outfile, pp->sd.ca.code);
3048: - fputs("} break;\n", outfile);
3049: - }
3050: - fputs("} return(_s->root);}\n", outfile);
3051: -
3052: - fputs ("mtEvalCost(_m, _ll, _s)\n", outfile);
3053: - fputs ("__match **_ll; __match *_m; skeleton *_s;\n", outfile);
3054: - fputs ("{ NODEPTR root = _s->root;\n", outfile);
3055: - fputs ("COST cost; cost = DEFAULT_COST;\n", outfile);
3056: - fputs ("switch(_m->tree) {\n", outfile);
3057: - for(pp=lists[A_COST].first; pp!=NULL; pp=pp->link) {
3058: - if ((tap=pp->sd.ca.assoc)==NULL) {
3059: - sem_error2 ("%s not used", pp->name);
3060: - continue;
3061: - }
3062: - for (; tap!=NULL; tap=tap->next)
3063: - fprintf (outfile, "case %d:", tap->tree);
3064: - fputs ("{\n", outfile);
3065: - CodeWrite (outfile, pp->sd.ca.code);
3066: - fputs ("} break;\n", outfile);
3067: - }
3068: - fputs("}\n", outfile);
3069: - fputs("_m->cost = cost; return(xDEFER);}\n", outfile);
3070: -
3071: -}
3072: -
3073: -SymbolWritePath (root)
3074: - Node *root;
3075: -{
3076: - Node *np;
3077: - if(root->nlleaves==0)
3078: - return;
3079: - if((root->sym)->attr==A_LABEL) {
3080: - oputint (eEVAL); oputoct (MV_LABEL((root->sym)->unique));
3081: - return;
3082: - }
3083: - oputint (ePUSH);
3084: - for(np = root->children;;) {
3085: - if(np->nlleaves > 0)
3086: - SymbolWritePath (np);
3087: - if ((np = np->siblings) == NULL)
3088: - break;
3089: - oputint (eNEXT);
3090: - }
3091: - oputint (ePOP);
3092: - return;
3093: -}
3094: -
3095: -static int gensymndx = 0;
3096: -
3097: -char *
3098: -SymbolGenUnique()
3099: -{
3100: - static char name[7];
3101: - name[0] = '$';
3102: - sprintf (&name[1], "%05d", gensymndx++);
3103: - return (name);
3104: -}
3105: //GO.SYSIN DD sym.c
3106: echo sym.h 1>&2
3107: sed 's/.//' >sym.h <<'//GO.SYSIN DD sym.h'
3108: -/* symbol table definitions */
3109: -extern int symbol_undefined;
3110: -
3111: -/*
3112: - * A LabelData structures are associated with label symbols. They
3113: - * indicate that a tree is labelled with the symbol
3114: - */
3115: -typedef struct LabelData LabelData;
3116: -
3117: -struct LabelData {
3118: - Node *tree;
3119: - int treeIndex;
3120: - int lineno;
3121: - SymbolEntry *label; /* back pointer */
3122: - LabelData *next;
3123: -};
3124: -
3125: -struct treeassoc {
3126: - int tree;
3127: - struct treeassoc *next;
3128: -};
3129: -
3130: -struct symbol_entry {
3131: - int hash;
3132: - char *name;
3133: - short attr;
3134: -# define A_UNDEFINED 0
3135: -# define A_NODE 1
3136: -# define A_LABEL 2
3137: -# define A_COST 3
3138: -# define A_ACTION 4
3139: -# define MAXCHAINS A_CONST
3140: -# define HAS_UNIQUE(x) (x<MAXCHAINS)
3141: -# define A_CONST 5
3142: -# define HAS_LIST(x) (x<=A_CONST)
3143: -# define A_ERROR 10
3144: -# define A_KEYWORD 11
3145: - short unique;
3146: - struct symbol_entry *link;
3147: - struct symbol_entry *next;
3148: - union {
3149: - int keyword;
3150: - int cvalue; /* a constant's value */
3151: - int arity; /* information stored for A_NODE type */
3152: - LabelData *lp;
3153: - struct {
3154: - int arity;
3155: - Code *code;
3156: - } predData;
3157: - struct {
3158: - struct treeassoc *assoc;
3159: - Code *code;
3160: - } ca; /* data for cost/action symbols */
3161: - } sd;
3162: -};
3163: -
3164: -extern void SymbolInit();
3165: -extern void SymbolEnter();
3166: -extern SymbolEntry *SymbolLookup();
3167: -extern SymbolEntry *SymbolAllocate();
3168: -extern void SymbolFree();
3169: -extern void SymbolEnterList();
3170: -extern char *SymbolGenUnique();
3171: -
3172: -extern SymbolEntry ErrorSymbol;
3173: -
3174: -/*
3175: - * In order for the walker to access the labelled leaves of a pattern,
3176: - * a table (mistakenly) called the path table is generated (see sym.c).
3177: - * This table contains the following possible values:
3178: - *
3179: - * ePush follow the children link in the walker skeleton.
3180: - * ePop Pop up to parent.
3181: - * eNext follow the siblings link.
3182: - * eEval <arg> The current node is a labelled leaf whose label id
3183: - * is the integer <arg>.
3184: - * eStop All done. stop!
3185: - *
3186: - * The table is interpreted by the _getleaves routine in the walker.
3187: - */
3188: -#define eSTOP 0
3189: -#define ePOP -1
3190: -#define eEVAL -2
3191: -#define eNEXT -3
3192: -#define ePUSH -4
3193: //GO.SYSIN DD sym.h
3194: echo trees.c 1>&2
3195: sed 's/.//' >trees.c <<'//GO.SYSIN DD trees.c'
3196: -#include "common.h"
3197: -#include "code.h"
3198: -#include "sym.h"
3199: -#include "mem.h"
3200: -
3201: -struct _mem node_mem;
3202: -
3203: -void
3204: -TreeFree(root)
3205: - Node *root;
3206: -{
3207: - if(root==NULL) return;
3208: - TreeFree(root->children);
3209: - TreeFree(root->siblings);
3210: - free(root);
3211: -}
3212: -
3213: -void
3214: -TreePrint(tree, flag)
3215: - Node *tree;
3216: - int flag;
3217: -{
3218: - if(tree==NULL)
3219: - return;
3220: - printf("%s", (tree->sym)->name);
3221: - putchar('(');
3222: - TreePrint(tree->children, 0);
3223: - putchar(')');
3224: - if(tree->siblings!=NULL) {
3225: - putchar(',');
3226: - TreePrint(tree->siblings, 0);
3227: - }
3228: - if(flag) putchar('\n');
3229: -}
3230: -
3231: -Node *
3232: -rev (sl, nl, nlleaves)
3233: - Node *sl, *nl;
3234: - int *nlleaves;
3235: -{
3236: - Node *sl2;
3237: - if(sl==NULL)
3238: - return(nl);
3239: - sl2 = sl->siblings;
3240: - sl->siblings = nl;
3241: - *nlleaves += sl->nlleaves;
3242: - return (rev (sl2, sl, nlleaves));
3243: -}
3244: -
3245: -Node *
3246: -TreeBuild (symp, children)
3247: - SymbolEntry *symp;
3248: - Node *children;
3249: -{
3250: - Node *np = (struct node *) mem_get(&node_mem);
3251: - np->sym = symp;
3252: - np->nlleaves = symp->attr==A_LABEL ? 1 : 0;
3253: - np->children = rev (children, NULL, &np->nlleaves);
3254: - return(np);
3255: -}
3256: -
3257: -TreeInit()
3258: -{
3259: - mem_init(&node_mem, sizeof(struct node));
3260: -}
3261: -
3262: -cntnodes(np)
3263: - Node *np;
3264: -{
3265: - if(np==NULL) return(0);
3266: - else return(1+cntnodes(np->children)+cntnodes(np->siblings));
3267: -}
3268: //GO.SYSIN DD trees.c
3269: echo twig.y 1>&2
3270: sed 's/.//' >twig.y <<'//GO.SYSIN DD twig.y'
3271: -%term ERROR
3272: -%{
3273: -#include "common.h"
3274: -#include "code.h"
3275: -#include "sym.h"
3276: -#define UNDEFINED -1
3277: -#define GIVENUP -2
3278: -
3279: -int debug_flag = 0;
3280: -int Dflag = 0;
3281: -int tflag = 0;
3282: -int line_xref_flag = 0;
3283: -int ntrees = 0;
3284: -int nerrors = 0;
3285: -int fatalerrors = 0;
3286: -int tree_lineno;
3287: -FILE *outfile;
3288: -FILE *symfile;
3289: -Code *epilogue;
3290: -
3291: -SymbolEntry ErrorSymbol;
3292: -%}
3293: -%union {
3294: - Node *y_nodep;
3295: - SymbolEntry *y_symp;
3296: - Code *y_code;
3297: - int y_int;
3298: -}
3299: -%start pattern_spec
3300: -%term K_NODE K_LABEL K_PROLOGUE K_CONST K_INSERT
3301: -%term K_COST K_ACTION
3302: -%token <y_symp> ID
3303: -%token <y_int> NUMBER
3304: -%token <y_code> CBLOCK
3305: -%type <y_nodep> tree tree_list
3306: -%type <y_symp> id_list label assoc_list assoc assoc_list2 assoc2
3307: -%type <y_symp> const_list const_def
3308: -%type <y_int> arity_spec constant
3309: -%type <y_symp> action cost
3310: -%%
3311: -
3312: -pattern_spec: declarations patternsOrInserts =
3313: - { if (nerrors==0) machine_build(); };
3314: -
3315: -declarations: declarations decl
3316: - | decl;
3317: -
3318: -decl: K_NODE assoc_list ';' = { SymbolEnterList ($2, A_NODE); }
3319: -
3320: - | K_NODE assoc_list2 ';'
3321: - = {
3322: - SymbolEnterList($2, A_NODE);
3323: - SymbolCheckNodeValues();
3324: - }
3325: -
3326: - | K_CONST const_list ';' = { SymbolEnterList ($2, A_CONST); }
3327: -
3328: - | K_LABEL id_list ';' = { SymbolEnterList ($2, A_LABEL); }
3329: -
3330: - | K_PROLOGUE CBLOCK ';' = { CodeWrite(outfile, $2); CodeFreeBlock($2); }
3331: -
3332: - | K_COST ID CBLOCK ';'
3333: - = { $2->sd.ca.code = $3; $2->sd.ca.assoc = NULL;
3334: - SymbolEnter ($2, A_COST); }
3335: -
3336: - | K_ACTION ID CBLOCK ';'
3337: - = { $2->sd.ca.code = $3; $2->sd.ca.assoc = NULL;
3338: - SymbolEnter ($2, A_ACTION); }
3339: -
3340: - | K_PROLOGUE error ';'
3341: - | K_ACTION error ';'
3342: - | K_COST error ';'
3343: - ;
3344: -
3345: -/*
3346: - * The rule id_list, assoc_list, and const_list build lists of identifiers.
3347: - * The field "next" is used as a link. This field is also used by the symbol
3348: - * table manager and thus the next field may not be used unless the identifiers
3349: - * have not already been defined.
3350: - */
3351: -
3352: -id_list:
3353: - id_list ID = {
3354: - if(CheckIsUndefined($2)) {
3355: - $2->next = $1;
3356: - $$ = $2;
3357: - } else $$ = $1;
3358: - }
3359: - | ID { if(CheckIsUndefined($1)) $$ = $1; else $$ = NULL; }
3360: - | id_list error;
3361: -
3362: -/*
3363: - * Assoc_list2 allows user assignment of node values
3364: - */
3365: -assoc_list2:
3366: - assoc_list2 assoc2
3367: - = {
3368: - if($2->attr==A_ERROR)
3369: - $$ = $1;
3370: - else { $2->next = $1; $$ = $2; }
3371: - }
3372: - | assoc2 { $$ = $1->attr==A_ERROR ? NULL : $1; }
3373: - | assoc_list2 error;
3374: -
3375: -assoc_list:
3376: - assoc_list assoc = {
3377: - if($2->attr==A_ERROR) $$ = $1;
3378: - else { $2->next = $1; $$ = $2; }
3379: - }
3380: - | assoc { $$ = $1->attr==A_ERROR ? NULL : $1; }
3381: - | assoc_list error;
3382: -
3383: -assoc: ID arity_spec
3384: - = {
3385: - if (CheckIsUndefined($1)) {
3386: - $1->sd.arity = $2; $$ = $1;
3387: - } else $$ = &ErrorSymbol;
3388: - };
3389: -
3390: -assoc2:
3391: - ID arity_spec '=' constant {
3392: - if(CheckIsUndefined($1)) {
3393: - $1->unique = $4; $1->sd.arity = $2;
3394: - $$ = $1;
3395: - } else $$ = &ErrorSymbol;
3396: - };
3397: -
3398: -arity_spec:
3399: - '(' constant ')' = { $$ = $2; };
3400: - | '(' '*' ')' = { $$=GIVENUP; };
3401: - | = { $$ = UNDEFINED; };
3402: -
3403: -const_list:
3404: - const_list const_def = {
3405: - if ($2->attr==A_ERROR) $$ = $1;
3406: - else { $2->next = $1; $$ = $2; }
3407: - }
3408: - | const_def { $$ = $1->attr==A_ERROR ? NULL : $1; }
3409: - | const_list error;
3410: -
3411: -const_def:
3412: - ID '=' constant = {
3413: - if(CheckIsUndefined($1)) {
3414: - $1->sd.cvalue = $3; $$ = $1;
3415: - } else $$ = &ErrorSymbol;
3416: - };
3417: -
3418: -constant:
3419: - NUMBER
3420: - | ID = {
3421: - if(!CheckIsDefined($1)) $$ = UNDEFINED;
3422: - else if($1->attr!=A_CONST) {
3423: - sem_error("non-constant id used");
3424: - $$ = -1;
3425: - } else $$ = $1->sd.cvalue;
3426: - };
3427: -
3428: -patternsOrInserts: patternsOrInserts pattern
3429: - | patternsOrInserts insert
3430: - | insert
3431: - | pattern
3432: - ;
3433: -
3434: -insert: K_INSERT CBLOCK ';' = { epilogue = CodeAppend(epilogue, $2); }
3435: - | K_INSERT error ';'
3436: - ;
3437: -
3438: -pattern:
3439: - label ':' tree cost action ';' = {
3440: - if ($1->attr==A_ERROR) {
3441: - error(0, "\"label: tree\" pair ignored");
3442: - TreeFree($3);
3443: - } else {
3444: - if(nerrors==0)
3445: - cgotofn(SymbolEnterTreeIntoLabel($1,
3446: - $3, $4, $5, tree_lineno));
3447: - if(debug_flag&DB_TREE)
3448: - TreePrint($3, 1);
3449: - }
3450: - }
3451: - | error ';' ;
3452: -
3453: -action: '=' CBLOCK { SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
3454: - sp->sd.ca.code = $2; sp->sd.ca.assoc = NULL;
3455: - SymbolEnter(sp, A_ACTION); $$ = sp; }
3456: - | '=' ID { if(CheckIsDefined($2)) {
3457: - if ($2->attr!=A_ACTION) {
3458: - sem_error ("non action id: %s", $2->name);
3459: - $$ = &ErrorSymbol;
3460: - } else $$ = $2;
3461: - } else $$ = &ErrorSymbol; }
3462: - | { $$ = NULL;};
3463: -
3464: -cost: CBLOCK { SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
3465: - sp->sd.ca.code = $1; sp->sd.ca.assoc = NULL;
3466: - SymbolEnter (sp, A_COST); $$ = sp;
3467: - }
3468: - | ID { if (CheckIsDefined($1)) {
3469: - if ($1->attr!=A_COST) {
3470: - sem_error ("non cost id: %s", $1->name);
3471: - $$ = &ErrorSymbol;
3472: - } else $$ = $1;
3473: - } else $$ = &ErrorSymbol; }
3474: - | { $$ = NULL; };
3475: -
3476: -/* labels play the same role that non-terminals do in YACC */
3477: -label: ID = {
3478: - tree_lineno = yyline; /* record line no */
3479: - if(!CheckIsDefined($1))
3480: - $1->attr = A_ERROR;
3481: - else if(!is_label($1)) {
3482: - sem_error("non label id: %s", $1->name);
3483: - $1->attr = A_ERROR;
3484: - }
3485: - $$ = $1;
3486: - };
3487: -
3488: -tree: ID {CheckIsNodeOrPred($1);} '(' tree_list ')'
3489: - = {
3490: - int count;
3491: - Node *ap;
3492: - /* check the arity of the node */
3493: - for(count=0, ap = $4; ap!=NULL; ap=ap->siblings) count++;
3494: - switch($1->attr) {
3495: - case A_NODE:
3496: - set_arity($1, &$1->sd.arity, count);
3497: - break;
3498: - }
3499: -
3500: - $$ = TreeBuild ($1, $4);
3501: - }
3502: - | ID
3503: - = {
3504: - CheckIsDefined($1);
3505: - switch ($1->attr) {
3506: - case A_NODE:
3507: - set_arity($1, &$1->sd.arity, 0);
3508: - break;
3509: - }
3510: - $$ = TreeBuild ($1, NULL);
3511: - };
3512: -
3513: -tree_list: tree_list ',' tree = {
3514: - /*
3515: - * build sibling list in reverse order TreeBuild will
3516: - * put it right later.
3517: - */
3518: - $3->siblings = $1;
3519: - $$ = $3;
3520: - }
3521: - | tree = { $1->siblings = NULL; $$ = $1; }
3522: - | error { $$ = NULL; };
3523: - | tree_list error;
3524: -
3525: -%%
3526: -
3527: -extern char *process_suffix();
3528: -
3529: -set_arity(symp, arityp, count)
3530: - SymbolEntry *symp;
3531: - int *arityp;
3532: - int count;
3533: -{
3534: - if(*arityp!=GIVENUP) {
3535: - if (*arityp==UNDEFINED)
3536: - *arityp = count;
3537: - else if (*arityp!=count) {
3538: - sem_error("inconsistent arity for %s", symp->name);
3539: - *arityp = GIVENUP;
3540: - }
3541: - }
3542: -}
3543: -
3544: -is_node(symp)
3545: - SymbolEntry *symp;
3546: -{ return(symp->attr==A_NODE); }
3547: -
3548: -is_label(symp)
3549: - SymbolEntry *symp;
3550: -{ return(symp->attr==A_LABEL); }
3551: -
3552: -CheckIsNodeOrPred (symp)
3553: - SymbolEntry *symp;
3554: -{
3555: - if (symp->attr==A_ERROR)
3556: - return;
3557: - if (symp->attr!=A_NODE)
3558: - sem_error ("non-node identifier %s", symp->name);
3559: -}
3560: -
3561: -CheckIsUndefined(symp)
3562: - SymbolEntry *symp;
3563: -{
3564: - if (symp->attr==A_ERROR)
3565: - return(0);
3566: - if (symp->attr!=A_UNDEFINED) {
3567: - sem_error ("multiple declaration: %s", symp->name);
3568: - return(0);
3569: - } else return(1);
3570: -}
3571: -
3572: -CheckIsDefined(symp)
3573: - SymbolEntry *symp;
3574: -{
3575: - if (symp->attr==A_ERROR)
3576: - return(0);
3577: - if (symp->attr==A_UNDEFINED) {
3578: - sem_error ("undefined identifier: %s", symp->name);
3579: - symp->attr=A_ERROR;
3580: - return(0);
3581: - } else return(1);
3582: -}
3583: -
3584: -
3585: -
3586: -/*VARARGS*/
3587: -yyerror(fmt, s1, s2, s3)
3588: - char *fmt, *s1, *s2, *s3;
3589: -{
3590: - fprintf(stderr, "line %d: ", yyline);
3591: - fprintf(stderr, fmt, s1, s2, s3);
3592: - if (token_buffer[0]!=0)
3593: - fprintf(stderr, " at \"%s\"\n", token_buffer);
3594: -}
3595: -
3596: -/*VARARGS*/
3597: -yyerror2 (fmt, s1, s2, s3)
3598: - char *fmt, *s1, *s2, *s3;
3599: -{
3600: - fprintf(stderr, "line %d: ", yyline);
3601: - fprintf(stderr, fmt, s1, s2, s3);
3602: - putchar('\n');
3603: -}
3604: -
3605: -char *cmdnam;
3606: -char *inFileName;
3607: -char *outFileName;
3608: -char prefixFile[100];
3609: -static char usage[] = "usage: mt [-d] file";
3610: -#define USAGE error(1, usage)
3611: -char *prefix_base = PREFIX_BASE;
3612: -char *suffix = "c1";
3613: -
3614: -main(argc, argv)
3615: - int argc;
3616: - char **argv;
3617: -{
3618: - int i;
3619: - char *cp;
3620: -
3621: -#ifndef PREFIX_BASE
3622: - error(1,"PREFIX_BASE has not been defined; recompile twig");
3623: -#endif
3624: -
3625: - cmdnam = argv[0];
3626: - argv++;
3627: - inFileName = NULL;
3628: -
3629: - while(--argc > 0) {
3630: - if (*argv[0]=='-')
3631: - switch(argv[0][1]) {
3632: - /* to see what each of these flags mean...
3633: - * see common.h */
3634: - case 'd': {
3635: - char *cp;
3636: - for(cp = &argv[0][2]; *cp!='\0'; cp++)
3637: - switch(*cp) {
3638: - case 'l': debug_flag |= DB_LEX; break;
3639: - case 'm': debug_flag |= DB_MACH; break;
3640: - case 's': debug_flag |= DB_SYM; break;
3641: - case 't': debug_flag |= DB_TREE; break;
3642: - case 'M': debug_flag |= DB_MEM; break;
3643: - }
3644: - }
3645: - break;
3646: - case 'D': Dflag++; break;
3647: - case 't': tflag++; break;
3648: - case 'w': suffix = process_suffix(&argv[0][2]); break;
3649: - case 'l': prefix_base = &argv[0][2]; break;
3650: - case 'x': line_xref_flag++; break;
3651: - default:
3652: - USAGE;
3653: - }
3654: - else inFileName = argv[0];
3655: - argv++;
3656: - }
3657: - if(inFileName==NULL)
3658: - USAGE;
3659: -
3660: - if(freopen(inFileName, "r", stdin)==NULL)
3661: - error(1, "can't open %s", inFileName);
3662: - if((cp=strrchr(inFileName, '.'))!=NULL && strcmp(cp,".mt")==0) {
3663: - if ((outfile = fopen("walker.c" , "w"))==NULL)
3664: - error(1, "can't write %s", outFileName);
3665: - if ((symfile = fopen("symbols.h", "w"))==NULL)
3666: - error(1, "can't write %s", outFileName);
3667: - } else error(1, "input file must have suffix .mt");
3668: -
3669: - ErrorSymbol.attr = A_LABEL;
3670: - TreeInit();
3671: - SymbolInit();
3672: - LexInit();
3673: - yyparse();
3674: -
3675: - SymbolDump();
3676: - if(nerrors == 0) {
3677: - if(!tflag) {
3678: - FILE *prefix;
3679: - char c;
3680: - sprintf(prefixFile, "%s.%s", prefix_base, suffix);
3681: - prefix = fopen(prefixFile, "r");
3682: - assert(prefix!=NULL);
3683: - if(Dflag)
3684: - fputs("#define DEBUG 1\n", outfile);
3685: - if(line_xref_flag)
3686: - fputs("#define LINE_XREF 1\n", outfile);
3687: - fprintf(outfile,"# line 1 \"%s\"\n", prefixFile);
3688: - while((c=getc(prefix))!=EOF) putc(c, outfile);
3689: - }
3690: - MachineGen();
3691: - SymbolGenerateWalkerCode();
3692: - CodeWrite(outfile, epilogue);
3693: - CodeFreeBlock(epilogue);
3694: - }
3695: -
3696: - /* cleanup */
3697: - cleanup(0);
3698: -}
3699: -
3700: -cleanup(retcode)
3701: - int retcode;
3702: -{
3703: - lexCleanup();
3704: - if(retcode==0) {
3705: - SymbolFinish();
3706: - }
3707: - exit(retcode);
3708: -}
3709: -
3710: -/*VARARGS*/
3711: -error(rc, fmt, a1, a2, a3)
3712: - int rc;
3713: - char *fmt, *a1, *a2, *a3;
3714: -{
3715: - fprintf(stderr, "%s: ", cmdnam);
3716: - fprintf(stderr, fmt, a1, a2, a3);
3717: - putc ('\n', stderr);
3718: - if(rc)
3719: - exit (rc);
3720: -}
3721: -
3722: -/*VARARGS*/
3723: -sem_error (fmt, a1, a2, a3)
3724: - char *fmt, *a1, *a2, *a3;
3725: -{
3726: - fprintf (stderr, "line %d: ", yyline);
3727: - sem_error2(fmt, a1, a2, a3);
3728: - nerrors++;
3729: - fatalerrors++;
3730: -}
3731: -
3732: -/*VARARGS*/
3733: -sem_error2(fmt, a1, a2, a3)
3734: - char *fmt, *a1, *a2, *a3;
3735: -{
3736: - fprintf (stderr, fmt, a1, a2, a3);
3737: - putc('\n', stderr);
3738: - nerrors++;
3739: -}
3740: -
3741: -char *
3742: -process_suffix(suf)
3743: - char *suf;
3744: -{
3745: - extern int gen_table2;
3746: - if(strcmp(suf,"exper")==0) {
3747: - /* experimental walker */
3748: - /* expect this to change alot */
3749: - gen_table2++;
3750: - }
3751: - return(suf);
3752: -}
3753: //GO.SYSIN DD twig.y
3754: echo walker.c1 1>&2
3755: sed 's/.//' >walker.c1 <<'//GO.SYSIN DD walker.c1'
3756: -/*
3757: - * The machine is laid out as a sequence of integers in the walker.
3758: - * The form described above is only used inside the preprocessor.
3759: - * Each machine state is one of the following sequence:
3760: - *
3761: - * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
3762: - * or
3763: - * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
3764: - * or
3765: - * ACCEPT <accept table index> -1
3766: - *
3767: - * The accept table is in the form:
3768: - *
3769: - * <tree index_1> ...<tree_index_m> -1
3770: - *
3771: - */
3772: -/* Keutzer - all "short int"'s have been changed to "short" for
3773: - portability to UTS. */
3774: -#include "symbols.h"
3775: -/* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
3776: -#include <varargs.h>
3777: -
3778: -#ifndef FILE
3779: -#include <stdio.h>
3780: -#endif
3781: -#include <assert.h>
3782: -
3783: -/* These constants must be the same as the ones in machine.c */
3784: -#define FASTLIM 0
3785: -#define TABLE 1
3786: -#define FAIL 2
3787: -#define ACCEPT 3
3788: -#define TABLE2 4
3789: -#define EOT -1
3790: -
3791: -/* special machine state */
3792: -#define HANG -1
3793: -
3794: -/* used by the evaluator to interpret path table */
3795: -#define eSTOP 0
3796: -#define ePOP -1
3797: -#define eEVAL -2
3798: -#define eNEXT -3
3799: -#define ePUSH -4
3800: -
3801: -/* Tags that indicate the type of a value */
3802: -#define M_BRANCH 010000
3803: -#define M_NODE 0
3804: -#define M_LABEL 01000
3805: -#define MAX_NODE_VALUE 00777
3806: -#define MTAG_SHIFT 9
3807: -#define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE))
3808: -
3809: -/* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */
3810: -#define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0)
3811: -#define MI_DEFINED(x) ((x)!=-1)
3812: -#define MI_LABEL(x) (((x)&M_LABEL)!=0)
3813: -#define MI_BRANCH(x) (((x)&M_BRANCH)!=0)
3814: -
3815: -/* build a tagged value */
3816: -#define MV_NODE(x) (x)
3817: -#define MV_BRANCH(x) ((x)|M_BRANCH)
3818: -#define MV_LABEL(x) ((x)|M_LABEL)
3819: -
3820: -/* limits */
3821: -/*
3822: - * The depth of a pattern must be 7 or less. Otherwise the type of he
3823: - * partial mask in skeleton must be changed
3824: - */
3825: -#define MAXDEPTH 7
3826: -
3827: -/* modes */
3828: -#define xTOPDOWN 3
3829: -#define xABORT 2
3830: -#define xREWRITE 1
3831: -#define xDEFER 0
3832: -
3833: -/* macros */
3834: -#define tDO(m) _do((m)->skel, (m), 1)
3835: -#define REWRITE return(_m->cost = cost, xREWRITE)
3836: -#define TOPDOWN return(_m->cost = cost, xTOPDOWN)
3837: -#define ABORT return(xABORT)
3838: -
3839: -/*
3840: - * REORDER macro allows a knowledgeable user to change the order
3841: - * of evaluation of the leaves.
3842: - */
3843: -#ifndef REORDER
3844: -#define REORDER(list) _evalleaves(list)
3845: -#endif
3846: -#define EVAL REORDER(_ll)
3847: -
3848: -#define mpush(s,m) (m)->next = s, s = m
3849: -
3850: -/* skeleton structure */
3851: -typedef struct skeleton skeleton;
3852: -typedef struct __match __match;
3853: -typedef struct __partial __partial;
3854: -typedef struct __hshcls __hshcls; /* a hashed closure entry */
3855: -typedef int labelset; /* a bit vector of labels */
3856: -
3857: -struct __partial {
3858: - unsigned char treeno;
3859: - char bits;
3860: -};
3861: -
3862: -struct __hshcls {
3863: - __hshcls *next;
3864: - labelset labels;
3865: - int treecnt; /* number of partial matches */
3866: - __partial partial[MAXTREES];
3867: -};
3868: -
3869: -struct skeleton {
3870: - skeleton *sibling;
3871: - skeleton *leftchild; /* leftmost child */
3872: - skeleton *rightchild; /* rightmost child */
3873: - NODEPTR root;
3874: - NODEPTR parent; /* our parent */
3875: - int nson;
3876: - int treecnt;
3877: - __match *succ[MAXLABELS];
3878: - __partial *partial;
3879: - __match *winner;
3880: - COST mincost;
3881: -};
3882: -
3883: -struct __match {
3884: - __match **lleaves; /* labelled leaves */
3885: - skeleton *skel; /* back pointer to associated skeleton node */
3886: - COST cost;
3887: - short tree;
3888: - short mode;
3889: -};
3890: -
3891: -struct freeb {
3892: - struct freeb *next;
3893: -};
3894: -
3895: -struct _mem {
3896: - struct _mem *next;
3897: - int size; /* size of individual elements in bytes */
3898: - int blkf; /* blocking factor */
3899: - int bsize; /* block size */
3900: - char *block; /* block */
3901: - int cnt; /* count of free elem in block */
3902: - char *freelist; /* free list */
3903: - int totelem; /* total number elements we have */
3904: - int freecnt; /* number of times mem_free was called */
3905: -};
3906: -
3907: -/* turn this flag on if your machine has a fast byte string zero operation */
3908: -/*#define BZERO 1*/
3909: -int mtDebug = 0;
3910: -int treedebug = 0;
3911: -extern int _machstep();
3912: -extern short mtStart;
3913: -extern short mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
3914: -#ifdef LINE_XREF
3915: - extern short mtLine[];
3916: -#endif
3917: -
3918: -#ifndef MPBSIZE
3919: -#define MPBSIZE 8000
3920: -#endif
3921: -
3922: -#ifdef ADDCOST
3923: -#define DEFAULT_COST sumleaves(_ll)
3924: -COST sumleaves(list) __match **list;
3925: -{COST cost;
3926: - cost=ZEROCOST;
3927: - for(; *list; list++)
3928: - {ADDCOST((cost),(*list)->cost);
3929: - }
3930: - return cost;
3931: -}
3932: -#endif
3933: -
3934: -extern NODEPTR mtGetNodes(), mtAction();
3935: -extern skeleton *_allocskel();
3936: -extern __match *_allocmatch();
3937: -extern __partial *_allocpartial();
3938: -
3939: -__match *_mpblock[MPBSIZE], **_mpbtop;
3940: -
3941: -__match **
3942: -_getleaves (mp, skp)
3943: - register __match *mp; register skeleton *skp;
3944: -{
3945: - skeleton *stack[MAXDEPTH];
3946: - skeleton **stp = stack;
3947: - register short *sip = &mtPaths[mtPathStart[mp->tree]];
3948: - register __match **mmp = _mpbtop;
3949: - __match **mmp2 = mmp;
3950: - if((_mpbtop += *sip++ + 1) > &_mpblock[MPBSIZE]) {
3951: - printf("Tree too large: make MPBSIZE larger.\n\
3952: -(i.e. cc -c -DMPBSIZE=%d walker.c)\n",MPBSIZE*2);
3953: - assert(0);
3954: - }
3955: -
3956: - for(;;)
3957: - switch(*sip++) {
3958: - case ePUSH:
3959: - *stp++ = skp;
3960: - skp = skp->leftchild;
3961: - break;
3962: -
3963: - case eNEXT:
3964: - skp = skp->sibling;
3965: - break;
3966: -
3967: - case eEVAL:
3968: - if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
3969: - *mmp++ = mp;
3970: - break;
3971: -
3972: - case ePOP:
3973: - skp = *--stp;
3974: - break;
3975: -
3976: - case eSTOP:
3977: - *mmp = NULL;
3978: - return (mmp2);
3979: - }
3980: -}
3981: -
3982: -_evalleaves (mpp)
3983: - register __match **mpp;
3984: -{
3985: - for (; *mpp!=NULL; mpp++) {
3986: - register __match *mp = *mpp;
3987: - _do (mp->skel, mp, 1);
3988: - }
3989: -}
3990: -
3991: -
3992: -_do(sp, winner, evalall)
3993: - skeleton *sp; register __match *winner; int evalall;
3994: -{
3995: - register __match **mpp;
3996: - register skeleton *skel = winner->skel;
3997: - if(winner==NULL) {
3998: - _nowin(sp);
3999: - return;
4000: - }
4001: - if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
4002: - REORDER(winner->lleaves);
4003: - mtSetNodes (skel->parent, skel->nson,
4004: - skel->root=mtAction (winner->tree, winner->lleaves, sp));
4005: -}
4006: -
4007: -skeleton *
4008: -_walk(sp, ostate)
4009: - register skeleton *sp;
4010: - int ostate;
4011: -{
4012: - int state, nstate, nson;
4013: - register __partial *pp;
4014: - register __match *mp, *mp2;
4015: - register skeleton *nsp, *lastchild = NULL;
4016: - NODEPTR son, root;
4017: -
4018: - root = sp->root;
4019: - nson = 1; sp->mincost = INFINITY;
4020: - state = _machstep (ostate, root, mtValue(root));
4021: -
4022: - while((son = mtGetNodes(root, nson))!=NULL) {
4023: - nstate = _machstep (state, NULL, MV_BRANCH(nson));
4024: - nsp = _allocskel();
4025: - nsp->root = son;
4026: - nsp->parent = root;
4027: - nsp->nson = nson;
4028: - _walk(nsp, nstate);
4029: - if(COSTLESS(nsp->mincost,INFINITY)) {
4030: - assert (nsp->winner->mode==xREWRITE);
4031: - _do(nsp, nsp->winner, 0);
4032: - _freeskel(nsp);
4033: - continue;
4034: - }
4035: - _merge (sp, nsp);
4036: - if (lastchild==NULL) sp->leftchild = nsp;
4037: - else lastchild->sibling = nsp;
4038: - lastchild = nsp;
4039: - nson++;
4040: - }
4041: -
4042: - for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
4043: - if (pp->bits&01==1) {
4044: - mp = _allocmatch();
4045: - mp->tree = pp->treeno;
4046: - _addmatches (ostate, sp, mp);
4047: - }
4048: - if(son==NULL && nson==1)
4049: - _closure (state, ostate, sp);
4050: -
4051: - sp->rightchild = lastchild;
4052: - if (root==NULL) {
4053: - COST c; __match *win; int i; nsp = sp->leftchild;
4054: - c = INFINITY;
4055: - win = NULL;
4056: - for (i = 0; i < MAXLABELS; i++) {
4057: - mp = nsp->succ[i];
4058: - if (mp!=NULL && COSTLESS (mp->cost, c))
4059: - { c = mp->cost; win = mp; }
4060: - }
4061: - _do (nsp, win, 0);
4062: - }
4063: - return(sp);
4064: -}
4065: -
4066: -/*
4067: - * Convert the start state which has a large branching factor into
4068: - * a index table. This must be called before the matcher is used.
4069: - */
4070: -static short _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
4071: -_matchinit()
4072: -{
4073: - short *sp;
4074: -/* Keutzer - this syntax doesn't work on UTS
4075: - struct pair { short val, where } *pp;
4076: -*/
4077: - struct pair { short val; short where; } *pp;
4078: - for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
4079: - for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
4080: - sp = &mtTable[mtStart];
4081: - assert (*sp==TABLE);
4082: - for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
4083: - if (MI_NODE(pp->val))
4084: - _nodetab[M_DETAG(pp->val)] = pp->where;
4085: - else if (MI_LABEL(pp->val))
4086: - _labeltab[M_DETAG(pp->val)] = pp->where;
4087: - }
4088: -}
4089: -
4090: -int
4091: -_machstep(state, root, input)
4092: - short state, input;
4093: - NODEPTR root;
4094: -{
4095: - register short *stp = &mtTable[state];
4096: - int start = 0;
4097: - if (state==HANG)
4098: - return (input==(MV_BRANCH(1)) ? mtStart : HANG);
4099: -rescan:
4100: - if (stp==&mtTable[mtStart]) {
4101: - if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
4102: - if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
4103: - }
4104: -
4105: - for(;;) {
4106: - if(*stp==ACCEPT) stp += 2;
4107: -
4108: - if(*stp==TABLE) {
4109: - stp++;
4110: - while(*stp!=EOT) {
4111: - if(input==*stp) {
4112: - return(*++stp);
4113: - }
4114: - stp += 2;
4115: - }
4116: - stp++;
4117: - }
4118: - if(*stp!=FAIL) {
4119: - if (start) return (HANG);
4120: - else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
4121: - } else {
4122: - stp++;
4123: - stp = &mtTable[*stp];
4124: - goto rescan;
4125: - }
4126: - }
4127: -}
4128: -
4129: -_addmatches(ostate, sp, np)
4130: - int ostate;
4131: - register skeleton *sp;
4132: - register __match *np;
4133: -{
4134: - int label;
4135: - int state;
4136: - register __match *mp;
4137: -
4138: - label = mtMap[np->tree];
4139: -
4140: - /*
4141: - * this is a very poor substitute for good design of the DFA.
4142: - * What we need is a special case that allows any label to be accepted
4143: - * by the start state but we don't want the start state to recognize
4144: - * them after a failure.
4145: - */
4146: - state = _machstep(ostate, NULL, MV_LABEL(label));
4147: - if (ostate!=mtStart && state==HANG) {
4148: - _freematch(np);
4149: - return;
4150: - }
4151: -
4152: - np->lleaves = _getleaves (np, sp);
4153: - np->skel = sp;
4154: - if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
4155: - {
4156: - _freematch(np);
4157: - return;
4158: - }
4159: -
4160: -/*
4161: - if(np->mode==xREWRITE && COSTLESS(np->cost, sp->mincost)) {
4162: - sp->mincost = np->cost;
4163: - sp->winner = np;
4164: - }
4165: -*/
4166: - if ((mp = sp->succ[label])!=NULL) {
4167: - if (!COSTLESS (np->cost, mp->cost))
4168: - { _freematch(np); return; }
4169: - else _freematch(mp);
4170: - }
4171: - if(COSTLESS(np->cost,sp->mincost)) {
4172: - if(np->mode==xREWRITE) {
4173: - sp->mincost = np->cost; sp->winner = np; }
4174: - else { sp->mincost = INFINITY; sp->winner = NULL; }
4175: - }
4176: - sp->succ[label] = np;
4177: - _closure(state, ostate, sp);
4178: -}
4179: -
4180: -_closure(state, ostate, skp)
4181: - int state, ostate;
4182: - skeleton *skp;
4183: -{
4184: - register struct ap { short tree, depth; } *ap;
4185: - short *sp = &mtTable[state];
4186: - register __match *mp;
4187: -
4188: - if(state==HANG || *sp!=ACCEPT) return(NULL);
4189: -
4190: - for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
4191: - if (ap->depth==0) {
4192: - mp = _allocmatch();
4193: - mp->tree = ap->tree;
4194: - _addmatches (ostate, skp, mp);
4195: - } else {
4196: - register __partial *pp, *lim = &skp->partial[skp->treecnt];
4197: - for(pp=skp->partial; pp < lim; pp++)
4198: - if(pp->treeno==ap->tree)
4199: - break;
4200: - if(pp==lim) {
4201: - skp->treecnt++;
4202: - pp->treeno = ap->tree;
4203: - pp->bits = (1<<(ap->depth));
4204: - } else pp->bits |= (1<<(ap->depth));
4205: - }
4206: -}
4207: -
4208: -_merge (old, new)
4209: - skeleton *old, *new;
4210: -{
4211: - register __partial *op = old->partial, *np = new->partial;
4212: - int nson = new->nson;
4213: - register __partial *lim = np + new->treecnt;
4214: - if (nson==1) {
4215: - old->treecnt = new->treecnt;
4216: - for(; np < lim; op++, np++) {
4217: - op->treeno = np->treeno;
4218: - op->bits = np->bits/2;
4219: - }
4220: - } else {
4221: - __partial *newer = _allocpartial();
4222: - register __partial *newerp = newer;
4223: - register int cnt;
4224: - lim = op+old->treecnt;
4225: - for(cnt=new->treecnt; cnt-- ; np++) {
4226: - for(op = old->partial; op < lim; op++)
4227: - if (op->treeno == np->treeno) {
4228: - newerp->treeno = op->treeno;
4229: - newerp++->bits = op->bits & (np->bits/2);
4230: - break;
4231: - }
4232: - }
4233: - _freepartial(old->partial);
4234: - old->partial = newer;
4235: - old->treecnt = newerp-newer;
4236: - }
4237: -}
4238: -
4239: -/* Save and Allocate Matches */
4240: -#define BLKF 100
4241: -__match *freep = NULL;
4242: -static int _count = 0;
4243: -static __match *_blockp = NULL;
4244: -#ifdef CHECKMEM
4245: -int x_matches, f_matches;
4246: -#endif
4247: -
4248: -__match *
4249: -_allocmatch()
4250: -{
4251: - __match *mp;
4252: -
4253: - if(freep!=NULL) {
4254: - mp = freep;
4255: - freep = ((__match *)((struct freeb *) freep)->next);
4256: -#ifdef CHECKMEM
4257: - f_matches--;
4258: -#endif
4259: - } else {
4260: - if(_count==0) {
4261: - _blockp = (__match *) malloc (BLKF*sizeof (__match));
4262: - _count = BLKF;
4263: -#ifdef CHECKMEM
4264: - x_matches += BLKF;
4265: -#endif
4266: - }
4267: - mp = _blockp++;
4268: - _count--;
4269: - }
4270: - return(mp);
4271: -}
4272: -
4273: -_freematch(mp)
4274: - __match *mp;
4275: -{
4276: - ((struct freeb *) mp)->next = (struct freeb *) freep;
4277: - freep = mp;
4278: -#ifdef CHECKMEM
4279: - f_matches++;
4280: -#endif
4281: -}
4282: -
4283: -static __partial *pfreep = NULL;
4284: -static int pcount = 0;
4285: -static __partial *pblock = NULL;
4286: -#ifdef CHECKMEM
4287: -static int x_partials, f_partials;
4288: -#endif
4289: -
4290: -__partial *
4291: -_allocpartial()
4292: -{
4293: - __partial *pp;
4294: - if (pfreep!=NULL) {
4295: - pp = pfreep;
4296: - pfreep = *(__partial **) pp;
4297: -#ifdef CHECKMEM
4298: - f_partials--;
4299: -#endif
4300: - } else {
4301: - if (pcount==0) {
4302: - pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
4303: - pcount = BLKF;
4304: -#ifdef CHECKMEM
4305: - x_partials += BLKF;
4306: -#endif
4307: - }
4308: - pp = pblock;
4309: - pblock += MAXTREES;
4310: - pcount--;
4311: - }
4312: - return(pp);
4313: -}
4314: -
4315: -_freepartial(pp)
4316: - __partial *pp;
4317: -{
4318: - * (__partial **)pp = pfreep;
4319: - pfreep = pp;
4320: -#ifdef CHECKMEM
4321: - f_partials++;
4322: -#endif
4323: -}
4324: -
4325: -
4326: -/* storage management */
4327: -static skeleton *sfreep = NULL;
4328: -static int scount = 0;
4329: -static skeleton * sblock = NULL;
4330: -
4331: -skeleton *
4332: -_allocskel()
4333: -{
4334: - skeleton *sp;
4335: - int i;
4336: - if(sfreep!=NULL) {
4337: - sp = sfreep;
4338: - sfreep = sp->sibling;
4339: - } else {
4340: - if(scount==0) {
4341: - sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
4342: - scount = BLKF;
4343: - }
4344: - sp = sblock++;
4345: - scount--;
4346: - }
4347: - sp->sibling = NULL; sp->leftchild = NULL;
4348: - for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
4349: - sp->treecnt = 0;
4350: - sp->partial = _allocpartial();
4351: - return(sp);
4352: -}
4353: -
4354: -_freeskel(sp)
4355: - skeleton *sp;
4356: -{
4357: - int i;
4358: - __match *mp;
4359: - if(sp==NULL) return;
4360: - _freeskel (sp->leftchild);
4361: - _freeskel (sp->sibling);
4362: - _freepartial (sp->partial);
4363: - for (i=0; i < MAXLABELS; i++)
4364: - if ((mp = sp->succ[i])!=NULL) _freematch (mp);
4365: - sp->sibling = sfreep;
4366: - sfreep = sp;
4367: -}
4368: -
4369: -_match()
4370: -{
4371: - skeleton *sp;
4372: - sp = _allocskel();
4373: - sp->root = NULL;
4374: - _mpbtop = _mpblock;
4375: - _freeskel(_walk(sp, HANG));
4376: -#ifdef CHECKMEM
4377: - if(f_matches+_count!=x_matches) {
4378: - printf(";#m %d %d %d\n", f_matches, _count, x_matches);
4379: - assert(0);
4380: - }
4381: - if(f_partials+pcount!=x_partials) {
4382: - printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
4383: - assert(0);
4384: - }
4385: -#endif
4386: -}
4387: -
4388: -/* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
4389: -NODEPTR _mtG(va_alist)
4390: -va_dcl
4391: -{
4392: - NODEPTR root;
4393: - int i=0;
4394: - va_list p_var;
4395: - va_start(p_var);
4396: - root = va_arg(p_var,NODEPTR);
4397: - while( (i = va_arg(p_var,int)) != -1){
4398: - root = mtGetNodes(root, i);
4399: - }
4400: - va_end(p_var);
4401: - return(root);
4402: -}
4403: -
4404: -/* diagnostic routines */
4405: -#ifdef NOMARK
4406: -markIfNoMatch(skp,mark)
4407: - skeleton *skp;
4408: - int mark;
4409: -{}
4410: -#else
4411: -markIfNoMatch(skp,mark) skeleton *skp; int mark;
4412: -{skeleton *child; int i; int found=0;
4413: - for(i=0; i<MAXLABELS; i++)
4414: - if (skp->succ[i]) found=1;
4415: - if (!found) skp->root->mark=mark;
4416: - for(child=skp->leftchild; child; child=child->sibling)
4417: - markIfNoMatch(child,mark);
4418: -}
4419: -#endif
4420: -
4421: -_nowin(skp) skeleton *skp;
4422: -{
4423: - markIfNoMatch(skp,1);
4424: - printf("# No match was found for the nodes printed in lowercase\n");
4425: - printTree(skp->root);
4426: - markIfNoMatch(skp,0);
4427: -}
4428: //GO.SYSIN DD walker.c1
4429: echo y.tab.c 1>&2
4430: sed 's/.//' >y.tab.c <<'//GO.SYSIN DD y.tab.c'
4431: -# define ERROR 257
4432: -
4433: -# line 3 "twig.y"
4434: -#include "common.h"
4435: -#include "code.h"
4436: -#include "sym.h"
4437: -#define UNDEFINED -1
4438: -#define GIVENUP -2
4439: -
4440: -int debug_flag = 0;
4441: -int Dflag = 0;
4442: -int tflag = 0;
4443: -int line_xref_flag = 0;
4444: -int ntrees = 0;
4445: -int nerrors = 0;
4446: -int fatalerrors = 0;
4447: -int tree_lineno;
4448: -FILE *outfile;
4449: -FILE *symfile;
4450: -Code *epilogue;
4451: -
4452: -SymbolEntry ErrorSymbol;
4453: -
4454: -# line 23 "twig.y"
4455: -typedef union {
4456: - Node *y_nodep;
4457: - SymbolEntry *y_symp;
4458: - Code *y_code;
4459: - int y_int;
4460: -} YYSTYPE;
4461: -# define K_NODE 258
4462: -# define K_LABEL 259
4463: -# define K_PROLOGUE 260
4464: -# define K_CONST 261
4465: -# define K_INSERT 262
4466: -# define K_COST 263
4467: -# define K_ACTION 264
4468: -# define ID 265
4469: -# define NUMBER 266
4470: -# define CBLOCK 267
4471: -#define yyclearin yychar = -1
4472: -#define yyerrok yyerrflag = 0
4473: -extern int yychar;
4474: -extern short yyerrflag;
4475: -#ifndef YYMAXDEPTH
4476: -#define YYMAXDEPTH 150
4477: -#endif
4478: -YYSTYPE yylval, yyval;
4479: -# define YYERRCODE 256
4480: -
4481: -# line 255 "twig.y"
4482: -
4483: -
4484: -extern char *process_suffix();
4485: -
4486: -set_arity(symp, arityp, count)
4487: - SymbolEntry *symp;
4488: - int *arityp;
4489: - int count;
4490: -{
4491: - if(*arityp!=GIVENUP) {
4492: - if (*arityp==UNDEFINED)
4493: - *arityp = count;
4494: - else if (*arityp!=count) {
4495: - sem_error("inconsistent arity for %s", symp->name);
4496: - *arityp = GIVENUP;
4497: - }
4498: - }
4499: -}
4500: -
4501: -is_node(symp)
4502: - SymbolEntry *symp;
4503: -{ return(symp->attr==A_NODE); }
4504: -
4505: -is_label(symp)
4506: - SymbolEntry *symp;
4507: -{ return(symp->attr==A_LABEL); }
4508: -
4509: -CheckIsNodeOrPred (symp)
4510: - SymbolEntry *symp;
4511: -{
4512: - if (symp->attr==A_ERROR)
4513: - return;
4514: - if (symp->attr!=A_NODE)
4515: - sem_error ("non-node identifier %s", symp->name);
4516: -}
4517: -
4518: -CheckIsUndefined(symp)
4519: - SymbolEntry *symp;
4520: -{
4521: - if (symp->attr==A_ERROR)
4522: - return(0);
4523: - if (symp->attr!=A_UNDEFINED) {
4524: - sem_error ("multiple declaration: %s", symp->name);
4525: - return(0);
4526: - } else return(1);
4527: -}
4528: -
4529: -CheckIsDefined(symp)
4530: - SymbolEntry *symp;
4531: -{
4532: - if (symp->attr==A_ERROR)
4533: - return(0);
4534: - if (symp->attr==A_UNDEFINED) {
4535: - sem_error ("undefined identifier: %s", symp->name);
4536: - symp->attr=A_ERROR;
4537: - return(0);
4538: - } else return(1);
4539: -}
4540: -
4541: -
4542: -
4543: -/*VARARGS*/
4544: -yyerror(fmt, s1, s2, s3)
4545: - char *fmt, *s1, *s2, *s3;
4546: -{
4547: - fprintf(stderr, "line %d: ", yyline);
4548: - fprintf(stderr, fmt, s1, s2, s3);
4549: - if (token_buffer[0]!=0)
4550: - fprintf(stderr, " at \"%s\"\n", token_buffer);
4551: -}
4552: -
4553: -/*VARARGS*/
4554: -yyerror2 (fmt, s1, s2, s3)
4555: - char *fmt, *s1, *s2, *s3;
4556: -{
4557: - fprintf(stderr, "line %d: ", yyline);
4558: - fprintf(stderr, fmt, s1, s2, s3);
4559: - putchar('\n');
4560: -}
4561: -
4562: -char *cmdnam;
4563: -char *inFileName;
4564: -char *outFileName;
4565: -char prefixFile[100];
4566: -static char usage[] = "usage: mt [-d] file";
4567: -#define USAGE error(1, usage)
4568: -char *prefix_base = PREFIX_BASE;
4569: -char *suffix = "c1";
4570: -
4571: -main(argc, argv)
4572: - int argc;
4573: - char **argv;
4574: -{
4575: - int i;
4576: - char *cp;
4577: -
4578: -#ifndef PREFIX_BASE
4579: - error(1,"PREFIX_BASE has not been defined; recompile twig");
4580: -#endif
4581: -
4582: - cmdnam = argv[0];
4583: - argv++;
4584: - inFileName = NULL;
4585: -
4586: - while(--argc > 0) {
4587: - if (*argv[0]=='-')
4588: - switch(argv[0][1]) {
4589: - /* to see what each of these flags mean...
4590: - * see common.h */
4591: - case 'd': {
4592: - char *cp;
4593: - for(cp = &argv[0][2]; *cp!='\0'; cp++)
4594: - switch(*cp) {
4595: - case 'l': debug_flag |= DB_LEX; break;
4596: - case 'm': debug_flag |= DB_MACH; break;
4597: - case 's': debug_flag |= DB_SYM; break;
4598: - case 't': debug_flag |= DB_TREE; break;
4599: - case 'M': debug_flag |= DB_MEM; break;
4600: - }
4601: - }
4602: - break;
4603: - case 'D': Dflag++; break;
4604: - case 't': tflag++; break;
4605: - case 'w': suffix = process_suffix(&argv[0][2]); break;
4606: - case 'l': prefix_base = &argv[0][2]; break;
4607: - case 'x': line_xref_flag++; break;
4608: - default:
4609: - USAGE;
4610: - }
4611: - else inFileName = argv[0];
4612: - argv++;
4613: - }
4614: - if(inFileName==NULL)
4615: - USAGE;
4616: -
4617: - if(freopen(inFileName, "r", stdin)==NULL)
4618: - error(1, "can't open %s", inFileName);
4619: - if((cp=strrchr(inFileName, '.'))!=NULL && strcmp(cp,".mt")==0) {
4620: - if ((outfile = fopen("walker.c" , "w"))==NULL)
4621: - error(1, "can't write %s", outFileName);
4622: - if ((symfile = fopen("symbols.h", "w"))==NULL)
4623: - error(1, "can't write %s", outFileName);
4624: - } else error(1, "input file must have suffix .mt");
4625: -
4626: - ErrorSymbol.attr = A_LABEL;
4627: - TreeInit();
4628: - SymbolInit();
4629: - LexInit();
4630: - yyparse();
4631: -
4632: - SymbolDump();
4633: - if(nerrors == 0) {
4634: - if(!tflag) {
4635: - FILE *prefix;
4636: - char c;
4637: - sprintf(prefixFile, "%s.%s", prefix_base, suffix);
4638: - prefix = fopen(prefixFile, "r");
4639: - assert(prefix!=NULL);
4640: - if(Dflag)
4641: - fputs("#define DEBUG 1\n", outfile);
4642: - if(line_xref_flag)
4643: - fputs("#define LINE_XREF 1\n", outfile);
4644: - fprintf(outfile,"# line 1 \"%s\"\n", prefixFile);
4645: - while((c=getc(prefix))!=EOF) putc(c, outfile);
4646: - }
4647: - MachineGen();
4648: - SymbolGenerateWalkerCode();
4649: - CodeWrite(outfile, epilogue);
4650: - CodeFreeBlock(epilogue);
4651: - }
4652: -
4653: - /* cleanup */
4654: - cleanup(0);
4655: -}
4656: -
4657: -cleanup(retcode)
4658: - int retcode;
4659: -{
4660: - lexCleanup();
4661: - if(retcode==0) {
4662: - SymbolFinish();
4663: - }
4664: - exit(retcode);
4665: -}
4666: -
4667: -/*VARARGS*/
4668: -error(rc, fmt, a1, a2, a3)
4669: - int rc;
4670: - char *fmt, *a1, *a2, *a3;
4671: -{
4672: - fprintf(stderr, "%s: ", cmdnam);
4673: - fprintf(stderr, fmt, a1, a2, a3);
4674: - putc ('\n', stderr);
4675: - if(rc)
4676: - exit (rc);
4677: -}
4678: -
4679: -/*VARARGS*/
4680: -sem_error (fmt, a1, a2, a3)
4681: - char *fmt, *a1, *a2, *a3;
4682: -{
4683: - fprintf (stderr, "line %d: ", yyline);
4684: - sem_error2(fmt, a1, a2, a3);
4685: - nerrors++;
4686: - fatalerrors++;
4687: -}
4688: -
4689: -/*VARARGS*/
4690: -sem_error2(fmt, a1, a2, a3)
4691: - char *fmt, *a1, *a2, *a3;
4692: -{
4693: - fprintf (stderr, fmt, a1, a2, a3);
4694: - putc('\n', stderr);
4695: - nerrors++;
4696: -}
4697: -
4698: -char *
4699: -process_suffix(suf)
4700: - char *suf;
4701: -{
4702: - extern int gen_table2;
4703: - if(strcmp(suf,"exper")==0) {
4704: - /* experimental walker */
4705: - /* expect this to change alot */
4706: - gen_table2++;
4707: - }
4708: - return(suf);
4709: -}
4710: -short yyexca[] ={
4711: --1, 1,
4712: - 0, -1,
4713: - -2, 0,
4714: --1, 10,
4715: - 0, 1,
4716: - -2, 0,
4717: --1, 66,
4718: - 40, 49,
4719: - -2, 51,
4720: - };
4721: -# define YYNPROD 56
4722: -# define YYLAST 261
4723: -short yyact[]={
4724: -
4725: - 16, 71, 4, 6, 7, 5, 14, 8, 9, 17,
4726: - 4, 6, 7, 5, 37, 8, 9, 29, 89, 79,
4727: - 88, 78, 73, 72, 54, 36, 61, 59, 28, 50,
4728: - 44, 40, 16, 92, 33, 31, 66, 27, 14, 25,
4729: - 22, 17, 66, 32, 30, 93, 65, 70, 94, 85,
4730: - 69, 53, 87, 76, 75, 64, 63, 62, 60, 58,
4731: - 57, 39, 48, 38, 83, 82, 86, 49, 24, 21,
4732: - 12, 20, 13, 3, 80, 10, 11, 2, 77, 84,
4733: - 23, 35, 19, 34, 18, 15, 26, 90, 1, 45,
4734: - 41, 0, 51, 0, 0, 0, 0, 0, 0, 0,
4735: - 0, 74, 0, 0, 0, 0, 67, 0, 0, 0,
4736: - 68, 0, 0, 0, 0, 0, 0, 81, 0, 0,
4737: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4738: - 0, 0, 0, 91, 0, 0, 0, 0, 0, 0,
4739: - 0, 96, 0, 0, 0, 0, 0, 0, 0, 0,
4740: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4741: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4742: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4743: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4744: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4745: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4746: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4747: - 0, 56, 0, 0, 73, 72, 52, 46, 42, 0,
4748: - 55, 0, 0, 0, 0, 25, 47, 43, 0, 0,
4749: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4750: - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4751: - 95 };
4752: -short yypact[]={
4753: -
4754: --248,-1000,-256,-1000,-225,-226,-228,-239,-221,-222,
4755: --224,-1000,-1000,-1000,-242, 5, 2,-1000, -28, -29,
4756: --1000,-1000, 27, -30,-1000, -10, -35,-1000, 1, 0,
4757: --240, -1,-241, -2,-1000,-1000, -3, -4,-229,-1000,
4758: --1000,-1000,-1000, 27,-1000,-1000,-1000, 27, -11, -41,
4759: --1000,-1000,-1000,-243,-1000,-1000,-1000,-1000,-1000, -5,
4760: --1000, -6,-1000,-1000,-1000,-246,-1000,-1000, -11,-243,
4761: - 24, 23,-1000,-1000,-1000,-1000,-1000, -12,-1000,-1000,
4762: - 26,-1000,-1000,-1000, -7,-247,-223,-1000,-1000,-1000,
4763: - 4,-1000,-1000,-1000,-229,-1000,-1000 };
4764: -short yypgo[]={
4765: -
4766: - 0, 88, 46, 87, 86, 85, 84, 71, 82, 69,
4767: - 80, 68, 62, 47, 79, 78, 77, 75, 73, 72,
4768: - 70, 74 };
4769: -short yyr1[]={
4770: -
4771: - 0, 1, 16, 16, 18, 18, 18, 18, 18, 18,
4772: - 18, 18, 18, 18, 4, 4, 4, 8, 8, 8,
4773: - 6, 6, 6, 7, 9, 12, 12, 12, 10, 10,
4774: - 10, 11, 13, 13, 17, 17, 17, 17, 20, 20,
4775: - 19, 19, 14, 14, 14, 15, 15, 15, 5, 21,
4776: - 2, 2, 3, 3, 3, 3 };
4777: -short yyr2[]={
4778: -
4779: - 0, 2, 2, 1, 3, 3, 3, 3, 3, 4,
4780: - 4, 3, 3, 3, 2, 1, 2, 2, 1, 2,
4781: - 2, 1, 2, 2, 4, 3, 3, 0, 2, 1,
4782: - 2, 3, 1, 1, 2, 2, 1, 1, 3, 3,
4783: - 6, 2, 2, 2, 0, 1, 1, 0, 1, 0,
4784: - 5, 1, 3, 1, 1, 2 };
4785: -short yychk[]={
4786: -
4787: --1000, -1, -16, -18, 258, 261, 259, 260, 263, 264,
4788: - -17, -18, -20, -19, 262, -5, 256, 265, -6, -8,
4789: - -7, -9, 265, -10, -11, 265, -4, 265, 267, 256,
4790: - 265, 256, 265, 256, -19, -20, 267, 256, 58, 59,
4791: - 59, -7, 256, 265, 59, -9, 256, 265, -12, 40,
4792: - 59, -11, 256, 61, 59, 265, 256, 59, 59, 267,
4793: - 59, 267, 59, 59, 59, -2, 265, -12, -12, 61,
4794: - -13, 42, 266, 265, -13, 59, 59, -15, 267, 265,
4795: - -21, -13, 41, 41, -14, 61, 40, 59, 267, 265,
4796: - -3, -2, 256, 41, 44, 256, -2 };
4797: -short yydef[]={
4798: -
4799: - 0, -2, 0, 3, 0, 0, 0, 0, 0, 0,
4800: - -2, 2, 36, 37, 0, 0, 0, 48, 0, 0,
4801: - 21, 18, 27, 0, 29, 0, 0, 15, 0, 0,
4802: - 0, 0, 0, 0, 34, 35, 0, 0, 0, 41,
4803: - 4, 20, 22, 27, 5, 17, 19, 27, 23, 0,
4804: - 6, 28, 30, 0, 7, 14, 16, 8, 11, 0,
4805: - 13, 0, 12, 38, 39, 47, -2, 23, 0, 0,
4806: - 0, 0, 32, 33, 31, 9, 10, 44, 45, 46,
4807: - 0, 24, 25, 26, 0, 0, 0, 40, 42, 43,
4808: - 0, 53, 54, 50, 0, 55, 52 };
4809: -# ifdef YYDEBUG
4810: -# include "y.debug"
4811: -# endif
4812: -
4813: -# define YYFLAG -1000
4814: -# define YYERROR goto yyerrlab
4815: -# define YYACCEPT return(0)
4816: -# define YYABORT return(1)
4817: -
4818: -/* parser for yacc output */
4819: -
4820: -#ifdef YYDEBUG
4821: -int yydebug = 0; /* 1 for debugging */
4822: -#endif
4823: -YYSTYPE yyv[YYMAXDEPTH]; /* where the values are stored */
4824: -int yychar = -1; /* current input token number */
4825: -int yynerrs = 0; /* number of errors */
4826: -short yyerrflag = 0; /* error recovery flag */
4827: -
4828: -yyparse()
4829: -{ short yys[YYMAXDEPTH];
4830: - int yyj, yym;
4831: - register YYSTYPE *yypvt;
4832: - register int yystate, yyn;
4833: - register short *yyps;
4834: - register YYSTYPE *yypv;
4835: - register short *yyxi;
4836: -
4837: - yystate = 0;
4838: - yychar = -1;
4839: - yynerrs = 0;
4840: - yyerrflag = 0;
4841: - yyps= &yys[-1];
4842: - yypv= &yyv[-1];
4843: -
4844: -yystack: /* put a state and value onto the stack */
4845: -#ifdef YYDEBUG
4846: - if(yydebug >= 3)
4847: - if(yychar < 0 || yytoknames[yychar] == 0)
4848: - printf("char %d in %s", yychar, yystates[yystate]);
4849: - else
4850: - printf("%s in %s", yytoknames[yychar], yystates[yystate]);
4851: -#endif
4852: - if( ++yyps >= &yys[YYMAXDEPTH] ) {
4853: - yyerror( "yacc stack overflow" );
4854: - return(1);
4855: - }
4856: - *yyps = yystate;
4857: - ++yypv;
4858: - *yypv = yyval;
4859: -yynewstate:
4860: - yyn = yypact[yystate];
4861: - if(yyn <= YYFLAG) goto yydefault; /* simple state */
4862: - if(yychar<0) {
4863: - yychar = yylex();
4864: -#ifdef YYDEBUG
4865: - if(yydebug >= 2) {
4866: - if(yychar <= 0)
4867: - printf("lex EOF\n");
4868: - else if(yytoknames[yychar])
4869: - printf("lex %s\n", yytoknames[yychar]);
4870: - else
4871: - printf("lex (%c)\n", yychar);
4872: - }
4873: -#endif
4874: - if(yychar < 0)
4875: - yychar = 0;
4876: - }
4877: - if((yyn += yychar) < 0 || yyn >= YYLAST)
4878: - goto yydefault;
4879: - if( yychk[ yyn=yyact[ yyn ] ] == yychar ){ /* valid shift */
4880: - yychar = -1;
4881: - yyval = yylval;
4882: - yystate = yyn;
4883: - if( yyerrflag > 0 ) --yyerrflag;
4884: - goto yystack;
4885: - }
4886: -yydefault:
4887: - /* default state action */
4888: - if( (yyn=yydef[yystate]) == -2 ) {
4889: - if(yychar < 0) {
4890: - yychar = yylex();
4891: -#ifdef YYDEBUG
4892: - if(yydebug >= 2)
4893: - if(yychar < 0)
4894: - printf("lex EOF\n");
4895: - else
4896: - printf("lex %s\n", yytoknames[yychar]);
4897: -#endif
4898: - if(yychar < 0)
4899: - yychar = 0;
4900: - }
4901: - /* look through exception table */
4902: - for(yyxi=yyexca; (*yyxi!= (-1)) || (yyxi[1]!=yystate);
4903: - yyxi += 2 ) ; /* VOID */
4904: - while( *(yyxi+=2) >= 0 ){
4905: - if( *yyxi == yychar ) break;
4906: - }
4907: - if( (yyn = yyxi[1]) < 0 ) return(0); /* accept */
4908: - }
4909: - if( yyn == 0 ){ /* error */
4910: - /* error ... attempt to resume parsing */
4911: - switch( yyerrflag ){
4912: - case 0: /* brand new error */
4913: -#ifdef YYDEBUG
4914: - yyerror("syntax error\n%s", yystates[yystate]);
4915: - if(yytoknames[yychar])
4916: - yyerror("saw %s\n", yytoknames[yychar]);
4917: - else if(yychar >= ' ' && yychar < '\177')
4918: - yyerror("saw `%c'\n", yychar);
4919: - else if(yychar == 0)
4920: - yyerror("saw EOF\n");
4921: - else
4922: - yyerror("saw char 0%o\n", yychar);
4923: -#else
4924: - yyerror( "syntax error" );
4925: -#endif
4926: -yyerrlab:
4927: - ++yynerrs;
4928: - case 1:
4929: - case 2: /* incompletely recovered error ... try again */
4930: - yyerrflag = 3;
4931: - /* find a state where "error" is a legal shift action */
4932: - while ( yyps >= yys ) {
4933: - yyn = yypact[*yyps] + YYERRCODE;
4934: - if( yyn>= 0 && yyn < YYLAST && yychk[yyact[yyn]] == YYERRCODE ){
4935: - yystate = yyact[yyn]; /* simulate a shift of "error" */
4936: - goto yystack;
4937: - }
4938: - yyn = yypact[*yyps];
4939: - /* the current yyps has no shift onn "error", pop stack */
4940: -#ifdef YYDEBUG
4941: - if( yydebug ) printf( "error recovery pops state %d, uncovers %d\n", *yyps, yyps[-1] );
4942: -#endif
4943: - --yyps;
4944: - --yypv;
4945: - }
4946: - /* there is no state on the stack with an error shift ... abort */
4947: -yyabort:
4948: - return(1);
4949: - case 3: /* no shift yet; clobber input char */
4950: -#ifdef YYDEBUG
4951: - if( yydebug ) {
4952: - printf("error recovery discards ");
4953: - if(yytoknames[yychar])
4954: - printf("%s\n", yytoknames[yychar]);
4955: - else if(yychar >= ' ' && yychar < '\177')
4956: - printf("`%c'\n", yychar);
4957: - else if(yychar == 0)
4958: - printf("EOF\n");
4959: - else
4960: - printf("char 0%o\n", yychar);
4961: - }
4962: -#endif
4963: - if( yychar == 0 ) goto yyabort; /* don't discard EOF, quit */
4964: - yychar = -1;
4965: - goto yynewstate; /* try again in the same state */
4966: - }
4967: - }
4968: - /* reduction by production yyn */
4969: -#ifdef YYDEBUG
4970: - if(yydebug) { char *s;
4971: - printf("reduce %d in:\n\t", yyn);
4972: - for(s = yystates[yystate]; *s; s++) {
4973: - putchar(*s);
4974: - if(*s == '\n' && *(s+1))
4975: - putchar('\t');
4976: - }
4977: - }
4978: -#endif
4979: - yyps -= yyr2[yyn];
4980: - yypvt = yypv;
4981: - yypv -= yyr2[yyn];
4982: - yyval = yypv[1];
4983: - yym=yyn;
4984: - /* consult goto table to find next state */
4985: - yyn = yyr1[yyn];
4986: - yyj = yypgo[yyn] + *yyps + 1;
4987: - if( yyj>=YYLAST || yychk[ yystate = yyact[yyj] ] != -yyn ) yystate = yyact[yypgo[yyn]];
4988: - switch(yym){
4989: -
4990: -case 1:
4991: -# line 42 "twig.y"
4992: -
4993: - { if (nerrors==0) machine_build(); } break;
4994: -case 4:
4995: -# line 48 "twig.y"
4996: - { SymbolEnterList (yypvt[-1].y_symp, A_NODE); } break;
4997: -case 5:
4998: -# line 51 "twig.y"
4999: - {
5000: - SymbolEnterList(yypvt[-1].y_symp, A_NODE);
5001: - SymbolCheckNodeValues();
5002: - } break;
5003: -case 6:
5004: -# line 56 "twig.y"
5005: - { SymbolEnterList (yypvt[-1].y_symp, A_CONST); } break;
5006: -case 7:
5007: -# line 58 "twig.y"
5008: - { SymbolEnterList (yypvt[-1].y_symp, A_LABEL); } break;
5009: -case 8:
5010: -# line 60 "twig.y"
5011: - { CodeWrite(outfile, yypvt[-1].y_code); CodeFreeBlock(yypvt[-1].y_code); } break;
5012: -case 9:
5013: -# line 63 "twig.y"
5014: - { yypvt[-2].y_symp->sd.ca.code = yypvt[-1].y_code; yypvt[-2].y_symp->sd.ca.assoc = NULL;
5015: - SymbolEnter (yypvt[-2].y_symp, A_COST); } break;
5016: -case 10:
5017: -# line 67 "twig.y"
5018: - { yypvt[-2].y_symp->sd.ca.code = yypvt[-1].y_code; yypvt[-2].y_symp->sd.ca.assoc = NULL;
5019: - SymbolEnter (yypvt[-2].y_symp, A_ACTION); } break;
5020: -case 14:
5021: -# line 83 "twig.y"
5022: - {
5023: - if(CheckIsUndefined(yypvt[-0].y_symp)) {
5024: - yypvt[-0].y_symp->next = yypvt[-1].y_symp;
5025: - yyval.y_symp = yypvt[-0].y_symp;
5026: - } else yyval.y_symp = yypvt[-1].y_symp;
5027: - } break;
5028: -case 15:
5029: -# line 89 "twig.y"
5030: -{ if(CheckIsUndefined(yypvt[-0].y_symp)) yyval.y_symp = yypvt[-0].y_symp; else yyval.y_symp = NULL; } break;
5031: -case 17:
5032: -# line 97 "twig.y"
5033: - {
5034: - if(yypvt[-0].y_symp->attr==A_ERROR)
5035: - yyval.y_symp = yypvt[-1].y_symp;
5036: - else { yypvt[-0].y_symp->next = yypvt[-1].y_symp; yyval.y_symp = yypvt[-0].y_symp; }
5037: - } break;
5038: -case 18:
5039: -# line 102 "twig.y"
5040: -{ yyval.y_symp = yypvt[-0].y_symp->attr==A_ERROR ? NULL : yypvt[-0].y_symp; } break;
5041: -case 20:
5042: -# line 106 "twig.y"
5043: - {
5044: - if(yypvt[-0].y_symp->attr==A_ERROR) yyval.y_symp = yypvt[-1].y_symp;
5045: - else { yypvt[-0].y_symp->next = yypvt[-1].y_symp; yyval.y_symp = yypvt[-0].y_symp; }
5046: - } break;
5047: -case 21:
5048: -# line 110 "twig.y"
5049: -{ yyval.y_symp = yypvt[-0].y_symp->attr==A_ERROR ? NULL : yypvt[-0].y_symp; } break;
5050: -case 23:
5051: -# line 114 "twig.y"
5052: - {
5053: - if (CheckIsUndefined(yypvt[-1].y_symp)) {
5054: - yypvt[-1].y_symp->sd.arity = yypvt[-0].y_int; yyval.y_symp = yypvt[-1].y_symp;
5055: - } else yyval.y_symp = &ErrorSymbol;
5056: - } break;
5057: -case 24:
5058: -# line 121 "twig.y"
5059: -{
5060: - if(CheckIsUndefined(yypvt[-3].y_symp)) {
5061: - yypvt[-3].y_symp->unique = yypvt[-0].y_int; yypvt[-3].y_symp->sd.arity = yypvt[-2].y_int;
5062: - yyval.y_symp = yypvt[-3].y_symp;
5063: - } else yyval.y_symp = &ErrorSymbol;
5064: - } break;
5065: -case 25:
5066: -# line 129 "twig.y"
5067: - { yyval.y_int = yypvt[-1].y_int; } break;
5068: -case 26:
5069: -# line 130 "twig.y"
5070: - { yyval.y_int=GIVENUP; } break;
5071: -case 27:
5072: -# line 131 "twig.y"
5073: - { yyval.y_int = UNDEFINED; } break;
5074: -case 28:
5075: -# line 134 "twig.y"
5076: - {
5077: - if (yypvt[-0].y_symp->attr==A_ERROR) yyval.y_symp = yypvt[-1].y_symp;
5078: - else { yypvt[-0].y_symp->next = yypvt[-1].y_symp; yyval.y_symp = yypvt[-0].y_symp; }
5079: - } break;
5080: -case 29:
5081: -# line 138 "twig.y"
5082: -{ yyval.y_symp = yypvt[-0].y_symp->attr==A_ERROR ? NULL : yypvt[-0].y_symp; } break;
5083: -case 31:
5084: -# line 142 "twig.y"
5085: - {
5086: - if(CheckIsUndefined(yypvt[-2].y_symp)) {
5087: - yypvt[-2].y_symp->sd.cvalue = yypvt[-0].y_int; yyval.y_symp = yypvt[-2].y_symp;
5088: - } else yyval.y_symp = &ErrorSymbol;
5089: - } break;
5090: -case 33:
5091: -# line 150 "twig.y"
5092: - {
5093: - if(!CheckIsDefined(yypvt[-0].y_symp)) yyval.y_int = UNDEFINED;
5094: - else if(yypvt[-0].y_symp->attr!=A_CONST) {
5095: - sem_error("non-constant id used");
5096: - yyval.y_int = -1;
5097: - } else yyval.y_int = yypvt[-0].y_symp->sd.cvalue;
5098: - } break;
5099: -case 38:
5100: -# line 164 "twig.y"
5101: - { epilogue = CodeAppend(epilogue, yypvt[-1].y_code); } break;
5102: -case 40:
5103: -# line 169 "twig.y"
5104: - {
5105: - if (yypvt[-5].y_symp->attr==A_ERROR) {
5106: - error(0, "\"label: tree\" pair ignored");
5107: - TreeFree(yypvt[-3].y_nodep);
5108: - } else {
5109: - if(nerrors==0)
5110: - cgotofn(SymbolEnterTreeIntoLabel(yypvt[-5].y_symp,
5111: - yypvt[-3].y_nodep, yypvt[-2].y_symp, yypvt[-1].y_symp, tree_lineno));
5112: - if(debug_flag&DB_TREE)
5113: - TreePrint(yypvt[-3].y_nodep, 1);
5114: - }
5115: - } break;
5116: -case 42:
5117: -# line 183 "twig.y"
5118: -{ SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
5119: - sp->sd.ca.code = yypvt[-0].y_code; sp->sd.ca.assoc = NULL;
5120: - SymbolEnter(sp, A_ACTION); yyval.y_symp = sp; } break;
5121: -case 43:
5122: -# line 186 "twig.y"
5123: -{ if(CheckIsDefined(yypvt[-0].y_symp)) {
5124: - if (yypvt[-0].y_symp->attr!=A_ACTION) {
5125: - sem_error ("non action id: %s", yypvt[-0].y_symp->name);
5126: - yyval.y_symp = &ErrorSymbol;
5127: - } else yyval.y_symp = yypvt[-0].y_symp;
5128: - } else yyval.y_symp = &ErrorSymbol; } break;
5129: -case 44:
5130: -# line 192 "twig.y"
5131: -{ yyval.y_symp = NULL;} break;
5132: -case 45:
5133: -# line 194 "twig.y"
5134: -{ SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
5135: - sp->sd.ca.code = yypvt[-0].y_code; sp->sd.ca.assoc = NULL;
5136: - SymbolEnter (sp, A_COST); yyval.y_symp = sp;
5137: - } break;
5138: -case 46:
5139: -# line 198 "twig.y"
5140: -{ if (CheckIsDefined(yypvt[-0].y_symp)) {
5141: - if (yypvt[-0].y_symp->attr!=A_COST) {
5142: - sem_error ("non cost id: %s", yypvt[-0].y_symp->name);
5143: - yyval.y_symp = &ErrorSymbol;
5144: - } else yyval.y_symp = yypvt[-0].y_symp;
5145: - } else yyval.y_symp = &ErrorSymbol; } break;
5146: -case 47:
5147: -# line 204 "twig.y"
5148: -{ yyval.y_symp = NULL; } break;
5149: -case 48:
5150: -# line 207 "twig.y"
5151: - {
5152: - tree_lineno = yyline; /* record line no */
5153: - if(!CheckIsDefined(yypvt[-0].y_symp))
5154: - yypvt[-0].y_symp->attr = A_ERROR;
5155: - else if(!is_label(yypvt[-0].y_symp)) {
5156: - sem_error("non label id: %s", yypvt[-0].y_symp->name);
5157: - yypvt[-0].y_symp->attr = A_ERROR;
5158: - }
5159: - yyval.y_symp = yypvt[-0].y_symp;
5160: - } break;
5161: -case 49:
5162: -# line 218 "twig.y"
5163: -{CheckIsNodeOrPred(yypvt[-0].y_symp);} break;
5164: -case 50:
5165: -# line 219 "twig.y"
5166: - {
5167: - int count;
5168: - Node *ap;
5169: - /* check the arity of the node */
5170: - for(count=0, ap = yypvt[-1].y_nodep; ap!=NULL; ap=ap->siblings) count++;
5171: - switch(yypvt[-4].y_symp->attr) {
5172: - case A_NODE:
5173: - set_arity(yypvt[-4].y_symp, &yypvt[-4].y_symp->sd.arity, count);
5174: - break;
5175: - }
5176: -
5177: - yyval.y_nodep = TreeBuild (yypvt[-4].y_symp, yypvt[-1].y_nodep);
5178: - } break;
5179: -case 51:
5180: -# line 233 "twig.y"
5181: - {
5182: - CheckIsDefined(yypvt[-0].y_symp);
5183: - switch (yypvt[-0].y_symp->attr) {
5184: - case A_NODE:
5185: - set_arity(yypvt[-0].y_symp, &yypvt[-0].y_symp->sd.arity, 0);
5186: - break;
5187: - }
5188: - yyval.y_nodep = TreeBuild (yypvt[-0].y_symp, NULL);
5189: - } break;
5190: -case 52:
5191: -# line 243 "twig.y"
5192: - {
5193: - /*
5194: - * build sibling list in reverse order TreeBuild will
5195: - * put it right later.
5196: - */
5197: - yypvt[-0].y_nodep->siblings = yypvt[-2].y_nodep;
5198: - yyval.y_nodep = yypvt[-0].y_nodep;
5199: - } break;
5200: -case 53:
5201: -# line 251 "twig.y"
5202: - { yypvt[-0].y_nodep->siblings = NULL; yyval.y_nodep = yypvt[-0].y_nodep; } break;
5203: -case 54:
5204: -# line 252 "twig.y"
5205: -{ yyval.y_nodep = NULL; } break;
5206: - }
5207: - goto yystack; /* stack new state and value */
5208: -}
5209: //GO.SYSIN DD y.tab.c
5210: echo y.tab.h 1>&2
5211: sed 's/.//' >y.tab.h <<'//GO.SYSIN DD y.tab.h'
5212: -# define ERROR 257
5213: -
5214: -typedef union {
5215: - Node *y_nodep;
5216: - SymbolEntry *y_symp;
5217: - Code *y_code;
5218: - int y_int;
5219: -} YYSTYPE;
5220: -extern YYSTYPE yylval;
5221: -# define K_NODE 258
5222: -# define K_LABEL 259
5223: -# define K_PROLOGUE 260
5224: -# define K_CONST 261
5225: -# define K_INSERT 262
5226: -# define K_COST 263
5227: -# define K_ACTION 264
5228: -# define ID 265
5229: -# define NUMBER 266
5230: -# define CBLOCK 267
5231: //GO.SYSIN DD y.tab.h
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.