# 语义分析

绑定，类型检查

# symbol table

Imperative style: 命令式风格
- Modify $\sigma_1$ until it becomes $\sigma_2$ .
- While $\sigma_2$ exists, we cannot look things up in $\sigma_1$ .
- When done with $\sigma_2$ , can undo the modification to get $\sigma_1$ back again.

方法：

Hashing
插入：找到哈希值然后插入链表的表头
查找：找到哈希值然后遍历链表
pop: 找到哈希值然后把链表表头删掉 table [hash (key)] = table [hash (key)].next

Functional style: 函数式风格
- To keep $\sigma_1$ in pristine condition while creating create $\sigma_2$ and $\sigma_3$

方法：

如果依旧用哈希，每次要复制一遍哈希表，开销太大了，不现实

所以用 persistent BST

先遍历二叉搜索树找到要插入的位置，然后对于插入节点把它从根节点到它全都复制一遍然后插入

# Tiger 编译器中的符号

对链表进行 lookup 的时候每一次都要进行 string compare，开销是很大的。所以使用新的数据结构将符号对象关联到一个整数上，因此对于任意给定字符串的所有不同出现，都会被转换成同一个符号对象。
Symbol 的实现：通过 hash 函数将字符串映射到一个 symbol 对象上
SymbolTable 的实现：beginScope () 和 endScope () 的实现

beginScope ()：添加一个 marksym
endScope ()：从符号表中不断 pop 直到 marksym
引入一个辅助栈 (Auxiliary stack) 来维护
- 符号入栈时，会将 binding 联动地插入对应 bucket 的链表头
- 弹出栈顶符号时，对应 bucket 的链表头也会联动地被移除
- beginScope: 压入一个特殊标记到辅助栈中
- endScope: 一直弹出符号直到弹出了一个特殊标记

# 类型检查

# 哪些类型表达式是合法 / 非法的

Tiger 的类型系统：

两种 primitive type: int, string
两种 constructed type: records, arrays

文法

typec → type type-id = ty
- 这表示定义一个类型。 typec 是一个类型定义的开始，它由关键字 type 、一个类型标识符 type-id 和一个等号 = 后跟类型定义 ty 组成。
ty → type-id
- 这表示类型 ty 可以直接是一个已定义的类型标识符 type-id 。
ty → ‘{’ tyfields ‘}’
- 这表示类型 ty 可以是一个记录（record），由花括号 {} 包围的一系列字段 tyfields 定义。
ty → array of type-id
- 这表示类型 ty 可以是一个数组，由关键字 array of 后跟一个类型标识符 type-id 定义。
tyfields → ε
- 这表示字段列表 tyfields 可以为空（ε 表示空串）。
tyfields → id: type-id
- 这表示字段列表 tyfields 由一个或多个字段组成，每个字段由一个标识符 id 和冒号 : 后跟一个类型标识符 type-id 定义，多个字段之间用逗号 , 分隔。

示例

let type a = {x: int; y: int}
    type b = a
    var i : a := ...
    var j : b := ...
in i := j
end

# 类型等价

Name equivalence (NE): 必须声明是同一个类型才是同一类型
Structure equivalence (SE): 如果两个类型的结构完全相同（即它们由相同的构造器以相同的顺序组成），那么它们就被认为是等价的，即使它们的名字不同

1 2	type A = {x: int; y: int} type B = {x: int; y: int}

Tiger 用的是 NE
在 Tiger 编程语言中，存在两个独立的命名空间：一个用于类型（Types），另一个用于函数和变量（Functions and Variables）。所以类型和函数 / 变量可以存在相同的名字，但是函数和变量不能存在相同的名字。
所以需要两个 env

Type env
- symbol -> Ty_ty
Value env
- 对于变量，symbol -> Ty_ty
- 对于函数，symbol -> struct

# 类型检查的 rule

类型检查分为两部分:

Type-checking expressions: 对于每个表达式，根据当前的 Type 和 Value 环境来确定其类型，并检查是否符合语言的类型规则
Type-checking declarations: 在 Tiger 语言中声明只可能在 let 语句中出现
好像就是讲了 transExp, transDec, transVar，AST 递归检查每个节点的类型然后一层一层往上传再检查

语义分析