编译原理6语义分析和中间代码生成

1、词法分析和语法分析之后的中间代码生成，是编译第三阶段的工作。本章介绍几种典型的中间代码形式，以及产生它的算法。中间代码的形式很多，如逆波兰记号、树形表示、三元式、四元式。他们都是介于单词流与目标指令之间的“中间产品”。目前还不存在一种广泛接受的方式来描述为典型程序语言产生中间代码所需的邻语言的动作。原因是代码生成依赖于对语义的解释，而语义的刻划的形式化系统尚未诞生。为每一个产生式配一个翻译子程序（语义子程序、动作），在语法分析的同时执行它。这样，配上语义动作之后，既指定了串的意义，同时又按这种意义规定了生成某种中间代码应作的基本动作。l语法制导翻译语法制导翻译l逆波兰表示法逆波兰表示法l三元式

2、和树三元式和树l四元式四元式l简单算术表达式和赋值句到四元式的翻译简单算术表达式和赋值句到四元式的翻译l布尔表达式到四元式的翻译布尔表达式到四元式的翻译l控制语句的翻译控制语句的翻译l数组元素的引用数组元素的引用l过程调用过程调用l说明语句的翻译说明语句的翻译l自上而下分析制导翻译概说自上而下分析制导翻译概说在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（语义动作）进行翻译（产生中间代码）的办法。概念标记说明标记说明l描述语义动作时，需要赋予每个文法符号X（终结符或者 非终结符）以种种不同方面的值，如X.TYPE(类型），X.VAL(值）等。l一个产生式中同一符号多次出

3、现，用上角标来区分。 E E + E 表示为 E E(1) + E(2)l每个产生式的语义动作，写在该产生式之后的花括号 内。#-S0XX.VALSm-1YY.VALSm文法符号，无须进栈，让其进栈只是为了醒目。需要保存的某些语义信息。实际上为一个指示器，指向分析表的某一行。l先对LR分析器的栈作一些改进，加入语义值。STATEVALSYMTOPl文法及其语义动作(0)S E print E.VAL(1)EE(1)+E(2) E.VAL:=E(1).VAL+E(2).VAL(2)EE(1)*E(2) E.VAL:=E(1).VAL*E(2).VAL(3)E(E(1) E.VAL:=E(1).V

4、AL(4)En E.VAL:=LEXVAL上述的语义动作等于给出了计算由、*组成的整数算术式的过程。其相应的程序段如下：(0)S E print VALTOP(1)EE(1)+E(2) VALTOP:=VALTOP+VALTOP+2(2)EE(1)*E(2) VALTOP:=VALTOP*VALTOP+2(3)E(E(1) VALTOP:=VALTOP+1(4)En VALTOP:=LEXVAL若把语义动作改为产生中间代码的动作，就能随着分析的进展逐步生成中间代码。属性文法属性文法(attribute grammar)属性文法属性文法( (也称属性翻译文法也称属性翻译文法) )是是KnuthK

5、nuth在在19681968年首年首先提出的。先提出的。它是在上下文无关文法的基础上，为每个文法符它是在上下文无关文法的基础上，为每个文法符号号( (终结符或非终结符终结符或非终结符) )配备若干相关的配备若干相关的“特性特性”（称（称为属性）。为属性）。这些属性代表与文法符号相关信息，例如它的类这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算对于文法的

6、每个产生式都配备了一组属性的计算规则，称为规则，称为语义规则语义规则。 所谓属性，其涉及的概念比较广泛，常用以描述所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。事物或人的特征、性质，品质等等。对编译程序使用的语法树的结点，可以用对编译程序使用的语法树的结点，可以用 类型类型 、 值值 或或 存储位置存储位置 来描述它。来描述它。 一个属性文法包含一个上下文无关文法和一系列一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。语义规则，这些语义规则附在文法的每个产生式上。所谓语法制导的翻译指的是在语法分析过程中，所谓语法制导的翻译指的

7、是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。完成这些语义规则描述的动作，从而实现语义处理。属性文法定义属性文法定义定义定义1： 形式上讲，属性文法是一个三元组形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中：其中：G:是一个上下文无关文法；是一个上下文无关文法；V:有穷的属性集有穷的属性集,每个属性与文法的一个终结符或非终每个属性与文法的一个终结符或非终结符相连结符相连,这些属性代表与文法符号相关信息；这些属性代表与文法符号相关信息；F:关于属性的属性断言或一组属性的计算规则关于属性的属性断言或一组属性的计算规则(称为语称为语义规则义规则) 。 断言或语义规则

8、与一个产生式相联断言或语义规则与一个产生式相联,只引只引用该产生式左端或右端的终结符或非终结符相联的用该产生式左端或右端的终结符或非终结符相联的属性。属性。 定义定义2 2：一个属性文法是一个三元组：一个属性文法是一个三元组：A=(G,V,F ),A=(G,V,F ),其中其中uG -G -基础文法（基础文法（一个上下文无关文法一个上下文无关文法）uV -V -每个文法符号有一组属性每个文法符号有一组属性uF -F -每个文法产生式每个文法产生式A A有一组形式为有一组形式为b b:=:=f f( (c c1 1, ,c c2 2,c ck k) )的语义规则，其中的语义规则，其中f f 是函

9、数，是函数，b b和和c c1 1, ,c c2 2,c ck k是该产生式文法符号的属性。是该产生式文法符号的属性。 属性的类型（从分析过程中属性值的计算方法来分类）：1、综合属性综合属性（Synthesized Attributes）：属性值是分析树中该结点的子结点的属性值的函数 2、继承属性继承属性（Inherited Attributes）：属性值是分析树中该结点的父结点和和/或或兄弟结点的属性值的函数对于产生式 AX1 X2 XnA AX X1 1X X2 2X Xn n计算 A 的综合属性, S ( A ) : = f ( I ( X1 ) , , I ( Xn ) )计算 Xj

10、的继承属性, T ( Xj ) : = f ( I ( A ) , ., I ( Xn ) )v综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息例例1 1 综合属性的例子综合属性的例子语 义 规 则 L EE E1+TETT T1 * FTFF(E)FdigitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产 生 式非终结符非终结符E、T及及F都有一个综合属性都有一个综合属性val,符号符号digit仅有仅

11、有一个综合属性一个综合属性，它，它的值由词法分析器的值由词法分析器提供。产生式提供。产生式L E语义规则是一个语义规则是一个过程过程,打印打印E的值的值,也可以理解也可以理解L的属的属性是空的或虚的。性是空的或虚的。综合属性的自下而上定值综合属性的自下而上定值LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树例例2继承属性的例子继承属性的例子产 生 式语 义 规 则D TL T int T rea

12、l L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)L.in 属性值置为该说明语句指定的类型，是继承属性继承属性。Addtype是一个过程，功能是把每个标识符的类型信息登陆在符号表的的相关项中。在表所示的语法制导翻译中，非终结符在表所示的语法制导翻译中，非终结符D D产生的声明由产生的声明由关键字关键字intint或或realreal及标识符表组成，非终结符及标识符表组成，非终结符T T有综合属有综合属性性typetype，它的值

13、由声明中的关键字决定。，它的值由声明中的关键字决定。 继承属性的自上而下定值继承属性的自上而下定值Real id1,id2,id3DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.，产 生 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)属性依赖图属性依赖图依赖图是一个有向图，用于描述分析树中的属性和属性之依赖图是一个

14、有向图，用于描述分析树中的属性和属性之间的相互依赖关系。间的相互依赖关系。依赖图构造算法：依赖图构造算法：for 语法树中每一结点语法树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for 语法树中每一个结点n do for 结点n所用产生式对应的每一个语义规则 b:=f(c1，c2，ck) do for i:=1 to k do 从ci结点到b结点构造一条有向边；注注:在构造依赖图之前在构造依赖图之前,要为每一个过程调用的语义规则引入一要为每一个过程调用的语义规则引入一个虚综合属性，即在依赖图中构造一个结点。这样，个虚综合属性，即在依赖图中构造

15、一个结点。这样，若属性若属性b依赖于属性依赖于属性c，则从，则从c的结点有一条有向边连接到的结点有一条有向边连接到b的结点的结点。D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 typeint id1, id2, id3的依赖图的依赖图产 生 式语 义 规 则D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)大部分的编译器都不直

