lab3.c

c—语言的句法分析器。读入一个C--语言程序

/*
 * file: lab3.c
 *----------------------------------
 * this file implements the functions in lab3.h
 */

#include "lab3.h"
#include "lab3.tab.h"

/*
 * function: separator
 * usage: separator()
 * -------------------------
 * just print out a separator
 */

void separator(void)
{
    printf("===========================================================\n");
}

/*
 * function: hashpjw
 * usage: h = hashpjw(s, size)
 * ----------------------------
 * use 's' to hash
 * the size of hash table is 'size'
 */

unsigned hashpjw(char *s, int size)
{
    char *p;
    unsigned h = 0, g;

    for (p = s; *p != '\0'; p++) {
        h = (h << 4) + (*p);
        if (g = h & 0xf0000000) {
            h = h ^ (g >> 24);
            h = h ^ g;
        }
    }
    return (h % size);
}

/*
 * function: InsertID
 * usage: s = InsertID(name)
 * ----------------------------
 * insert identifier 'name' to id_hash_table
 */

char *InsertID(char *name)
{
    unsigned h = hashpjw(name, HASHTABLESIZE);
    struct id_entry *p = id_hash_table[h];

    while (p && strcmp(p->id, name) != 0) {
        p = p->next;
    }
    if (p) {
        return (p->id);
    }
    p = (struct id_entry *)malloc(sizeof(struct id_entry));
    if (0 == p) {
        printf("malloc for id: %s error\n", name);
        exit(1);
    }
    p->id = (char *)malloc(strlen(name) + 1);
    if (0 == p->id) {
        printf("malloc for id name: %s error\n", name);
        exit(1);
    }
    strcpy(p->id, name);
    p->next = id_hash_table[h];
    id_hash_table[h] = p;
    return (p->id);
}

/*
 * function: InsertFun
 * usage: s = InsertFun(name, returntype)
 * ----------------------------
 * insert function 'name' to funtable
 * the type of function's return value is 'returntype' 
 */

char *InsertFun(char *name, int returntype)
{
    unsigned h = hashpjw(name, FUNCTIONSIZE);
    struct fun *p = funtable[h];

    while (p && strcmp(p->funame, name) != 0) {
        p = p->next;
    }
    if (p) {
        return (0);
    }
    p = (struct fun *)malloc(sizeof(struct fun));
    if (0 == p) {
        printf("malloc for fun id: %s error\n", name);
        exit(1);
    }
    p->funame = name;
    p->retype = returntype;
    p->count = typecount;
    p->type = argtemp.temp;
    p->next = funtable[h];
    funtable[h] = p;
    if (debug) {
        separator();
        printf("insert function: %s in funtable[%u]\n", name, h);
        printf("argument:");
        for (returntype = 0; returntype < typecount; returntype++) {
            switch (p->type[returntype]) {
                case VOID:
                    printf(" void");
                    break;
                case INT:
                    printf(" int");
                    break;
                case CHAR:
                    printf(" char");
                    break;
                case VOID+100:
                    printf(" void*");
                    break;
                case INT+100:
                    printf(" int*");
                    break;
                case CHAR+100:
                    printf(" char*");
                    break;
                default:
                    printf(" %d",p->type[returntype]);
                    break;
            }

        }
        printf("\n");
        separator();
    }
    return (p->funame);
}

/*
 * function: LookUpFun
 * usage: type = LookUpFun(name)
 * ----------------------------
 * lookup function 'name'
 * check up the afferent arguments 
 * return the type value of function 'name' 
 */

int LookUpFun(char *name)
{
    unsigned h = hashpjw(name, FUNCTIONSIZE);
    struct fun *p;
    int i;

    if (debug) {
        separator();
        printf("lookup function: %s in funtable[%u] and check arguments\n", name, h);
        separator();
    }
    for (p  = funtable[h]; p; p = p->next) {
        if (p->funame == name) {
            if (typecheck < p->count) {
                printf("line %3d error: %s : too few actual parameters\n", lineno, name);
                right = 0;
            }
            for (i = 0; i < typecheck; i++) {
                if (p->type[i] == ELLIPSIS) {
                    break;
                }
                if (p->type[i] != arg_in.temp[i]) {
                    printf("line %3d error: %s : different types for formal and actual parameter %d\n", lineno, name, i+1);
                    right = 0;
                }
            }
            return (p->retype);
        }
    }
    return (0);
}

/*
 * function: MakeTable
 * usage: tp = MakeTable(previous, level)
 * ----------------------------
 * make a new table which previous table is 'previous'
 * its depth is 'level'
 * return the table' 
 */

struct table *MakeTable(struct table *previous, int level)
{
    int i;

    struct table *p = (struct table *)malloc(sizeof(struct table));
    if (0 == p) {
        printf("malloc for symbol table error\n");
        exit(1);
    }
    p->previous = previous;
    p->level = level;
    for (i = 0; i < BUCKETSIZE; i++) {
        p->buckets[i] = 0;
    }
    return (p);
}

/*
 * function: InsertSym
 * usage: sym = InsertSym(name, tp)
 * ----------------------------
 * insert the symbol 'name' to table 'tp'
 */

symbol *InsertSym(char *name, struct table *tp)
{
    unsigned h = hashpjw(name, BUCKETSIZE);
    struct table *qt = tp;
    struct sym_entry *p;

    if (debug) {
        separator();
        printf("qt->level=%d  level=%d insert_symbol_name=%s potential_symboltable[%d]\n", qt->level, level, name, tablelen-1);
    }
    if (qt->level < level) {
        if (debug) {
            printf("maketable symboltable[%d]\n",tablelen);
        }
        qt = MakeTable(tp, level);
        symboltable[tablelen] = qt;
        tablelen++;
    }
    if (debug) {
        printf("actually insert symboltable[%d]\n", tablelen-1);
        separator();
    }
    for (p = qt->buckets[h]; p; p = p->next) {
        if (0 == strcmp(p->sym.name, name)) {
            return (0);
        }
    }
    if (0 == (p = (struct sym_entry *)malloc(sizeof(struct sym_entry)))) {
        printf("malloc for symbol entry error\n");
        exit(1);
    }
    p->sym.name = name;
    p->sym.scope = level;
    p->sym.type = 0;
    p->next = qt->buckets[h];
    qt->buckets[h] = p;
    return (&p->sym);
}

/*
 * function: LookUp
 * usage: sym = LookUp(name, tp)
 * ----------------------------
 * find the symbol 'name' in table 'tp'
 */

symbol *LookUp(char *name, struct table *tp)
{
    struct sym_entry *p;
    unsigned h = hashpjw(name, BUCKETSIZE);
    int i = tablelen - 1;

    do {
        if (debug) {
            if (i == tablelen -1) {
                separator();
                printf("lookup id: %s in symboltable[%d] hash h=%u\n", name, i--, h);
            } else {
                printf("lookup id: %s in symboltable[%d]\n", name, i--);
            }
        }
        for (p = tp->buckets[h]; p; p= p->next) {
            if (debug) {
                printf("tp->buckets[%u]->sym.name=%s\n", h, p->sym.name);
            }
            if (name == p->sym.name) {
                if (debug) {
                    printf("I find it\n");
                    separator();
                }
                return (&p->sym);
            }
        }
    } while (tp = tp->previous);
    if (debug) {
        printf("not find\n");
        separator();
    }
    return (0);
}