C++|编译器|语义分析-符号表
Reference： Compilers in IPADS SE SJTU + Tiger book
通过词法分析和语法分析，我们可以将程序转换为一棵抽象语法树，根节点为statement，并递归子节点为statement或者expression，叶节点为terminal（如'A'）。然而，我们并不仅仅需要语法本身，同时要考虑语法的实际含义。编译器进入语义分析阶段。
语义分析- 将变量的定义与各个使用联系起来，type check，并且将抽象语法转换为更简单的适合生成机器代码表示。
符号表
符号表是由一组绑定组成的集合（又称环境environment），例如{g->string,a->int},每一个绑定都具有一定的作用域。新增的绑定会覆盖先前的绑定。（这个很容易实现，只要你新增的绑定先于旧的被找到就行）
为了实现符号表的改变，存在两种风格
函数式风格- 在每次符号表改变时，并不改变原符号表，保持数据unmutable。
命令式风格- 共用一个environment，符号表改变会破坏性更新原符号表，但是提供给一个撤销栈（存储撤销破坏性更新的信息). 环境中添加符号时，同时也会加入撤销栈中，在作用域结束点，撤销栈弹出符号并且删除绑定，恢复到之前的符号表。
在某些语言中，可以同时存在多个活跃的环境，module/class/record各自拥有自己的符号表
命令式风格符号表实现
需求1：查找迅速- hash
需求2: 易撤销
open hashing： 拉链法（我们选择链表，容易实现作用域的删除）
closed hashing： 开放寻址法（数组中你玩delete不是在作死么, 舍弃）
新增的binding加入链表头，如果要撤销，删除第一个binding就行。
HINT
void pop(string key)
{
int index = hash(key) % SIZE ;
table[index] = table[index]->next;
}我们可能会奇怪，上面的代码为什么直接删除index处的首节点而不是第一个找到的key节点。难道不会出现我pop（"a"）而实际上pop了一个key为“c”的节点么。 因为有了撤销栈作为辅助，我们在撤销时，pop的key必定是该索引处最后加入的key，因此首节点也就是第一个找到的key节点。
函数式风格符号表实现
原先的表不变，新增的部分链接到之前的表的首节点（避免拷贝之前的表的开销）
由于所有数据都是unmutable的，可以放心地进行引用
我们还可以使用二分查找树加速查找，这样的话，如果新增的binding深度为d，那么我们需要复制向上的d个节点，但不需要复制整棵树（logn），插入和查找开销相同。
在新表中插入Mouse的binding
撤销栈
除了hash自带的链表之外，另外存在着一个链表top处理作用域。下文binder_的prevtop就是按照插入顺序对于所有节点进行了链接。沿着prevtop遍历我们可以得到FILO的撤销栈。
struct binder_ {
void *key; void *value; /* a binding */
void *prevtop; /* to implement a stack */
binder next; /* imperative style */
};
struct TAB_table_ {
binder table[TABSIZE];
void *top;
};在TAB表中我们通过top指针可以获取撤销栈的栈顶。我们用ADT S_table进行一些接口的封装。
当新的作用域开始时，不会插入binder，而是插入一个特殊的marker哨兵。
当作用域结束时，沿着top不断进行pop，直到pop最顶端的哨兵。这样一来整个作用域中新增的符号就全部被撤销了。
void S_enter(S_table t, S_symbol sym, void* value) {
TAB_enter(t, sym, value);
}
void S_beginScope(S_table t) {
S_enter(t, &marksym, NULL);
}
void S_endScope(S_table t) {
S_symbl s;
do s=TAB_pop(t); while (s != &marksym);
}type environment//value environment
在程序中，绑定的不仅是类型，还有值。因此作用域中同时存在两个S_table。类型中通过使用<field,type*>指针，可以实现嵌套的类型，例如结构体和类。
需要注意的是，在程序中写的type本身就是symbol，而不是实际的type，因此我们需要在venv中先获取typename（如果一个变量的类型是type，例如typedef？），再根据typename在t_env获取对应的实际的type。（这段有点不太清晰，得复习下）
base environment
初始化built-in环境