Semantic Analysis⚓︎

typedef struct S_symbol_ *S_symbol;
S_symbol S_symbol (string);     // string -> symbol
string S_name(S_symbol);        // symbol -> string

typedef struct TAB_table_ *S_table;
S_table S_empty(void);     // create an empty symbol table
void S_enter(S_table t, S_symbol sym, void *value);  // enter binding
void *S_look(S_table t, S_symbol sym);  // look up symbol
void S_beginScope(S_table t);  // remember current table state
void S_endScope(S_table t);  // restore to most recent beginScope 
                             // that is not closed yet

static S_symbol mksymbol (string name , S_symbol next) {
    S_symbol s = checked_malloc(sizeof(*s));
    s->name = name; s->next = next;
    return s;
}

S_symbol S_symbol (string name) {
        int index = hash(name) % SIZE;
        S_symbol syms = hashtable[index].sym;
        for (sym = syms; sym; sym = sym->next)
            if (0 == strcmp(sym->name, name)) return sym;
        sym = mksymbol(name, syms);
        hashtable[index] = sym;
    return sym;
}

string S_name (S_symbol sym) {
    return sym->name;
}

// make a new S_Table
S_table S_empty(void) {
    return TAB_empty(); 
}

// insert a binding
void S_enter(S_table t, S_symbol sym, void *value){ 
    TAB_enter(t,sym,value);
} 

// look up a symbol
void *S_look(S_table t, S_symbol sym) { 
    return TAB_look(t,sym); 
}

static struct S_symbol_ marksym = { “<mark>”, 0 };

void S_beginScope(S_table t) { 
    S_enter(t, &marksym, NULL); 
}

void S_endScope(S_table t) {
    S_symbol s;
    do 
        s = TAB_pop(t); 
    while (s != &marksym);
}

struct TAB_table_ {
    binder table[TABSIZE];
    void *top;
};

static binder Binder(void *key, void *value, binder next, void *prevtop) {
    binder b = checked_malloc(sizeof(*b));
    b->key = key; b->value = value; b->next = next; 
    b->prevtop = prevtop; 
    return b;
}

typedef struct Ty_ty_ *Ty_ty;
struct Ty_ty_ {
    enum {Ty_record, Ty_nil, Ty_int, Ty_string,
            Ty_array, Ty_name, Ty_void} kind;
    union {
        Ty_fieldList record;
        Ty_ty array;
        struct {S_symbol sym; Ty_ty ty;} name;
    } u;
};
``` -->


### Environments

由于有两个独立的命名空间，即两种从符号到绑定的映射环境（类型环境/值环境），那么如何区分哪个 a 是类型，哪个 a 是变量？答案是基于语法上下文。类型环境和值环境中的绑定分别为：

- 类型环境：`symbol` -> `Ty_ty`
- 值环境：
    - 变量：`symbol` -> `Ty_ty`
    - 函数：`symbol` -> `struct { Ty_tyList formals, Ty_ty result; }`

```c hl_lines="5-6 10-11"
typedef struct E_enventry_ *E_enventry;
struct E_enventry_ {
    enum {E_varEntry, E_funEntry} kind;
    union {
        struct {Ty_ty ty;} var;
        struct {Ty_tyList formals; Ty_ty result;} fun;
    } u;
};

E_enventry E_VarEntry(Ty_ty ty); 
E_enventry E_FunEntry(Ty_tyList formals, Ty_ty result);

S_table E_base_tenv(void);   // Ty_ty environment
S_table E_base_venv(void);   // E_enventry environment

Struct expty transVar(S_table venv, S_table tenv, A_var v);
Struct expty transExp(S_table venv, S_table tenv, A_exp a);
Void transDec(S_table venv, S_table tenv, A_dec d);
Ty_ty transTY(S_table tenv, A_ty a);

struct expty transExp(S_table venv, S_table tenv, A_exp a) {
    switch(a->kind) {
    ...
    case A_opExp: {
        A_oper oper = a->u.op.oper;
        struct expty left =transExp(venv, tenv, a->u.op.left);
        struct expty right=transExp(venv, tenv, a->u.op.right); 
        if (oper == A_plusOp) {
        if (left.ty->kind != Ty_int)
            EM_error(a->u.op.left->pos, "integer required");
        if (right.ty->kind != Ty_int)
            EM_error(a->u.op.right->pos,"integer required");
        return expTy(NULL, Ty_Int()); 
        }...
    }
    } 
    assert(0); /* should have returned from some clause of the switch */
}

struct expty transVar(S_table venv, S_table tenv, A_var v) {
    switch (v->kind) {
        case A_simpleVar: {
            E_enventry x = S_look(venv, v->u.simple);
            if (x && x->kind == E_varEntry)   // v is a defined var in value env
            return expTy(NULL, actual_ty(x->u.var.ty));   // skip placeholders
            else {
                EM_error(v->pos, “undefined variable %s”, S_name(v->u.simple));
                return expTy(NULL, Ty_Int());
            }
        }
        case A_fieldVar:
            ...
    }
}

struct expty transExp (S_table venv, S_table tenv, A_exp a) {
    switch(a->kind) {
        ...
        case A_letExp: {
            struct expty exp; 
            A_decList d; 
            S_beginScope(venv); S_beginScope(tenv);
            for (d = a->u.let.decs; d; d = d->tail)
                transDec(venv, tenv,d->head);
            exp = transExp(venv, tenv, a->u.let.body); 
            S_endScope(tenv); S_endScope(venv); 
            return exp;
        }
    } ...
}

void transDec(S_table venv, S_table tenv, A_dec d) {
    switch(d->kind) { 
        case A_varDec: { 
            struct expty e = transExp(venv, tenv, d->u.var.init);
            S_enter(venv, d->u.var.var, E_VarEntry(e.ty));
            // the type of x inherits from that of exp
        }
        ...
    }
    ...
}

void transDec(S_table venv, S_table tenv, A_dec d) { 
    ...
    case A_typeDec: { 
        S_enter
        (tenv, d->u.type->head->name, transTy(d->u.type->head->ty)); 
    }
    ...
}

void transDec(S_table venv, S_table tenv, A_dec d) { 
    switch(d->kind) {
        ...
        case A_functionDec: {
            A_fundec f = d->u.function->head;
            Ty_ty resultTy = S_look(tenv, f->result); 
            Ty_tyList formalTys = makeFormalTyList(tenv, f->params); 
            S_enter(venv, f->name, E_FunEntry(formalTys,resultTy));
            S_beginScope(venv); 
            {A_fieldList l; Ty_tyList t;
            for(l = f->params, t = formalTys; l; l = l->tail, t = t->tail)
                S_enter(venv, l->head->name, E_VarEntry(t->head));
            } 
            transExp(venv, tenv, d->u.function->body); 
            S_endScope(venv); 
            break; 
        } 
        ...
    }
}