语义分析
语义分析的任务
- 语义分析也称为类型检查，上下文相关分析
- 负责检查程序（抽象语法树）的上下文相关的属性：
- 这个是由具体语言相关的，典型的情况包括
- 变量使用之前先进行声明
- 每个表达式都有合适的类型
- 函数调用和函数的定义要一致
- …等
下面是示例代码，其中有些典型的错误
void f(int *p) { x += 4; p(23); "hello" + "world"; } int main() { f() + 5; break; return; }
语义分析的阶段是根据上述代码，找出代码错误。
程序语言的语义
- 传统上，大部分的程序设计语言都采用自然语言来表达程序语言的语义
- 例如，对于+运算：要求左右操作数必须是整形
- 编译器的实现者必须对语言中的语义规定有全面的理解
- 主要的挑战是如何能够正确高效的实现
符号表
- 用来存储程序中的变量相关信息
- 类型
- 作用域
- 访问控制信息等
- 必须非常高效
- 程序中的变量规模会很大
- 为了高效，可以使用hash表等数据结构来实现符号表
- 查找的时间时O(1)
- 为了节约空间，也可以使用红黑树等平衡树
- 查找是O(logN)时间
类型相等
- 类型检查问题往往归结为判断两个类型是否相等 t1 == t2
- 在实际的语言中，这往往是个需要谨慎处理的复杂问题
- 名字相等vs结构相等
- 对采用名字相等的语言，可直接比较
- 对采用结构相等的语言需要递归比较各个区域
错误诊断
- 要给出尽可能准确的错误信息
- 要给出尽可能多的错误信息
- 从错误中进行恢复
- 要给出尽可能准确的出错位置
- 程序代码的位置信息要从前端保留并传递过来
代码翻译
- 现代的编译器中的语义分析模块，除了做语义分析外，还要负责生成中间代码或者目标代码
- 代码生成的过程也同样是对树的某种遍历
- 因此语义分析模块往往是编译器中最庞大也最复杂的模块
代码生成
- 负责把源程序翻译成目标机器上的代码
- 目标机器
- 可以是真实的物理机器
- 可以是虚拟机
- 两个重要任务
给源程序的数据分配计算资源
源程序的数据
全局变量、局部变量、动态分配等
机器计算资源
寄存器、数据区、代码区、栈区、堆区
根据程序的特点和编译器的设计目标，合理的为数据分配计算资源
例如：变量放在内存里还是寄存器里
给源程序的代码选择指令
源程序的代码
表达式运算、语句、函数等
机器指令
算数运算、比较、跳转、函数调用返回
用机器指令实现高层代码的语义
等价性
对机器指令集体系结构的熟悉
栈式计算机
- 栈式计算机在历史上非常流行
上世纪70年代层有很多栈式计算机
- 但是今天已经基本退出历史舞台
效率问题
- 我们还需要讨论栈式计算机的代码生成技术的原因是：
给栈式计算机生成代码是最容易的
仍然有很多的栈式虚拟机
Pascal P code
JVM
Postscript等等
结构
- 内存：存放所有的变量
- 栈：进行运算的空间
- 执行引擎：指令的执行
指令集
java字节码
S-> push NUM | load x | store x | add | sub | times | div
变量内存分配伪指令
- stack机器只支持一种数据类型int，并且给变量x分配内存的伪指令是：.int x
- stack机器在装在一个程序时，就会读取伪指令，并且给相关变量分配内存空间
代码生成
寄存器计算机
- 寄存器计算机是目前最流行的机器体系结构之一
- 效率很高
- 机器体系结构规整
- 机器基于寄存器架构
- 典型的有16,32或者更多个寄存器
- 所有的操作都在寄存器中进行
- 访问都通过load/store进行
- 内存不能直接运算
Reg的结构
- 内存
- 存放溢出的变量
- 寄存器
- 进行运算的空间
- 假设有无限多个
- 执行引擎
- 指令的执行
伪指令
- reg机器只支持一种数据类型int 则分配寄存器的伪指令是.int x
- 在代码生成的阶段，假设reg机器上有无限多个寄存器
- 因此每个声明变量和临时变量都会占用一个(虚拟)寄存器
- 把虚拟寄存器分配到物理寄存器的过程称为寄存器的分配
