编译原理——第5章

Chapter 5 语法制导翻译技术与中间代码生成

5.1 概述

对语法分析后的语法单位进行，首先编译程序审查每个语法结构的静态语义，如果静态语义正确，再生成中间代码，也有的编译程序不生成中间代码直接生成实际的目标代码。

5.2 属性文法

属性文法：带有属性的文法，每一个文法符号都有对应的属性值代表其实际意义。属性分为继承属性和综合属性两种。

非终结符可以有继承属性和综合属性，而终结符只可能有综合属性。

• 综合属性：指自下而上的属性，即在一个文法中，左式非终结符的属性值根据右式语句中符号的属性确定。
• 继承属性：指自上而下的属性，即在一个文法中，右式非终结符的属性值根据左式非终结符的属性决定。

属性文法：一种上下文无关文法，除此之外还有一系列语义规则，为文法的每一个规则配备的计算属性的规则，称为语义规则，含属性计算、静态语义检查、符号表操作、代码生成等。

由上面的定义可知，文法产生式的左式非终结符的综合属性和右式非终结符的继承属性一定需要一个语义规则定义出来，否则将无法从现有规则中推导出这些语义。

5.3 语法制导翻译概述

相关概念
依赖图：一棵语法树中属性示例之间的信息流，它和语法树的形状相同，箭头自下而上指向。

S-属性文法：仅含有综合属性的属性文法。

L-属性文法：在产生式$A\rightarrow X_1X_2...X_n$中属性可以为继承属性也可以为综合属性且右侧某符号$X_j$的继承属性仅依赖于其左边$X_1X_2...X_{j-1}$某些符号的属性或$A$的继承属性的文法。它是S-属性文法的超集。

文法表示方法
与文法符号相关的属性和规则使用大括号括起来，插入在产生式右部的任何位置，它显式给出了计算的顺序。

如$E\rightarrow E^{(1)}+E^{(2)}\{E.\operatorname{val}=E^{(1)}.\operatorname{val}+E^{(2)}.\operatorname{val}\}$

根据语法树进行语义分析时，只需进行先根遍历逐一计算即可。

语法树遍历
对于继承属性，由于子节点的继承属性值由其父节点决定，直接由上而下进行计算即可。

对于综合属性，由于父节点的综合属性值由其子节点决定，需要由下而上进行计算。

由于S-属性文法不存在继承属性，因此直接由下而上遍历一次即可，计算同时也可以分析语法。对于L-属性文法，由于产生式右式偏后面的符号不会影响偏前面的符号的值，而由上而下规约在一个产生式中是以从左到右的顺序进行。因此每一次遍历到的符号的属性值无论是继承属性还是综合属性都可以由前面已经遍历过的符号的值决定，因此只需要由上而下进行分析即可。

注意：S-属性文法的自下而上分析需要使用栈，除文法分析使用到的状态栈和文法符号栈之外还需要一个语义值栈。由于S-属性文法使用LL文法的分析方式进行分析，因此不能产生无限左递归，需要参考LL文法的左递归消除方式消除文法的左递归。

例：（第五章作业第1题）给定文法G[S]: S→L.L | L，L→ LB | B， B→ 0 | 1，设计一个S-属性文法将该文法描述的二进制数转换成十进制数，比如10.11翻译之后得到2.75。（提示：设计综合属性分别表示值以及二进制数的位数）
解答：
原文法：
$G[S]: \\ S→L.L | L\\L→ LB | B\\B→ 0 | 1$
设计非终结符的两个属性：十进制值（val）和位数（bits）
容易得到文法规则$B\rightarrow 0|1$的语义规则为：
$B.\operatorname{val}=\operatorname{Lex.digit},B.\operatorname{bits}=1$
对于文法规则$L\rightarrow B$，可得其语义规则为：
$L.\operatorname{val}=B.\operatorname{val},L.\operatorname{bits}=1$
对于文法规则$L^{(1)}\rightarrow L^{(2)}B$，不考虑值有可能成为小数，其语义规则为：
$L^{(1)}.\operatorname{val}=L^{(2)}\times2+B.\operatorname{val},L.\operatorname{bits}=L^{(1)}.\operatorname{bits}+1$
对于文法规则$S\rightarrow L$，语义规则为：
$S.\operatorname{val}=L.\operatorname{val},S.\operatorname{bits}=L.\operatorname{bits}$
对于文法规则$S\rightarrow L^{(1)}.L^{(2)}$，其语义规则为：
$S.\operatorname{val}=L^{(1)}.\operatorname{val}+L^{(2)}.\operatorname{val}\times2^{-L^{(2)}.\operatorname{bits}}$，由此得到$S$表示的十进制数。
则设计出来的S-属性文法为：
$G[S]: \\S→L^{(1)}.L^{(2)}:S.\operatorname{val}=L^{(1)}.\operatorname{val}+L^{(2)}.\operatorname{val}\times2^{-L^{(2)}.\operatorname{bits}} \\S→L:S.\operatorname{val}=L.\operatorname{val},S.\operatorname{bits}=L.\operatorname{bits} \\L^{(1)}→ L^{(2)}B:L^{(1)}.\operatorname{val}=L^{(2)}\times2+B.\operatorname{val},L.\operatorname{bits}=L^{(1)}.\operatorname{bits}+1 \\L→B:L.\operatorname{val}=B.\operatorname{val},L.\operatorname{bits}=1 \\B→ 0:B.\operatorname{val}=0 \\B→1:B.\operatorname{val}=1$

