编译原理 第六部分
符号表
一张符号表的每一项（或称入口）包含两大栏（或称区段、字域），即名字栏和信息栏。
信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，由于查填符号表一般是通过匹配名字来实现的，因此，名字栏也称主栏。主栏的内容称为关键字（key word）
在整个编译期间，对于符号表的操作大致可归纳为五类：
对给定名字，查询名字是否已在表中；
往表中填入一个新的名字；
对给定名字，访问它的某些信息；
对给定名字，填写或更新它的某些信息；
删除一个或一组无用的项。
不同种类的表格所涉及的操作往往也是不同的。上述五个方面只是一些基本的共同操作。
符号属性(信息）
符号名
符号的类型
符号的存储类别
符号的作用域及可视性
符号变量的存储分配信息
符号的其它属性 ：
- 数组内情向量
- 记录结构型的成员信息
- 函数及过程的形参
符号表的组织
由于处理对象的作用和作用域可以有多种，所以符号表也有多种组织方式。
按照处理对象的特点，符号表的组织方式一般可以分为直接方式和间接方式
符号表按照标识符的种属进行组织：根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性
符号表项的组织传统上采用三种构造方法。即 线性法，二分法 及 散列法。
线性组织
这种方法规定符号表中表项按它的符号被扫描到的先后顺序建立
排序组织及二分法
排序组织的符号表，就是在符号表中的表项按其符号的字符代码串的值的大小排列．
关于排序表的表项建立及符号查找，通常采用“二分法”．
散列组织
散列法又称为杂凑法或Hash法．散列法的基本思想是：设置一个足够大的空间M，构造一个散列函数Hash(Ki)，函数值的取值范围在0~M-1之间．这样查找Ki时，Hash(Ki)就决定了Ki在M中的位置．由此可见，构造Hash函数是散列法的关键问题．
构造Hash函数的方法，如，可以设M为素数，将Hash(Ki)定义为Ki/M的余数．
中间代码
翻译为中间语言的好处：
- 便于进行与机器无关的代码优化；
- 使编译程序改变目标机更容易；
- 使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。
编译程序所使用的中间代码有多种形式。常见的有逆波兰式、三元式和树形、四元式表示。
逆波兰式
这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀表达式
三元式
每个三元式由三个部分组成，分别是：
(算符op，第一运算对象ARG1，第二运算对象ARG2)
运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。
对于一目算符op，只需选用一个运算对象，不妨规定只用ARG1。至于多目算符，可用若干个相继的三元式表示。
树形表示
四元式
四元式是一种比较普遍采用的中间代码形式。
四元式的四个组成成分是：
- 算符op
- 第一运算对象ARG1
- 第二运算对象ARG2
- 运算结果RESULT
运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。
四元式形式： (op ,arg1,arg2,result)
【例如】a=b * c+d*e的四元式为：
（1）（*， b， c， T1）
（2）（*， d， e， T2）
（3）（+， T1， T2， T3）
（4）（=， T3， －， a）
四元式表示很类似于三地址指令，确实，有时把这类中间表示称为“三地址代码”，因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条“指令”包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对于代码优化和目标代码生成都较有利
简单赋值语句的翻译
语义过程GEN表示产生一个四元式，并且填入四元式表中。
语义过程Newtemp表示生成一个临时变量，每调用一次，生成一新的临时变量。
语义变量E.place，表示存放E值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）。
语义变量Entry(id)回送标识符id在符号表中的入口地址。
布尔表达式的翻译
程序设计语言中的布尔表达式有两个作用
一是计算逻辑值
二是用做改变控制流语句中的条件表达式，如在if-then，if-then-else，或是while-do语句中那样
计算布尔表达式的值有两种办法
第一种办法，如同计算算术表达式一样，计算出各部分的真假值，最后计算出整个表达式的值
第二种办法，采取某种优化措施，只计算部分表达式
拉链
为了记录需回填地址的四元式，常采用一种“拉链”的办法。
把需回填E.TC的四元式拉成一条链子，把需回填E.FC的四元式拉成一条链子，分别称做”真”链和”假”链。