讲稿第8章 语法制导翻译和中间代码生成.docx
《讲稿第8章 语法制导翻译和中间代码生成.docx》由会员分享，可在线阅读，更多相关《讲稿第8章 语法制导翻译和中间代码生成.docx（13页珍藏版）》请在冰点文库上搜索。
讲稿第8章语法制导翻译和中间代码生成
第8章语法制导翻译和中间代码生成（3学时，15分钟）
编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，它们的语法结构可以不同，但表达的结果应完全相同。
通常，在语法分析过程中，每当一个产生式获得匹配（自上而下分析）或用于归约（自下而上分析）时，就执行相应于该产生式的语义子程序进行语义处理，这个过程就是语法制导翻译。
编译中的语义处理是指两个功能：
第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义，也称为静态语义检查或静态审查。
动态语义检查需要生成相应的目标代码，在运行时进行。
静态语义检查主要涉及以下几个方面：
（1）类型检查，如参与运算的操作数及类型应相容。
（2）控制流检查，用以保证控制语句有合法的转向点。
如C语言中不允许goto转入case语句流；break语句需要寻找包含它的最小switch、while或for语句方可找到转向点，否则出错。
（3）一致性检查，如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。
第二，如果静态语义正确，语义处理的工作是要执行真正的翻译，即生成程序的一种中间表示形式（中间代码），或者直接生成实际的目标代码。
虽然源程序可以直接翻译为目标语言代码，但是通常编译程序还是采用了独立于机器的、复杂性介于源语言与机器语言之间的中间语言。
这样做的好处是：
（1）便于进行与机器无关的代码优化；
（2）使编译程序改变目标机更容易；
（3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。
静态语义检查和中间代码产生在编译程序中的位置如图所示：
需要指出的是：
从单词符号序列的源程序到某种形式的中间代码，不像词法分析和语法分析那样有一套形式化的理论和算法（如自动机等），尽管已经有了一些形式语义系统，但大都没有得到公认。
这就是说，语义的形式化描述要远比语法的形式化困难得多。
目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。
本章引入基于属性文法的语法制导翻译方法的基本思想，介绍几种典型的中间代码形式及相关的一些问题。
教学内容：
8.1属性文法；
8.2语法制导翻译；
8.3中间代码；
教学要求：
理解语法制导翻译的基本思想
会写出语句的逆波兰表示、三元式、四元式和树形结构
教学重点：
中间代码的形式：
逆波兰记号、三元式和树形表示、四元式
8.1属性文法（55分钟）
属性文法是Knuth在1968年首先提出的。
它是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）附加若干相关的“值”（称为属性）。
这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等。
属性与变量一样，可以进行计算和传递。
属性的加工过程即是语义处理的过程。
对于文法的每个产生式附加一组属性的计算规则，称为语义规则。
这样一来，属性文法实际上就是附加了一组属性和语义规则的文法。
一、属性文法的形式
属性文法（AG，attributegrammar）是一个三元组：
A=（G,V,F），其中，
G:
是一个上下文无关文法；
V:
有穷的属性集，每个属性与一个文法符号相连；
F：
语义规则，每条与一个产生式相联。
文法符号X的属性t常用X.t来表示。
二、属性文法的分类
Knuth把属性分为两类：
综合属性和继承属性。
综合属性：
在语法树中，一个结点的综合属性的值由其子结点的属性值确定，因此，通常使用自下而上的方法在每个结点处使用语义规则计算综合属性的值。
仅仅使用综合属性的属性文法称为S—属性文法。
继承属性：
在语法树中，一个结点的继承属性的值由此结点的父结点和/或兄弟结点的某些属性确定。
用继承属性来表示程序语言结构中的上下文依赖关系很方便。
于是，对应于产生式Aα的语法规则的形式可以表示为关于属性的函数（见教材P170）：
b:
=f（c1,c2,...,ck）
其中，f是一个函数，b和c1,c2,...,ck是该产生式文法符号的属性。
语义规则中的属性存在下述性质与关系：
（1）若b是A的属性，c1,c2,...,ck是产生式右部文法符号的属性，或者A的其他属性，则称b是A的综合属性；
（2）若b是产生式右部某文法符号X的属性，并且c1,c2,...,ck是A或产生式右部任意文法符号的属性，则称b是X的继承属性。
在这两种情况下，我们说属性b依赖于属性c1,c2,...,ck。
这种依赖关系实质上反映了属性计算的先后次序，即所有属性ci被计算之后才能计算属性b。
要特别强调的是：
（1）终结符只有综合属性，它们由词法分析器提供；
（2）非终结符既可有综合属性，也可有继承属性，但文法开始符号没有继承属性。
出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由参数提供。
例8.1可用作台式计算器的简单算术表达式求值的语义描述（见教材P171）：
产生式
语义规则
（0）LE
print（E.val）
（1）EE1+T
E.val:
=E1.val+T.val
（2）ET
E.val:
=T.val
（3）TT1*F
T.val:
=T1.val*F.val
（4）TF
T.val:
=F.val
（5）F（E）
F.val:
=E.val
（6）Fdigit
F.val:
=digit.lexval
非终结符E、T及F都有一个综合属性val，符号i有一个综合属性，它的值由词法分析器提供。
与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的属性是空的或是一个虚属性。
某些非终结符加上标（也有的参考书加下标）是为了区分一个产生式中同一非终结符多次出现。
例8.2见教材P171描述说明语句中各种变量的类型信息的语义规则
产生式
语义规则
（0）DTL
L.Type=T.Type
（1）Tint
T.Type=int
（2）Tfloat
T.Type=float
（3）LL1,id
L1.Type=L.Type ;id.Type=L.Type
（4）Lid
id.Type=L.Type
8.2语法制导翻译（30分钟）
在语法分析过程中，每当一个产生式获得匹配（自上而下分析）或用于归约（自下而上分析）时，就执行相应于该产生式的语义子程序进行语义处理，这个过程就是语法制导翻译。
假定我们现在要分析的语法成分是简单算术表达式，所完成的语义处理不是将它翻译成中间代码或是目标代码，而是计算表达式的值。
采用的描述系统是上节的例8.1。
假如语法分析方法是自下而上的。
在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的"值"也就同时产生了，例如输入串是3*5+4，其语法树如下图。
语法制导翻译的具体实现途径不困难。
假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在例8.1的属性文法中描述的语义动作。
每步工作后的语义值保存在扩充的分析栈里的语义栈中。
采用的LR分析（SLR
（1）分析表见教材P142表7.8），其中使用d代替digit。
状态
ACTION
GOTO
d
+
*
（
）
#
E
T
F
0
S5
S4
1
2
3
1
S6
acc
2
r2
S7
r2
r2
3
r4
r4
r4
r4
4
S5
S4
8
2
3
5
r6
r6
r6
r6
6
S5
S4
9
3
7
S5
S4
10
8
S6
S11
9
r1
S7
r1
r1
10
r3
r3
r3
r3
11
r5
r5
r5
r5
分析和计值2+3*5的过程如下（见教材P174图8.7）：
步骤
符号栈
输入串
状态栈
语义栈
Action
Goto
1
#
2+3*5#
0
-
S5
2
#2
+3*5#
05
--
r6
3
3
#F
+3*5#
03
-2
r4
2
4
#T
+3*5#
02
-2
r2
1
5
#E
+3*5#
01
-2
S6
6
#E+
3*5#
016
-2-
S5
7
#E+3
*5#
0165
-2--
r6
3
8
#E+F
*5#
0163
-2-3
r4
9
9
#E+T
*5#
0169
-2-3
S7
10
#E+T*
5#
01697
-2-3-
S5
11
#E+T*5
#
016975
-2-3--
r6
10
12
#E+T*F
#
01697（10）
-2-3-5
r3
9
13
#E+T
#
0169
-2-（15）
r1
1
14
#E
#
01
-（17）
acc
8.3中间代码（50分钟）
所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：
一是容易生成；二是容易将它翻译成目标代码。
编译程序所使用的中间代码有多种形式。
常见的有逆波兰记号、三元式、四元式和树型表示。
8.3.1逆波兰记号
逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。
这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。
注意：
逆波兰记号用不着使用括号，例如（a+b）*c将被表示为ab+c*。
根据运算对象和运算符号出现的先后位置，以及每个运算符号的目数，就完全决定了一个表达式的分解。
把中缀式转换为后缀式的简单方法：
按中缀式中各种运算符号的优先规则，从最先执行的部分开始写，一层层地套。
程序设计语言中的表示逆波兰表示
a+bab+
a+b*cabc*+
（a+b）*cab+c*
a:
=b*c+b*dabc*bd*+:
=
例如分别给出下列表达式的后缀表示：
后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。
常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。
例如B@CD*+（它的中缀表示为－B+C*D，使用@表示一目减）的计值过程为：
1.B进栈；
2.对栈顶元素施行一目减运算，并将结果代替栈顶，即－B置于栈顶；
3.C进栈；
4.D进栈；
5.栈顶两元素相乘，两元素退栈，相乘结果置栈顶；
6.栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。
8.3.2三元式
把表达式及各种语句表示成一组三元式。
每个三元式由三个部分组成，分别是：
算符op，第一运算对象ARG1和第二运算对象ARG2。
运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。
三元式出现的先后顺序是和表达式各部份的计值顺序相一致的。
例如a∶=b*c+b*d的表示为：
（1）（*bc）
（2）（*bd）
（3）（+
（1）
（2））
（4）（∶＝（3）a）
与后缀式不同，三元式中含有对中间计算结果的显式引用，比如三元式
（1）表示的是b*c的结果。
三元式（3）中的
（1）和
（2）分别表示第一个三元式和第二个三元式的结果。
对于一目运算符，我们规定只用ARG1。
赋值运算符：
=一般看做是二目运算符。
为了便于代码优化处理，作为中间代码，常常不直接使用三元式。
因为移动某条语句时要改变引用该语句的其他语句，所以改动三元式很困难。
为此，我们另设一张间接码表，按运算的先后顺序列出有关三元式在间接码表中的位置。
这种表示法称为间接三元式。
例如：
语句X:
=（A+B）*C;Y:
=D↑（A+B）的间接三元式
间接三元式间接码表
（1）（+AB）
（1）
（2）（*
（1）C）
（2）
（3）（:
=
（2）X）（3）
（4）（↑D
（1））
（1）
（5）（:
=（4）Y）（4）
（5）
有了间接码表后，一方面相同的三元式就无须重复填进表中，节约了空间；另一方面，当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表，无须改动三元式。
当然这样一来，向三元式表中每填入一个三元式前，必须先查看一下此式是否已经在表中出现过。
8.3.3树形表示
树形表示是三元式表示的翻版。
8.3.2中三元式可表示成右面的树表示：
表达式的树形表示很容易实现：
简单变量或常数的树就是该变量或常数自身，如果表达式e1和e2的树分别为T1和T2，那么e1+e2，e1*e2，－e1的树分别为：
二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存储空间，一棵多叉子树可以通过引进新结而表示成一棵二叉子树。
8.3.4四元式
四元式是一种比较普遍采用的中间代码形式。
四元式的四个组成成分是：
算符op，第一和第二运算对象ARG1和ARG@及运算结果RESULT。
它实际上就是一条三地址的指令。
运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。
例如a∶=b*c+b*d的四元式表示如下：
（1）（*bct1）
（2）（*bdt2）
（3）（+t1t2t3）
（4）（∶=t3－a）
四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。
也就是说，四元式之间的联系是通过临时变量实现的。
为了复习与巩固一下前面所学习的几种中间代码的形式，下面举一个例子，分别用几种中间代码的形式来表示
例:
A+B*（C-D）+E/（C-D）^N
逆波兰式：
ABCD-*+ECD–N^/+
四元式：
（1）（-CDt1）
（2）（*Bt1t2）
（3）（+At2t3）
（4）（^t1Nt4）
（5）（/Et4t5）
（6）（+t3t5t6）
三元式：
（1）（－CD）
（2）（*B
（1））
（3）（+A
（2））
（4）（^
（1）N）
（5）（/E（4））
（6）（+（3）（5））
间接三元式间接码表
（1）（-CD）
（1）
（2）（*B
（1））
（2）
（3）（+A
（2））（3）
（4）（^
（1）N）
（1）
（5）（/E（4））（4）
（6）（+（3）（5））（5）
（3）
（6）
第8章小结（5分钟）
属性文法
语法制导翻译概论
中间代码的形式（要求掌握）：
逆波兰记号；三元式和树形表示；四元式
第8章作业（5分钟）
P2031
（1）（3）（5）、2
升级会员 