《编译原理：第七章语义分析和中间代码产生》由会员分享，可在线阅读，更多相关《编译原理：第七章语义分析和中间代码产生（104页珍藏版）》请在金锄头文库上搜索。
1、合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所编译原理第七章 语义分析和中间代码产生合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所第七章 语义分析和中间代码产生o 静态语义检查 n 类型检查 n 控制流检查 n 一致性检查 n 相关名字检查 n 名字的作用域分析 语法分 析器中间代码 产生器静态检 查器中间代码优化器合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o 中间语言(复杂性界于源语言和目标语言之 间)的好处：n 便于进行与机器无关的代码优化工作 n 易于移植 n 使编译程序的结构在逻辑上更为简单明确 源语言 程序目标语 言程序
2、中间语 言程序Compiler Front EndCompiler Back End合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o 常用的中间语言： n 后缀式，逆波兰表示 n 图表示： DAG、抽象语法树n 三地址代码 o 三元式 o 四元式 o 间接三元式7.1 中间语言 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所7.1.1 后缀式 o 后缀式表示法：Lukasiewicz发明的一种表示表 达式的方法，又称逆波兰表示法。 o 一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自 身。 2. 如果E是E1 op
3、E2形式的表达式，其中op是任 何二元操作符，则E的后缀式为E1 E2 op，其 中E1 和E2 分别为E1 和E2的后缀式。 3. 如果E是(E1)形式的表达式，则E1 的后缀式就 是E的后缀式。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o 逆波兰表示法不用括号。只要知道每个算 符的目数，对于后缀式，不论从哪一端进 行扫描，都能对它进行唯一分解。o 后缀式的计算 n 用一个栈实现。 n 一般的计算过程是：自左至右扫描后缀式 ，每碰到运算量就把它推进栈。每碰到k目 运算符就把它作用于栈顶的k个项，并用运 算结果代替这k个项。合肥工业大学合肥工业大学 计算机信息学院软件所
4、计算机信息学院软件所把表达式翻译成后缀式的语义规则描述 产生式 EE(1)op E(2) E (E(1) Eid语义动作 E.code:= E(1).code | E(2).code |op E.code:= E(1).code E.code:=id E.code表示E后缀形式 op表示任意二元操作符 “|”表示后缀形式的连接。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o 数组POST存放后缀式：k为下标，初值为1o 上述语义动作可实现为： 产生式程序段 EE(1)op E(2)POSTk:=op;k:=k+1 E (E(1) EiPOSTk:=i;k:=k+1 o 例
5、：输入串a+b+c的分析和翻译 POST： 1 2 3 4 5EE(1)op E(2) E.code:= E(1).code | E(2).code |op E (E(1)E.code:= E(1).code EidE.code:=idab+c+合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所7.1.2 图表示法o图表示法 n DAG n 抽象语法树 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所7.1.2 图表示法o 无循环有向图(Directed Acyclic Graph，简称 DAG) n 对表达式中的每个子表达式，DAG中都有一个 结点 n 一个
6、内部结点代表一个操作符，它的孩子代表 操作数 n 在一个DAG中代表公共子表达式的结点具有多 个父结点合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所a:=b*(-c)+b*(-c)的图表示法 assigna+*buminusc DAGassigna+*buminusc 抽象语法树*buminusc合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所抽象语法树对应的代码：T1:=-cT2:=b*T1 T3:=-cT4:=b*T3T5:=T2+T4 a:=T5assigna+*buminusc 抽象语法树*buminusc合肥工业大学合肥工业大学 计算机信息学院软
7、件所计算机信息学院软件所DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5assigna+*buminusc DAG抽象语法树对应的代码：T1:=-cT2:=b*T1 T3:=-cT4:=b*T3T5:=T2+T4 a:=T5合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所产生赋值语句抽象语法树的属性文法 产 生 式语义规则 Sid:=ES.nptr:=mknode(assign, mkleaf(id,id.place),E.nptr) EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr) EE1*E2E.nptr:=
8、mknode(*,E1.nptr,E2.nptr) E-E1 E.nptr:=mknode(uminus,E1.nptr) E (E1)E.nptr:=E1.nptr Eid E.nptr:=mkleaf(id,id.place)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所7.1.3 三地址代码 o 三地址代码x:=y op z o 三地址代码可以看成是抽象语法树或DAG的 一种线性表示 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所a:=b*(-c)+b*(-c)的图表示法 assigna+*buminusc DAGassigna+*buminusc
9、 抽象语法树*buminuscDAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5抽象语法树对应的代码： T1:=-cT2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所三地址语句的种类 o x:=y op z o x:=op y o x:=y o goto L o if x relop y goto L或if a goto L o param x和call p,n，以及返回语句return y o x:=yi及xi:=y的索引赋值 o x:=E.code:=E1.cod
10、e | E2.code |gen(E.place := E1.place + E2.place) EE1*E2E.place:=newtemp;E.code:=E1.code | E2.code |gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp;E.code:=E1.code | gen(E.place := uminus E1.place) E (E1)E.place:=E1.place;E.code:=E1.code Eid E.place:=id.place;E.code= 合肥工业大学合肥工业大学 计算机信息学院软件所
11、计算机信息学院软件所三地址语句o 四元式 n 一个带有四个域的记录结构，这四个域分 别称为op, arg1, arg2及result oparg1arg2result (0) uminus cT1 (1) * bT1T2 (2) uminus cT3 (3) * bT3T4 (4) + T2T4T5 (5) := T5a 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所三地址语句o 三元式 n 通过计算临时变量值的语句的位置来引用 这个临时变量 n 三个域：op、arg1和arg2 oparg1arg2 (0) uminus c (1) * b(0) (2) uminus c
12、 (3) * b(2) (4) + (1)(3) (5) assign a(4)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所三地址语句o xi:=y op arg1 arg2 (0) = x i (1) assign (0) yo x:=yi op arg1 arg2 (0) = y i (1) assign x (0)合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所三地址语句o 间接三元式 n 为了便于优化，用 三元式表+间接码表 表 示中间代码 n 间接码表:一张指示器表，按运算的先后次 序列出有关三元式在三元式表中的位置。 n 优点: 方便优化，节
13、省空间合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所o 例如，语句 X:=(A+B)*C; Y:=D(A+B) 的间接三元式表示如下表所示。合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所7.2 说明语句合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所7.3 赋值语句的翻译 o 7.3.1 简单算术表达式及赋值语句 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所为赋值语句生成三地址代码的S-属性文法定义 产生式语义规则 Sid:=ES.code:=E.code | gen(id.place := E.place) EE
14、1+E2E.place:=newtemp;E.code:=E1.code | E2.code |gen(E.place := E1.place + E2.place) EE1*E2E.place:=newtemp;E.code:=E1.code | E2.code |gen(E.place := E1.place * E2.place) E-E1 E.place:=newtemp;E.code:=E1.code | gen(E.place := uminus E1.place) E (E1)E.place:=E1.place;E.code:=E1.code Eid E.place:=id.pl
15、ace;E.code= 合肥工业大学合肥工业大学 计算机信息学院软件所计算机信息学院软件所产生赋值语句三地址代码的翻译模式 Sid:=E p:=lookup(id.name);if pnil then emit(p := E.place)else error EE1+E2 E.place:=newtemp;emit(E.place := E1.place + E2.place)EE1*E2 E.place:=newtemp;emit(E.place := E 1.place * E 2.place)Sid:=E S.code:=E.code | gen(id.place := E.place) EE1+E2 E.pla
