[toc]
前后端衔接，同时进行静态类型检查 分层进行中间代码生成，高层处理高级特性，低层处理更抽象、统一的优化，底层考虑架构相关问题
- 静态分析和动态分析
- 静态语义分析类似词法语法分析，但由于种类和总量的变化范围很大，难以有一个通用的清晰框架
- 属性文法和抽象文法是描述语义分析的较好方法
- 语义分析的实现算法与语义分析完成的时刻有关
## 中间代码的形式
- 标识并复用公共子表达式，使之有不止一个父节点
- 可以通过修改构造点的函数来构造tag，但检查开销巨大
- DAG值编码方法
- 记录数组每行保存一个记录<op,l,r>
- 叶子节点只有一个附加字段，内部节点有两个附加字段
- 查询开销大，可以用哈希优化
- 一条指令右侧最多一个运算符
- 地址包括名字和常数和临时变量；指令包括双目算符和单目算符和复制指令和无条件转移和条件转移和过程调用返回和数组访问和地址指针赋值
- 指定编号的两种形式：符号编号和位置号
-
$result ;\ := ;\ arg1 ;\ op ;\ arg2$ ，即形如op arg1 arg2 result - resulthe和arg通常为符号表条目指针。若为临时变量，则要进符号表
- 一元运算不使用arg2，param不适用arg2和result
- 最终要用复制指令完成赋值
- 转移语句的目标语句标号放在result
- 易于调整次序，比那与优化；占用空间大，引入新符号表表项
- 形如num op arg1 arg2
- 序号num存储临时值，arg可以是符号表指针或序号num
- 有些三地址语句需要多个三元式表示。如数组赋值：一次[]=，一次:=
- 避免临时量，节省空间；不便于（顺序调整的）优化
- 在三元式基础上增加索引列表，便于重排
- 空间类似四元式，临时值引用次数越多，间接三元式越节省空间
- 引入$\empty$节点，合并多个对同一变量的定值，换名分离多次引用和多次定值，从而避免冗余引用
- 数据类型的规范和语法表示包括属性、值、操作
- 声明可以表明数据对象的生存期
- 声明包括显式声明和隐式声明<注意区分与动态/静态类型体系的区别>
- 声明的目的包括选择存储表示、存储管理、多态操作、类型检查
- 语言结构的类型，一般包括boolean/char/integer/real/type_error（检查中的错误）/void（语句检查）
- 类型表达式可以命名，类型名是类型表达式，如struct和typedef
- 类型名用类型表管理
- 类型构造器（如数组）作用于类型表达式的结果仍是类型表达式
- 类型表达式可以包含变量，变量值为类型表达式
- 类型系统是派类型表达式的规则，由类型检查器实现
- 静态检查由编译器完成，检查所有操作和执行路径，不包括数组越界检查
- 动态检查在目标运行时完成，在每个数据对象中保存一个类型标签，难于调试且速度慢
- 健全的类型系统指允许静态确定错误是否在运行时发生
- 强类型化：一个语言的编译器保证接受程序不会有运行时的类型错误（C语言可通过限制类型转换近似认为强类型）
- 两个类型表达式是同样的基本类型或同样的类型构造器作用于结构等价的类型
- 实际可能放宽限制，如数组不考虑界。但结构的顺序是重要的
- 类型表达式名字等价：只考虑名字完全相同，不把名字替换为基本类型
- 名字等价缺点在于传参需要全局定义名字，结构等价算法开销大且可能遗漏操作错误
- 看到新类型名或对应类型构造器时，构造新结点
- 引用自身时构造环
- 检查结构等价时，若遇到类型构造器，直接检查类型名字
- 编译器记录类型，并计算偏移地址。对变长类型或动态数组，一般保存指向的指针
- 声明翻译时同时记录类型的宽度，数组描述为array(value, type)。包括继承属性（基类型）t/w和综合属性type和width
- 将所有声明作为一组处理
- 引入相对偏移offset，每个变量处理后offset增加相应的width
- 函数嵌套时offset不计算子函数符号表大小，但结构体中需要计算
- 引入属性addr和code
- gen(x '=' y '+' z)表示生成三地址指令x=y+z
- 可以使用增量翻译避免code属性过长
- 假设数组下标下界为low，首地址为base，元素宽度为w，则A[i]的相对地址为$addr=base+(i-low)w=iw+(base-low*w)$。其中后式的后半部分作为常量，可在编译时计算以优化
- 多维时有类似计算和优化
- 数组引用进行翻译时，需要引入三个综合属性：addr/array/type，分别表示数组引用偏移量/指向数组名符号表条目的指针（base为基地址）/子数组类型
- 最终计算对象为$L.array.base[L.addr]$，即基地址和偏移量相加
- 包括类型综合和类型推导两种形式
- 类型综合
- 根据子表达式类型自下而上构造表达式类型
- 名字要先声明后使用
- 类型推导
- 根据语言结构的使用方式确定结构类型
- 引入类型变量和量词描述
- 使运算对象类型符合预期
- 在SDT中计算类型后可能需要补充生成类型转换代码
- 拓宽转换和窄化转换。前者可以保持原有信息，但可能丢失精度（int→float）；后者可能丢失信息。
- 隐式类型转换和显式类型转换。前者是编译器根据约定自动实现的
- 类型转换的翻译实现：生成两个变量到最小上界的类型转换
- 重载：根据上下文不同，符号又不同含义，如整数加法和浮点加法
- 重载消除（算符鉴别）：唯一确定引用点处重载符号的含义
- 仅看参数无法消除重载时，自下而上通过子表达式计算
- 表达式类型检查规则修改：允许一个表达式对应一个类型集合。检查到可能类型集合为空或不唯一时，报错
- 两次深度优先遍历实现语法制导定义：自下而上综合得到types属性，自上而下传播unique属性，返回时计算code
- 多态函数允许一个参数有不同类型（如算符、数组索引、指针操作、函数作用）
- 类型变量：在不要求先声明后使用的语言中，检查标识符使用的一致性
- 类型推导：从语言结构的使用方式推导类型
- 类型置换
- 类型变量到类型表达式的置换，同时去除量词限制
- 置换结果称为表达式的一个实例，实例范围不能大于原表达式
- 若存在置换使两个表达式相同，则置换是合一的
- 多态函数的类型推导
- 输入一个由一系列函数定义及待求值表达式组成的程序，输出程序中名字的类型
- 对函数$E_1(E_2)$，若推导出$E_2$类型为t，$E_1$类型为$s \rightarrow s^\prime$，则二者必须合一
- 多态函数每次出现，都将类型表达式中的受限变量替换为互不相同的新变量，并移除全称量词
- 合一算法
- 类型变量用叶结点表示
- 类型构造算子用内部结点表示
- 节点被分为若干等价类，同一等价类内的两个结点的类型表达式必须合一
- 合一过程中不能扩大等价类范围，变量和类型表达式合一时只能合一为等价类的代表
- 计算逻辑值并在改变控制流的语句中作为条件表达式
- rel算法包括6种算符
- 计算方法：真假值数值化和关系表达式控制流（简化计算开销，如C的特性，称为短路代码）
- 控制流语句生成中，继承属性next应避免连续跳转
- 对true和false各生成标签
- 避免冗余goto指令的方法：生成fall语句（不跳转）或调整判别方式（翻转条件）
- truelist和falselist：等待真/假出口的标号
- 控制转移语句翻译方式相似
- 标记非终结符N：跳过else
- break的翻译：跟踪外围语句
- switch语句翻译：计算表达式的值，并逐条比对
- 优化：候选值少时直接比对，多时使用散列表；选值有一定范围时使用跳转表间接寻址
- 函数调用拆分为准备参数并求值和调用
- 参数传递采用值调用方式
- 函数类型计算及类型检查
- 符号表生成
- 函数调用：对每个参数生成param指令后生成调用指令