![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sym.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / twig|
Return to sym.c CVS log | Up to [Research Unix] / researchv10no / cmd / twig |
1.1 root 1: /*
2: * Symbol manipulation routines
3: */
4: #include "common.h"
5: #include "code.h"
6: #include "sym.h"
7: #include "machine.h"
8: #include "y.tab.h"
9: #include "mem.h"
10:
11: #define SAFE 1 /* generates code to do redundant checks */
12: #define MAXSYMS 100
13: #define MAX_UNIQUE 255
14:
15: static void AppendToList();
16: typedef
17: struct SymbolList {
18: SymbolEntry *first, *last;
19: int count;
20: }
21: SymbolList;
22:
23: /*
24: * The range of the unique numbers assigned to each type of
25: * symbol is [min,max)
26: */
27: struct ranges {
28: int min,max;
29: int limit;
30: } uniques[] = {
31: {0, 0, MAX_UNIQUE}, /* A_UNDEFINED -- not used */
32: {0, 0, MAX_NODE_VALUE}, /* A_NODE */
33: {0, 0, MAX_UNIQUE}, /* A_LABEL */
34: {0, 0, MAX_UNIQUE}, /* A_COST */
35: {0, 0, MAX_UNIQUE}, /* A_ACTION */
36: };
37:
38: int treeIndex = 0;
39:
40: static SymbolList lists[] = {
41: { NULL, NULL, 0}, /* A_UNDEFINED -- never used */
42: { NULL, NULL, 0}, /* A_NODE */
43: { NULL, NULL, 0}, /* A_LABEL */
44: { NULL, NULL, 0}, /* A_COST */
45: { NULL, NULL, 0}, /* A_ACTION */
46: { NULL, NULL, 0}, /* A_CONST */
47: };
48:
49: struct _mem sym_mem, lab_mem, tree_mem;
50: SymbolEntry *hash_table[HASHSIZE];
51: SymbolEntry *startSymbol;
52:
53: static int
54: RawHash(s)
55: register char *s;
56: {
57: register int sum = 0;
58: register int i = 0;
59: while(*s)
60: sum += (++i)*(0377&*s++);
61: return(sum);
62: }
63:
64:
65: /*
66: * Allocate a new symbol_entry structure for the given structure and
67: * return it. There is no check of whether the symbol is already defined or
68: * not. The caller is expected to fill in the uninitialized fields.
69: */
70: SymbolEntry *
71: SymbolAllocate(s)
72: char *s;
73: {
74: SymbolEntry *sp;
75: sp = (SymbolEntry *) mem_get(&sym_mem);
76: assert(sp!=NULL);
77:
78: #ifdef SAFE
79: assert (SymbolLookup(s) == NULL);
80: #endif
81:
82: sp->name = malloc(strlen(s)+1);
83: assert(sp->name!=NULL);
84: strcpy (sp->name, s);
85: sp->hash = RawHash(s);
86: sp->next = NULL;
87: sp->attr = A_UNDEFINED;
88: sp->unique = -1;
89: return(sp);
90: }
91:
92: void
93: SymbolFree (symp)
94: SymbolEntry *symp;
95: {
96: assert (symp->next == NULL);
97: free(symp);
98: }
99:
100: SymbolEntry *
101: SymbolLookup(s)
102: char *s;
103: {
104: int hash_value = RawHash(s);
105: register SymbolEntry * hp = hash_table[hash_value%HASHSIZE];
106:
107: while(hp!=NULL) {
108: if(hp->hash == hash_value &&
109: strcmp (s, hp->name)==0) break;
110: hp = hp->next;
111: }
112: return(hp);
113: }
114:
115: /*
116: * enter the symbol into the symbol table. It believes everything in the
117: * symp argument.
118: */
119: void
120: SymbolEnter (symp, attr)
121: SymbolEntry *symp;
122: byte attr;
123: {
124: struct symbol_entry *hp;
125:
126: #ifdef SAFE
127: assert (symp!=NULL);
128: assert (symp->hash == RawHash(symp->name));
129: assert (symp->attr == A_UNDEFINED);
130: #endif
131:
132: hp = hash_table[symp->hash%HASHSIZE];
133: symp->next = hp;
134: hash_table[symp->hash%HASHSIZE] = symp;
135: symp->attr = attr;
136: if (HAS_UNIQUE(attr)){
137: struct ranges *rp = &uniques[attr];
138: int new_unique;
139: if(symp->unique==-1)
140: symp->unique = new_unique = rp->max++;
141: else {
142: new_unique = symp->unique;
143: if(new_unique>=rp->max)
144: rp->max = new_unique+1;
145: else if(new_unique < rp->min)
146: rp->min = new_unique;
147: }
148: if(new_unique>rp->limit)
149: sem_error("number assigned to %s (%d) out of range",
150: symp->name, new_unique);
151: if(new_unique<0)
152: sem_error("number assigned to %s (%d) is negative",
153: symp->name, new_unique);
154: assert(rp->max>=rp->min);
155: }
156: if (HAS_LIST(attr)) {
157: AppendToList(&lists[attr], symp);
158: }
159: }
160:
161: static void
162: AppendToList(list, sp)
163: SymbolList *list;
164: SymbolEntry *sp;
165: {
166: sp->link = NULL;
167: if(list->first==NULL)
168: list->first = sp;
169: else (list->last)->link = sp;
170: list->last = sp;
171: list->count++;
172: }
173:
174: SymbolCheckNodeValues()
175: {
176: SymbolList *slist;
177: SymbolEntry **stab, **spp, *sp;
178: struct ranges *rp;
179: int i, range;
180:
181: rp = &uniques[A_NODE];
182: slist = &lists[A_NODE];
183: range = rp->max - rp->min + 1;
184: stab = (SymbolEntry **) malloc(range*sizeof(SymbolEntry *));
185:
186: for(i=range, spp = stab; i-->0; spp++) *spp = NULL;
187:
188: for(sp = slist->first; sp; sp = sp->link) {
189: SymbolEntry *sp2 = stab[sp->unique];
190: if(sp2==NULL)
191: stab[sp->unique] = sp;
192: else
193: sem_error("%s and %s have the same node value",
194: sp2->name, sp->name);
195: }
196: free(stab);
197: }
198:
199: SymbolEntry *
200: SymbolEnterKeyword(s, value)
201: char *s;
202: int value;
203: {
204: SymbolEntry *sp = SymbolAllocate(s);
205: sp->sd.keyword = value;
206: SymbolEnter (sp, A_KEYWORD);
207: return(sp);
208: }
209:
210: void
211: SymbolInit()
212: {
213: SymbolEntry *sp;
214:
215: mem_init(&sym_mem,sizeof(SymbolEntry));
216: mem_init(&lab_mem,sizeof(LabelData));
217: mem_init(&tree_mem,sizeof(struct treeassoc));
218: SymbolEnterKeyword ("node", K_NODE);
219: SymbolEnterKeyword ("label", K_LABEL);
220: SymbolEnterKeyword ("prologue", K_PROLOGUE);
221: SymbolEnterKeyword ("const", K_CONST);
222: SymbolEnterKeyword ("insert", K_INSERT);
223: SymbolEnterKeyword ("cost", K_COST);
224: SymbolEnterKeyword ("action", K_ACTION);
225: }
226:
227: void
228: SymbolMap(f)
229: int (*f)();
230: {
231: SymbolEntry **spp, *sp;
232: for(spp = hash_table; spp < &hash_table[HASHSIZE]; spp++)
233: for(sp= *spp; sp!=NULL; sp = sp->next)
234: f(sp);
235: };
236:
237: static int symcnt, labcnt, nodecnt;
238: static
239: sym_count(sp)
240: SymbolEntry *sp;
241: {
242: symcnt++;
243: switch(sp->attr) {
244: case A_LABEL: {
245: LabelData *lp;
246: for(lp = sp->sd.lp;lp!=NULL;lp=lp->next) {
247: labcnt++;
248: nodecnt += cntnodes(lp->tree);
249: }
250: } break;
251: }
252: }
253:
254: void
255: SymbolFinish()
256: {
257: if(DB_MEM&debug_flag) {
258: extern struct _mem node_mem;
259: int symout = mem_outstanding(&sym_mem);
260: int labout = mem_outstanding(&lab_mem);
261: int nodeout = mem_outstanding(&node_mem);
262: SymbolMap(sym_count);
263: fprintf(stderr,"symbols defined=%d out=%d\n",symcnt, symout);
264: fprintf(stderr,"labdata def=%d out=%d\n",labcnt,labout);
265: fprintf(stderr,"node def=%d out=%d\n",nodecnt,nodeout);
266: assert(symcnt==symout);
267: assert(labcnt==labout);
268: assert(nodecnt==nodeout);
269: }
270: }
271:
272: void
273: SymbolEnterList (symp, attr)
274: SymbolEntry *symp;
275: int attr;
276: {
277: /*
278: * enter in reverse order because the list was built in reverse
279: * order by the parser
280: */
281:
282: if(symp==NULL)
283: return;
284: SymbolEnterList(symp->next, attr);
285: if(symp->attr!=A_UNDEFINED)
286: sem_error ("multiple declaration ignored: %s", symp->name);
287: SymbolEnter (symp, attr);
288: }
289:
290: LabelData *
291: SymbolEnterTreeIntoLabel(symp, tree, costfunc, action, lineno)
292: SymbolEntry *symp, *action, *costfunc;
293: struct node *tree;
294: int lineno;
295: {
296: LabelData *tp = (LabelData *) mem_get(&lab_mem);
297: struct treeassoc *ap;
298:
299: if (symp==&ErrorSymbol) return(NULL);
300: #ifdef SAFE
301: assert (tp!=NULL);
302: assert (symp->attr==A_LABEL);
303: #endif
304:
305: tp->tree = tree;
306: tp->treeIndex = treeIndex++;
307: tp->lineno = lineno;
308: tp->next = symp->sd.lp;
309: tp->label = symp;
310: symp->sd.lp = tp;
311:
312: if (action!=NULL) {
313: ap = (struct treeassoc *) mem_get(&tree_mem);
314: ap->tree = tp->treeIndex;
315: ap->next = action->sd.ca.assoc;
316: action->sd.ca.assoc = ap;
317: }
318:
319: if (costfunc!=NULL) {
320: ap = (struct treeassoc *) mem_get(&tree_mem);
321: ap->tree = tp->treeIndex;
322: ap->next = costfunc->sd.ca.assoc;
323: costfunc->sd.ca.assoc = ap;
324: }
325: return(tp);
326: }
327:
328: static void
329: WriteSymbols(sp, mask)
330: SymbolEntry *sp;
331: int mask;
332: {
333: for(;sp!=NULL; sp = sp->link)
334: fprintf(symfile, "#define %s\t0%o\n", sp->name, sp->unique|mask);
335: }
336:
337: void
338: SymbolDump()
339: {
340: WriteSymbols(lists[A_NODE].first, M_NODE);
341: WriteSymbols(lists[A_LABEL].first, 0);
342: WriteSymbols(lists[A_CONST].first, 0);
343: fprintf(symfile, "#define MAXLABELS %d\n", uniques[A_LABEL].max);
344: fprintf(symfile, "#define MAXTREES %d\n", treeIndex);
345: fprintf(symfile, "#define MAXNDVAL %d\n", uniques[A_NODE].max);
346: }
347:
348: void
349: SymbolGenerateWalkerCode()
350: {
351: register SymbolEntry *pp;
352: int i;
353: extern int line_xref_flag;
354: struct treeassoc *tap;
355: register LabelData *lp;
356: register short int *mapTab;
357:
358: /*
359: * Write out the table of tree index to label correspondence
360: */
361: mapTab = (short int *) malloc (treeIndex * sizeof(short int));
362: for(pp=lists[A_LABEL].first; pp!=NULL; pp=pp->link) {
363: lp = pp->sd.lp;
364: if(lp==NULL)
365: sem_error2("%s undefined\n", pp->name);
366: for(;lp!=NULL;lp=lp->next)
367: mapTab[lp->treeIndex] = pp->unique;
368: }
369: fputs("short int mtMap[] = {\n", outfile);
370: for(i=0, oreset(); i < treeIndex;)
371: oputoct(mapTab[i++]);
372: fputs("};\n", outfile);
373:
374: /* generate tree to line index table */
375: if(line_xref_flag) {
376: for(pp=lists[A_LABEL].first; pp!=NULL; pp=pp->link) {
377: lp = pp->sd.lp;
378: for(;lp!=NULL;lp=lp->next)
379: mapTab[lp->treeIndex] = lp->lineno;
380: }
381: fputs("short int mtLine[] = {\n", outfile);
382: for(i=0, oreset(); i<treeIndex;)
383: oputint(mapTab[i++]);
384: fputs("};\n", outfile);
385: }
386: /*
387: * Generate path table
388: */
389: fputs ("short int mtPaths[] = {\n", outfile);
390: for(pp=lists[A_LABEL].first, oreset(); pp!=NULL; pp=pp->link) {
391: lp = pp->sd.lp;
392: if(lp==NULL)
393: sem_error2("%s undefined\n", pp->name);
394: do {
395: mapTab[lp->treeIndex] = ointcnt();
396: oputint (lp->tree->nlleaves);
397: SymbolWritePath (lp->tree);
398: oputint (eSTOP);
399: lp = lp->next;
400: } while (lp!=NULL);
401: }
402: fputs(" };\nshort int mtPathStart[] = {\n", outfile);
403: for(i=0, oreset(); i < treeIndex;)
404: oputint (mapTab[i++]);
405: fputs("};\n", outfile);
406:
407: /*
408: * Code to perform the action of the trees
409: */
410: fputs("NODEPTR\nmtAction (_t, _ll, _s)\n", outfile);
411: fputs("int _t; __match **_ll; skeleton *_s;\n", outfile);
412: fputs("{ NODEPTR root = _s->root;\n", outfile);
413: fputs("switch (_t) {\n", outfile);
414: for (pp=lists[A_ACTION].first; pp!=NULL; pp=pp->link) {
415: if ((tap=pp->sd.ca.assoc)==NULL) {
416: sem_error2 ("%s not used", pp->name);
417: continue;
418: }
419: for (; tap!=NULL; tap=tap->next)
420: fprintf (outfile, "case %d:", tap->tree);
421: fputs ("{\n", outfile);
422: CodeWrite (outfile, pp->sd.ca.code);
423: fputs("} break;\n", outfile);
424: }
425: fputs("} return(_s->root);}\n", outfile);
426:
427: fputs ("mtEvalCost(_m, _ll, _s)\n", outfile);
428: fputs ("__match **_ll; __match *_m; skeleton *_s;\n", outfile);
429: fputs ("{ NODEPTR root = _s->root;\n", outfile);
430: fputs ("COST cost; cost = DEFAULT_COST;\n", outfile);
431: fputs ("switch(_m->tree) {\n", outfile);
432: for(pp=lists[A_COST].first; pp!=NULL; pp=pp->link) {
433: if ((tap=pp->sd.ca.assoc)==NULL) {
434: sem_error2 ("%s not used", pp->name);
435: continue;
436: }
437: for (; tap!=NULL; tap=tap->next)
438: fprintf (outfile, "case %d:", tap->tree);
439: fputs ("{\n", outfile);
440: CodeWrite (outfile, pp->sd.ca.code);
441: fputs ("} break;\n", outfile);
442: }
443: fputs("}\n", outfile);
444: fputs("_m->cost = cost; return(xDEFER);}\n", outfile);
445:
446: }
447:
448: SymbolWritePath (root)
449: Node *root;
450: {
451: Node *np;
452: if(root->nlleaves==0)
453: return;
454: if((root->sym)->attr==A_LABEL) {
455: oputint (eEVAL); oputoct (MV_LABEL((root->sym)->unique));
456: return;
457: }
458: oputint (ePUSH);
459: for(np = root->children;;) {
460: if(np->nlleaves > 0)
461: SymbolWritePath (np);
462: if ((np = np->siblings) == NULL)
463: break;
464: oputint (eNEXT);
465: }
466: oputint (ePOP);
467: return;
468: }
469:
470: static int gensymndx = 0;
471:
472: char *
473: SymbolGenUnique()
474: {
475: static char name[7];
476: name[0] = '$';
477: sprintf (&name[1], "%05d", gensymndx++);
478: return (name);
479: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.