Return to sym.c CVS log

Up to [Research Unix] / researchv10no / cmd / twig

Annotation of researchv10no/cmd/twig/sym.c, revision 1.1

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.