16、接产生目标代码，虽然这是可以实现的，但是产生的代码不是最优的。因为这涉及到寄存器的分配问题，在语义分析阶段，很难有效地分配它们。中间代码的必要性引入中间代码的目的1. 方便生成目标代码；2. 便于优化；3. 便于移植。波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示法。一般，若e1,e2为任意的后缀表达式， 为任意双目运算符，则用作用于e1和e2所代表的结果用后缀式e1e2 表示。推而广之， 为k目运算符，则作用于e1e2ek的结果用e1e2ek 来表示。概念l a * ( b + c ) abc+*l(a + b)*(c + d) ab + cd +*若用？表示if-then-

17、else,则lIf a then if c-d then a+c else a*c else a+b a cd- ac+ ac*? ab+?示例使用一个栈（软件栈或者硬件栈）来求值。求值过程：从左到右扫描后缀式，每碰到运算量就把它推进栈，每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果来代替这k个项。a进栈1 1 3 3 + + 5 5* *b进栈ab相加，移去两项，和置于栈顶4 43+1=3+1=c进栈栈顶两项相乘，移去两项，积置于栈顶5 5* *4=4=2020计算完毕，结果为20前面讲到，if-then-else运算符的实现”exy?” e不等于0，取x，否则取y.这种表示法要求在