原文法：
$G[S]: \\S→L.L | L\\L→ LB | B\\B→ 0 | 1$
设计非终结符的两个属性：十进制值（val）和位数（bits）
容易得到文法规则$B\rightarrow 0|1$的语义规则为：
$B.\operatorname{val}=\operatorname{Lex.digit},B.\operatorname{bits}=1$
对于文法规则$L\rightarrow B$，可得其语义规则为：
$L.\operatorname{val}=B.\operatorname{val},L.\operatorname{bits}=1$
对于文法规则$L^{(1)}\rightarrow L^{(2)}B$，不考虑值有可能成为小数，其语义规则为：
$L^{(1)}.\operatorname{val}=L^{(2)}\times2+B.\operatorname{val},L.\operatorname{bits}=L^{(1)}.\operatorname{bits}+1$
对于文法规则$S\rightarrow L$，语义规则为：
$S.\operatorname{val}=L.\operatorname{val},S.\operatorname{bits}=L.\operatorname{bits}$
对于文法规则$S\rightarrow L^{(1)}.L^{(2)}$，其语义规则为：
$S.\operatorname{val}=L^{(1)}.\operatorname{val}+L^{(2)}.\operatorname{val}\times2^{-L^{(2)}.\operatorname{bits}}$，由此得到$S$表示的十进制数。
则设计出来的S-属性文法为：
$G[S]: \\S→L^{(1)}.L^{(2)}:S.\operatorname{val}=L^{(1)}.\operatorname{val}+L^{(2)}.\operatorname{val}\times2^{-L^{(2)}.\operatorname{bits}} \\S→L:S.\operatorname{val}=L.\operatorname{val},S.\operatorname{bits}=L.\operatorname{bits} \\L^{(1)}→ L^{(2)}B:L^{(1)}.\operatorname{val}=L^{(2)}\times2+B.\operatorname{val},L.\operatorname{bits}=L^{(1)}.\operatorname{bits}+1 \\L→B:L.\operatorname{val}=B.\operatorname{val},L.\operatorname{bits}=1 \\B→ 0:B.\operatorname{val}=0 \\B→1:B.\operatorname{val}=1$

5.4 中间语言

5.4.1 逆波兰式

逆波兰式又称为后缀式，不存在因为运算符优先级问题而产生的冲突。
逆波兰式的计算较为简单，只需要使用一个栈即可完成计算。

5.4.2 三元式和树形表示

三元式：(op, arg1, arg2)，其中op为运算符，arg1和arg2分别为操作数。
特点：

• 三元式出来的顺序和语法成分的计值顺序相一致。其运算结果由每一个三元式之前的序号指示（称为指示器）
• 三元式之间的联系是通过指示器实现的。

间接三元式：为减少三元式在优化时的顺序改动，需要增加一个间接码表，以这种方式进行处理的称为间接三元式。间接三元式的理解也不难，对于传统三元式，如果需要转换的表达式中出现了重复的计算，那么就会出现重复的三元式，在优化时为了消除重复，势必会修改一些三元式的序号名，这样就需要修改所有引用的序号名。为了避免这种情况发生，干脆将所有三元式放入一个类似于三元式池的地方，实际的计算顺序只使用序号表示（保存在间接码表之中），这样在优化时只需要修改间接码表即可，而不需要对三元式进行直接的修改。

树形表示：三元式的另一种表示形式，即将三元式的计算以树形结构进行表示，类似于语法树。

5.4.3 四元式

四元式：(op, arg1, arg2, result)
特点：

• 出现的顺序和语法成分的计值顺序相一致。
• 易于调整和变动四元式，不会出现三元式的问题。
• 便于优化处理。

三地址代码：result=arg1 op arg2

5.5 自上而下语法制导翻译

5.5.1 简单算数表达式和赋值语句的翻译

简单算数表达式和赋值语句到四元式的翻译步骤：

• 分析文法特点。
• 设置一系列语义变量，定义语义过程、语义函数。
• 修改文法，写出每一规则式的语义子程序。
• 扩充LR分析栈，构造LR分析表。

