编译原理语法制导翻译和中间代码生成Word文档下载推荐.docx
《编译原理语法制导翻译和中间代码生成Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《编译原理语法制导翻译和中间代码生成Word文档下载推荐.docx（27页珍藏版）》请在冰点文库上搜索。
简单算术表达式求值的语义描述。
产生式语义规则
（0）L→Eprint（E.val）
（1）E→E1+TE.val：
=E1.val+T.val
（2）E→TE.val：
=T.val
（3）T→T1*FT.val：
=T1.val×
F.val
（4）T→FT.val：
=F.val
（5）F→（E）F.val：
=E.val
（6）F→digitF.val：
=digit.lexval
在该描述中，每个非终结符都有一个属性：
一个整数值的称作val的属性。
按照语义规则对每个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性。
单词digit仅有综合属性，它的值是由词法分析程序提供的。
和产生式L→E相联的语义规则是一个过程，打印由E产生的表达式的值。
我们可以理解为L的属性是空的或是虚的。
第二节语法制导翻译概论
在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。
假定我们现在要分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间代码或目标代码，而是计算表达式的值。
采用的描述系统是上节的例1。
假如语法分析方法是自下而上的。
在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的“值”也就同时产生了，例如输入串是2+3*5，其语法树如图7-2-1（a），在第一步归约用到了产生式（6），执行的语义动作是置F.val的值为单词digit值，我们把语法树中每个结点的语义值括在该结点处。
那么第一步归约并完成语义动作后的情形在图7-2-1（b）中指出。
继续进行分析，第七次归约后的情形在图7-2-1（c）中指出归约至E时，它的值17也计算出来了。
语法制导翻译的具体实现途径不困难。
假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成图7-2-2所示那样。
Sm
y.Val
Y
Sm-1
x.Val
X
┆
S0
—
#
状态栈
语义值
符号栈
图7-2-2扩充的分析栈
状态
ACTION（动作）
GOTO（转换）
d
+
*
（
）
E
T
F
s5
s4
1
2
3
s6
Acc
r2
s7
r4
4
8
5
r6
6
9
7
10
s11
r1
r3
11
r5
图7-2-3LR分析表
同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在例1的属性文法中描述的语义动作。
每步工作后的语义值保存在扩充的分析栈里“语义值”栏中。
采用的LR分析表见图7-2-3，其中使用d代替digit。
分析和计值2+3*5的过程列在图7-2-4中。
按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法分析的制导下，随着分析的进展逐步生成中间代码。
步骤
归约动作
语义栈（值栈）
留余输入串
1）
2+3*5#
2）
05
——
#2
+3*5#
3）
03
—2
#F
4）
02
#T
5）
01
#E
6）
016
—2—
#E+
3*5#
7）
0165
—2——
#E+3
*5#
8）
0163
—2—3
#E+F
9）
0169
#E+T
10）
01697
—2—3—
#E+T*
5#
11）
016975
—2—3——
#E+T*5
12）
01697（10）
—2—3—5
#E+T*F
13）
—2—（15）
14）
-（17）
15）
接受
图7-2-42+3*5的分析和计值过程
第三节中间代码的形式
编译程序所使用的中间代码有多种形式。
常见的有逆波兰记号、三元式、四元式和树形表示。
下面分别介绍。
一、逆波兰记号
逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。
这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。
图7-3-1给出了程序设计语言中的简单表达式和赋值语句相应的逆波兰表示形式：
程序设计语言中的表示
逆波兰表示
a+b
ab+
a+b*c
abc*+
（a+b）*c
ab+c*
a：
=b*c+b*d
abc*bd*+：
=
图7-3-1逆波兰表示
后缀表示法表示表达式，其最大的优点是最易于计算机处理表达式。
利用一个栈，自左至右扫描算术表达式（后缀表示）。
每碰到运算对象，就把它推进栈；
碰到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施运算，并将运算结果代替这两个运算对象而进栈。
若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈。
最后的结果留在栈顶。
例如B@CD*+（它的中缀表示为—B+C*D，使用@表示一目减）的计值过程为：
1、B进栈；
2、对栈顶元素施行一目减运算，并将结果代替栈顶，即—B置于栈顶；
3、C进栈；
4、D进栈；
5、栈顶两元素相乘，两元素退栈，相乘结果置栈顶；
6、栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。
由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。
逆波兰表示很容易扩充到表达式以外的范围。
二、三元式和树形表示
另一类中间代码形式是三元式。
把表达式及各种语句表示成一组三元式。
每个三元式三个组成部分是：
算符op，第一运算对象ARG1，和第二运算对象ARG2。
例如：
=b*c+b*d的表示为：
（1）（*b，c）
（2）（*b，c）
（3）（+
（1），
（2））
（4）（：
=（3），a）
与后缀式不同，三元式中含有对中间计算结果的显式引用，比如三元式
（1）表示的是b*c的结果。
三元式（3）中的
（1）和
（2）分别表示第一个三元式和第二个三元式的结果。
对于一目算符op，只需选用一个运算对象，不防规定只用ARG1。
至于多目算符，可用若干个相继的三元式表示。
树形表示是三元式表示翻版。
上述三元式可表示成下面的树表示：
表达式的树形表示很容易实现：
简单变量或常数的树就是该变量或常数自身，如果表达式e1和e2的树分别为T1和T2，那么e1+e2，e1*e2，—e1的树分别为：
二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存储空间，一棵多叉子树可以通过引进新结而表示成一棵二叉子树。
三、四元式
四元式是一种比较普遍采用的中间代码形式。
四元式的四个组成成分是：
算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。
运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。
例如a:
=b*c+b*d的四元式表示如下：
（1）（*,b,c,t1）
（2）（*,b,d,t2）
（3）（*,t1,t2,t3）
（4）（:
=,t3,—,a）
四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。
也就是说，四元式之间的联系是通过临时变量实现的。
四元式表示很类似于三地址指令，有时把这类中间表示称为“三地址代码”因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条“指令”包含操作符和三个地址，两个是为运算对象的，一个是为结果的。
这种表示对于代码优化的目标代码生成都较有利。
为了更直观，把四元式的形式写成简单赋值形式。
比如把上述四元式序列写成：
（1）t1：
=b*c
（2）t2：
=b*d
（3）t3：
=t1+t2
（4）a：
=t3
把（jump，—，—，L）写成gotoL
把（jrop，B，C，L）写成ifBropCgotoL
为了叙述的方便，两种形式我们将同时使用。
第四节简单赋值语句的翻译
在第三节的四元式中，使用变量名字本身表示运算对象ARG1和ARG2，用ti表示RESULT。
在实际实现中，它们或者是一个指针，指向符号表的某一登录项，或者是一个临时变量的整数码。
在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登录项。
首先对id表示的单词定义一属性id.name，用做语义变量，用Lookup（id.name）表示审查id.name是否出现在符号表中，如在，则返回一指向该登录项的指针，否则返回nil。
语义过程emit表示输出四元式到输出文件上。
语义过程newtemp表示生成一临时变量，每调用一次，生成一新的临时变量。
语义变量E.place，表示存放E值的变量名在符号表的登录项或一整数码（若此变量是一个临时变量）下面，列出了翻译赋值语句到四元式的语义描述。
这里的语义工作包括对变量进行“先定义后使用”的检查。
（1）S→id：
=E{p：
=lookup（id.name）；
ifp≠nilthen
emit（p′：
=′E.place）
elseerror}
（2）E→E1+E2{E.place：
=newtemp；
emit（E.place′：
=′E1.place′+′E2.place）}
（3）E→E1*E2{E.place：
=′E1.place′*′E2.place）}
（4）E→—E1{E.place：
=newtemp；
=′′uminus′E1.place）}
（5）E→（E1）{E.place：
=E1.place}
（6）E→id{p：
=lookup（id.name）}；
ifp≠nilthen
E.place：
=p
第五节布尔表达式的翻译
程序设计语言中的布尔表达式有两个作用。
一是计算逻辑值，二是用做改变控制流语句中的条件表达式，如if-then,if-then-else，或是while-do语句中那样。
布尔表达式是由布尔算符（and,or和not）（或表示∧∨和乑）施于布尔变量或关系表达式而成。
即布尔表达式的形式为E1ropE2，其中E1和E2都是算术表达式，rop是关系符，如〈=<
，=，〉=，≠等等。
我们考虑如下文法生成的布尔表达式。
E→EandE|EorE|notE|idropid|true|false按通常习惯，约定布尔算符的优先顺序（从高到低）为乑、∧、∨，并且∧和∨服从左结合。
一、布达表达式的翻译方法
计算布尔表达式的值有两种办法，第一种办法，如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。
例如，用数1表示true，用0表示false。
那么布尔表达式1or（not0and0）or0的计算过程是：
1or（not0and0）or0
=1or（1and0）or0
=1or0or0
=1or0
=1
另一种计算方法是采取某种优化措施，只计算部分表达式，例如要计算AorB，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，AorB的值都为1。
上述两种方法对于不包含布尔函数调用的表达式是没有什么差别的。
但是，假若一个布尔式中会有布尔函数调用，并且这种函数调用引起副作用（如有对全局量的赋值）时，这两种方法未必等价。
采用哪种方法取决于程序设计语言的语义，。
若按第一种办法计算布尔表达式。
布尔表达式aorbandnotc翻译成四元式序列为：
=notc
（2）t1：
=bandt1
（3）t1：
=aort2
对于像a<
b这样的关系表达式，可看成等价的条件语句ifa<
bthen1else0，它翻译成的四元式序列为：
（1）ifa<
bgoto（4）
（2）t：
=0
（3）goto（5）
（4）t：
（5）…
其中用临时变量t存放布尔表达式a<
b的值，（5）为后续的四元式序号。
下面给出了按第一种办法计算布尔表达式的值，将布尔表达式翻译成四元式的描述，其中nextstat给出的输出序列中下一四元式序号。
emit过程每被调用一次，nextstat增加1。
E→E1orE2{E.place：
emit（E.place′：
=′E1.place′or′E2.place）}
E→E1andE2{E.place：
=′E1.place′and′E2.place）}
E→notE1{E.place：
=newtemp：
；
=′not′E1.place）}
E→（E1）{E.place：
E→id1relopid2{E.place：
emit（′if′id1.placerelop.opid2.place′goto′nextstat+3）；
=′′0′）
emit（′goto′nextstat+2）
=′′1′）}
E→ture{E.place：
E→false（{E.place：
=′′0′）}
二、控制语句中布尔表达式的翻译
现在讨论出现在if-then；
if-then-else和while-do等语句中的布尔表达式E的翻译。
这三种语句的语法为：
S→ifEthenS1|ifEthenS1elseS2
|whileEdoS1
这些语句的代码结构示意分别在图7-5-1（a）（b）（c）中，其中使用·
和。
两个出口分别用于表示E为真和假时控制流向的转移。
分别叫真出口和假出口。
作为条件转移的E，仅把E翻译成代码是一串条件转和无条件转四元式。
翻译的基本思路是，对于E为aropb的形式生成代码为：
ifaropbgotoE.true和
gotoE.false
其中，使用E.true和E.false分别表示E的“真”“假”出口转移目标。
对于E为E1orE2的形式，若E1是真，则可知道E为真即E1的真出口和E的真出口一样。
如果E1是假，那么必须计算E2，E1的假出口就是E2代码的第一个四元式标号，这时E2的真出口和假出口分别与E的真出口和假出口一样。
类似的考虑适于E1andE2的情形。
┐E1的翻译理解容易，只需调换E1的真假出口即可得到E的真假出口。
例如布尔表达式a＜borc＜dande＞f翻译为如下四元式序列：
（1）ifa＜gotoE.true
（2）goto3
（3）ifc＜dgoto5
（4）gotoE.false
（5）ife＞fgotoE.true
（6）gotoE.false
当然生成的四元式显然不是最优的，如
（2）是不需要的。
这种问题可留待代码优化阶段解决。
在上例中，我们使用E.ture和E.false分别表示整个表达式a＜borc＜dande＞f的真、假出口，而E.false的值并不能在产生四元式的同时就知道的。
为了看清这一点，我们把该表达式放在条件语句中考虑，如语句
ifa＜borc＜dande＞fthenS1elseS2四元式序列为
（1）ifa＜bgoto（7）/*（7）是整个布尔表达式的真出口*/
（2）goto（3）
（3）ifc＜dgoto（5）
（4）goto（p+1）/*（p+1）是整个布尔表达式的假出口*/
（5）ife＜fgoto（7）
（6）goto（p+1）
（7）（关于S1的四元式）
（p）goto（q）
（p+1）（关于S2的四元式）
（q）
上述四元式
（1）和（5），（4）和（6）的转移地址并不能产生这些四元式的同时得知。
例如
（1）和（5）的转移地址是在整个布尔表达式的四元式产生完毕之后才得知。
因此要回填这个地址。
为了记录需回填地址的四元式，常采用一种“拉链”的办法。
把需回填E.true的四元式拉成一链，把需回填E.false的四元式拉成一链，分别称做“真”链和“假”链。
拉链的方式是这样的，若有四元式序列：
（10）…gotoE.true
（20）…gotoE.true
（30）…gotoE.true
则链成
（10）…goto（0）
（20）…goto（10）
（30）…goto（20）
把地址（30）称作链首，0为链尾标志，即地址（10）为链尾。
第六节控制结构的翻译
一、开关语句
开关语句（case语句或swith语句）是很多程序设计语言中都有的，方式不尽相同。
。
我们假定要讨论的开关语句的形式为：
switchEof
caseV1:
S1
caseV2:
S2
caseVn-1:
Sn-1
default:
Sn
end
这里的E是一个表达式。
开关语句是分情形选择机制，在E被计算之后，测试它的值符合哪种case中的值，而执行和该值相关的语句，并做相应的转移。
如果E的值不能与任何Vi（1≤i≤n-1）匹配，便执行“default”时的语句。
直观上看，case语句可翻译成如下的一连串条件转移语句。
t:
=E;
L1:
if≠V1gotoL2;
S1;
gotonext;
L2:
ift≠V2gotoL3;
S2
Ln-1:
ift≠Vn-1gotoLn;
Sn-1;
Ln:
Sn;
next:
还可以采用另外的实现办法，这种办法是建立一个n项的二元组表。
第一元为Vi的值，第二元为Vi对应的语句Si的标号（或序号）。
编译程序构造一张这样的表，产生把选择子E的值传送到该表末项第一元的指令。
该项的另一元是缺省情况（default）的语句号。
并构造一个对E值查该表的程序，即该程序把E的值和二元组表项中的各个Vi值相比，若与某个Vi匹配，就去执行相应的Si，如果找不到这样的Vi，则末项自动匹配，便去执行Sn。
下面（图7-6-1）给出开关语句的一种翻译结果（中间代码），其中把所有的测试都放在最后，以便目标代码生成阶段产生高质量的目标指令。
计算E值、并把结果放到临时变量t的中间代码
gototest
L
升级会员 