18、任何情况下都要把x,y都计算出来，尽管只用到其中一个。而且，如果运算量无定义或者有副作用，则后缀表示法不仅无效，而且可能是错误的。引入标号，在后缀式中加入条件转移，无条件转移算符。存储方式后缀式存放在一维数组POST1.N中，每个元素是运算符或者分量（指向符号表）。 p jump 转到POSTp e1e2pjlt e1BC不合法。布尔表达式(E)在语言中的用途 求值 X:=ABD 条件控制 WHILE ABD DO S IF ABD THEN S1 ELSE S2布尔表达式的求值1 通常算法，如同算术表达式求值一样，一步步地计算各部分的值，进而计算出整个表达式的值。2 采用优化措施 AB if

19、 A then true else B AB if A then B else false A if A then false else true说明 上述两种计算方法对于不包含布尔函数调用的式子是没有什么差别的。仅当遇到布尔函数调用，并且这种函数调用引起副作用时，上述两种算法不等价。对于第一种方法而言，可以如同翻译算术表达式一样来翻译布尔表达式。ABC=D 翻译成 = C D T1 B T1 T2 A T2 T3 第二种方法是本节主要内容，下面将详细讨论。 一.IF语句的四元式结构 二.翻译的困难和解决办法 三.E的文法和语义子程序 四.例例 IF ABD THEN S1 ELSE S2E的

