V10/cmd/twig/kindling
# To unbundle, sh this file
echo README 1>&2
sed 's/.//' >README <<'//GO.SYSIN DD README'
-Installation Procedure
-----------------------
-To install twig, you must decide in which directories to place:
-
-(1) the twig compiler binary, and
-(2) the twig template files.
-
-Once you have made these two decisions, you should edit the makefile and
-set the variable INSTALL to the value of (1), and the variable TEMPLATES to
-(2). The definitions of INSTALL and TEMPLATES should be near the beginning
-of the makefile. The installation can then be completed by typing:
-
- make install
-
-Once a user has written a twig specification, the command twig is used to
-compile it. The compilation creates two files called walker.c,
-containing several subroutines, and symbols.h, containing definitions.
-Walker.c is compiled and linked with the rest of the user program, and
-tree matching occurs when the user's program calls a subroutine called _match.
-More details about twig specifications, and how to interface to the
-subroutines in walker.c is given in the ``Twig Reference Manual'', AT&T Bell
-Laboratories, Computing Science Technical Report #120.
-
-Addendum to the ``Twig Reference Manual''
------------------------------------------
-
-1. In a node declaration, the user can override the automatic numbering
- of a node id by expliciting assigning a number using the ``= int''
- construct. However, the user must then assign a number to all
- of the node ids. In other words, the user must either assign
- numbers to each of the node ids, or to none of them. The ids must
- have unique numbers.
-
-2. The default action of executing the labelled leaves from
- right to left is inadequate. ``Execution,'' as used here, is in
- the sense as described in the ``Twig Reference Manual.'' Although
- one could simulate any execution order by using a top-down rule, and
- explicitly requesting the execution of labelled leaves with the tDO
- macro, it is tedious to do so. For example, implementing a Sethi-Ullman
- style register allocator in such a fashion is extremely awkward.
- To alleviate this tedium, reordering scheme has been proposed, and
- implemented by Andrew Appel of Princeton University. It is included
- in this version of twig.
-
- A function, ``_do'' performs the execution of the matches. This
- function is part of the walker.c file generated by twig. In versions
- of the walker without reordering, _do performs the call:
-
- _evalleaves(winner->lleaves);
-
- where winner->lleaves are the labelled leaves of the winning match.
- Lleaves has type ``__match *[], '' and is a NULL terminated sequence
- of matches for the labelled leaves in left to right order. Calling
- tDO with an element of lleaves executes the match associated with
- the labelled leaf.
-
- Reordering is accomplished by changing the call to _evalleaves with
- the statement:
-
- REORDER(winner->lleaves);
-
- REORDER is a macro, or function defined by the user that may execute
- the leaves in any order. If the user does not define REORDER then
- twig will generate a default, which is to call _evalleaves.
-
- For example, if the user wishes to execute the leaves in the order of
- decreasing cost, the following definition could be used.
-
- prologue {
- ...
- #define REORDER(list) reorder(list)
- ...
- }
-
- ...
-
- insert {
-
- reorder(list)
- __match **list;
- {
- int i, j, n;
- __match *index[16];
-
- /* copy list into index */
- for(n=0; list[n]; n++) index[n] = list[n];
-
- /* insertion sort */
- for(j=0;j<n;j++)
- for(i=j; i>0; i--)
- if(index[i]->cost > index[i-1]->cost) {
- /* swap them */
- __match *temp = index[i];
- index[i] = index[i-1]; index[i-1] = p;
- }
-
- /* now execute */
- for(j=0;j<n;j++)
- tDO(index[j]);
- }
-
- }
-
-
-3. In a top-down rule, there is often a desire to execute all the
- labelled leaves after performing some preparatory actions. This
- could be done by saying
-
- tDO($%1$); tDO($%2$); ...
-
- However, the short hand notation, ``EVAL;'' provides the same function.
-
-4. In the previous version of twig, Walker.c had a reference to
- walker.h. Hence the user had to compile walker.c with the command:
-
- cc -Iinclude_dir -c walker.c
-
- where include_dir was the directory containing walker.h.
- The reference to walker.h has been eliminated by inserting walker.h
- into all the template files that could generate walker.c.
- Therefore the new compile command is:
-
- cc -c walker.c
-
-5. Twig assigns numbers to the node symbols, which are used to identify
- nodes to the tree matcher. In the previous version of twig, the
- tree matcher actually recognized ``M_NODE|number'' as the value
- assigned to the node symbol rather than just plain ``number.''
- This was completely undocumented. The current version fixed the
- tree matcher to recognize ``number'' as the correct value associated
- with a node symbol.
-
-6. Twig now uses dynamic initialization of costs rather than static
- initialization. This permits the user to declare COST as structure.
-
-7. Many cost metrics used in twig programs are additive. That is,
- the cost of a match is some constant cost plus the sum of the
- costs of the matches at the labelled leaves. The macros ZEROCOST, and
- ADDCOST provide an easy way to implement this. For example, if costs
- are integers, then the definition
-
- #define ZEROCOST 1
- #define ADDCOST(accum,y) (accum) += (y)
-
- would cause twig to generate, for rules without a cost part, code that
- calculate the default cost as one plus the sum of the costs of the
- matches at the labelled leaves.
-
- ZEROCOST, and ADDCOST must both be defined, if the above facility is
- to be used. DEFAULT_COST must not be defined when ADDCOST is defined.
-
-8. Changes made by Keutzer (allegra!keutzer) and Appel (research!appel)
-
- modifications by keutzer:
-
- char c ->int c
- all over lex.c
-
- varargs added in _mtG in walker.c
- may be too expensive for some people.
- code is not portable to a SUN4 without it however.
-
- "short int"'s were changed to "short"'s for UTS compatability.
-
- The NODE struct pointed to by a NODEPTR now needs a "mark" field.
-
- A printTree(NODEPTR n) routine must also be supplied by the user.
-
- If you were using the values of nodes in your symbols.h file
- then the command
- cc -g -c -DDUMPNAMES sym.c
- should be used to compile sym.c.
//GO.SYSIN DD README
echo code.c 1>&2
sed 's/.//' >code.c <<'//GO.SYSIN DD code.c'
-#include "common.h"
-#include "code.h"
-#define BLOCKSIZE 10
-
-Code *cdfreep = NULL;
-
-Code *
-CodeGetBlock()
-{
- static int count = 0;
- static Code *blockp = NULL;
- Code *cp;
-
- if(cdfreep!=NULL) {
- cp = cdfreep;
- cdfreep = cdfreep->prev;
- } else {
- if(count==0) {
- blockp = (Code *) malloc (BLOCKSIZE*sizeof(Code));
- count = BLOCKSIZE;
- }
- cp = blockp++;
- count--;
- }
- cp->prev = NULL;
- cp->firstFree = cp->segment;
- return(cp);
-}
-
-void
-CodeFreeBlock(cd)
- Code *cd;
-{
- if (cd!=NULL) {
- cd->prev = cdfreep;
- cdfreep = cd;
- }
-}
-
-Code *
-CodeStoreChar(cd, c)
- Code *cd;
- char c;
-{
- if(cd->firstFree - cd->segment >= CSEGSIZE) {
- Code *ncd = CodeGetBlock();
- ncd->prev = cd;
- cd = ncd;
- }
- *cd->firstFree = c;
- cd->firstFree++;
- return(cd);
-}
-
-Code *
-CodeStoreString(cd, s)
- Code *cd;
- char *s;
-{
- while(*s!='\0') cd = CodeStoreChar(cd, *s++);
- return(cd);
-}
-
-Code *
-CodeAppend(cd1, cd2)
- Code *cd1, *cd2;
-{
- if(cd2==NULL) return(cd1);
- cd2->prev = CodeAppend(cd1, cd2->prev);
- return(cd2);
-}
-
-void
-CodeWrite(f, cd)
- FILE *f;
- Code *cd;
-{
- register char *cp;
-
- if (cd != NULL)
- {CodeWrite(outfile, cd->prev);
- for(cp=cd->segment; cp < cd->firstFree; cp++)
- putc(*cp, f);
- }
-}
-
-Code *
-CodeMarkLine(cd,lineno)
- Code *cd;
- int lineno;
-{
- char buf[100];
- sprintf(buf,"\n# line %d \"%s\"\n", lineno, inFileName);
- return(CodeStoreString(cd,buf));
-}
//GO.SYSIN DD code.c
echo code.h 1>&2
sed 's/.//' >code.h <<'//GO.SYSIN DD code.h'
-#define CSEGSIZE 512-2*sizeof(int)
-
-typedef struct Code {
- struct Code *prev;
- char *firstFree;
- char segment[CSEGSIZE];
- } Code;
-
-extern Code *CodeStoreChar();
-extern Code *CodeGetBlock();
-extern Code *CodeAppend();
-extern Code *CodeStoreString(), *CodeMarkLine();
//GO.SYSIN DD code.h
echo common.h 1>&2
sed 's/.//' >common.h <<'//GO.SYSIN DD common.h'
-#include <stdio.h>
-#include <assert.h>
-
-#define MAXIDSIZE 100
-#define HASHSIZE 1181
-#define MAXPATH 32
-#define MAXBRANCH 10
-#define MAXACCEPTS 100
-#define MAXSTATES 200
-/* type definitions */
-typedef char byte;
-
-/* forward and external type defs */
-extern struct node *GetNode();
-extern struct edges *GetEdge();
-extern struct augmented_edges *GetAugEdges();
-extern char *malloc();
-extern char *strrchr();
-extern FILE *outfile;
-extern FILE *symfile;
-
-extern int debug_flag;
-# define DB_LEX 1 /* print out lexical analyser debugging info */
-# define DB_MACH 2 /* print out machine information */
-# define DB_SYM 4 /* print out symbol debugging info */
-# define DB_TREE 8 /* print out trees */
-# define DB_MEM 16 /* check memory usage */
-extern int tflag; /* generate tables only */
-extern int ntrees;
-extern int unique;
-
-/* tree definitions */
-typedef struct node Node;
-typedef struct symbol_entry SymbolEntry;
-
-/* Nodes provide the backbone for the trees built by the parser */
-struct node {
- SymbolEntry *sym;
- int nlleaves; /* count of the labelled leaves */
- Node *children;
- Node *siblings;
-};
-
-extern Node *TreeBuild();
-
-/* path defintions */
-extern void path_setup();
-
-/* lexical analyser */
-extern int yyline;
-extern char *inFileName;
-extern char token_buffer[MAXIDSIZE+1];
-
-extern void LexInit();
-extern yylex();
//GO.SYSIN DD common.h
echo doc 1>&2
sed 's/.//' >doc <<'//GO.SYSIN DD doc'
//GO.SYSIN DD doc
echo examples 1>&2
sed 's/.//' >examples <<'//GO.SYSIN DD examples'
//GO.SYSIN DD examples
echo io.c 1>&2
sed 's/.//' >io.c <<'//GO.SYSIN DD io.c'
-#include "common.h"
-#define MAXINTONLINE 10
-static int intcnt, intonline, firstint;
-
-oreset()
-{
- intcnt = 0;
- intonline = 0;
- firstint = 1;
-}
-
-ointcnt() { return(intcnt); }
-
-oputint(i)
-{
- if(!firstint) putc(',', outfile);
- else firstint = 0;
- fprintf(outfile, "%d", i);
- intonline++;
- intcnt++;
- if(intonline >= MAXINTONLINE) { putc('\n', outfile); intonline = 0; }
-}
-
-oputoct(i)
-{
- if(!firstint) putc(',', outfile);
- else firstint = 0;
- fprintf(outfile, "0%o", i);
- intonline++;
- intcnt++;
- if(intonline >= MAXINTONLINE) { putc('\n', outfile); intonline = 0; }
-}
//GO.SYSIN DD io.c
echo lex.c 1>&2
sed 's/.//' >lex.c <<'//GO.SYSIN DD lex.c'
-#include <ctype.h>
-#include "common.h"
-#include "code.h"
-#include "sym.h"
-#include "y.tab.h"
-
-int yyline = 1;
-char token_buffer[MAXIDSIZE+1];
-extern YYSTYPE yylval;
-static void ScanCodeBlock();
-static void ScanComment();
-static Code *curCdBlock;
-static char get();
-
-yylex()
-{
- register c;
- register char *cp;
- int in_ident = 0;
- yylval.y_nodep = (struct node *) NULL;
- cp = token_buffer;
- while((c=getchar())!=EOF) {
- switch(c) {
- case ' ': case '\t': case '\f':
- continue;
- case '@': case '[': case ']': case ';': case ':':
- case '(': case ')': case ',': case '=':
- case '*':
- if(debug_flag&DB_LEX) {
- putc(c,stderr);
- putc('\n', stderr);
- }
- *cp++ = c;
- *cp = '\0';
- return(c);
-
- case '{':
- ScanCodeBlock();
- yylval.y_code = curCdBlock;
- curCdBlock = NULL;
- *cp++ = '{'; *cp++ = '}';
- return(CBLOCK);
-
- case '\n':
- yyline++;
- continue;
- case '/':
- if ((c=getchar())=='*') {
- ScanComment(get);
- continue;
- } else {
- ungetc(c, stdin);
- c = '/';
- }
- /* FALL THRU */
-
- default:
- if (isdigit(c)) {
- int errs = 0;
- do {
- if(cp > &token_buffer[MAXIDSIZE]) {
- token_buffer[MAXIDSIZE] = '\0';
- yyerror("number too long");
- errs++;
- } else *cp++ = c;
- c = getchar();
- } while (isdigit(c));
- if(isalpha(c))
- yyerror2("illegal digit '%c'", c);
- ungetc(c, stdin);
- if(errs)
- return(ERROR);
- yylval.y_int = atoi(token_buffer);
- return(NUMBER);
- }
- if (isalpha(c)) {
- SymbolEntry *sp;
- int errs = 0;
- do {
- if(cp > &token_buffer[MAXIDSIZE]) {
- token_buffer[MAXIDSIZE] = '\0';
- yyerror("ID too long");
- errs++;
- } else *cp++ = c;
- c = getchar();
- } while (isalpha(c)||isdigit(c)||c=='_');
- ungetc(c, stdin);
- if(errs)
- return(ERROR);
- *cp = '\0';
-
- sp = SymbolLookup (token_buffer);
- if (sp==NULL) {
- /* undefined */
- yylval.y_symp = SymbolAllocate(token_buffer);
- } else {
- /* already defined */
- if (sp->attr == A_KEYWORD)
- return (sp->sd.keyword);
- yylval.y_symp = sp;
- }
- if(debug_flag&DB_LEX)
- fprintf(stderr, "ID\n");
- return(ID);
- }
- yyerror2("illegal character (\\%03o)", c);
- }
- }
- strcpy(token_buffer, "EOF");
- return(0);
-}
-
-void
-LexInit()
-{
-}
-
-lexCleanup()
-{
-}
-
-/*
- * Beware: ungets of the characters from these routines may screw up the
- * line count
- */
-static char
-getput()
-{
- /* keutzer
- char c;
- */
- int c;
- c = getchar();
- if(c=='\n') yyline++;
- if(c!=EOF)
- curCdBlock = CodeStoreChar(curCdBlock, c);
- return(c);
-}
-
-static char
-get()
-{
- /* keutzer
- char c;
- */
- int c;
- c = getchar();
- if(c=='\n') yyline++;
- return(c);
-}
-
-extern int nerrors;
-
-static void
-ScanComment(rdfunc)
- char (*rdfunc)();
-{
- int startline = yyline;
- /* keutzer
- char c;
- */
- int c;
- int saw_star = 0;
- while ((c=rdfunc())!=EOF) {
- if (c=='*')
- saw_star++;
- else if(c=='/' && saw_star) {
- return;
- } else saw_star = 0;
- }
- yyerror2("unexpected EOF in comment beginning on line %d", startline);
- nerrors++;
- cleanup(1);
-}
-
-static
-ScanString(rdfunc)
- char (*rdfunc)();
-{
- int startline = yyline;
- /* keutzer
- char c;
- */
- int c;
- int saw_backsl = 0;
-
- while((c=rdfunc())!=EOF) {
- if (c=='"' && !saw_backsl)
- return;
- if (c=='\\' && !saw_backsl) {
- saw_backsl = 1;
- continue;
- }
- saw_backsl = 0;
- }
- /* fall thru due to EOF */
- yyerror2("unexpected EOF in string beginning on line %d", startline);
- nerrors++;
- cleanup(1);
-}
-
-static
-ScanChar()
-{
- int startline = yyline;
- /* keutzer
- char c;
- */
- int c;
- int saw_backsl = 0;
-
- while((c=getput(stdin))!=EOF) {
- if (c=='\'' && !saw_backsl)
- return;
- if (c=='\\' && !saw_backsl) {
- saw_backsl = 1;
- continue;
- }
- saw_backsl = 0;
- }
- /* fall thru due to EOF */
- yyerror2("unexpected EOF in character constant beginning on line %d",
- startline);
- nerrors++;
- cleanup(1);
-}
-
-static void
-ScanTreeReference()
-{
-
- /* keutzer
- char c;
- */
- int c;
- c = getchar();
- if(c=='%') {
- curCdBlock = CodeStoreString (curCdBlock, "_ll[(");
- while ((c=getchar())!=EOF && c!='$') {
- if(!isdigit(c)) {
- yyerror("unclosed $ reference");
- ungetc(c,stdin);
- break;
- }
- curCdBlock = CodeStoreChar(curCdBlock, c);
- }
- curCdBlock = CodeStoreString (curCdBlock, ")-1]");
- return;
- }
- else if(c=='$') {
- curCdBlock = CodeStoreString(curCdBlock, "root");
- return;
- } else curCdBlock = CodeStoreString(curCdBlock, "_mtG(root,");
- do {
- if(!isdigit(c) && c!='.') {
- yyerror("unclosed $ reference");
- ungetc(c,stdin);
- break;
- }
- curCdBlock = CodeStoreChar(curCdBlock, c=='.' ? ',' : c);
- } while((c=getchar())!=EOF && c!='$');
- curCdBlock = CodeStoreString(curCdBlock, ", -1)");
-}
-
-static void
-ScanCodeBlock()
-{
- int startline = yyline;
- /* keutzer
- char c;
- */
- int c;
- if(curCdBlock==NULL) {
- curCdBlock = CodeGetBlock();
- curCdBlock = CodeMarkLine(curCdBlock,yyline);
- }
- while((c=getc(stdin))!=EOF) {
- if (c=='}')
- return;
- else if (c=='$') ScanTreeReference();
- else curCdBlock = CodeStoreChar(curCdBlock, c);
- if (c=='\n') yyline++;
- if (c=='"') ScanString(getput);
- else if (c=='\'') ScanChar();
- else if (c=='/') {
- if ((c=getc(stdin))=='*') {
- curCdBlock = CodeStoreChar(curCdBlock, '*');
- ScanComment(getput);
- }
- else ungetc(c, stdin);
- }
- else if (c=='{') {
- ScanCodeBlock();
- curCdBlock = CodeStoreChar (curCdBlock, '}');
- }
- }
- yyerror2("{ on line %d has no closing }", startline);
- nerrors++;
-}
//GO.SYSIN DD lex.c
echo machcomm.h 1>&2
sed 's/.//' >machcomm.h <<'//GO.SYSIN DD machcomm.h'
-/*
- * The machine is laid out as a sequence of integers in the walker.
- * The form described above is only used inside the preprocessor.
- * Each machine state is one of the following sequence:
- *
- * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
- * or
- * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
- * or
- * ACCEPT <accept table index> -1
- *
- * The accept table is in the form:
- *
- * <tree index_1> ...<tree_index_m> -1
- *
- */
-
-#define FASTLIM 0
-#define TABLE 1
-#define FAIL 2
-#define ACCEPT 3
-#define TABLE2 4
-#define EOT -1
-
-/* special machine state */
-#define HANG -1
-
-/* used by the evaluator to interpret path table */
-#define eSTOP 0
-#define ePOP -1
-#define eEVAL -2
-#define eNEXT -3
-#define ePUSH -4
-
-/* Tags that indicate the type of a value */
-#define M_BRANCH 010000
-#define M_NODE 0
-#define M_LABEL 01000
-#define MAX_NODE_VALUE 00777
-#define MTAG_SHIFT 9
-#define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE))
-
-/* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */
-#define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0)
-#define MI_DEFINED(x) ((x)!=-1)
-#define MI_LABEL(x) (((x)&M_LABEL)!=0)
-#define MI_BRANCH(x) (((x)&M_BRANCH)!=0)
-
-/* build a tagged value */
-#define MV_NODE(x) (x)
-#define MV_BRANCH(x) ((x)|M_BRANCH)
-#define MV_LABEL(x) ((x)|M_LABEL)
-
//GO.SYSIN DD machcomm.h
echo machine.c 1>&2
sed 's/.//' >machine.c <<'//GO.SYSIN DD machine.c'
-#include "common.h"
-#include "code.h"
-#include "sym.h"
-#include "machine.h"
-
-int gen_table2; /* generate type two tables */
-struct machine_node *machine = NULL;
-static int depth;
-
-static struct machine_node *
-get_state()
-{
- struct machine_node *mp = (struct machine_node *)
- malloc (sizeof (struct machine_node));
- assert (mp!=NULL);
- mp->inp.value = -1;
- mp->nst = NULL;
- mp->link = NULL;
- mp->fail = NULL;
- mp->match = NULL;
- return(mp);
-}
-
-add_match(s, tp, depth)
- struct machine_node *s;
- LabelData *tp;
- int depth;
-{
- struct match *mp = (struct match *) malloc (sizeof (struct match));
-
- assert (mp!=NULL);
- mp->next = s->match;
- mp->depth = depth;
- mp->tree = tp;
- s->match = mp;
-}
-
-/*
- * Build a trie from the path strings. Failure transition are added later.
- */
-cgotofn(tp)
- LabelData *tp;
-{
- struct machine_input inp;
- int ret;
- register struct machine_node *s;
- register int quit = 0;
-
- if (machine==NULL) {
- /* first time thru */
- machine = get_state();
- }
- s = machine;
- depth = -1;
-
- assert (tp->tree!=NULL);
- path_setup (tp->tree);
-
- for(;;) {
- ret = path_getsym(&inp);
-
- /* no more paths */
- if (ret == EOF)
- break;
-
- if (ret == NULL) {
- /*
- * the end of the path. Add a match to the
- * accepting state.
- */
- assert ((depth&01)==0); /* make sure it's even */
- add_match(s, tp, depth >> 1);
- s = machine;
- depth = -1;
- ntrees++;
- continue;
- }
-
- while (!MI_EQUAL(s->inp, inp)) {
- if (!MI_DEFINED(s->inp.value) || s->link == NULL) {
- if (MI_DEFINED(s->inp.value)) {
- /*
- * The trie must be split here
- */
- s->link = get_state();
- s = s->link;
- }
- /*
- * Fill in the state
- */
- s->inp = inp;
- s->nst = get_state();
- s = s->nst;
- depth++;
- break;
- } else s = s->link;
- }
- if (MI_EQUAL(s->inp, inp)) {
- s = s->nst;
- depth++;
- }
- }
-}
-
-/* print out the machine for debugging */
-machine_print(mp)
- struct machine_node *mp;
-{
- register struct machine_node *mp2;
- struct machine_node *fail;
- struct match *match, *p;
-
- if (mp==NULL)
- return;
- printf("%x %d:", mp, mp->index);
- if((fail = mp->fail))
- printf("\tfail %x", fail);
- if((match = mp->match)) {
- printf("\taccept ");
- for(p = match; p!=NULL; p = p->next) {
- LabelData *tp = p->tree;
- printf("%s ", (tp->label)->name);
- }
- }
- putchar('\n');
- for(mp2=mp; mp2!=NULL; mp2 = mp2->link) {
- if (MI_DEFINED(mp2->inp.value)) {
- if (MI_BRANCH(mp->inp.value))
- printf(" %d -> ", mp2->inp.value);
- else
- printf(" [%s] -> ", (mp2->inp.sym)->name);
- printf("%x", mp2->nst);
- }
- assert(mp2->fail==fail);
- assert(mp2->match==match);
- }
- if(MI_DEFINED(mp->inp.value))
- putchar('\n');
- for (mp2 = mp; mp2!=NULL; mp2=mp2->link) {
- machine_print(mp2->nst);
- }
-}
-
-/*
- * This routine augments the machine with failure transition.
- * The trie is examined in breadth first order.
- * See Aho, Corasick Comm ACM 18:6 for details
- */
-cfail()
-{
- struct machine_node **stack, **stack2;
- struct machine_node **stackTop, **stack2Top, **temp;
- int stackCnt, stack2Cnt;
- struct machine_node *state;
- struct machine_input sym;
- register struct machine_node *s, *q;
-
- /* allocate stacks */
- stackTop = stack = (struct machine_node **) malloc
- (ntrees*sizeof (struct machine_node *));
- stack2 = stack2Top = (struct machine_node **) malloc
- (ntrees*sizeof (struct machine_node *));
- stackCnt = stack2Cnt = 0;
- s = machine;
- do {
- if (MI_DEFINED(s->inp.value)) {
- assert(++stackCnt <= ntrees);
- *stackTop++ = s->nst;
- }
- s = s->link;
- } while (s != NULL);
-
- for(;;) {
- if (stackCnt == 0) {
- /* swap stacks */
- if (stack2Cnt == 0)
- break;
- stackCnt = stack2Cnt; stack2Cnt = 0;
- stackTop = stack2Top;
- temp = stack; stack = stack2; stack2 = temp;
- stack2Top = stack2;
- }
- stackCnt--;
- s = *--stackTop;
- do {
- int startstate = 0;
- sym = s->inp;
- if (MI_DEFINED(sym.value)) { /* g(s,c) != 0 */
- assert (++stack2Cnt <= ntrees);
- *stack2Top++ = (q=s->nst);
- state = s->fail; /* state = f(s) */
- for(;;) {
- if (state == 0) {
- state = machine;
- startstate++;
- }
- if (MI_EQUAL(state->inp, sym)) {
- struct match *mp = NULL;
-
- /* append any accepting matches */
- for(mp=(state->nst)->match;mp;mp=mp->next)
- add_match(q,mp->tree, mp->depth);
- mp = q->match;
-
- do {
- /* f(q) = g(state,sym)
- * for all q links */
- q->fail = state->nst;
- q->match = mp;
- } while ((q = q->link) != 0);
- break;
- }
- else if (state->link != 0)
- state = state->link;
- else {
- state = state->fail;
- if (state==NULL&&startstate)
- break;
- }
- }
- }
- s = s->link;
- } while (s!=NULL);
- }
-}
-
-/*
- * Called from the YACC rule pattern_spec
- */
-void
-machine_build()
-{
- cfail();
- (void) MachineNumber(machine, 0);
- if(debug_flag&DB_MACH) {
- fputs("\n-------\n", stderr);
- machine_print(machine);
- }
-}
-
-struct match *acceptTable[MAXACCEPTS];
-struct match **acceptTableTop = acceptTable;
-static short int *arityTable;
-int nextAcceptIndex = 0;
-
-/*
- * This is the first pass of the process to generate the
- * flattened machine used in the walker. Called from machine_build
- */
-int
-MachineNumber(mach, index)
- struct machine_node *mach;
- int index;
-{
- struct machine_node *mp;
-
- for(mp=mach; mp!=NULL; mp = mp->link)
- if(MI_DEFINED(mp->inp.value))
- index = MachineNumber(mp->nst, index);
-
- mach->index = index;
- if (mach->match!=NULL) index += 2;
- if(mach->link!=NULL || mach->nst!=NULL) {
- index += 2;
- for(mp = mach; mp!=NULL; mp = mp->link)
- if(mp->nst!=NULL)
- index += 2;
- }
-
- if (mach->fail!=NULL)
- index += 2;
- index++;
- return(index);
-}
-
-/*
- * Build the flattened out machine used in the walker.
- * See machine.h for description
- */
-MachineGen()
-{
- struct match **atp, *ap;
- short int *sp;
-
- oreset();
- fputs("short int mtTable[] = {\n", outfile);
- machineGen2(machine);
- fputs("};\n", outfile);
-
- fputs("short int mtAccept[] = {\n", outfile);
-
- oreset();
- for(atp = acceptTable; atp < acceptTableTop; atp++) {
- for(ap = *atp; ap!=NULL; ap = ap->next) {
- register LabelData *tree = ap->tree;
-
- /* if you change any of the code below you must change
- * the increment added to nextAcceptIndex in
- * machineGen2
- */
- oputint(tree->treeIndex);
- oputint(ap->depth);
- }
- oputint(-1);
- }
- fprintf(outfile, "};\nshort int mtStart = %d;\n", machine->index);
-}
-
-machineGen2(mach)
- struct machine_node *mach;
-{
- struct machine_node *mp;
- struct match *ap;
-
- if (mach==NULL)
- return;
-
- for(mp=mach; mp!=NULL; mp = mp->link)
- if(MI_DEFINED(mp->inp.value))
- machineGen2(mp->nst);
-
- assert(mach->index == ointcnt());
- if (mach->match!=NULL) {
- *acceptTableTop++ = mach->match;
- oputint(ACCEPT); oputint(nextAcceptIndex);
- for(ap = mach->match; ap!=NULL; ap = ap->next)
- nextAcceptIndex += 2;
- nextAcceptIndex++;
- }
- if(mach->link!=NULL || mach->nst!=NULL) {
- if(MI_BRANCH(mp->inp.value)&&gen_table2) {
- oputint (TABLE2);
- for(mp = mach; mp!=NULL; mp = mp->link) {
- if(mp->nst!=NULL) {
- oputoct(mp->inp.value);
- oputint((mp->nst)->index);
- }
- }
- } else {
- oputint (TABLE);
- for(mp = mach; mp!=NULL; mp = mp->link) {
- if(mp->nst!=NULL) {
- oputoct(mp->inp.value);
- oputint((mp->nst)->index);
- }
- }
- }
- oputint(-1);
- }
-
- /* A failure transition or a -1 terminate every state */
- if (mach->fail!=NULL) {
- oputint(FAIL); oputint((mach->fail)->index);
- }
- oputint(-1);
-}
//GO.SYSIN DD machine.c
echo machine.h 1>&2
sed 's/.//' >machine.h <<'//GO.SYSIN DD machine.h'
-/*
- * The machine used here is the same as the one used in fgrep.
- * Logically, it is a trie of all the strings to be recognized.
- * In this case, the strings are the paths of tree patterns.
- * The nodes of the trie are the states of the machine and leaves
- * are accepting states. The trie is augmented by failure transitions.
- *
- * Each machine state is a linked list of machine_node's and referred to
- * by pointing to the head of the list. The machine_node represents a
- * transition. The nst field points to the next state when the current
- * input is MI_EQUAL to the inp field. If the input is not MI_EQUAL to any
- * of the inp fields in the list, the next state is the one that fail
- * points to. The fail field must be the same for all machine_node's in
- * a state. Accepting states have inp.value equal to -1, and the match
- * field points to a list of match structures. The match structures record
- * which trees have been partially matched.
- *
- * The index is used by the machine generator to convert the machine into
- * a list of integers.
- *
- * Further details about the data structure and algorithms can be
- * found in:
- * Knuth, Morris, Pratt in SIAM J Computing 6:3
- * Aho, Corasick in Comm ACM 18:6
- * Hoffman, O'Donnell in JACM 29:1
- */
-struct machine_input {
- short value;
- struct symbol_entry *sym;
-};
-#define MI_EQUAL(x,y) ((x).value==(y).value)
-
-#include "machcomm.h"
-
-extern int path_getsym();
-
-struct machine_node {
- struct machine_input inp;
- struct machine_node *nst;
- struct machine_node *link;
- struct machine_node *fail;
- struct match *match;
- short int index;
-};
-
-struct match {
- struct match *next;
- short int depth;
- LabelData *tree;
-};
-
-extern struct machine_node *machine;
-
-extern void machine_build();
//GO.SYSIN DD machine.h
echo makefile 1>&2
sed 's/.//' >makefile <<'//GO.SYSIN DD makefile'
-#
-CC= cc
-INSTALL= /usr/bin
-TEMPLATES = /usr/lib/twig
-SRCS= twig.y sym.c path.c machine.c trees.c lex.c code.c io.c mem.c
-OBJS= y.tab.o sym.o path.o machine.o trees.o lex.o code.o io.o mem.o
-HDRS= common.h code.h sym.h machine.h mem.h
-PREFIX= \"$(TEMPLATES)/walker\"
-
-all: twig
-
-install: twig
- mv twig $(INSTALL)
- mv walker.c1 $(TEMPLATES)
-
-kindling:
- bundle README makefile *.y *.c *.h rawwalker.* >kindling
-
-sym.h: code.h
-machine.h: machcomm.h
- touch machine.h
-
-machine.o: common.h sym.h machine.h machine.c
- $(CC) -g -c machine.c
-
-path.o: common.h sym.h path.c
- $(CC) -g -c path.c
-
-y.tab.h: common.h sym.h twig.y
- yacc -d twig.y
-
-y.tab.c: y.tab.h common.h sym.h twig.y
-y.tab.o: y.tab.c
- $(CC) -DPREFIX_BASE=$(PREFIX) -g -c y.tab.c
-
-sym.o: common.h sym.h y.tab.h sym.c
- $(CC) -g -c sym.c
-
-trees.o: common.h sym.h
- $(CC) -g -c trees.c
-
-lex.o: common.h sym.h y.tab.h lex.c
- $(CC) -g -c lex.c
-
-code.o: common.h code.h
- $(CC) -g -c code.c
-
-io.o: common.h io.c
- $(CC) -g -c io.c
-
-mem.o: common.h mem.c
- $(CC) -g -c mem.c
-
-twig: $(OBJS)
- $(CC) -g -o twig $(OBJS)
-
-# generate walker from templates
-walker.c1: machcomm.h walker.h rawwalker.c1
- cat machcomm.h walker.h rawwalker.c1 >walker.c1
-
-walker.ex: machcomm.h walker.h rawwalker.ex
- cat machcomm.h walker.h rawwalker.ex >walker.ex
-
-# at bell labs only
-print:
- pr makefile $(HDRS) $(SRCS) | 4can
-bell_print:
- pp makefile $(HDRS) $(SRCS) | dcan
-
-# at stanford only
-enscript:
- enscript -Pbt -2r makefile $(HDRS) $(SRCS)
-
//GO.SYSIN DD makefile
echo mem.c 1>&2
sed 's/.//' >mem.c <<'//GO.SYSIN DD mem.c'
-#include <stdio.h>
-#include <assert.h>
-#include "mem.h"
-
-#define BLKF 100
-
-static struct _mem *mlist;
-
-static void
-zap(cp,size)
- char *cp;
- int size;
-{
- for(;size>0;size--) {
- *cp = 0xff;
- }
-}
-void
-mem_init(mp, size)
- struct _mem *mp;
- int size;
-{
- int i, s;
- assert(size>=4);
- mp->size = s = size;
- s *= BLKF;
- for (i=1; i < s; i <<= 1);
- mp->bsize = i;
- mp->blkf = mp->bsize/size;
- mp->cnt = 0;
- mp->freelist = NULL;
- mp->totelem = 0;
- mp->freecnt = 0;
- mp->next = mlist;
- mlist = mp;
-};
-
-char *
-mem_get(mp)
- struct _mem *mp;
-{
- char *cp;
- if (mp->freelist!=NULL) {
- cp = mp->freelist;
- mp->freelist = *(char **) cp;
- mp->freecnt--;
- zap(cp,mp->size);
- return(cp);
- } else if (mp->cnt==0) {
- mp->block = (char *)malloc(mp->bsize);
- mp->cnt = mp->blkf;
- mp->totelem += mp->blkf;
- }
- mp->cnt--;
- cp = mp->block;
- mp->block += mp->size;
- zap(cp,mp->size);
- return(cp);
-}
-
-mem_free(mp, cp)
- struct _mem *mp;
- char *cp;{
- *(char **)cp = mp->freelist;
- mp->freelist = cp;
- mp->freecnt++;
-}
-
-mem_outstanding(mp)
- struct _mem *mp;
-{
- /* returns elements that are outstanding..i.e. asked for
- * but haven't yet been returned
- */
- return(mp->totelem - (mp->cnt+mp->freecnt));
-}
-
-mem_epilogue()
-{
- struct _mem *mp;
- /*
- * if the following assertion fails then one of the following
- * has happened:
- * 1) somebody forgot to free something or
- * 2) there is leakage.
- */
- for(mp=mlist; mp!=NULL; mp = mp->next) {
- assert(mem_outstanding(mp)==0);
- }
-}
//GO.SYSIN DD mem.c
echo mem.h 1>&2
sed 's/.//' >mem.h <<'//GO.SYSIN DD mem.h'
-struct _mem {
- struct _mem *next;
- int size; /* size of individual elements in bytes */
- int blkf; /* blocking factor */
- int bsize; /* block size */
- char *block; /* block */
- int cnt; /* count of free elem in block */
- char *freelist; /* free list */
- int totelem; /* total number elements we have */
- int freecnt; /* number of times mem_free was called */
-};
//GO.SYSIN DD mem.h
echo path.c 1>&2
sed 's/.//' >path.c <<'//GO.SYSIN DD path.c'
-#include <stdio.h>
-#include "common.h"
-#include "code.h"
-#include "sym.h"
-#include "machine.h"
-
-/*
- * Routines to enumerate paths of a tree. Firt call path_setup to
- * initialize the internal data structure. Each component of the
- * path may be consecutively retrieved by calling path_getsym.
- */
-
-/*
- * For trees, a path is defined to be the sequence of nodes and edges
- * from the root to a leaf. A path is represented here as a list of
- * path components. Each component is represented by the following
- * strucutre and may either be a pointer to a node or an integer.
- * If the integer is i then the next component is the ith child of the
- * previous component in the list. For example, "a 3 b 1 c" is a path
- * for the tree "a(x,y,b(c,k))". The tag field indicates whether the
- * component is a node or a branch.
- * When the component represents a node then the node field points
- * the corresponding Node structure. When the component is a branch then
- * branch is the index of the current branch followed (1 is leftmost...)
- * and node is a list of all unexamined children.
- */
-struct path {
- int tag;
-#define P_NODE 0
-#define P_BRANCH 1
- int branch;
- Node *node;
-};
-
-/*
- * The path component list is stored in the path array. Path_length
- * is the length of the path. Path_ptr points to the first unread
- * component of the path component list. (see path_getsym
- * and path_build for details)
- */
-struct path path[2*MAXPATH];
-static int path_length;
-static struct path *path_ptr = NULL;
-
-/*
- * Given a tree, path_setup updates the path array with the leftmost
- * of a subtree starting at root. The leftmost path is produced by
- * following the leftmost branch of every encountered interior node
- * starting at the root. Note that this routine can be used to layout
- * the leftmost branch of a subtree into part of the path array and for
- * initializing the path array with the leftmost path of the whole tree.
- */
-void
-path_setup(root)
- Node *root;
-{
- for(;;) {
- register struct path *pp = &path[path_length++];
- Node *ep;
- assert (root!=NULL);
-
- /* Place node in the component list */
- pp->tag = P_NODE;
- pp->node = root;
-
- /* If leaf encountered exit */
- if ((ep=root->children)==NULL)
- break;
-
- /*
- * Mark that the left branch (i.e. 1st in our numbering
- * scheme) was followed.
- */
- pp = &path[path_length++];
- pp->tag = P_BRANCH;
- pp->branch = 1;
- pp->node = ep->siblings;
- root = ep;
- }
- path_ptr = path;
-}
-
-/*
- * Path_build generates the next path of the tree and returns 0 if
- * there are no more paths. Each path can be associated
- * with exactly one leaf. Hence the ordering of paths generated by
- * this routine is the same as a left to right ordering of the leaves.
- */
-path_build()
-{
- Node *np, *ep;
- struct path *pp = &path[path_length-1];
-
- /*
- * Assert that the end of the last path was indeed
- * a leaf.
- */
- assert (pp->tag == P_NODE);
- assert ((pp->node)->children == NULL);
-
- /*
- * back up until we find a node that still has children
- */
- pp--;
- while (pp >= &path[1] && pp->node==NULL) pp -= 2;
-
- /*
- * If we hit the beginning of the path array, there are
- * no more leaves and hence no more paths.
- */
- if (pp < &path[1]) {
- /* reset path_length */
- path_length = 0;
- return(0);
- }
-
- /*
- * append the new leftmost branch onto the rest of
- * the path component list.
- */
- pp->branch++;
- np = pp->node;
- pp->node = np->siblings;
- path_length = pp-path+1;
- path_setup(np);
- return(1);
-}
-
-/*
- * Get the next component in the path component list.
- * When the end of a path is reached, NULL is returned and
- * the next call will retrieve the first component of the next path.
- * EOF is returned if there are no more paths.
- * A return value of 1 indicates that the value returned in mi is
- * valid.
- */
-int
-path_getsym(mi)
- register struct machine_input *mi;
-{
- if(path_ptr > &path[path_length]) {
- /*
- * When the end of that path is passed, generate the
- * next path.
- */
- if(!path_build())
- return(EOF);
- path_ptr = path;
- }
- if (path_ptr == &path[path_length]) {
- /*
- * Path_ptr just encountered the end of
- * the path, return a marker value
- * to notify caller.
- */
- mi->value = 0;
- path_ptr++;
- return(NULL);
- } else if (path_ptr->tag != P_BRANCH) {
- /*
- * Translate the right machine input value
- */
- mi->sym = (path_ptr->node)->sym;
- switch((mi->sym)->attr) {
-
- case A_NODE:
- mi->value = MV_NODE((mi->sym)->unique);
- break;
-
- case A_LABEL:
- mi->value = MV_LABEL((mi->sym)->unique);
- break;
-
- default:
- assert(0);
- }
- } else {
- mi->value = MV_BRANCH(path_ptr->branch);
- }
- path_ptr++;
- return(1);
-}
-
-/*
- * Prints out path for debugging
- */
-void
-prpath()
-{
- register int i;
- for(i=0; i < path_length; i++) {
- struct path *pp = &path[i];
- if (pp->tag==P_NODE) {
- struct node *np = pp->node;
- printf("[%s]", (np->sym)->name);
- } else {
- assert (pp->tag == P_BRANCH);
- printf("%d", pp->branch);
- }
- }
- putchar('\n');
-
-}
//GO.SYSIN DD path.c
echo rawwalker.c1 1>&2
sed 's/.//' >rawwalker.c1 <<'//GO.SYSIN DD rawwalker.c1'
-/*
- * See Aho, Corasick Comm ACM 18:6, and Hoffman and O'Donell JACM 29:1
- * for detail of the matching algorithm
- */
-
-/* turn this flag on if your machine has a fast byte string zero operation */
-/*#define BZERO 1*/
-int mtDebug = 0;
-int treedebug = 0;
-extern int _machstep();
-extern short int mtStart;
-extern short int mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
-#ifdef LINE_XREF
- extern short int mtLine[];
-#endif
-extern NODEPTR mtGetNodes(), mtAction();
-extern skeleton *_allocskel();
-extern __match *_allocmatch();
-extern __partial *_allocpartial();
-
-#define MPBLOCKSIZ 3000
-__match *_mpblock[MPBLOCKSIZ], **_mpbtop;
-
-/*
- * See sym.h in the preprocessor for details
- * Basically used to support eh $%n$ construct.
- */
-__match **
-_getleaves (mp, skp)
- register __match *mp; register skeleton *skp;
-{
- skeleton *stack[MAXDEPTH];
- skeleton **stp = stack;
- register short int *sip = &mtPaths[mtPathStart[mp->tree]];
- register __match **mmp = _mpbtop;
- __match **mmp2 = mmp;
- if((_mpbtop += *sip++ + 1) > &_mpblock[MPBLOCKSIZ]) {
- printf ("ich: %d\n", _mpbtop-_mpblock);
- assert(0);
- }
-
- for(;;)
- switch(*sip++) {
- case ePUSH:
- *stp++ = skp;
- skp = skp->leftchild;
- break;
-
- case eNEXT:
- skp = skp->sibling;
- break;
-
- case eEVAL:
- if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
- *mmp++ = mp;
- break;
-
- case ePOP:
- skp = *--stp;
- break;
-
- case eSTOP:
- *mmp = NULL;
- return (mmp2);
- }
-}
-
-_evalleaves (mpp)
- register __match **mpp;
-{
- for (; *mpp!=NULL; mpp++) {
- register __match *mp = *mpp;
- _do (mp->skel, mp, 1);
- }
-}
-
-
-_do(sp, winner, evalall)
- skeleton *sp; register __match *winner; int evalall;
-{
- register __match **mpp;
- register skeleton *skel = winner->skel;
- if(winner==NULL) {
- _prskel(sp, 0);
- puts ("no winner");
- return;
- }
- if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
- REORDER (winner->lleaves);
- mtSetNodes (skel->parent, skel->nson,
- skel->root=mtAction (winner->tree, winner->lleaves, sp));
-}
-
-skeleton *
-_walk(sp, ostate)
- register skeleton *sp;
- int ostate;
-{
- int state, nstate, nson;
- register __partial *pp;
- register __match *mp, *mp2;
- register skeleton *nsp, *lastchild = NULL;
- NODEPTR son, root;
-
- root = sp->root;
- nson = 1; sp->mincost = INFINITY;
- state = _machstep (ostate, root, mtValue(root));
-
- while((son = mtGetNodes(root, nson))!=NULL) {
- nstate = _machstep (state, NULL, MV_BRANCH(nson));
- nsp = _allocskel();
- nsp->root = son;
- nsp->parent = root;
- nsp->nson = nson;
- _walk(nsp, nstate);
- if(COSTLESS(nsp->mincost, INFINITY)) {
- assert (nsp->winner->mode==xREWRITE);
- if (mtDebug || treedebug) {
- printf ("rewrite\n");
- _prskel (nsp, 0);
- }
- _do(nsp, nsp->winner, 0);
- _freeskel(nsp);
- continue;
- }
- _merge (sp, nsp);
- if (lastchild==NULL) sp->leftchild = nsp;
- else lastchild->sibling = nsp;
- lastchild = nsp;
- nson++;
- }
-
- for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
- if (pp->bits&01==1) {
- mp = _allocmatch();
- mp->tree = pp->treeno;
- _addmatches (ostate, sp, mp);
- }
- if(son==NULL && nson==1)
- _closure (state, ostate, sp);
-
- sp->rightchild = lastchild;
- if (root==NULL) {
- COST c; __match *win; int i; nsp = sp->leftchild;
- c = INFINITY;
- win = NULL;
- for (i = 0; i < MAXLABELS; i++) {
- mp = nsp->succ[i];
- if (mp!=NULL && COSTLESS (mp->cost, c))
- { c = mp->cost; win = mp; }
- }
- if (mtDebug || treedebug)
- _prskel (nsp, 0);
- _do (nsp, win, 0);
- }
- if (mtDebug)
- _prskel (sp, 0);
- return(sp);
-}
-
-static short int _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
-
-/*
- * Convert the start state which has a large branching factor into
- * a index table. This must be called before the matcher is used.
- */
-_matchinit()
-{
- short int *sp;
- struct pair { short int val, where } *pp;
- for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
- for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
- sp = &mtTable[mtStart];
- assert (*sp==TABLE);
- for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
- if (MI_NODE(pp->val))
- _nodetab[M_DETAG(pp->val)] = pp->where;
- else if (MI_LABEL(pp->val))
- _labeltab[M_DETAG(pp->val)] = pp->where;
- }
-}
-
-int
-_machstep(state, root, input)
- short int state, input;
- NODEPTR root;
-{
- register short int *stp = &mtTable[state];
- int start = 0;
- if (state==HANG)
- return (input==(MV_BRANCH(1)) ? mtStart : HANG);
-rescan:
- if (stp==&mtTable[mtStart]) {
- if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
- if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
- }
-
- for(;;) {
- if(*stp==ACCEPT) stp += 2;
-
- if(*stp==TABLE) {
- stp++;
- while(*stp!=EOT) {
- if(input==*stp) {
- return(*++stp);
- }
- stp += 2;
- }
- stp++;
- }
- if(*stp!=FAIL) {
- if (start) return (HANG);
- else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
- } else {
- stp++;
- stp = &mtTable[*stp];
- goto rescan;
- }
- }
-}
-
-_addmatches(ostate, sp, np)
- int ostate;
- register skeleton *sp;
- register __match *np;
-{
- int label;
- int state;
- register __match *mp;
-
- label = mtMap[np->tree];
-
- /*
- * this is a very poor substitute for good design of the DFA.
- * What we need is a special case that allows any label to be accepted
- * by the start state but we don't want the start state to recognize
- * them after a failure.
- */
- state = _machstep(ostate, NULL, MV_LABEL(label));
- if (ostate!=mtStart && state==HANG) {
- _freematch(np);
- return;
- }
-
- np->lleaves = _getleaves (np, sp);
- np->skel = sp;
- if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
- {
- _freematch(np);
- return;
- }
-
-/*
- if(np->mode==xREWRITE && COSTLESS(np->cost, sp->mincost)) {
- sp->mincost = np->cost;
- sp->winner = np;
- }
-*/
- if ((mp = sp->succ[label])!=NULL) {
- if (!COSTLESS (np->cost, mp->cost))
- { _freematch(np); return; }
- else _freematch(mp);
- }
- if(COSTLESS(np->cost,sp->mincost)) {
- if(np->mode==xREWRITE) {
- sp->mincost = np->cost; sp->winner = np; }
- else { sp->mincost = INFINITY; sp->winner = NULL; }
- }
- sp->succ[label] = np;
- _closure(state, ostate, sp);
-}
-
-_closure(state, ostate, skp)
- int state, ostate;
- skeleton *skp;
-{
- register struct ap { short int tree, depth; } *ap;
- short int *sp = &mtTable[state];
- register __match *mp;
-
- if(state==HANG || *sp!=ACCEPT) return(NULL);
-
- for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
- if (ap->depth==0) {
- mp = _allocmatch();
- mp->tree = ap->tree;
- _addmatches (ostate, skp, mp);
- } else {
- register __partial *pp, *lim = &skp->partial[skp->treecnt];
- for(pp=skp->partial; pp < lim; pp++)
- if(pp->treeno==ap->tree)
- break;
- if(pp==lim) {
- skp->treecnt++;
- pp->treeno = ap->tree;
- pp->bits = (1<<(ap->depth));
- } else pp->bits |= (1<<(ap->depth));
- }
-}
-
-_merge (old, new)
- skeleton *old, *new;
-{
- register __partial *op = old->partial, *np = new->partial;
- int nson = new->nson;
- register __partial *lim = np + new->treecnt;
- if (nson==1) {
- old->treecnt = new->treecnt;
- for(; np < lim; op++, np++) {
- op->treeno = np->treeno;
- op->bits = np->bits/2;
- }
- } else {
- __partial *newer = _allocpartial();
- register __partial *newerp = newer;
- register int cnt;
- lim = op+old->treecnt;
- for(cnt=new->treecnt; cnt-- ; np++) {
- for(op = old->partial; op < lim; op++)
- if (op->treeno == np->treeno) {
- newerp->treeno = op->treeno;
- newerp++->bits = op->bits & (np->bits/2);
- break;
- }
- }
- _freepartial(old->partial);
- old->partial = newer;
- old->treecnt = newerp-newer;
- }
-}
-
-/* Save and Allocate Matches */
-#define BLKF 100
-__match *freep = NULL;
-static int _count = 0;
-static __match *_blockp = NULL;
-#ifdef CHECKMEM
-int x_matches, f_matches;
-#endif
-
-__match *
-_allocmatch()
-{
- __match *mp;
-
- if(freep!=NULL) {
- mp = freep;
- freep = ((__match *)((struct freeb *) freep)->next);
-#ifdef CHECKMEM
- f_matches--;
-#endif
- } else {
- if(_count==0) {
- _blockp = (__match *) malloc (BLKF*sizeof (__match));
- _count = BLKF;
-#ifdef CHECKMEM
- x_matches += BLKF;
-#endif
- }
- mp = _blockp++;
- _count--;
- }
- return(mp);
-}
-
-_freematch(mp)
- __match *mp;
-{
- ((struct freeb *) mp)->next = (struct freeb *) freep;
- freep = mp;
-#ifdef CHECKMEM
- f_matches++;
-#endif
-}
-
-static __partial *pfreep = NULL;
-static int pcount = 0;
-static __partial *pblock = NULL;
-#ifdef CHECKMEM
-static int x_partials, f_partials;
-#endif
-
-__partial *
-_allocpartial()
-{
- __partial *pp;
- if (pfreep!=NULL) {
- pp = pfreep;
- pfreep = *(__partial **) pp;
-#ifdef CHECKMEM
- f_partials--;
-#endif
- } else {
- if (pcount==0) {
- pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
- pcount = BLKF;
-#ifdef CHECKMEM
- x_partials += BLKF;
-#endif
- }
- pp = pblock;
- pblock += MAXTREES;
- pcount--;
- }
- return(pp);
-}
-
-_freepartial(pp)
- __partial *pp;
-{
- * (__partial **)pp = pfreep;
- pfreep = pp;
-#ifdef CHECKMEM
- f_partials++;
-#endif
-}
-
-
-/* storage management */
-static skeleton *sfreep = NULL;
-static int scount = 0;
-static skeleton * sblock = NULL;
-
-skeleton *
-_allocskel()
-{
- skeleton *sp;
- int i;
- if(sfreep!=NULL) {
- sp = sfreep;
- sfreep = sp->sibling;
- } else {
- if(scount==0) {
- sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
- scount = BLKF;
- }
- sp = sblock++;
- scount--;
- }
- sp->sibling = NULL; sp->leftchild = NULL;
- for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
- sp->treecnt = 0;
- sp->partial = _allocpartial();
- return(sp);
-}
-
-_freeskel(sp)
- skeleton *sp;
-{
- int i;
- __match *mp;
- if(sp==NULL)
- return;
- if(sp->leftchild)
- _freeskel(sp->leftchild);
- if(sp->sibling)
- _freeskel(sp->sibling);
- _freepartial (sp->partial);
- for (i=0; i < MAXLABELS; i++)
- if ((mp = sp->succ[i])!=NULL) _freematch (mp);
- sp->sibling = sfreep;
- sfreep = sp;
-}
-
-_match()
-{
- skeleton *sp;
- sp = _allocskel();
- sp->root = NULL;
- _mpbtop = _mpblock;
- _freeskel(_walk(sp, HANG));
-#ifdef CHECKMEM
- if(f_matches+_count!=x_matches) {
- printf(";#m %d %d %d\n", f_matches, _count, x_matches);
- assert(0);
- }
- if(f_partials+pcount!=x_partials) {
- printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
- assert(0);
- }
-#endif
-}
-
-NODEPTR
-_mtG(root,i)
- NODEPTR root;
- int i;
-{
- int *p = &i;
- while(*p!=-1)
- root = mtGetNodes(root, *p++);
- return(root);
-}
-
-/* diagnostic routines */
-
-_prskel (skp, lvl)
- skeleton *skp; int lvl;
-{
- int i; __match *mp;
- __partial *pp;
- if(skp==NULL) return;
- for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
- printf ("###\n");
- for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
- for (i = 0; i < MAXLABELS; i++)
- if ((mp=skp->succ[i])!=NULL)
-#ifdef LINE_XREF
- printf ("[%d<%d> %d]", mp->tree,
- mtLine[mp->tree], mp->cost);
-#else
- printf ("[%d %d]", mp->tree, mp->cost);
-#endif
- putchar('\n');
- for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
- for (i = 0, pp=skp->partial; i < skp->treecnt; i++, pp++)
-#ifdef LINE_XREF
- printf("(%d<%d> %x)", pp->treeno, mtLine[pp->treeno],
- pp->bits);
-#else
- printf ("(%d %x)", pp->treeno, pp->bits);
-#endif
- putchar('\n');
- fflush(stdout);
- _prskel (skp->leftchild, lvl+2);
- _prskel (skp->sibling, lvl);
-}
//GO.SYSIN DD rawwalker.c1
echo rawwalker.ex 1>&2
sed 's/.//' >rawwalker.ex <<'//GO.SYSIN DD rawwalker.ex'
-/*
- * See Aho, Corasick Comm ACM 18:6, and Hoffman and O'Donell JACM 29:1
- * for detail of the matching algorithm
- */
-
-/* turn this flag on if your machine has a fast byte string zero operation */
-/*#define BZERO 1*/
-int mtDebug = 0;
-int treedebug = 0;
-extern int _machstep();
-extern short int mtStart;
-extern short int mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
-#ifdef LINE_XREF
- extern short int mtLine[];
-#endif
-extern NODEPTR mtGetNodes(), mtAction();
-extern skeleton *_allocskel();
-extern __match *_allocmatch();
-extern __partial *_allocpartial();
-
-#define MPBLOCKSIZ 3000
-__match *_mpblock[MPBLOCKSIZ], **_mpbtop;
-
-/*
- * See sym.h in the preprocessor for details
- * Basically used to support eh $%n$ construct.
- */
-__match **
-_getleaves (mp, skp)
- register __match *mp; register skeleton *skp;
-{
- skeleton *stack[MAXDEPTH];
- skeleton **stp = stack;
- register short int *sip = &mtPaths[mtPathStart[mp->tree]];
- register __match **mmp = _mpbtop;
- __match **mmp2 = mmp;
- if((_mpbtop += *sip++ + 1) > &_mpblock[MPBLOCKSIZ]) {
- printf ("ich: %d\n", _mpbtop-_mpblock);
- assert(0);
- }
-
- for(;;)
- switch(*sip++) {
- case ePUSH:
- *stp++ = skp;
- skp = skp->leftchild;
- break;
-
- case eNEXT:
- skp = skp->sibling;
- break;
-
- case eEVAL:
- if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
- *mmp++ = mp;
- break;
-
- case ePOP:
- skp = *--stp;
- break;
-
- case eSTOP:
- *mmp = NULL;
- return (mmp2);
- }
-}
-
-_evalleaves (mpp)
- register __match **mpp;
-{
- for (; *mpp!=NULL; mpp++) {
- register __match *mp = *mpp;
- _do (mp->skel, mp, 1);
- }
-}
-
-
-_do(sp, winner, evalall)
- skeleton *sp; register __match *winner; int evalall;
-{
- register __match **mpp;
- register skeleton *skel = winner->skel;
- if(winner==NULL) {
- _prskel(sp, 0);
- puts ("no winner");
- return;
- }
- if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
- REORDER (winner->lleaves);
- mtSetNodes (skel->parent, skel->nson,
- skel->root=mtAction (winner->tree, winner->lleaves, sp));
-}
-
-skeleton *
-_walk(sp, ostate)
- register skeleton *sp;
- int ostate;
-{
- int state, nstate, nson;
- register __partial *pp;
- register __match *mp, *mp2;
- register skeleton *nsp, *lastchild = NULL;
- NODEPTR son, root;
-
- root = sp->root;
- nson = 1; sp->mincost = INFINITY;
- state = _machstep (ostate, root, mtValue(root));
-
- while((son = mtGetNodes(root, nson))!=NULL) {
- nstate = _machstep (state, NULL, MV_BRANCH(nson));
- nsp = _allocskel();
- nsp->root = son;
- nsp->parent = root;
- nsp->nson = nson;
- _walk(nsp, nstate);
- if(COSTLESS(nsp->mincost, INFINITY)) {
- assert (nsp->winner->mode==xREWRITE);
- if (mtDebug || treedebug) {
- printf ("rewrite\n");
- _prskel (nsp, 0);
- }
- _do(nsp, nsp->winner, 0);
- _freeskel(nsp);
- continue;
- }
- _merge (sp, nsp);
- if (lastchild==NULL) sp->leftchild = nsp;
- else lastchild->sibling = nsp;
- lastchild = nsp;
- nson++;
- }
-
- for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
- if (pp->bits&01==1) {
- mp = _allocmatch();
- mp->tree = pp->treeno;
- _addmatches (ostate, sp, mp);
- }
- if(son==NULL && nson==1)
- _closure (state, ostate, sp);
-
- sp->rightchild = lastchild;
- if (root==NULL) {
- COST c; __match *win; int i; nsp = sp->leftchild;
- c = INFINITY;
- win = NULL;
- for (i = 0; i < MAXLABELS; i++) {
- mp = nsp->succ[i];
- if (mp!=NULL && COSTLESS (mp->cost, c))
- { c = mp->cost; win = mp; }
- }
- if (mtDebug || treedebug)
- _prskel (nsp, 0);
- _do (nsp, win, 0);
- }
- if (mtDebug)
- _prskel (sp, 0);
- return(sp);
-}
-
-static short int _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
-
-/*
- * Convert the start state which has a large branching factor into
- * a index table. This must be called before the matcher is used.
- */
-_matchinit()
-{
- short int *sp;
- struct pair { short int val, where } *pp;
- for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
- for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
- sp = &mtTable[mtStart];
- assert (*sp==TABLE);
- for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
- if (MI_NODE(pp->val))
- _nodetab[M_DETAG(pp->val)] = pp->where;
- else if (MI_LABEL(pp->val))
- _labeltab[M_DETAG(pp->val)] = pp->where;
- }
-}
-
-int
-_machstep(state, root, input)
- short int state, input;
- NODEPTR root;
-{
- register short int *stp = &mtTable[state];
- int start = 0;
- if (state==HANG)
- return (input==(MV_BRANCH(1)) ? mtStart : HANG);
-rescan:
- if (stp==&mtTable[mtStart]) {
- if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
- if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
- }
-
- for(;;) {
- if(*stp==ACCEPT) stp += 2;
-
- if(*stp==TABLE) {
- stp++;
- while(*stp!=EOT) {
- if(input==*stp) {
- return(*++stp);
- }
- stp += 2;
- }
- stp++;
- }
- if(*stp!=FAIL) {
- if (start) return (HANG);
- else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
- } else {
- stp++;
- stp = &mtTable[*stp];
- goto rescan;
- }
- }
-}
-
-_addmatches(ostate, sp, np)
- int ostate;
- register skeleton *sp;
- register __match *np;
-{
- int label;
- int state, qstate;
- register __match *mp;
- static short int quick[128][MAXLABELS];
- static short int qtag[128][MAXLABELS];
-
- label = mtMap[np->tree];
-
- /*
- * The following lines replace the line:
- *
- * state = _machstep(ostate, NULL, MV_LABEL(label));
- *
- * Statistics show that a large percentage (approx 2/3) of calls to
- * _machstep occur in this function. The lines below attempt
- * to reduce the number of these calls by using an unsophisticated
- * but apparently adequate caching scheme.
- */
- qstate = ((ostate>>2)+2)&0177;
- if(ostate != qtag[qstate][label]) {
- state = _machstep(ostate, NULL, MV_LABEL(label));
- quick[qstate][label] = state;
- qtag[qstate][label] = ostate;
- } else state = quick[qstate][label];
-
- /*
- * this is a very poor substitute for good design of the DFA.
- * What we need is a special case that allows any label to be accepted
- * by the start state but we don't want the start state to recognize
- * them after a failure.
- */
- if (ostate!=mtStart && state==HANG) {
- _freematch(np);
- return;
- }
-
- np->lleaves = _getleaves (np, sp);
- np->skel = sp;
- if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
- {
- _freematch(np);
- return;
- }
-
- if ((mp = sp->succ[label])!=NULL) {
- if (!COSTLESS (np->cost, mp->cost))
- { _freematch(np); return; }
- else _freematch(mp);
- }
- if(COSTLESS(np->cost,sp->mincost)) {
- if(np->mode==xREWRITE) {
- sp->mincost = np->cost; sp->winner = np; }
- else { sp->mincost = INFINITY; sp->winner = NULL; }
- }
- sp->succ[label] = np;
- _closure(state, ostate, sp);
-}
-
-_closure(state, ostate, skp)
- int state, ostate;
- skeleton *skp;
-{
- register struct ap { short int tree, depth; } *ap;
- short int *sp = &mtTable[state];
- register __match *mp;
-
- if(state==HANG || *sp!=ACCEPT) return(NULL);
-
- for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
- if (ap->depth==0) {
- mp = _allocmatch();
- mp->tree = ap->tree;
- _addmatches (ostate, skp, mp);
- } else {
- register __partial *pp, *lim = &skp->partial[skp->treecnt];
- for(pp=skp->partial; pp < lim; pp++)
- if(pp->treeno==ap->tree)
- break;
- if(pp==lim) {
- skp->treecnt++;
- pp->treeno = ap->tree;
- pp->bits = (1<<(ap->depth));
- } else pp->bits |= (1<<(ap->depth));
- }
-}
-
-_merge (old, new)
- skeleton *old, *new;
-{
- register __partial *op = old->partial, *np = new->partial;
- int nson = new->nson;
- register __partial *lim = np + new->treecnt;
- if (nson==1) {
- old->treecnt = new->treecnt;
- for(; np < lim; op++, np++) {
- op->treeno = np->treeno;
- op->bits = np->bits/2;
- }
- } else {
- __partial *newer = _allocpartial();
- register __partial *newerp = newer;
- register int cnt;
- lim = op+old->treecnt;
- for(cnt=new->treecnt; cnt-- ; np++) {
- for(op = old->partial; op < lim; op++)
- if (op->treeno == np->treeno) {
- newerp->treeno = op->treeno;
- newerp++->bits = op->bits & (np->bits/2);
- break;
- }
- }
- _freepartial(old->partial);
- old->partial = newer;
- old->treecnt = newerp-newer;
- }
-}
-
-/* Save and Allocate Matches */
-#define BLKF 100
-__match *freep = NULL;
-static int _count = 0;
-static __match *_blockp = NULL;
-#ifdef CHECKMEM
-int x_matches, f_matches;
-#endif
-
-__match *
-_allocmatch()
-{
- __match *mp;
-
- if(freep!=NULL) {
- mp = freep;
- freep = ((__match *)((struct freeb *) freep)->next);
-#ifdef CHECKMEM
- f_matches--;
-#endif
- } else {
- if(_count==0) {
- _blockp = (__match *) malloc (BLKF*sizeof (__match));
- _count = BLKF;
-#ifdef CHECKMEM
- x_matches += BLKF;
-#endif
- }
- mp = _blockp++;
- _count--;
- }
- return(mp);
-}
-
-_freematch(mp)
- __match *mp;
-{
- ((struct freeb *) mp)->next = (struct freeb *) freep;
- freep = mp;
-#ifdef CHECKMEM
- f_matches++;
-#endif
-}
-
-static __partial *pfreep = NULL;
-static int pcount = 0;
-static __partial *pblock = NULL;
-#ifdef CHECKMEM
-static int x_partials, f_partials;
-#endif
-
-__partial *
-_allocpartial()
-{
- __partial *pp;
- if (pfreep!=NULL) {
- pp = pfreep;
- pfreep = *(__partial **) pp;
-#ifdef CHECKMEM
- f_partials--;
-#endif
- } else {
- if (pcount==0) {
- pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
- pcount = BLKF;
-#ifdef CHECKMEM
- x_partials += BLKF;
-#endif
- }
- pp = pblock;
- pblock += MAXTREES;
- pcount--;
- }
- return(pp);
-}
-
-_freepartial(pp)
- __partial *pp;
-{
- * (__partial **)pp = pfreep;
- pfreep = pp;
-#ifdef CHECKMEM
- f_partials++;
-#endif
-}
-
-
-/* storage management */
-static skeleton *sfreep = NULL;
-static int scount = 0;
-static skeleton * sblock = NULL;
-
-skeleton *
-_allocskel()
-{
- skeleton *sp;
- int i;
- if(sfreep!=NULL) {
- sp = sfreep;
- sfreep = sp->sibling;
- } else {
- if(scount==0) {
- sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
- scount = BLKF;
- }
- sp = sblock++;
- scount--;
- }
- sp->sibling = NULL; sp->leftchild = NULL;
- for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
- sp->treecnt = 0;
- sp->partial = _allocpartial();
- return(sp);
-}
-
-_freeskel(sp)
- skeleton *sp;
-{
- int i;
- __match *mp;
- if(sp==NULL)
- return;
- if(sp->leftchild)
- _freeskel(sp->leftchild);
- if(sp->sibling)
- _freeskel(sp->sibling);
- _freepartial (sp->partial);
- for (i=0; i < MAXLABELS; i++)
- if ((mp = sp->succ[i])!=NULL) _freematch (mp);
- sp->sibling = sfreep;
- sfreep = sp;
-}
-
-_match()
-{
- skeleton *sp;
- sp = _allocskel();
- sp->root = NULL;
- _mpbtop = _mpblock;
- _freeskel(_walk(sp, HANG));
-#ifdef CHECKMEM
- if(f_matches+_count!=x_matches) {
- printf(";#m %d %d %d\n", f_matches, _count, x_matches);
- assert(0);
- }
- if(f_partials+pcount!=x_partials) {
- printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
- assert(0);
- }
-#endif
-}
-
-NODEPTR
-_mtG(root,i)
- NODEPTR root;
- int i;
-{
- int *p = &i;
- while(*p!=-1)
- root = mtGetNodes(root, *p++);
- return(root);
-}
-
-/* diagnostic routines */
-
-_prskel (skp, lvl)
- skeleton *skp; int lvl;
-{
- int i; __match *mp;
- __partial *pp;
- if(skp==NULL) return;
- for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
- printf ("###\n");
- for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
- for (i = 0; i < MAXLABELS; i++)
- if ((mp=skp->succ[i])!=NULL)
-#ifdef LINE_XREF
- printf ("[%d<%d> %d]", mp->tree,
- mtLine[mp->tree], mp->cost);
-#else
- printf ("[%d %d]", mp->tree, mp->cost);
-#endif
- putchar('\n');
- for (i = lvl; i > 0; i--) { putchar (' '); putchar (' '); }
- for (i = 0, pp=skp->partial; i < skp->treecnt; i++, pp++)
-#ifdef LINE_XREF
- printf("(%d<%d> %x)", pp->treeno, mtLine[pp->treeno],
- pp->bits);
-#else
- printf ("(%d %x)", pp->treeno, pp->bits);
-#endif
- putchar('\n');
- fflush(stdout);
- _prskel (skp->leftchild, lvl+2);
- _prskel (skp->sibling, lvl);
-}
//GO.SYSIN DD rawwalker.ex
echo sym.c 1>&2
sed 's/.//' >sym.c <<'//GO.SYSIN DD sym.c'
-/*
- * Symbol manipulation routines
- */
-#include "common.h"
-#include "code.h"
-#include "sym.h"
-#include "machine.h"
-#include "y.tab.h"
-#include "mem.h"
-
-#define SAFE 1 /* generates code to do redundant checks */
-#define MAXSYMS 100
-#define MAX_UNIQUE 255
-
-static void AppendToList();
-typedef
- struct SymbolList {
- SymbolEntry *first, *last;
- int count;
- }
- SymbolList;
-
-/*
- * The range of the unique numbers assigned to each type of
- * symbol is [min,max)
- */
-struct ranges {
- int min,max;
- int limit;
-} uniques[] = {
- {0, 0, MAX_UNIQUE}, /* A_UNDEFINED -- not used */
- {0, 0, MAX_NODE_VALUE}, /* A_NODE */
- {0, 0, MAX_UNIQUE}, /* A_LABEL */
- {0, 0, MAX_UNIQUE}, /* A_COST */
- {0, 0, MAX_UNIQUE}, /* A_ACTION */
-};
-
-int treeIndex = 0;
-
-static SymbolList lists[] = {
- { NULL, NULL, 0}, /* A_UNDEFINED -- never used */
- { NULL, NULL, 0}, /* A_NODE */
- { NULL, NULL, 0}, /* A_LABEL */
- { NULL, NULL, 0}, /* A_COST */
- { NULL, NULL, 0}, /* A_ACTION */
- { NULL, NULL, 0}, /* A_CONST */
-};
-
-struct _mem sym_mem, lab_mem, tree_mem;
-SymbolEntry *hash_table[HASHSIZE];
-SymbolEntry *startSymbol;
-
-static int
-RawHash(s)
- register char *s;
-{
- register int sum = 0;
- register int i = 0;
- while(*s)
- sum += (++i)*(0377&*s++);
- return(sum);
-}
-
-
-/*
- * Allocate a new symbol_entry structure for the given structure and
- * return it. There is no check of whether the symbol is already defined or
- * not. The caller is expected to fill in the uninitialized fields.
- */
-SymbolEntry *
-SymbolAllocate(s)
- char *s;
-{
- SymbolEntry *sp;
- sp = (SymbolEntry *) mem_get(&sym_mem);
- assert(sp!=NULL);
-
-#ifdef SAFE
- assert (SymbolLookup(s) == NULL);
-#endif
-
- sp->name = malloc(strlen(s)+1);
- assert(sp->name!=NULL);
- strcpy (sp->name, s);
- sp->hash = RawHash(s);
- sp->next = NULL;
- sp->attr = A_UNDEFINED;
- sp->unique = -1;
- return(sp);
-}
-
-void
-SymbolFree (symp)
- SymbolEntry *symp;
-{
- assert (symp->next == NULL);
- free(symp);
-}
-
-SymbolEntry *
-SymbolLookup(s)
- char *s;
-{
- int hash_value = RawHash(s);
- register SymbolEntry * hp = hash_table[hash_value%HASHSIZE];
-
- while(hp!=NULL) {
- if(hp->hash == hash_value &&
- strcmp (s, hp->name)==0) break;
- hp = hp->next;
- }
- return(hp);
-}
-
-/*
- * enter the symbol into the symbol table. It believes everything in the
- * symp argument.
- */
-void
-SymbolEnter (symp, attr)
- SymbolEntry *symp;
- byte attr;
-{
- struct symbol_entry *hp;
-
-#ifdef SAFE
- assert (symp!=NULL);
- assert (symp->hash == RawHash(symp->name));
- assert (symp->attr == A_UNDEFINED);
-#endif
-
- hp = hash_table[symp->hash%HASHSIZE];
- symp->next = hp;
- hash_table[symp->hash%HASHSIZE] = symp;
- symp->attr = attr;
- if (HAS_UNIQUE(attr)){
- struct ranges *rp = &uniques[attr];
- int new_unique;
- if(symp->unique==-1)
- symp->unique = new_unique = rp->max++;
- else {
- new_unique = symp->unique;
- if(new_unique>=rp->max)
- rp->max = new_unique+1;
- else if(new_unique < rp->min)
- rp->min = new_unique;
- }
- if(new_unique>rp->limit)
- sem_error("number assigned to %s (%d) out of range",
- symp->name, new_unique);
- if(new_unique<0)
- sem_error("number assigned to %s (%d) is negative",
- symp->name, new_unique);
- assert(rp->max>=rp->min);
- }
- if (HAS_LIST(attr)) {
- AppendToList(&lists[attr], symp);
- }
-}
-
-static void
-AppendToList(list, sp)
- SymbolList *list;
- SymbolEntry *sp;
-{
- sp->link = NULL;
- if(list->first==NULL)
- list->first = sp;
- else (list->last)->link = sp;
- list->last = sp;
- list->count++;
-}
-
-SymbolCheckNodeValues()
-{
- SymbolList *slist;
- SymbolEntry **stab, **spp, *sp;
- struct ranges *rp;
- int i, range;
-
- rp = &uniques[A_NODE];
- slist = &lists[A_NODE];
- range = rp->max - rp->min + 1;
- stab = (SymbolEntry **) malloc(range*sizeof(SymbolEntry *));
-
- for(i=range, spp = stab; i-->0; spp++) *spp = NULL;
-
- for(sp = slist->first; sp; sp = sp->link) {
- SymbolEntry *sp2 = stab[sp->unique];
- if(sp2==NULL)
- stab[sp->unique] = sp;
- else
- sem_error("%s and %s have the same node value",
- sp2->name, sp->name);
- }
- free(stab);
-}
-
-SymbolEntry *
-SymbolEnterKeyword(s, value)
- char *s;
- int value;
-{
- SymbolEntry *sp = SymbolAllocate(s);
- sp->sd.keyword = value;
- SymbolEnter (sp, A_KEYWORD);
- return(sp);
-}
-
-void
-SymbolInit()
-{
- SymbolEntry *sp;
-
- mem_init(&sym_mem,sizeof(SymbolEntry));
- mem_init(&lab_mem,sizeof(LabelData));
- mem_init(&tree_mem,sizeof(struct treeassoc));
- SymbolEnterKeyword ("node", K_NODE);
- SymbolEnterKeyword ("label", K_LABEL);
- SymbolEnterKeyword ("prologue", K_PROLOGUE);
- SymbolEnterKeyword ("const", K_CONST);
- SymbolEnterKeyword ("insert", K_INSERT);
- SymbolEnterKeyword ("cost", K_COST);
- SymbolEnterKeyword ("action", K_ACTION);
-}
-
-void
-SymbolMap(f)
- int (*f)();
-{
- SymbolEntry **spp, *sp;
- for(spp = hash_table; spp < &hash_table[HASHSIZE]; spp++)
- for(sp= *spp; sp!=NULL; sp = sp->next)
- f(sp);
-};
-
-static int symcnt, labcnt, nodecnt;
-static
-sym_count(sp)
- SymbolEntry *sp;
-{
- symcnt++;
- switch(sp->attr) {
- case A_LABEL: {
- LabelData *lp;
- for(lp = sp->sd.lp;lp!=NULL;lp=lp->next) {
- labcnt++;
- nodecnt += cntnodes(lp->tree);
- }
- } break;
- }
-}
-
-void
-SymbolFinish()
-{
- if(DB_MEM&debug_flag) {
- extern struct _mem node_mem;
- int symout = mem_outstanding(&sym_mem);
- int labout = mem_outstanding(&lab_mem);
- int nodeout = mem_outstanding(&node_mem);
- SymbolMap(sym_count);
- fprintf(stderr,"symbols defined=%d out=%d\n",symcnt, symout);
- fprintf(stderr,"labdata def=%d out=%d\n",labcnt,labout);
- fprintf(stderr,"node def=%d out=%d\n",nodecnt,nodeout);
- assert(symcnt==symout);
- assert(labcnt==labout);
- assert(nodecnt==nodeout);
- }
-}
-
-void
-SymbolEnterList (symp, attr)
- SymbolEntry *symp;
- int attr;
-{
- /*
- * enter in reverse order because the list was built in reverse
- * order by the parser
- */
-
- if(symp==NULL)
- return;
- SymbolEnterList(symp->next, attr);
- if(symp->attr!=A_UNDEFINED)
- sem_error ("multiple declaration ignored: %s", symp->name);
- SymbolEnter (symp, attr);
-}
-
-LabelData *
-SymbolEnterTreeIntoLabel(symp, tree, costfunc, action, lineno)
- SymbolEntry *symp, *action, *costfunc;
- struct node *tree;
- int lineno;
-{
- LabelData *tp = (LabelData *) mem_get(&lab_mem);
- struct treeassoc *ap;
-
- if (symp==&ErrorSymbol) return(NULL);
-#ifdef SAFE
- assert (tp!=NULL);
- assert (symp->attr==A_LABEL);
-#endif
-
- tp->tree = tree;
- tp->treeIndex = treeIndex++;
- tp->lineno = lineno;
- tp->next = symp->sd.lp;
- tp->label = symp;
- symp->sd.lp = tp;
-
- if (action!=NULL) {
- ap = (struct treeassoc *) mem_get(&tree_mem);
- ap->tree = tp->treeIndex;
- ap->next = action->sd.ca.assoc;
- action->sd.ca.assoc = ap;
- }
-
- if (costfunc!=NULL) {
- ap = (struct treeassoc *) mem_get(&tree_mem);
- ap->tree = tp->treeIndex;
- ap->next = costfunc->sd.ca.assoc;
- costfunc->sd.ca.assoc = ap;
- }
- return(tp);
-}
-
-static void
-WriteSymbols(sp, mask)
- SymbolEntry *sp;
- int mask;
-{
- for(;sp!=NULL; sp = sp->link)
- fprintf(symfile, "#define %s\t0%o\n", sp->name, sp->unique|mask);
-}
-
-void
-SymbolDump()
-{
- WriteSymbols(lists[A_NODE].first, M_NODE);
- WriteSymbols(lists[A_LABEL].first, 0);
- WriteSymbols(lists[A_CONST].first, 0);
- fprintf(symfile, "#define MAXLABELS %d\n", uniques[A_LABEL].max);
- fprintf(symfile, "#define MAXTREES %d\n", treeIndex);
- fprintf(symfile, "#define MAXNDVAL %d\n", uniques[A_NODE].max);
-}
-
-void
-SymbolGenerateWalkerCode()
-{
- register SymbolEntry *pp;
- int i;
- extern int line_xref_flag;
- struct treeassoc *tap;
- register LabelData *lp;
- register short int *mapTab;
-
- /*
- * Write out the table of tree index to label correspondence
- */
- mapTab = (short int *) malloc (treeIndex * sizeof(short int));
- for(pp=lists[A_LABEL].first; pp!=NULL; pp=pp->link) {
- lp = pp->sd.lp;
- if(lp==NULL)
- sem_error2("%s undefined\n", pp->name);
- for(;lp!=NULL;lp=lp->next)
- mapTab[lp->treeIndex] = pp->unique;
- }
- fputs("short int mtMap[] = {\n", outfile);
- for(i=0, oreset(); i < treeIndex;)
- oputoct(mapTab[i++]);
- fputs("};\n", outfile);
-
- /* generate tree to line index table */
- if(line_xref_flag) {
- for(pp=lists[A_LABEL].first; pp!=NULL; pp=pp->link) {
- lp = pp->sd.lp;
- for(;lp!=NULL;lp=lp->next)
- mapTab[lp->treeIndex] = lp->lineno;
- }
- fputs("short int mtLine[] = {\n", outfile);
- for(i=0, oreset(); i<treeIndex;)
- oputint(mapTab[i++]);
- fputs("};\n", outfile);
- }
- /*
- * Generate path table
- */
- fputs ("short int mtPaths[] = {\n", outfile);
- for(pp=lists[A_LABEL].first, oreset(); pp!=NULL; pp=pp->link) {
- lp = pp->sd.lp;
- if(lp==NULL)
- sem_error2("%s undefined\n", pp->name);
- do {
- mapTab[lp->treeIndex] = ointcnt();
- oputint (lp->tree->nlleaves);
- SymbolWritePath (lp->tree);
- oputint (eSTOP);
- lp = lp->next;
- } while (lp!=NULL);
- }
- fputs(" };\nshort int mtPathStart[] = {\n", outfile);
- for(i=0, oreset(); i < treeIndex;)
- oputint (mapTab[i++]);
- fputs("};\n", outfile);
-
- /*
- * Code to perform the action of the trees
- */
- fputs("NODEPTR\nmtAction (_t, _ll, _s)\n", outfile);
- fputs("int _t; __match **_ll; skeleton *_s;\n", outfile);
- fputs("{ NODEPTR root = _s->root;\n", outfile);
- fputs("switch (_t) {\n", outfile);
- for (pp=lists[A_ACTION].first; pp!=NULL; pp=pp->link) {
- if ((tap=pp->sd.ca.assoc)==NULL) {
- sem_error2 ("%s not used", pp->name);
- continue;
- }
- for (; tap!=NULL; tap=tap->next)
- fprintf (outfile, "case %d:", tap->tree);
- fputs ("{\n", outfile);
- CodeWrite (outfile, pp->sd.ca.code);
- fputs("} break;\n", outfile);
- }
- fputs("} return(_s->root);}\n", outfile);
-
- fputs ("mtEvalCost(_m, _ll, _s)\n", outfile);
- fputs ("__match **_ll; __match *_m; skeleton *_s;\n", outfile);
- fputs ("{ NODEPTR root = _s->root;\n", outfile);
- fputs ("COST cost; cost = DEFAULT_COST;\n", outfile);
- fputs ("switch(_m->tree) {\n", outfile);
- for(pp=lists[A_COST].first; pp!=NULL; pp=pp->link) {
- if ((tap=pp->sd.ca.assoc)==NULL) {
- sem_error2 ("%s not used", pp->name);
- continue;
- }
- for (; tap!=NULL; tap=tap->next)
- fprintf (outfile, "case %d:", tap->tree);
- fputs ("{\n", outfile);
- CodeWrite (outfile, pp->sd.ca.code);
- fputs ("} break;\n", outfile);
- }
- fputs("}\n", outfile);
- fputs("_m->cost = cost; return(xDEFER);}\n", outfile);
-
-}
-
-SymbolWritePath (root)
- Node *root;
-{
- Node *np;
- if(root->nlleaves==0)
- return;
- if((root->sym)->attr==A_LABEL) {
- oputint (eEVAL); oputoct (MV_LABEL((root->sym)->unique));
- return;
- }
- oputint (ePUSH);
- for(np = root->children;;) {
- if(np->nlleaves > 0)
- SymbolWritePath (np);
- if ((np = np->siblings) == NULL)
- break;
- oputint (eNEXT);
- }
- oputint (ePOP);
- return;
-}
-
-static int gensymndx = 0;
-
-char *
-SymbolGenUnique()
-{
- static char name[7];
- name[0] = '$';
- sprintf (&name[1], "%05d", gensymndx++);
- return (name);
-}
//GO.SYSIN DD sym.c
echo sym.h 1>&2
sed 's/.//' >sym.h <<'//GO.SYSIN DD sym.h'
-/* symbol table definitions */
-extern int symbol_undefined;
-
-/*
- * A LabelData structures are associated with label symbols. They
- * indicate that a tree is labelled with the symbol
- */
-typedef struct LabelData LabelData;
-
-struct LabelData {
- Node *tree;
- int treeIndex;
- int lineno;
- SymbolEntry *label; /* back pointer */
- LabelData *next;
-};
-
-struct treeassoc {
- int tree;
- struct treeassoc *next;
-};
-
-struct symbol_entry {
- int hash;
- char *name;
- short attr;
-# define A_UNDEFINED 0
-# define A_NODE 1
-# define A_LABEL 2
-# define A_COST 3
-# define A_ACTION 4
-# define MAXCHAINS A_CONST
-# define HAS_UNIQUE(x) (x<MAXCHAINS)
-# define A_CONST 5
-# define HAS_LIST(x) (x<=A_CONST)
-# define A_ERROR 10
-# define A_KEYWORD 11
- short unique;
- struct symbol_entry *link;
- struct symbol_entry *next;
- union {
- int keyword;
- int cvalue; /* a constant's value */
- int arity; /* information stored for A_NODE type */
- LabelData *lp;
- struct {
- int arity;
- Code *code;
- } predData;
- struct {
- struct treeassoc *assoc;
- Code *code;
- } ca; /* data for cost/action symbols */
- } sd;
-};
-
-extern void SymbolInit();
-extern void SymbolEnter();
-extern SymbolEntry *SymbolLookup();
-extern SymbolEntry *SymbolAllocate();
-extern void SymbolFree();
-extern void SymbolEnterList();
-extern char *SymbolGenUnique();
-
-extern SymbolEntry ErrorSymbol;
-
-/*
- * In order for the walker to access the labelled leaves of a pattern,
- * a table (mistakenly) called the path table is generated (see sym.c).
- * This table contains the following possible values:
- *
- * ePush follow the children link in the walker skeleton.
- * ePop Pop up to parent.
- * eNext follow the siblings link.
- * eEval <arg> The current node is a labelled leaf whose label id
- * is the integer <arg>.
- * eStop All done. stop!
- *
- * The table is interpreted by the _getleaves routine in the walker.
- */
-#define eSTOP 0
-#define ePOP -1
-#define eEVAL -2
-#define eNEXT -3
-#define ePUSH -4
//GO.SYSIN DD sym.h
echo trees.c 1>&2
sed 's/.//' >trees.c <<'//GO.SYSIN DD trees.c'
-#include "common.h"
-#include "code.h"
-#include "sym.h"
-#include "mem.h"
-
-struct _mem node_mem;
-
-void
-TreeFree(root)
- Node *root;
-{
- if(root==NULL) return;
- TreeFree(root->children);
- TreeFree(root->siblings);
- free(root);
-}
-
-void
-TreePrint(tree, flag)
- Node *tree;
- int flag;
-{
- if(tree==NULL)
- return;
- printf("%s", (tree->sym)->name);
- putchar('(');
- TreePrint(tree->children, 0);
- putchar(')');
- if(tree->siblings!=NULL) {
- putchar(',');
- TreePrint(tree->siblings, 0);
- }
- if(flag) putchar('\n');
-}
-
-Node *
-rev (sl, nl, nlleaves)
- Node *sl, *nl;
- int *nlleaves;
-{
- Node *sl2;
- if(sl==NULL)
- return(nl);
- sl2 = sl->siblings;
- sl->siblings = nl;
- *nlleaves += sl->nlleaves;
- return (rev (sl2, sl, nlleaves));
-}
-
-Node *
-TreeBuild (symp, children)
- SymbolEntry *symp;
- Node *children;
-{
- Node *np = (struct node *) mem_get(&node_mem);
- np->sym = symp;
- np->nlleaves = symp->attr==A_LABEL ? 1 : 0;
- np->children = rev (children, NULL, &np->nlleaves);
- return(np);
-}
-
-TreeInit()
-{
- mem_init(&node_mem, sizeof(struct node));
-}
-
-cntnodes(np)
- Node *np;
-{
- if(np==NULL) return(0);
- else return(1+cntnodes(np->children)+cntnodes(np->siblings));
-}
//GO.SYSIN DD trees.c
echo twig.y 1>&2
sed 's/.//' >twig.y <<'//GO.SYSIN DD twig.y'
-%term ERROR
-%{
-#include "common.h"
-#include "code.h"
-#include "sym.h"
-#define UNDEFINED -1
-#define GIVENUP -2
-
-int debug_flag = 0;
-int Dflag = 0;
-int tflag = 0;
-int line_xref_flag = 0;
-int ntrees = 0;
-int nerrors = 0;
-int fatalerrors = 0;
-int tree_lineno;
-FILE *outfile;
-FILE *symfile;
-Code *epilogue;
-
-SymbolEntry ErrorSymbol;
-%}
-%union {
- Node *y_nodep;
- SymbolEntry *y_symp;
- Code *y_code;
- int y_int;
-}
-%start pattern_spec
-%term K_NODE K_LABEL K_PROLOGUE K_CONST K_INSERT
-%term K_COST K_ACTION
-%token <y_symp> ID
-%token <y_int> NUMBER
-%token <y_code> CBLOCK
-%type <y_nodep> tree tree_list
-%type <y_symp> id_list label assoc_list assoc assoc_list2 assoc2
-%type <y_symp> const_list const_def
-%type <y_int> arity_spec constant
-%type <y_symp> action cost
-%%
-
-pattern_spec: declarations patternsOrInserts =
- { if (nerrors==0) machine_build(); };
-
-declarations: declarations decl
- | decl;
-
-decl: K_NODE assoc_list ';' = { SymbolEnterList ($2, A_NODE); }
-
- | K_NODE assoc_list2 ';'
- = {
- SymbolEnterList($2, A_NODE);
- SymbolCheckNodeValues();
- }
-
- | K_CONST const_list ';' = { SymbolEnterList ($2, A_CONST); }
-
- | K_LABEL id_list ';' = { SymbolEnterList ($2, A_LABEL); }
-
- | K_PROLOGUE CBLOCK ';' = { CodeWrite(outfile, $2); CodeFreeBlock($2); }
-
- | K_COST ID CBLOCK ';'
- = { $2->sd.ca.code = $3; $2->sd.ca.assoc = NULL;
- SymbolEnter ($2, A_COST); }
-
- | K_ACTION ID CBLOCK ';'
- = { $2->sd.ca.code = $3; $2->sd.ca.assoc = NULL;
- SymbolEnter ($2, A_ACTION); }
-
- | K_PROLOGUE error ';'
- | K_ACTION error ';'
- | K_COST error ';'
- ;
-
-/*
- * The rule id_list, assoc_list, and const_list build lists of identifiers.
- * The field "next" is used as a link. This field is also used by the symbol
- * table manager and thus the next field may not be used unless the identifiers
- * have not already been defined.
- */
-
-id_list:
- id_list ID = {
- if(CheckIsUndefined($2)) {
- $2->next = $1;
- $$ = $2;
- } else $$ = $1;
- }
- | ID { if(CheckIsUndefined($1)) $$ = $1; else $$ = NULL; }
- | id_list error;
-
-/*
- * Assoc_list2 allows user assignment of node values
- */
-assoc_list2:
- assoc_list2 assoc2
- = {
- if($2->attr==A_ERROR)
- $$ = $1;
- else { $2->next = $1; $$ = $2; }
- }
- | assoc2 { $$ = $1->attr==A_ERROR ? NULL : $1; }
- | assoc_list2 error;
-
-assoc_list:
- assoc_list assoc = {
- if($2->attr==A_ERROR) $$ = $1;
- else { $2->next = $1; $$ = $2; }
- }
- | assoc { $$ = $1->attr==A_ERROR ? NULL : $1; }
- | assoc_list error;
-
-assoc: ID arity_spec
- = {
- if (CheckIsUndefined($1)) {
- $1->sd.arity = $2; $$ = $1;
- } else $$ = &ErrorSymbol;
- };
-
-assoc2:
- ID arity_spec '=' constant {
- if(CheckIsUndefined($1)) {
- $1->unique = $4; $1->sd.arity = $2;
- $$ = $1;
- } else $$ = &ErrorSymbol;
- };
-
-arity_spec:
- '(' constant ')' = { $$ = $2; };
- | '(' '*' ')' = { $$=GIVENUP; };
- | = { $$ = UNDEFINED; };
-
-const_list:
- const_list const_def = {
- if ($2->attr==A_ERROR) $$ = $1;
- else { $2->next = $1; $$ = $2; }
- }
- | const_def { $$ = $1->attr==A_ERROR ? NULL : $1; }
- | const_list error;
-
-const_def:
- ID '=' constant = {
- if(CheckIsUndefined($1)) {
- $1->sd.cvalue = $3; $$ = $1;
- } else $$ = &ErrorSymbol;
- };
-
-constant:
- NUMBER
- | ID = {
- if(!CheckIsDefined($1)) $$ = UNDEFINED;
- else if($1->attr!=A_CONST) {
- sem_error("non-constant id used");
- $$ = -1;
- } else $$ = $1->sd.cvalue;
- };
-
-patternsOrInserts: patternsOrInserts pattern
- | patternsOrInserts insert
- | insert
- | pattern
- ;
-
-insert: K_INSERT CBLOCK ';' = { epilogue = CodeAppend(epilogue, $2); }
- | K_INSERT error ';'
- ;
-
-pattern:
- label ':' tree cost action ';' = {
- if ($1->attr==A_ERROR) {
- error(0, "\"label: tree\" pair ignored");
- TreeFree($3);
- } else {
- if(nerrors==0)
- cgotofn(SymbolEnterTreeIntoLabel($1,
- $3, $4, $5, tree_lineno));
- if(debug_flag&DB_TREE)
- TreePrint($3, 1);
- }
- }
- | error ';' ;
-
-action: '=' CBLOCK { SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
- sp->sd.ca.code = $2; sp->sd.ca.assoc = NULL;
- SymbolEnter(sp, A_ACTION); $$ = sp; }
- | '=' ID { if(CheckIsDefined($2)) {
- if ($2->attr!=A_ACTION) {
- sem_error ("non action id: %s", $2->name);
- $$ = &ErrorSymbol;
- } else $$ = $2;
- } else $$ = &ErrorSymbol; }
- | { $$ = NULL;};
-
-cost: CBLOCK { SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
- sp->sd.ca.code = $1; sp->sd.ca.assoc = NULL;
- SymbolEnter (sp, A_COST); $$ = sp;
- }
- | ID { if (CheckIsDefined($1)) {
- if ($1->attr!=A_COST) {
- sem_error ("non cost id: %s", $1->name);
- $$ = &ErrorSymbol;
- } else $$ = $1;
- } else $$ = &ErrorSymbol; }
- | { $$ = NULL; };
-
-/* labels play the same role that non-terminals do in YACC */
-label: ID = {
- tree_lineno = yyline; /* record line no */
- if(!CheckIsDefined($1))
- $1->attr = A_ERROR;
- else if(!is_label($1)) {
- sem_error("non label id: %s", $1->name);
- $1->attr = A_ERROR;
- }
- $$ = $1;
- };
-
-tree: ID {CheckIsNodeOrPred($1);} '(' tree_list ')'
- = {
- int count;
- Node *ap;
- /* check the arity of the node */
- for(count=0, ap = $4; ap!=NULL; ap=ap->siblings) count++;
- switch($1->attr) {
- case A_NODE:
- set_arity($1, &$1->sd.arity, count);
- break;
- }
-
- $$ = TreeBuild ($1, $4);
- }
- | ID
- = {
- CheckIsDefined($1);
- switch ($1->attr) {
- case A_NODE:
- set_arity($1, &$1->sd.arity, 0);
- break;
- }
- $$ = TreeBuild ($1, NULL);
- };
-
-tree_list: tree_list ',' tree = {
- /*
- * build sibling list in reverse order TreeBuild will
- * put it right later.
- */
- $3->siblings = $1;
- $$ = $3;
- }
- | tree = { $1->siblings = NULL; $$ = $1; }
- | error { $$ = NULL; };
- | tree_list error;
-
-%%
-
-extern char *process_suffix();
-
-set_arity(symp, arityp, count)
- SymbolEntry *symp;
- int *arityp;
- int count;
-{
- if(*arityp!=GIVENUP) {
- if (*arityp==UNDEFINED)
- *arityp = count;
- else if (*arityp!=count) {
- sem_error("inconsistent arity for %s", symp->name);
- *arityp = GIVENUP;
- }
- }
-}
-
-is_node(symp)
- SymbolEntry *symp;
-{ return(symp->attr==A_NODE); }
-
-is_label(symp)
- SymbolEntry *symp;
-{ return(symp->attr==A_LABEL); }
-
-CheckIsNodeOrPred (symp)
- SymbolEntry *symp;
-{
- if (symp->attr==A_ERROR)
- return;
- if (symp->attr!=A_NODE)
- sem_error ("non-node identifier %s", symp->name);
-}
-
-CheckIsUndefined(symp)
- SymbolEntry *symp;
-{
- if (symp->attr==A_ERROR)
- return(0);
- if (symp->attr!=A_UNDEFINED) {
- sem_error ("multiple declaration: %s", symp->name);
- return(0);
- } else return(1);
-}
-
-CheckIsDefined(symp)
- SymbolEntry *symp;
-{
- if (symp->attr==A_ERROR)
- return(0);
- if (symp->attr==A_UNDEFINED) {
- sem_error ("undefined identifier: %s", symp->name);
- symp->attr=A_ERROR;
- return(0);
- } else return(1);
-}
-
-
-
-/*VARARGS*/
-yyerror(fmt, s1, s2, s3)
- char *fmt, *s1, *s2, *s3;
-{
- fprintf(stderr, "line %d: ", yyline);
- fprintf(stderr, fmt, s1, s2, s3);
- if (token_buffer[0]!=0)
- fprintf(stderr, " at \"%s\"\n", token_buffer);
-}
-
-/*VARARGS*/
-yyerror2 (fmt, s1, s2, s3)
- char *fmt, *s1, *s2, *s3;
-{
- fprintf(stderr, "line %d: ", yyline);
- fprintf(stderr, fmt, s1, s2, s3);
- putchar('\n');
-}
-
-char *cmdnam;
-char *inFileName;
-char *outFileName;
-char prefixFile[100];
-static char usage[] = "usage: mt [-d] file";
-#define USAGE error(1, usage)
-char *prefix_base = PREFIX_BASE;
-char *suffix = "c1";
-
-main(argc, argv)
- int argc;
- char **argv;
-{
- int i;
- char *cp;
-
-#ifndef PREFIX_BASE
- error(1,"PREFIX_BASE has not been defined; recompile twig");
-#endif
-
- cmdnam = argv[0];
- argv++;
- inFileName = NULL;
-
- while(--argc > 0) {
- if (*argv[0]=='-')
- switch(argv[0][1]) {
- /* to see what each of these flags mean...
- * see common.h */
- case 'd': {
- char *cp;
- for(cp = &argv[0][2]; *cp!='\0'; cp++)
- switch(*cp) {
- case 'l': debug_flag |= DB_LEX; break;
- case 'm': debug_flag |= DB_MACH; break;
- case 's': debug_flag |= DB_SYM; break;
- case 't': debug_flag |= DB_TREE; break;
- case 'M': debug_flag |= DB_MEM; break;
- }
- }
- break;
- case 'D': Dflag++; break;
- case 't': tflag++; break;
- case 'w': suffix = process_suffix(&argv[0][2]); break;
- case 'l': prefix_base = &argv[0][2]; break;
- case 'x': line_xref_flag++; break;
- default:
- USAGE;
- }
- else inFileName = argv[0];
- argv++;
- }
- if(inFileName==NULL)
- USAGE;
-
- if(freopen(inFileName, "r", stdin)==NULL)
- error(1, "can't open %s", inFileName);
- if((cp=strrchr(inFileName, '.'))!=NULL && strcmp(cp,".mt")==0) {
- if ((outfile = fopen("walker.c" , "w"))==NULL)
- error(1, "can't write %s", outFileName);
- if ((symfile = fopen("symbols.h", "w"))==NULL)
- error(1, "can't write %s", outFileName);
- } else error(1, "input file must have suffix .mt");
-
- ErrorSymbol.attr = A_LABEL;
- TreeInit();
- SymbolInit();
- LexInit();
- yyparse();
-
- SymbolDump();
- if(nerrors == 0) {
- if(!tflag) {
- FILE *prefix;
- char c;
- sprintf(prefixFile, "%s.%s", prefix_base, suffix);
- prefix = fopen(prefixFile, "r");
- assert(prefix!=NULL);
- if(Dflag)
- fputs("#define DEBUG 1\n", outfile);
- if(line_xref_flag)
- fputs("#define LINE_XREF 1\n", outfile);
- fprintf(outfile,"# line 1 \"%s\"\n", prefixFile);
- while((c=getc(prefix))!=EOF) putc(c, outfile);
- }
- MachineGen();
- SymbolGenerateWalkerCode();
- CodeWrite(outfile, epilogue);
- CodeFreeBlock(epilogue);
- }
-
- /* cleanup */
- cleanup(0);
-}
-
-cleanup(retcode)
- int retcode;
-{
- lexCleanup();
- if(retcode==0) {
- SymbolFinish();
- }
- exit(retcode);
-}
-
-/*VARARGS*/
-error(rc, fmt, a1, a2, a3)
- int rc;
- char *fmt, *a1, *a2, *a3;
-{
- fprintf(stderr, "%s: ", cmdnam);
- fprintf(stderr, fmt, a1, a2, a3);
- putc ('\n', stderr);
- if(rc)
- exit (rc);
-}
-
-/*VARARGS*/
-sem_error (fmt, a1, a2, a3)
- char *fmt, *a1, *a2, *a3;
-{
- fprintf (stderr, "line %d: ", yyline);
- sem_error2(fmt, a1, a2, a3);
- nerrors++;
- fatalerrors++;
-}
-
-/*VARARGS*/
-sem_error2(fmt, a1, a2, a3)
- char *fmt, *a1, *a2, *a3;
-{
- fprintf (stderr, fmt, a1, a2, a3);
- putc('\n', stderr);
- nerrors++;
-}
-
-char *
-process_suffix(suf)
- char *suf;
-{
- extern int gen_table2;
- if(strcmp(suf,"exper")==0) {
- /* experimental walker */
- /* expect this to change alot */
- gen_table2++;
- }
- return(suf);
-}
//GO.SYSIN DD twig.y
echo walker.c1 1>&2
sed 's/.//' >walker.c1 <<'//GO.SYSIN DD walker.c1'
-/*
- * The machine is laid out as a sequence of integers in the walker.
- * The form described above is only used inside the preprocessor.
- * Each machine state is one of the following sequence:
- *
- * TABLE <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
- * or
- * TABLE2 <value_1><index_1>...<value_n><index_n> -1 [FAIL <fail_index>] -1
- * or
- * ACCEPT <accept table index> -1
- *
- * The accept table is in the form:
- *
- * <tree index_1> ...<tree_index_m> -1
- *
- */
-/* Keutzer - all "short int"'s have been changed to "short" for
- portability to UTS. */
-#include "symbols.h"
-/* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
-#include <varargs.h>
-
-#ifndef FILE
-#include <stdio.h>
-#endif
-#include <assert.h>
-
-/* These constants must be the same as the ones in machine.c */
-#define FASTLIM 0
-#define TABLE 1
-#define FAIL 2
-#define ACCEPT 3
-#define TABLE2 4
-#define EOT -1
-
-/* special machine state */
-#define HANG -1
-
-/* used by the evaluator to interpret path table */
-#define eSTOP 0
-#define ePOP -1
-#define eEVAL -2
-#define eNEXT -3
-#define ePUSH -4
-
-/* Tags that indicate the type of a value */
-#define M_BRANCH 010000
-#define M_NODE 0
-#define M_LABEL 01000
-#define MAX_NODE_VALUE 00777
-#define MTAG_SHIFT 9
-#define M_DETAG(x) ((x)&~(M_BRANCH|M_LABEL|M_NODE))
-
-/* predicates to tell whether a value x is of type NODE, BRANCH, or LABEL */
-#define MI_NODE(x) (((x)&(M_BRANCH|M_LABEL))==0)
-#define MI_DEFINED(x) ((x)!=-1)
-#define MI_LABEL(x) (((x)&M_LABEL)!=0)
-#define MI_BRANCH(x) (((x)&M_BRANCH)!=0)
-
-/* build a tagged value */
-#define MV_NODE(x) (x)
-#define MV_BRANCH(x) ((x)|M_BRANCH)
-#define MV_LABEL(x) ((x)|M_LABEL)
-
-/* limits */
-/*
- * The depth of a pattern must be 7 or less. Otherwise the type of he
- * partial mask in skeleton must be changed
- */
-#define MAXDEPTH 7
-
-/* modes */
-#define xTOPDOWN 3
-#define xABORT 2
-#define xREWRITE 1
-#define xDEFER 0
-
-/* macros */
-#define tDO(m) _do((m)->skel, (m), 1)
-#define REWRITE return(_m->cost = cost, xREWRITE)
-#define TOPDOWN return(_m->cost = cost, xTOPDOWN)
-#define ABORT return(xABORT)
-
-/*
- * REORDER macro allows a knowledgeable user to change the order
- * of evaluation of the leaves.
- */
-#ifndef REORDER
-#define REORDER(list) _evalleaves(list)
-#endif
-#define EVAL REORDER(_ll)
-
-#define mpush(s,m) (m)->next = s, s = m
-
-/* skeleton structure */
-typedef struct skeleton skeleton;
-typedef struct __match __match;
-typedef struct __partial __partial;
-typedef struct __hshcls __hshcls; /* a hashed closure entry */
-typedef int labelset; /* a bit vector of labels */
-
-struct __partial {
- unsigned char treeno;
- char bits;
-};
-
-struct __hshcls {
- __hshcls *next;
- labelset labels;
- int treecnt; /* number of partial matches */
- __partial partial[MAXTREES];
-};
-
-struct skeleton {
- skeleton *sibling;
- skeleton *leftchild; /* leftmost child */
- skeleton *rightchild; /* rightmost child */
- NODEPTR root;
- NODEPTR parent; /* our parent */
- int nson;
- int treecnt;
- __match *succ[MAXLABELS];
- __partial *partial;
- __match *winner;
- COST mincost;
-};
-
-struct __match {
- __match **lleaves; /* labelled leaves */
- skeleton *skel; /* back pointer to associated skeleton node */
- COST cost;
- short tree;
- short mode;
-};
-
-struct freeb {
- struct freeb *next;
-};
-
-struct _mem {
- struct _mem *next;
- int size; /* size of individual elements in bytes */
- int blkf; /* blocking factor */
- int bsize; /* block size */
- char *block; /* block */
- int cnt; /* count of free elem in block */
- char *freelist; /* free list */
- int totelem; /* total number elements we have */
- int freecnt; /* number of times mem_free was called */
-};
-
-/* turn this flag on if your machine has a fast byte string zero operation */
-/*#define BZERO 1*/
-int mtDebug = 0;
-int treedebug = 0;
-extern int _machstep();
-extern short mtStart;
-extern short mtTable[], mtAccept[], mtMap[], mtPaths[], mtPathStart[];
-#ifdef LINE_XREF
- extern short mtLine[];
-#endif
-
-#ifndef MPBSIZE
-#define MPBSIZE 8000
-#endif
-
-#ifdef ADDCOST
-#define DEFAULT_COST sumleaves(_ll)
-COST sumleaves(list) __match **list;
-{COST cost;
- cost=ZEROCOST;
- for(; *list; list++)
- {ADDCOST((cost),(*list)->cost);
- }
- return cost;
-}
-#endif
-
-extern NODEPTR mtGetNodes(), mtAction();
-extern skeleton *_allocskel();
-extern __match *_allocmatch();
-extern __partial *_allocpartial();
-
-__match *_mpblock[MPBSIZE], **_mpbtop;
-
-__match **
-_getleaves (mp, skp)
- register __match *mp; register skeleton *skp;
-{
- skeleton *stack[MAXDEPTH];
- skeleton **stp = stack;
- register short *sip = &mtPaths[mtPathStart[mp->tree]];
- register __match **mmp = _mpbtop;
- __match **mmp2 = mmp;
- if((_mpbtop += *sip++ + 1) > &_mpblock[MPBSIZE]) {
- printf("Tree too large: make MPBSIZE larger.\n\
-(i.e. cc -c -DMPBSIZE=%d walker.c)\n",MPBSIZE*2);
- assert(0);
- }
-
- for(;;)
- switch(*sip++) {
- case ePUSH:
- *stp++ = skp;
- skp = skp->leftchild;
- break;
-
- case eNEXT:
- skp = skp->sibling;
- break;
-
- case eEVAL:
- if ((mp = skp->succ[M_DETAG(*sip++)])==NULL) abort();
- *mmp++ = mp;
- break;
-
- case ePOP:
- skp = *--stp;
- break;
-
- case eSTOP:
- *mmp = NULL;
- return (mmp2);
- }
-}
-
-_evalleaves (mpp)
- register __match **mpp;
-{
- for (; *mpp!=NULL; mpp++) {
- register __match *mp = *mpp;
- _do (mp->skel, mp, 1);
- }
-}
-
-
-_do(sp, winner, evalall)
- skeleton *sp; register __match *winner; int evalall;
-{
- register __match **mpp;
- register skeleton *skel = winner->skel;
- if(winner==NULL) {
- _nowin(sp);
- return;
- }
- if(winner->mode==xDEFER || (evalall && winner->mode!=xTOPDOWN))
- REORDER(winner->lleaves);
- mtSetNodes (skel->parent, skel->nson,
- skel->root=mtAction (winner->tree, winner->lleaves, sp));
-}
-
-skeleton *
-_walk(sp, ostate)
- register skeleton *sp;
- int ostate;
-{
- int state, nstate, nson;
- register __partial *pp;
- register __match *mp, *mp2;
- register skeleton *nsp, *lastchild = NULL;
- NODEPTR son, root;
-
- root = sp->root;
- nson = 1; sp->mincost = INFINITY;
- state = _machstep (ostate, root, mtValue(root));
-
- while((son = mtGetNodes(root, nson))!=NULL) {
- nstate = _machstep (state, NULL, MV_BRANCH(nson));
- nsp = _allocskel();
- nsp->root = son;
- nsp->parent = root;
- nsp->nson = nson;
- _walk(nsp, nstate);
- if(COSTLESS(nsp->mincost,INFINITY)) {
- assert (nsp->winner->mode==xREWRITE);
- _do(nsp, nsp->winner, 0);
- _freeskel(nsp);
- continue;
- }
- _merge (sp, nsp);
- if (lastchild==NULL) sp->leftchild = nsp;
- else lastchild->sibling = nsp;
- lastchild = nsp;
- nson++;
- }
-
- for (pp = sp->partial; pp < &sp->partial[sp->treecnt]; pp++)
- if (pp->bits&01==1) {
- mp = _allocmatch();
- mp->tree = pp->treeno;
- _addmatches (ostate, sp, mp);
- }
- if(son==NULL && nson==1)
- _closure (state, ostate, sp);
-
- sp->rightchild = lastchild;
- if (root==NULL) {
- COST c; __match *win; int i; nsp = sp->leftchild;
- c = INFINITY;
- win = NULL;
- for (i = 0; i < MAXLABELS; i++) {
- mp = nsp->succ[i];
- if (mp!=NULL && COSTLESS (mp->cost, c))
- { c = mp->cost; win = mp; }
- }
- _do (nsp, win, 0);
- }
- return(sp);
-}
-
-/*
- * Convert the start state which has a large branching factor into
- * a index table. This must be called before the matcher is used.
- */
-static short _nodetab[MAXNDVAL], _labeltab[MAXLABELS];
-_matchinit()
-{
- short *sp;
-/* Keutzer - this syntax doesn't work on UTS
- struct pair { short val, where } *pp;
-*/
- struct pair { short val; short where; } *pp;
- for (sp=_nodetab; sp < &_nodetab[MAXNDVAL]; sp++) *sp = HANG;
- for (sp=_labeltab; sp < &_labeltab[MAXLABELS]; sp++) *sp = HANG;
- sp = &mtTable[mtStart];
- assert (*sp==TABLE);
- for (pp = (struct pair *) ++sp; pp->val!=EOF; pp++) {
- if (MI_NODE(pp->val))
- _nodetab[M_DETAG(pp->val)] = pp->where;
- else if (MI_LABEL(pp->val))
- _labeltab[M_DETAG(pp->val)] = pp->where;
- }
-}
-
-int
-_machstep(state, root, input)
- short state, input;
- NODEPTR root;
-{
- register short *stp = &mtTable[state];
- int start = 0;
- if (state==HANG)
- return (input==(MV_BRANCH(1)) ? mtStart : HANG);
-rescan:
- if (stp==&mtTable[mtStart]) {
- if (MI_NODE(input)) return(_nodetab[M_DETAG(input)]);
- if (MI_LABEL(input)) return(_labeltab[M_DETAG(input)]);
- }
-
- for(;;) {
- if(*stp==ACCEPT) stp += 2;
-
- if(*stp==TABLE) {
- stp++;
- while(*stp!=EOT) {
- if(input==*stp) {
- return(*++stp);
- }
- stp += 2;
- }
- stp++;
- }
- if(*stp!=FAIL) {
- if (start) return (HANG);
- else { stp = &mtTable[mtStart]; start = 1; goto rescan;}
- } else {
- stp++;
- stp = &mtTable[*stp];
- goto rescan;
- }
- }
-}
-
-_addmatches(ostate, sp, np)
- int ostate;
- register skeleton *sp;
- register __match *np;
-{
- int label;
- int state;
- register __match *mp;
-
- label = mtMap[np->tree];
-
- /*
- * this is a very poor substitute for good design of the DFA.
- * What we need is a special case that allows any label to be accepted
- * by the start state but we don't want the start state to recognize
- * them after a failure.
- */
- state = _machstep(ostate, NULL, MV_LABEL(label));
- if (ostate!=mtStart && state==HANG) {
- _freematch(np);
- return;
- }
-
- np->lleaves = _getleaves (np, sp);
- np->skel = sp;
- if((np->mode = mtEvalCost(np, np->lleaves, sp))==xABORT)
- {
- _freematch(np);
- return;
- }
-
-/*
- if(np->mode==xREWRITE && COSTLESS(np->cost, sp->mincost)) {
- sp->mincost = np->cost;
- sp->winner = np;
- }
-*/
- if ((mp = sp->succ[label])!=NULL) {
- if (!COSTLESS (np->cost, mp->cost))
- { _freematch(np); return; }
- else _freematch(mp);
- }
- if(COSTLESS(np->cost,sp->mincost)) {
- if(np->mode==xREWRITE) {
- sp->mincost = np->cost; sp->winner = np; }
- else { sp->mincost = INFINITY; sp->winner = NULL; }
- }
- sp->succ[label] = np;
- _closure(state, ostate, sp);
-}
-
-_closure(state, ostate, skp)
- int state, ostate;
- skeleton *skp;
-{
- register struct ap { short tree, depth; } *ap;
- short *sp = &mtTable[state];
- register __match *mp;
-
- if(state==HANG || *sp!=ACCEPT) return(NULL);
-
- for(ap = (struct ap *) &mtAccept[*++sp]; ap->tree!=-1; ap++)
- if (ap->depth==0) {
- mp = _allocmatch();
- mp->tree = ap->tree;
- _addmatches (ostate, skp, mp);
- } else {
- register __partial *pp, *lim = &skp->partial[skp->treecnt];
- for(pp=skp->partial; pp < lim; pp++)
- if(pp->treeno==ap->tree)
- break;
- if(pp==lim) {
- skp->treecnt++;
- pp->treeno = ap->tree;
- pp->bits = (1<<(ap->depth));
- } else pp->bits |= (1<<(ap->depth));
- }
-}
-
-_merge (old, new)
- skeleton *old, *new;
-{
- register __partial *op = old->partial, *np = new->partial;
- int nson = new->nson;
- register __partial *lim = np + new->treecnt;
- if (nson==1) {
- old->treecnt = new->treecnt;
- for(; np < lim; op++, np++) {
- op->treeno = np->treeno;
- op->bits = np->bits/2;
- }
- } else {
- __partial *newer = _allocpartial();
- register __partial *newerp = newer;
- register int cnt;
- lim = op+old->treecnt;
- for(cnt=new->treecnt; cnt-- ; np++) {
- for(op = old->partial; op < lim; op++)
- if (op->treeno == np->treeno) {
- newerp->treeno = op->treeno;
- newerp++->bits = op->bits & (np->bits/2);
- break;
- }
- }
- _freepartial(old->partial);
- old->partial = newer;
- old->treecnt = newerp-newer;
- }
-}
-
-/* Save and Allocate Matches */
-#define BLKF 100
-__match *freep = NULL;
-static int _count = 0;
-static __match *_blockp = NULL;
-#ifdef CHECKMEM
-int x_matches, f_matches;
-#endif
-
-__match *
-_allocmatch()
-{
- __match *mp;
-
- if(freep!=NULL) {
- mp = freep;
- freep = ((__match *)((struct freeb *) freep)->next);
-#ifdef CHECKMEM
- f_matches--;
-#endif
- } else {
- if(_count==0) {
- _blockp = (__match *) malloc (BLKF*sizeof (__match));
- _count = BLKF;
-#ifdef CHECKMEM
- x_matches += BLKF;
-#endif
- }
- mp = _blockp++;
- _count--;
- }
- return(mp);
-}
-
-_freematch(mp)
- __match *mp;
-{
- ((struct freeb *) mp)->next = (struct freeb *) freep;
- freep = mp;
-#ifdef CHECKMEM
- f_matches++;
-#endif
-}
-
-static __partial *pfreep = NULL;
-static int pcount = 0;
-static __partial *pblock = NULL;
-#ifdef CHECKMEM
-static int x_partials, f_partials;
-#endif
-
-__partial *
-_allocpartial()
-{
- __partial *pp;
- if (pfreep!=NULL) {
- pp = pfreep;
- pfreep = *(__partial **) pp;
-#ifdef CHECKMEM
- f_partials--;
-#endif
- } else {
- if (pcount==0) {
- pblock=(__partial *)malloc(BLKF*MAXTREES*sizeof(__partial));
- pcount = BLKF;
-#ifdef CHECKMEM
- x_partials += BLKF;
-#endif
- }
- pp = pblock;
- pblock += MAXTREES;
- pcount--;
- }
- return(pp);
-}
-
-_freepartial(pp)
- __partial *pp;
-{
- * (__partial **)pp = pfreep;
- pfreep = pp;
-#ifdef CHECKMEM
- f_partials++;
-#endif
-}
-
-
-/* storage management */
-static skeleton *sfreep = NULL;
-static int scount = 0;
-static skeleton * sblock = NULL;
-
-skeleton *
-_allocskel()
-{
- skeleton *sp;
- int i;
- if(sfreep!=NULL) {
- sp = sfreep;
- sfreep = sp->sibling;
- } else {
- if(scount==0) {
- sblock = (skeleton *) malloc (BLKF * sizeof (skeleton));
- scount = BLKF;
- }
- sp = sblock++;
- scount--;
- }
- sp->sibling = NULL; sp->leftchild = NULL;
- for (i=0; i < MAXLABELS; sp->succ[i++] = NULL);
- sp->treecnt = 0;
- sp->partial = _allocpartial();
- return(sp);
-}
-
-_freeskel(sp)
- skeleton *sp;
-{
- int i;
- __match *mp;
- if(sp==NULL) return;
- _freeskel (sp->leftchild);
- _freeskel (sp->sibling);
- _freepartial (sp->partial);
- for (i=0; i < MAXLABELS; i++)
- if ((mp = sp->succ[i])!=NULL) _freematch (mp);
- sp->sibling = sfreep;
- sfreep = sp;
-}
-
-_match()
-{
- skeleton *sp;
- sp = _allocskel();
- sp->root = NULL;
- _mpbtop = _mpblock;
- _freeskel(_walk(sp, HANG));
-#ifdef CHECKMEM
- if(f_matches+_count!=x_matches) {
- printf(";#m %d %d %d\n", f_matches, _count, x_matches);
- assert(0);
- }
- if(f_partials+pcount!=x_partials) {
- printf(";#p %d %d %d\n", f_partials, pcount, x_partials);
- assert(0);
- }
-#endif
-}
-
-/* Keutzer 1/88- _mtG now uses varargs for portability to SUN4 etc.*/
-NODEPTR _mtG(va_alist)
-va_dcl
-{
- NODEPTR root;
- int i=0;
- va_list p_var;
- va_start(p_var);
- root = va_arg(p_var,NODEPTR);
- while( (i = va_arg(p_var,int)) != -1){
- root = mtGetNodes(root, i);
- }
- va_end(p_var);
- return(root);
-}
-
-/* diagnostic routines */
-#ifdef NOMARK
-markIfNoMatch(skp,mark)
- skeleton *skp;
- int mark;
-{}
-#else
-markIfNoMatch(skp,mark) skeleton *skp; int mark;
-{skeleton *child; int i; int found=0;
- for(i=0; i<MAXLABELS; i++)
- if (skp->succ[i]) found=1;
- if (!found) skp->root->mark=mark;
- for(child=skp->leftchild; child; child=child->sibling)
- markIfNoMatch(child,mark);
-}
-#endif
-
-_nowin(skp) skeleton *skp;
-{
- markIfNoMatch(skp,1);
- printf("# No match was found for the nodes printed in lowercase\n");
- printTree(skp->root);
- markIfNoMatch(skp,0);
-}
//GO.SYSIN DD walker.c1
echo y.tab.c 1>&2
sed 's/.//' >y.tab.c <<'//GO.SYSIN DD y.tab.c'
-# define ERROR 257
-
-# line 3 "twig.y"
-#include "common.h"
-#include "code.h"
-#include "sym.h"
-#define UNDEFINED -1
-#define GIVENUP -2
-
-int debug_flag = 0;
-int Dflag = 0;
-int tflag = 0;
-int line_xref_flag = 0;
-int ntrees = 0;
-int nerrors = 0;
-int fatalerrors = 0;
-int tree_lineno;
-FILE *outfile;
-FILE *symfile;
-Code *epilogue;
-
-SymbolEntry ErrorSymbol;
-
-# line 23 "twig.y"
-typedef union {
- Node *y_nodep;
- SymbolEntry *y_symp;
- Code *y_code;
- int y_int;
-} YYSTYPE;
-# define K_NODE 258
-# define K_LABEL 259
-# define K_PROLOGUE 260
-# define K_CONST 261
-# define K_INSERT 262
-# define K_COST 263
-# define K_ACTION 264
-# define ID 265
-# define NUMBER 266
-# define CBLOCK 267
-#define yyclearin yychar = -1
-#define yyerrok yyerrflag = 0
-extern int yychar;
-extern short yyerrflag;
-#ifndef YYMAXDEPTH
-#define YYMAXDEPTH 150
-#endif
-YYSTYPE yylval, yyval;
-# define YYERRCODE 256
-
-# line 255 "twig.y"
-
-
-extern char *process_suffix();
-
-set_arity(symp, arityp, count)
- SymbolEntry *symp;
- int *arityp;
- int count;
-{
- if(*arityp!=GIVENUP) {
- if (*arityp==UNDEFINED)
- *arityp = count;
- else if (*arityp!=count) {
- sem_error("inconsistent arity for %s", symp->name);
- *arityp = GIVENUP;
- }
- }
-}
-
-is_node(symp)
- SymbolEntry *symp;
-{ return(symp->attr==A_NODE); }
-
-is_label(symp)
- SymbolEntry *symp;
-{ return(symp->attr==A_LABEL); }
-
-CheckIsNodeOrPred (symp)
- SymbolEntry *symp;
-{
- if (symp->attr==A_ERROR)
- return;
- if (symp->attr!=A_NODE)
- sem_error ("non-node identifier %s", symp->name);
-}
-
-CheckIsUndefined(symp)
- SymbolEntry *symp;
-{
- if (symp->attr==A_ERROR)
- return(0);
- if (symp->attr!=A_UNDEFINED) {
- sem_error ("multiple declaration: %s", symp->name);
- return(0);
- } else return(1);
-}
-
-CheckIsDefined(symp)
- SymbolEntry *symp;
-{
- if (symp->attr==A_ERROR)
- return(0);
- if (symp->attr==A_UNDEFINED) {
- sem_error ("undefined identifier: %s", symp->name);
- symp->attr=A_ERROR;
- return(0);
- } else return(1);
-}
-
-
-
-/*VARARGS*/
-yyerror(fmt, s1, s2, s3)
- char *fmt, *s1, *s2, *s3;
-{
- fprintf(stderr, "line %d: ", yyline);
- fprintf(stderr, fmt, s1, s2, s3);
- if (token_buffer[0]!=0)
- fprintf(stderr, " at \"%s\"\n", token_buffer);
-}
-
-/*VARARGS*/
-yyerror2 (fmt, s1, s2, s3)
- char *fmt, *s1, *s2, *s3;
-{
- fprintf(stderr, "line %d: ", yyline);
- fprintf(stderr, fmt, s1, s2, s3);
- putchar('\n');
-}
-
-char *cmdnam;
-char *inFileName;
-char *outFileName;
-char prefixFile[100];
-static char usage[] = "usage: mt [-d] file";
-#define USAGE error(1, usage)
-char *prefix_base = PREFIX_BASE;
-char *suffix = "c1";
-
-main(argc, argv)
- int argc;
- char **argv;
-{
- int i;
- char *cp;
-
-#ifndef PREFIX_BASE
- error(1,"PREFIX_BASE has not been defined; recompile twig");
-#endif
-
- cmdnam = argv[0];
- argv++;
- inFileName = NULL;
-
- while(--argc > 0) {
- if (*argv[0]=='-')
- switch(argv[0][1]) {
- /* to see what each of these flags mean...
- * see common.h */
- case 'd': {
- char *cp;
- for(cp = &argv[0][2]; *cp!='\0'; cp++)
- switch(*cp) {
- case 'l': debug_flag |= DB_LEX; break;
- case 'm': debug_flag |= DB_MACH; break;
- case 's': debug_flag |= DB_SYM; break;
- case 't': debug_flag |= DB_TREE; break;
- case 'M': debug_flag |= DB_MEM; break;
- }
- }
- break;
- case 'D': Dflag++; break;
- case 't': tflag++; break;
- case 'w': suffix = process_suffix(&argv[0][2]); break;
- case 'l': prefix_base = &argv[0][2]; break;
- case 'x': line_xref_flag++; break;
- default:
- USAGE;
- }
- else inFileName = argv[0];
- argv++;
- }
- if(inFileName==NULL)
- USAGE;
-
- if(freopen(inFileName, "r", stdin)==NULL)
- error(1, "can't open %s", inFileName);
- if((cp=strrchr(inFileName, '.'))!=NULL && strcmp(cp,".mt")==0) {
- if ((outfile = fopen("walker.c" , "w"))==NULL)
- error(1, "can't write %s", outFileName);
- if ((symfile = fopen("symbols.h", "w"))==NULL)
- error(1, "can't write %s", outFileName);
- } else error(1, "input file must have suffix .mt");
-
- ErrorSymbol.attr = A_LABEL;
- TreeInit();
- SymbolInit();
- LexInit();
- yyparse();
-
- SymbolDump();
- if(nerrors == 0) {
- if(!tflag) {
- FILE *prefix;
- char c;
- sprintf(prefixFile, "%s.%s", prefix_base, suffix);
- prefix = fopen(prefixFile, "r");
- assert(prefix!=NULL);
- if(Dflag)
- fputs("#define DEBUG 1\n", outfile);
- if(line_xref_flag)
- fputs("#define LINE_XREF 1\n", outfile);
- fprintf(outfile,"# line 1 \"%s\"\n", prefixFile);
- while((c=getc(prefix))!=EOF) putc(c, outfile);
- }
- MachineGen();
- SymbolGenerateWalkerCode();
- CodeWrite(outfile, epilogue);
- CodeFreeBlock(epilogue);
- }
-
- /* cleanup */
- cleanup(0);
-}
-
-cleanup(retcode)
- int retcode;
-{
- lexCleanup();
- if(retcode==0) {
- SymbolFinish();
- }
- exit(retcode);
-}
-
-/*VARARGS*/
-error(rc, fmt, a1, a2, a3)
- int rc;
- char *fmt, *a1, *a2, *a3;
-{
- fprintf(stderr, "%s: ", cmdnam);
- fprintf(stderr, fmt, a1, a2, a3);
- putc ('\n', stderr);
- if(rc)
- exit (rc);
-}
-
-/*VARARGS*/
-sem_error (fmt, a1, a2, a3)
- char *fmt, *a1, *a2, *a3;
-{
- fprintf (stderr, "line %d: ", yyline);
- sem_error2(fmt, a1, a2, a3);
- nerrors++;
- fatalerrors++;
-}
-
-/*VARARGS*/
-sem_error2(fmt, a1, a2, a3)
- char *fmt, *a1, *a2, *a3;
-{
- fprintf (stderr, fmt, a1, a2, a3);
- putc('\n', stderr);
- nerrors++;
-}
-
-char *
-process_suffix(suf)
- char *suf;
-{
- extern int gen_table2;
- if(strcmp(suf,"exper")==0) {
- /* experimental walker */
- /* expect this to change alot */
- gen_table2++;
- }
- return(suf);
-}
-short yyexca[] ={
--1, 1,
- 0, -1,
- -2, 0,
--1, 10,
- 0, 1,
- -2, 0,
--1, 66,
- 40, 49,
- -2, 51,
- };
-# define YYNPROD 56
-# define YYLAST 261
-short yyact[]={
-
- 16, 71, 4, 6, 7, 5, 14, 8, 9, 17,
- 4, 6, 7, 5, 37, 8, 9, 29, 89, 79,
- 88, 78, 73, 72, 54, 36, 61, 59, 28, 50,
- 44, 40, 16, 92, 33, 31, 66, 27, 14, 25,
- 22, 17, 66, 32, 30, 93, 65, 70, 94, 85,
- 69, 53, 87, 76, 75, 64, 63, 62, 60, 58,
- 57, 39, 48, 38, 83, 82, 86, 49, 24, 21,
- 12, 20, 13, 3, 80, 10, 11, 2, 77, 84,
- 23, 35, 19, 34, 18, 15, 26, 90, 1, 45,
- 41, 0, 51, 0, 0, 0, 0, 0, 0, 0,
- 0, 74, 0, 0, 0, 0, 67, 0, 0, 0,
- 68, 0, 0, 0, 0, 0, 0, 81, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 91, 0, 0, 0, 0, 0, 0,
- 0, 96, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 56, 0, 0, 73, 72, 52, 46, 42, 0,
- 55, 0, 0, 0, 0, 25, 47, 43, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 95 };
-short yypact[]={
-
--248,-1000,-256,-1000,-225,-226,-228,-239,-221,-222,
--224,-1000,-1000,-1000,-242, 5, 2,-1000, -28, -29,
--1000,-1000, 27, -30,-1000, -10, -35,-1000, 1, 0,
--240, -1,-241, -2,-1000,-1000, -3, -4,-229,-1000,
--1000,-1000,-1000, 27,-1000,-1000,-1000, 27, -11, -41,
--1000,-1000,-1000,-243,-1000,-1000,-1000,-1000,-1000, -5,
--1000, -6,-1000,-1000,-1000,-246,-1000,-1000, -11,-243,
- 24, 23,-1000,-1000,-1000,-1000,-1000, -12,-1000,-1000,
- 26,-1000,-1000,-1000, -7,-247,-223,-1000,-1000,-1000,
- 4,-1000,-1000,-1000,-229,-1000,-1000 };
-short yypgo[]={
-
- 0, 88, 46, 87, 86, 85, 84, 71, 82, 69,
- 80, 68, 62, 47, 79, 78, 77, 75, 73, 72,
- 70, 74 };
-short yyr1[]={
-
- 0, 1, 16, 16, 18, 18, 18, 18, 18, 18,
- 18, 18, 18, 18, 4, 4, 4, 8, 8, 8,
- 6, 6, 6, 7, 9, 12, 12, 12, 10, 10,
- 10, 11, 13, 13, 17, 17, 17, 17, 20, 20,
- 19, 19, 14, 14, 14, 15, 15, 15, 5, 21,
- 2, 2, 3, 3, 3, 3 };
-short yyr2[]={
-
- 0, 2, 2, 1, 3, 3, 3, 3, 3, 4,
- 4, 3, 3, 3, 2, 1, 2, 2, 1, 2,
- 2, 1, 2, 2, 4, 3, 3, 0, 2, 1,
- 2, 3, 1, 1, 2, 2, 1, 1, 3, 3,
- 6, 2, 2, 2, 0, 1, 1, 0, 1, 0,
- 5, 1, 3, 1, 1, 2 };
-short yychk[]={
-
--1000, -1, -16, -18, 258, 261, 259, 260, 263, 264,
- -17, -18, -20, -19, 262, -5, 256, 265, -6, -8,
- -7, -9, 265, -10, -11, 265, -4, 265, 267, 256,
- 265, 256, 265, 256, -19, -20, 267, 256, 58, 59,
- 59, -7, 256, 265, 59, -9, 256, 265, -12, 40,
- 59, -11, 256, 61, 59, 265, 256, 59, 59, 267,
- 59, 267, 59, 59, 59, -2, 265, -12, -12, 61,
- -13, 42, 266, 265, -13, 59, 59, -15, 267, 265,
- -21, -13, 41, 41, -14, 61, 40, 59, 267, 265,
- -3, -2, 256, 41, 44, 256, -2 };
-short yydef[]={
-
- 0, -2, 0, 3, 0, 0, 0, 0, 0, 0,
- -2, 2, 36, 37, 0, 0, 0, 48, 0, 0,
- 21, 18, 27, 0, 29, 0, 0, 15, 0, 0,
- 0, 0, 0, 0, 34, 35, 0, 0, 0, 41,
- 4, 20, 22, 27, 5, 17, 19, 27, 23, 0,
- 6, 28, 30, 0, 7, 14, 16, 8, 11, 0,
- 13, 0, 12, 38, 39, 47, -2, 23, 0, 0,
- 0, 0, 32, 33, 31, 9, 10, 44, 45, 46,
- 0, 24, 25, 26, 0, 0, 0, 40, 42, 43,
- 0, 53, 54, 50, 0, 55, 52 };
-# ifdef YYDEBUG
-# include "y.debug"
-# endif
-
-# define YYFLAG -1000
-# define YYERROR goto yyerrlab
-# define YYACCEPT return(0)
-# define YYABORT return(1)
-
-/* parser for yacc output */
-
-#ifdef YYDEBUG
-int yydebug = 0; /* 1 for debugging */
-#endif
-YYSTYPE yyv[YYMAXDEPTH]; /* where the values are stored */
-int yychar = -1; /* current input token number */
-int yynerrs = 0; /* number of errors */
-short yyerrflag = 0; /* error recovery flag */
-
-yyparse()
-{ short yys[YYMAXDEPTH];
- int yyj, yym;
- register YYSTYPE *yypvt;
- register int yystate, yyn;
- register short *yyps;
- register YYSTYPE *yypv;
- register short *yyxi;
-
- yystate = 0;
- yychar = -1;
- yynerrs = 0;
- yyerrflag = 0;
- yyps= &yys[-1];
- yypv= &yyv[-1];
-
-yystack: /* put a state and value onto the stack */
-#ifdef YYDEBUG
- if(yydebug >= 3)
- if(yychar < 0 || yytoknames[yychar] == 0)
- printf("char %d in %s", yychar, yystates[yystate]);
- else
- printf("%s in %s", yytoknames[yychar], yystates[yystate]);
-#endif
- if( ++yyps >= &yys[YYMAXDEPTH] ) {
- yyerror( "yacc stack overflow" );
- return(1);
- }
- *yyps = yystate;
- ++yypv;
- *yypv = yyval;
-yynewstate:
- yyn = yypact[yystate];
- if(yyn <= YYFLAG) goto yydefault; /* simple state */
- if(yychar<0) {
- yychar = yylex();
-#ifdef YYDEBUG
- if(yydebug >= 2) {
- if(yychar <= 0)
- printf("lex EOF\n");
- else if(yytoknames[yychar])
- printf("lex %s\n", yytoknames[yychar]);
- else
- printf("lex (%c)\n", yychar);
- }
-#endif
- if(yychar < 0)
- yychar = 0;
- }
- if((yyn += yychar) < 0 || yyn >= YYLAST)
- goto yydefault;
- if( yychk[ yyn=yyact[ yyn ] ] == yychar ){ /* valid shift */
- yychar = -1;
- yyval = yylval;
- yystate = yyn;
- if( yyerrflag > 0 ) --yyerrflag;
- goto yystack;
- }
-yydefault:
- /* default state action */
- if( (yyn=yydef[yystate]) == -2 ) {
- if(yychar < 0) {
- yychar = yylex();
-#ifdef YYDEBUG
- if(yydebug >= 2)
- if(yychar < 0)
- printf("lex EOF\n");
- else
- printf("lex %s\n", yytoknames[yychar]);
-#endif
- if(yychar < 0)
- yychar = 0;
- }
- /* look through exception table */
- for(yyxi=yyexca; (*yyxi!= (-1)) || (yyxi[1]!=yystate);
- yyxi += 2 ) ; /* VOID */
- while( *(yyxi+=2) >= 0 ){
- if( *yyxi == yychar ) break;
- }
- if( (yyn = yyxi[1]) < 0 ) return(0); /* accept */
- }
- if( yyn == 0 ){ /* error */
- /* error ... attempt to resume parsing */
- switch( yyerrflag ){
- case 0: /* brand new error */
-#ifdef YYDEBUG
- yyerror("syntax error\n%s", yystates[yystate]);
- if(yytoknames[yychar])
- yyerror("saw %s\n", yytoknames[yychar]);
- else if(yychar >= ' ' && yychar < '\177')
- yyerror("saw `%c'\n", yychar);
- else if(yychar == 0)
- yyerror("saw EOF\n");
- else
- yyerror("saw char 0%o\n", yychar);
-#else
- yyerror( "syntax error" );
-#endif
-yyerrlab:
- ++yynerrs;
- case 1:
- case 2: /* incompletely recovered error ... try again */
- yyerrflag = 3;
- /* find a state where "error" is a legal shift action */
- while ( yyps >= yys ) {
- yyn = yypact[*yyps] + YYERRCODE;
- if( yyn>= 0 && yyn < YYLAST && yychk[yyact[yyn]] == YYERRCODE ){
- yystate = yyact[yyn]; /* simulate a shift of "error" */
- goto yystack;
- }
- yyn = yypact[*yyps];
- /* the current yyps has no shift onn "error", pop stack */
-#ifdef YYDEBUG
- if( yydebug ) printf( "error recovery pops state %d, uncovers %d\n", *yyps, yyps[-1] );
-#endif
- --yyps;
- --yypv;
- }
- /* there is no state on the stack with an error shift ... abort */
-yyabort:
- return(1);
- case 3: /* no shift yet; clobber input char */
-#ifdef YYDEBUG
- if( yydebug ) {
- printf("error recovery discards ");
- if(yytoknames[yychar])
- printf("%s\n", yytoknames[yychar]);
- else if(yychar >= ' ' && yychar < '\177')
- printf("`%c'\n", yychar);
- else if(yychar == 0)
- printf("EOF\n");
- else
- printf("char 0%o\n", yychar);
- }
-#endif
- if( yychar == 0 ) goto yyabort; /* don't discard EOF, quit */
- yychar = -1;
- goto yynewstate; /* try again in the same state */
- }
- }
- /* reduction by production yyn */
-#ifdef YYDEBUG
- if(yydebug) { char *s;
- printf("reduce %d in:\n\t", yyn);
- for(s = yystates[yystate]; *s; s++) {
- putchar(*s);
- if(*s == '\n' && *(s+1))
- putchar('\t');
- }
- }
-#endif
- yyps -= yyr2[yyn];
- yypvt = yypv;
- yypv -= yyr2[yyn];
- yyval = yypv[1];
- yym=yyn;
- /* consult goto table to find next state */
- yyn = yyr1[yyn];
- yyj = yypgo[yyn] + *yyps + 1;
- if( yyj>=YYLAST || yychk[ yystate = yyact[yyj] ] != -yyn ) yystate = yyact[yypgo[yyn]];
- switch(yym){
-
-case 1:
-# line 42 "twig.y"
-
- { if (nerrors==0) machine_build(); } break;
-case 4:
-# line 48 "twig.y"
- { SymbolEnterList (yypvt[-1].y_symp, A_NODE); } break;
-case 5:
-# line 51 "twig.y"
- {
- SymbolEnterList(yypvt[-1].y_symp, A_NODE);
- SymbolCheckNodeValues();
- } break;
-case 6:
-# line 56 "twig.y"
- { SymbolEnterList (yypvt[-1].y_symp, A_CONST); } break;
-case 7:
-# line 58 "twig.y"
- { SymbolEnterList (yypvt[-1].y_symp, A_LABEL); } break;
-case 8:
-# line 60 "twig.y"
- { CodeWrite(outfile, yypvt[-1].y_code); CodeFreeBlock(yypvt[-1].y_code); } break;
-case 9:
-# line 63 "twig.y"
- { yypvt[-2].y_symp->sd.ca.code = yypvt[-1].y_code; yypvt[-2].y_symp->sd.ca.assoc = NULL;
- SymbolEnter (yypvt[-2].y_symp, A_COST); } break;
-case 10:
-# line 67 "twig.y"
- { yypvt[-2].y_symp->sd.ca.code = yypvt[-1].y_code; yypvt[-2].y_symp->sd.ca.assoc = NULL;
- SymbolEnter (yypvt[-2].y_symp, A_ACTION); } break;
-case 14:
-# line 83 "twig.y"
- {
- if(CheckIsUndefined(yypvt[-0].y_symp)) {
- yypvt[-0].y_symp->next = yypvt[-1].y_symp;
- yyval.y_symp = yypvt[-0].y_symp;
- } else yyval.y_symp = yypvt[-1].y_symp;
- } break;
-case 15:
-# line 89 "twig.y"
-{ if(CheckIsUndefined(yypvt[-0].y_symp)) yyval.y_symp = yypvt[-0].y_symp; else yyval.y_symp = NULL; } break;
-case 17:
-# line 97 "twig.y"
- {
- if(yypvt[-0].y_symp->attr==A_ERROR)
- yyval.y_symp = yypvt[-1].y_symp;
- else { yypvt[-0].y_symp->next = yypvt[-1].y_symp; yyval.y_symp = yypvt[-0].y_symp; }
- } break;
-case 18:
-# line 102 "twig.y"
-{ yyval.y_symp = yypvt[-0].y_symp->attr==A_ERROR ? NULL : yypvt[-0].y_symp; } break;
-case 20:
-# line 106 "twig.y"
- {
- if(yypvt[-0].y_symp->attr==A_ERROR) yyval.y_symp = yypvt[-1].y_symp;
- else { yypvt[-0].y_symp->next = yypvt[-1].y_symp; yyval.y_symp = yypvt[-0].y_symp; }
- } break;
-case 21:
-# line 110 "twig.y"
-{ yyval.y_symp = yypvt[-0].y_symp->attr==A_ERROR ? NULL : yypvt[-0].y_symp; } break;
-case 23:
-# line 114 "twig.y"
- {
- if (CheckIsUndefined(yypvt[-1].y_symp)) {
- yypvt[-1].y_symp->sd.arity = yypvt[-0].y_int; yyval.y_symp = yypvt[-1].y_symp;
- } else yyval.y_symp = &ErrorSymbol;
- } break;
-case 24:
-# line 121 "twig.y"
-{
- if(CheckIsUndefined(yypvt[-3].y_symp)) {
- yypvt[-3].y_symp->unique = yypvt[-0].y_int; yypvt[-3].y_symp->sd.arity = yypvt[-2].y_int;
- yyval.y_symp = yypvt[-3].y_symp;
- } else yyval.y_symp = &ErrorSymbol;
- } break;
-case 25:
-# line 129 "twig.y"
- { yyval.y_int = yypvt[-1].y_int; } break;
-case 26:
-# line 130 "twig.y"
- { yyval.y_int=GIVENUP; } break;
-case 27:
-# line 131 "twig.y"
- { yyval.y_int = UNDEFINED; } break;
-case 28:
-# line 134 "twig.y"
- {
- if (yypvt[-0].y_symp->attr==A_ERROR) yyval.y_symp = yypvt[-1].y_symp;
- else { yypvt[-0].y_symp->next = yypvt[-1].y_symp; yyval.y_symp = yypvt[-0].y_symp; }
- } break;
-case 29:
-# line 138 "twig.y"
-{ yyval.y_symp = yypvt[-0].y_symp->attr==A_ERROR ? NULL : yypvt[-0].y_symp; } break;
-case 31:
-# line 142 "twig.y"
- {
- if(CheckIsUndefined(yypvt[-2].y_symp)) {
- yypvt[-2].y_symp->sd.cvalue = yypvt[-0].y_int; yyval.y_symp = yypvt[-2].y_symp;
- } else yyval.y_symp = &ErrorSymbol;
- } break;
-case 33:
-# line 150 "twig.y"
- {
- if(!CheckIsDefined(yypvt[-0].y_symp)) yyval.y_int = UNDEFINED;
- else if(yypvt[-0].y_symp->attr!=A_CONST) {
- sem_error("non-constant id used");
- yyval.y_int = -1;
- } else yyval.y_int = yypvt[-0].y_symp->sd.cvalue;
- } break;
-case 38:
-# line 164 "twig.y"
- { epilogue = CodeAppend(epilogue, yypvt[-1].y_code); } break;
-case 40:
-# line 169 "twig.y"
- {
- if (yypvt[-5].y_symp->attr==A_ERROR) {
- error(0, "\"label: tree\" pair ignored");
- TreeFree(yypvt[-3].y_nodep);
- } else {
- if(nerrors==0)
- cgotofn(SymbolEnterTreeIntoLabel(yypvt[-5].y_symp,
- yypvt[-3].y_nodep, yypvt[-2].y_symp, yypvt[-1].y_symp, tree_lineno));
- if(debug_flag&DB_TREE)
- TreePrint(yypvt[-3].y_nodep, 1);
- }
- } break;
-case 42:
-# line 183 "twig.y"
-{ SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
- sp->sd.ca.code = yypvt[-0].y_code; sp->sd.ca.assoc = NULL;
- SymbolEnter(sp, A_ACTION); yyval.y_symp = sp; } break;
-case 43:
-# line 186 "twig.y"
-{ if(CheckIsDefined(yypvt[-0].y_symp)) {
- if (yypvt[-0].y_symp->attr!=A_ACTION) {
- sem_error ("non action id: %s", yypvt[-0].y_symp->name);
- yyval.y_symp = &ErrorSymbol;
- } else yyval.y_symp = yypvt[-0].y_symp;
- } else yyval.y_symp = &ErrorSymbol; } break;
-case 44:
-# line 192 "twig.y"
-{ yyval.y_symp = NULL;} break;
-case 45:
-# line 194 "twig.y"
-{ SymbolEntry *sp = SymbolAllocate (SymbolGenUnique());
- sp->sd.ca.code = yypvt[-0].y_code; sp->sd.ca.assoc = NULL;
- SymbolEnter (sp, A_COST); yyval.y_symp = sp;
- } break;
-case 46:
-# line 198 "twig.y"
-{ if (CheckIsDefined(yypvt[-0].y_symp)) {
- if (yypvt[-0].y_symp->attr!=A_COST) {
- sem_error ("non cost id: %s", yypvt[-0].y_symp->name);
- yyval.y_symp = &ErrorSymbol;
- } else yyval.y_symp = yypvt[-0].y_symp;
- } else yyval.y_symp = &ErrorSymbol; } break;
-case 47:
-# line 204 "twig.y"
-{ yyval.y_symp = NULL; } break;
-case 48:
-# line 207 "twig.y"
- {
- tree_lineno = yyline; /* record line no */
- if(!CheckIsDefined(yypvt[-0].y_symp))
- yypvt[-0].y_symp->attr = A_ERROR;
- else if(!is_label(yypvt[-0].y_symp)) {
- sem_error("non label id: %s", yypvt[-0].y_symp->name);
- yypvt[-0].y_symp->attr = A_ERROR;
- }
- yyval.y_symp = yypvt[-0].y_symp;
- } break;
-case 49:
-# line 218 "twig.y"
-{CheckIsNodeOrPred(yypvt[-0].y_symp);} break;
-case 50:
-# line 219 "twig.y"
- {
- int count;
- Node *ap;
- /* check the arity of the node */
- for(count=0, ap = yypvt[-1].y_nodep; ap!=NULL; ap=ap->siblings) count++;
- switch(yypvt[-4].y_symp->attr) {
- case A_NODE:
- set_arity(yypvt[-4].y_symp, &yypvt[-4].y_symp->sd.arity, count);
- break;
- }
-
- yyval.y_nodep = TreeBuild (yypvt[-4].y_symp, yypvt[-1].y_nodep);
- } break;
-case 51:
-# line 233 "twig.y"
- {
- CheckIsDefined(yypvt[-0].y_symp);
- switch (yypvt[-0].y_symp->attr) {
- case A_NODE:
- set_arity(yypvt[-0].y_symp, &yypvt[-0].y_symp->sd.arity, 0);
- break;
- }
- yyval.y_nodep = TreeBuild (yypvt[-0].y_symp, NULL);
- } break;
-case 52:
-# line 243 "twig.y"
- {
- /*
- * build sibling list in reverse order TreeBuild will
- * put it right later.
- */
- yypvt[-0].y_nodep->siblings = yypvt[-2].y_nodep;
- yyval.y_nodep = yypvt[-0].y_nodep;
- } break;
-case 53:
-# line 251 "twig.y"
- { yypvt[-0].y_nodep->siblings = NULL; yyval.y_nodep = yypvt[-0].y_nodep; } break;
-case 54:
-# line 252 "twig.y"
-{ yyval.y_nodep = NULL; } break;
- }
- goto yystack; /* stack new state and value */
-}
//GO.SYSIN DD y.tab.c
echo y.tab.h 1>&2
sed 's/.//' >y.tab.h <<'//GO.SYSIN DD y.tab.h'
-# define ERROR 257
-
-typedef union {
- Node *y_nodep;
- SymbolEntry *y_symp;
- Code *y_code;
- int y_int;
-} YYSTYPE;
-extern YYSTYPE yylval;
-# define K_NODE 258
-# define K_LABEL 259
-# define K_PROLOGUE 260
-# define K_CONST 261
-# define K_INSERT 262
-# define K_COST 263
-# define K_ACTION 264
-# define ID 265
-# define NUMBER 266
-# define CBLOCK 267
//GO.SYSIN DD y.tab.h