一般需要定义下列函数：

• newtemp函数：产生一个新的变量名，一般会送入符号表中。
• emit函数：根据一个三地址代码产生一个四元式，并填入四元式表中。
• lookup函数：传入一个变量名，判断这个变量名是否在符号表中，如果在则返回其指针，否则返回NULL。
• 语义变量place：表示存放该非终结符的变量名在符号表中的入口地址或临时变量名的整数码（可以参与运算）。

书中第119页给出了对加法和乘法的文法的语法制导翻译。注意右边的函数中引号的作用是将运算符引用起来，并没有其他的意思。

5.5.2 布尔表达式的翻译

布尔表达式用于计算逻辑值，可作为控制语句的条件式。在翻译时仿照算数表达式进行计值。考虑到布尔表达式中有短路情况存在，因此还需要一定的控制流，转移到某个位置表示其求值结果。

布尔表达式的文法：
$E\rightarrow E\land E|E\vee E|\lnot E|(E)|i \operatorname{rop}i|i$

较为固定的翻译方法：

• 对于$A\vee B$，可翻译为：if A then true else B
• 对于$A\land B$，可翻译为：if A then B else false
• 对于$\lnot A$，可翻译为：if A then false else true
• 在书本第121页

还需要定义下面的控制流转换四元式：

• if E goto L₁：如果E为真，则跳转到L₁。
• if E⁽¹⁾ rop E⁽²⁾ goto L₁：如果E⁽¹⁾ rop E⁽²⁾，则跳转到L₁。
• goto L₂：无条件跳转到L₂。

定义了上面的四元式后，将布尔表达式转换为四元式的过程就类似于将C语言中的条件判断式转换为汇编语言。

转换的相关技巧：由于条件判断和赋值不能在一个四元式中进行，因此如果需要翻译包含有E⁽¹⁾ rop E⁽²⁾的布尔表达式，需要进行一定的转换。转换方式如下：

• if E⁽¹⁾ rop E⁽²⁾ goto L₂
• L₁: t₁=0
• goto L₃
• L₂: t₁=1
• L₃: …

注意：if四元式的跳转是向距离自己较远的一条赋值语句跳转，而距离自己较近的赋值语句需要通过无条件跳转最终到达其他四元式。实际上这也是编译器处理布尔表达式条件跳转时常用的方法。在不考虑使用控制流优化的情况下，上述方法已经完全够用。

控制语句中布尔表达式的翻译
对于控制语句而言，存在一个短路现象。两个表达式相与，第一个为假则整个语句一定为假；两个表达式相或，第一个为真则整个语句一定为真。因此利用此特性简化对布尔表达式求值的判断。

真出口、假出口：布尔表达式为真/假时控制流向的转移目标

为规范化针对短路现象的优化，定义以下三个非终结符属性和两个函数：

• tr：记录表达式E所对应的四元式需要回填真出口的四元式的地址所构成的链。
• fa：记录表达式E所对应的四元式需要回填假出口的四元式的地址所都成的链。
• code：记录表达式E所对应第一条四元式的序号。
• merg(p₁, p₂)：链接函数，用于链接真链或假链。其对应的情况是二者相与前者为假或二者相或前者为真的情况，即不需要判断第二个表达式的真假。如在二者相或表达式中，最后一条语句为E.tr=merg(E⁽¹⁾.tr, E⁽²⁾.tr)，这是在让第二个表达式为真时跳转到第一个表达式为真时需要执行的跳转四元式。并且将两个表达式相或作为整体指明其为真时应该执行的四元式的编号，赋值给E。需要注意的是：相或时真出口应该是第一个表达式的真出口，因为第一个表达式为真时会直接从真出口出去。该函数实际上就是合并两条链，并返回链首。
• bp(p, t)：回填函数，用于回填真链与假链。其对应的情况是二者相与前者为真或二者相或前者为假的情况，即需要判断第二个表达式的真假。如在二者相或表达式中，第一条语句即为bp(E⁽¹⁾.fa, E⁽²⁾.code)，指的是让表达式1为假时跳转到表达式2。在二者相与表达式中，则对应为bp(E⁽¹⁾.tr, E⁽²⁾.code)。该函数实际上就是将一条链上链接的所有四元式的第四个字段都填写为一个值。

翻译过程理解：

• 两者相或：回填是将表达式1的假出口设置为表达式2，链接是将表达式2的真出口设置为表达式1的真出口，同时将表达式整体的真出口设置为表达式2的真出口，最后将表达式整体的假出口设置为表达式2的假出口。
• 两者相与：回填是将表达式1的真出口设置为表达式2，链接是将表达式2的假出口设置为表达式1的假出口，同时将表达式整体的假出口设置为表达式2的假出口，最后将表达式整体的真出口设置为表达式2的真出口。

例：翻译布尔表达式$E_1\lor E_2\land E_3$
分析：首先列出四元式：

100: if E₁ goto ?
101: goto ?
102: if E₂ goto ?
103: goto ?
104: if E₃ goto ?
105: goto ?

然后按照语法树顺序进行句子的翻译（语法树略）
根据算符优先级，应该首先翻译$E_2\land E_3$，使用规则$E\rightarrow E^{(1)}\land E^{(2)}$
第一条语句： bp(E⁽¹⁾.tr, E⁽²⁾.code)，执行后：

100: if E₁ goto ?
101: goto ?
102: if E₂ goto 104
103: goto ?
104: if E₃ goto ?
105: goto ?

第二条语句： E.code=E⁽¹⁾.code，执行后，E.code=102
第三条语句： E.tr=E⁽²⁾.tr，执行后，E.tr=104
第四条语句： E.fa=merg(E⁽¹⁾.fa, E⁽²⁾.fa)，执行后，E.fa=105

100: if E₁ goto ?
101: goto ?
102: if E₂ goto 104
103: goto 105
104: if E₃ goto ?
105: goto ?

然后翻译或语句：
第一条语句： bp(E⁽¹⁾.fa, E⁽²⁾.code)，执行后：

100: if E₁ goto ?
101: goto 102
102: if E₂ goto 104
103: goto 105
104: if E₃ goto ?
105: goto ?

第二条语句： E.code=E⁽¹⁾.code，执行后，E.code=100
第三条语句： E.fa=E⁽²⁾.fa，执行后，E.tr=105
第四条语句： E.fa=merg(E⁽¹⁾.tr, E⁽²⁾.tr)，执行后，E.fa=104

100: if E₁ goto ? // 真出口
101: goto 102
102: if E₂ goto 104
103: goto ? // 假出口
104: if E₃ goto 100
105: goto 103

5.5.3 控制语句的翻译

if语句和if-else语句的翻译

对于if语句和if-else语句，由于可能存在嵌套现象，因此在文法规则$S\rightarrow \operatorname{if} E \operatorname{then} S^{(1)} \operatorname{else} S^{(2)}$中，E也有可能是控制语句，在S⁽²⁾没有分析完之前，S⁽¹⁾执行完之后跳转到哪里实际上是不知道的，而内部的嵌套语句也是如此。因此定义一个语义变量chain记忆所有待填信息的四元式链，便于在翻译完成后回填。

将原有文法扩展为：
S→if E then M S
S→if E then M S N else M S
M→ε
N→ε

语法规则定义如下：

以此规则尝试翻译下列语句：
if(A) then (if(B) then C else D) else E

首先列出四元式（也要按照文法分析顺序进行）：

100: if A goto ?
101: goto ?
102: if B goto ?
103: goto ?
104: C
105: goto ?
106: D
107: E
108: goto ?

其中102~106为内部if-else语句翻译出来的四元式。

首先肯定是翻译内部的if-else语句：
第一条语句： bp(B.tr, M.s)

100: if A goto ?
101: goto ?
102: if B goto 104
103: goto ?
104: C
105: goto ?
106: D
107: E
108: goto ?

第二条语句： bp(B.fa, M⁽¹⁾.s)

100: if A goto ?
101: goto ?
102: if B goto 104
103: goto 106
104: C
105: goto ?
106: D
107: E
108: goto ?

第三条语句： tmp=merg(C.chain, N.s)（修改了N.s）
第四条语句： B.chain=merg(tmp, D.chain)（让B.chain链接到了C.chain和D.chain）

然后翻译外层的if-else语句：
第一条语句： bp(A.tr, M.s)

100: if A goto 102
101: goto ?
102: if B goto 104
103: goto 106
104: C
105: goto ?
106: D
107: E
108: goto ?

第二条语句： bp(A.fa, M⁽¹⁾.s)

100: if A goto 102
101: goto 107
102: if B goto 104
103: goto 106
104: C
105: goto ?
106: D
107: E
108: goto ?

第三条语句： tmp=merg(X.chain, N.s)（修改了N.s）
第四条语句： A.chain=merg(tmp, E.chain)（让A.chain链接到了X.chain和E.chain）

从上面的例子可以看出，对于if-else语句的分析是由内而外的。关键在于内部不能确定的跳转到底是哪些。定义chain的目的正是为了记录这些不能确定的四元式。

5.5.4 循环语句的翻译

while语句的翻译
同样进行扩展：
(1) S→while E do M S⁽¹⁾
(2) M→ε

相较于if-else语句要简单些，在内部四元式执行完成之后无条件跳转到开头的判断即可。

5.5.5 简单说明语句的翻译

定义函数FILL：将名字id和属性A登记在符号表中。
定义语义变量ATT：该非终结符的属性。