20、结构从整体上，E对外只能转向两个目标EE转向E为假时的目标转向E为真时的目标(1) (1) (jnz,A,_,5)(jnz,A,_,5)(2) (j,_,_,3)(2) (j,_,_,3)(3) (3) (j,B,D,5)(j,B,D,5)(4) (4) (j,_,_,p+1)(j,_,_,p+1)(5) (5) (p)(p)(p+1)(p+1)(q)(q)S1S1(j,_,_,q)(j,_,_,q)S2S2 下一语句下一语句 1.1.困难困难 转移的目标在对它的应用之后才出现； (j,_,_,0)(j,_,_,0) E可以很复杂，上面的情况可以频繁出现(1) (1) (jnz,A,_,5)(

21、jnz,A,_,5)(2) (j,_,_,3)(2) (j,_,_,3)(3) (3) (j,B,D,5)(jEEEE|E|(E)|i|i rop i G2 E-E E|EE|E|(E)|i|i rop i E -E E-E 2. 2.语义动作语义动作(1)(2 )(1)(1)(1)(2)(1)(.:;.:1;(,( ), _,0);( , _, _,0).:;.:1;(,(),(),0);( , _, _,0).:.;.:.(1)(2)(3)()(4)E TCNXQ E FCNXQGENjnz ENTRY iGENjE TCNXQ E FCNXQGENjnop ENTRY iENTRY iG

22、ENjE TCETC E FCEFCEiEirop iEEEE (1)(1)1).:.;.:.E TCEFC E FCETC(1)(1)( 2 )( 2 )(1)0(1)( 2 )0( 2 )(1)(2)0(1)0(2)(.,);.:.:.;.:(.,.)(.,);.:.:.;.:(.,.(5)(6)(7)(8)BACKPATCHETC NXQEFCEFCE TCETCE FCMERG EFC EFCBACKPATCHEFC NXQETCETCE FCEFCE TCMERG ETC EEEEE EEEEE E)TC 用自下而上语法分析方法，语法制导生成ABD的四元式)0,();0,)(,(;

23、1.;.) 1)1()1(1JGENiEntryjnzGENNXQFCENXQTCEiE）（.:.);,.()2)1(0)1()1(0TCETCENXQFCEBACKPATCHEE)0 ,();0),(),(,(; 1:.;:.)3)2()1()2()1(，jGENiENTRYiENTRYjropGENNXQFCENXQTCEiropiEAE)1(. 1)0,() 1Ajnz)0,()2jTCE.)1(1FCE.)1(2)1(0.2EE)3,.(FCEB31TCE .0DBE)2(. 3TCE.)2(3FCE.)2(4)0,()3DBj )0,()4j)2(0.4EEE 4FCE.1TCE.3

24、).,.()2(0TCETCEMERG).,.(:.;.:.)4)2(0)2()2(0TCETCEMERGTCEFCEFCEEEE 本小节讨论无条件和条件语句的翻译，只讨论四元式的产生。本节内容l 标号和转移语句l 条件语句l 分叉语句标号的两种使用方法 L: S Goto L语言中允许标号先定义后使用，也允许先使用后定义。(1) 先定义L1 : S1L1 : S1Goto L1Goto L1遇到遇到L1 : S1L1 : S1L1标号 定义P1符号表遇到遇到Goto L1Goto L1(j, _, _, P1)名字类型定义否地址P1 ( )(2) (2) 先使用先使用 q1q1 goto L

25、2goto L2 q2 q2 Goto L2Goto L2 q3 q3 L2 : S2L2 : S2名字类型定义地址L2标号 未 q1遇到goto L2, 填符号表，“未定义”，把NXQ填入L2的地址部分，作为链头。产生( j, _, _, 0)q1 (j, _, _, 0 )遇到goto L2, 查到未定义，取符号表中L2的地址q1填入四元式q2:(j, _, _,q1),将q2填入符号表。 q2 (j, _, _, q1 )q2遇到L2:S2,就可以回填。q3q3q3一般而言，带标号语句产生式 S label S label i:Label i: 的语义动作1. 若i所指的标识符(假定为L

26、)不在符号表中，则把它填入，置类型为“标号”，“定义否”为“已”，地址为NXQ。2, 若 L已在符号表中，但“类型”不为“标号”或者“定义否”为“已”，则报告出错。3. 若L已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链头(记为q)取出，同时把NXQ填在其中，最后，执行BACKPATCH(q,NXQ)。1 较为复杂的程序控制语句常常是嵌套的。 S1后有一条无条件转移指令，跳转到本语句之后。这里，与上一节不同的是，在S2翻译之后，也不能确定其跳转地址，它要跨越S2,S3。 所以，转移地址的确定与语句所处的环境有关。if E1 THENif E2 then S1 else S2ELS

27、E S3 解决办法 令每个非终结符S(L)附带一项语义值S.CHAIN，它指出一条链的头，该链是所有期待翻译完S后回填目标的四元式组成的。注意 回填目标可能是S得下一条四元式，也可能不是。真正的回填，要在处理完S的外层后进行。考虑语句 WHILE E(1) DO S(1) 译为代码结构E(1)的代码S(1)的代码假出口真出口由于语句的嵌套，WHILE翻译完了也未必知道假出口的转移目标，所以作为S(1).CHAIN保留下来,以便伺机回填。While E(1) do S(1)E(1).TCE(1).FCIF E THENELSE S示例示例 S if E then S |if E the S el

28、se S |while E do S |begin L end |A L L; S |S (5.5) S语句 L语句串 A赋值句 E布尔表达式为了能及时回填有关四元式的转移目标，如同处理布尔表达式一样，需要对文法(5.5)进行改写。 S C S | TP S | Wd S | begin L end | A L LS S | S C if E then TP CS else Wd W E do W while LS L; (5.6)语义动作C if E then BACKPATCH (E.TC, NXQ); C.CHAIN := E.FC S C S(1) S.CHAIN := MERG(C.

29、CHAIN, S(1).CHAINTP C S(1) else q := NXQ; GEN(j, _, _, 0); BACKPATCH(C.CHAIN,NXQ); TP.CHAIN := MERGE(S(1).CHAIN,q)S TP S(2) S.CHIAN := MERG(TP.CHIAN, S(2).CHIAN语义动作W while W.QUAD := NXQ Wd W E do BACKPATCH (E.TC,NXQ); Wd.CHAIN := E.FC; Wd.QUAD := W.QUAD S Wd S(1) BACHPATCH(S(1).CHAIN,Wd.QUAD); GEN(j

30、, _, _, Wd.QUAD); S.CHAIN := Wd.CHAIN语义动作L S L.CHAIN := S.CHAINLS L; BACKPATCH(L.CHAIN,NXQ) L LS S(1) L.CHAIN := S(1).CHAINS begin L end S.CHAIN := L.CHAIN S A S.CHAIN := 0 空链IF E THEN S(1) ELSE S(2)CTPS示例示例ES(1)的代码S(2)的代码E的代码E.TCE.FCS(1).CHAINS(2).CHAINC.CHAINBACKPATCH(E.TC,NXQ)S.CHAINMERG(TP.CH,S(

31、2).CH)C IF E THENTP C S(1) ELSES TP S(2)q: ( j, _, _, 0)TP.CHAINBACKPATCH(C.CH,NXQ)MERG(S(1).CH,q)IF E THEN WHILE E(1) DO S(1) ELSE S(2) 的示意图IF E THEN WHILE E(1) DO S(1) ELSE S(2)WCWdS1TPSIFTHENWHILEE 的代码E.TCE.FCC.CHE(1)的代码E(1).TE(1).FWd.CWd.Q=W.QS(1)的代码S(1).C C IF E THENBACKPATCH(E.TC,NXQ); C.CHAIN

32、 := E.FC W WHILEW.QUAD := NXQWd W E(1) DOBACKPATCH(E(1).TC,NXQ); Wd.CHAIN := E(1).FC Wd.quad := W.QUAD S1 Wd S(1)BACKPATCH(S(1).C,Wd.Q); GEN(j,_,_,Wd.Q); S1.C := Wd.C TP C S1 ELSE q := NXQ; GEN(j,_,_,0); BACKPATCH(C.CH,NXQ); TP.C:=MERG(S1.C,q); ELSES(2)的代码S(2).Cq:(j,_,_,0)TP.CS TP S(2) S.CH := MERG(

33、TP.CH,S(2).CH) S.C(j,_,_,Wd.Q)S1.C语句翻译完成，结果如图所示例子While AB DO if CD then X:= Y+ZWE(1)WdE(2)CS(1)S(2)SE(2).TC102 (j,C,D, 0)E(2).FC102103103 (j,_,_, 0)103S(2).CHE(1).FC E(1).TC100101100 (j,A,B, 0)101 (j,_,_, 0 )104 (+,Y, Z, T)WWHILEW.QUAD := NXQW.QUAD:=100E(1) i(1) rop i(2)E(1).TC:=NXQ;E(1).FC:=NXQ+1;G

34、EN(jrop,ENTRY(i(1),ENTRY(i(2),0);GEN(j,_,_,0);Wd W E(1) DOBACKPATCH(E(1).TC,NXQ); Wd.CHAIN := E(1).FC; Wd.QUAD :=W.QUADE(2)i(1) rop i(2)E(2).TC:=NXQ;E(2).FC:=NXQ+1;GEN(jrop,ENTRY(i(1),ENTRY(i(2),0);GEN(j,_,_,0);Wd.CWd.QUAD:=100101102C IF E(2) THENBACKPATCH(E(2).TC,NXQ); C.CHAIN :=E(2).FC104103C.CHE

35、i(1)+i(2) E.PLACE := NEWTEMP; GEN(+,ENTRY(i(1),ENTRY(i(2),E.PALCE)A i:=E GEN(:=,E.PALCE,_,ENTRY(i)105 (:=,T,_, X)S(2) C S(1) S(2).CHAIN := MERG(C.CHAIN,S(1).CHAIN) S Wd S(2) BACKPATCH(S(2).CHAIN,Wd.QUAD); GEN(j,_,_,Wd.QUAD); S.CHAIN := Wd.CHAIN 100106 (j,_,_,100)S.CH101While AB DO if CD then X:= Y+Z

36、语句翻译完成0S(1).CH1 设计属性文法，讨论翻译的一般语义规则。1 产生标志，被转目标，在S.code中出现S.Begin := newlabelE.True := newlabel如 S while E do S1 的语义规则包含四部分：E.CODES1.CODEGoto S.beginS.beginE.tE.f2 “内部的”/可隐藏标志用S.Next及两标志表示。/S.next构成E.F := S.nextS1.next := S.begin3 S.code 的组成 S.code := gen(S.begin :)| E.code| gen(S.true :)| S1.code |

37、gen (goto S.begin)4 对1，2归纳，可知转移目标有两类：一类在S.code和S.next中；另一类是可隐藏的，内部的。2 一遍扫描产生代码，翻译模式。S while M1 E do M2 S2 M M.quad := nextquad S if E then M1 S1 N else M2 S2 b(E.truelist, M1.q); b(E.falselist,M2.q); S.nextlist := merg(S1.nextlist,N.nextlist, S2.nextlist) N N.n := nakelist(nextquad); M M.q := nextquad C if E then b(e.tc, NXQ) C.C := E.FCTP C S1 ELSEq: (j, _,_,_)b(c.c,NXQ)TP.C := merg(S1.c,q);S TP S2 S.C := merg(TP.C, S2.C) 形式: case E of C1: S1 C2: S2 Cn-1: