编译原理第5章 语义分析及中间代码产生

1、第五章语法制导翻译和中间代码产生2022年5月10日星期二1第五章语法制导翻译和中间代码产生2022年5月10日星期二2根据语法成分的结构，分析其含义，并用一种内部形式（中间代码）或直接用目标语言表示出来。具体：静态语义检查和翻译包括：类型检查（操作符是否相容，例如%） 控制流检查（break是否有switch和for,while） 一致性检查（int a; float a;） 相关名字检查、等等第五章语法制导翻译和中间代码产生2022年5月10日星期二35.1 一般原理和树变换5.2 简单SDTS和自上而下翻译器5.3 简单后缀SDTS和自下而上翻译器5.4 抽象语法树的构造5.5 属性文法

2、5.6 中间代码形式5.7 属性翻译文法的应用第五章语法制导翻译和中间代码产生2022年5月10日星期二4 语法制导翻译法语法制导翻译法SDTS是一个五元组 T=(VT,VN,R,S)。VT是一个有穷的输入字母表，包含源语言中的符号；VN是一个有穷的非终结符号集合；是一个有穷的输出字母表，包含出现在翻译串中的那些符号；R是形如Aw,y的规则的有穷集合，w是由终结符或非终结符组成的串，y是由VN或中的符号组成的串；SVN是一个开始符号。第五章语法制导翻译和中间代码产生2022年5月10日星期二5例如：SDTS T1=(a,b,c,+,-,E,T,A,ADD,SUB,NEG,x,y,z,R,E)，

3、其中R由下列翻译规则组成： EE+T , T E ADD EE-T , E T SUB ET, T NEG ET , T TE , E TA , A Aa , x Ab , y Ac , z T1的基础源文法基础源文法是EE+T|E-T|-T|TTE|AAa|b|cT1的基础目标文法基础目标文法是ET E ADD|E T SUB| T NEG |TTE|AAx|y|z第五章语法制导翻译和中间代码产生2022年5月10日星期二6 一个翻译模式翻译模式是一个形如(u,v)的串对，其中，u是SDTS基础源文法的一个句型，而v称为与其对应的翻译，它是由VN和中元素组成的串。翻译模式的定义如下： (S,

4、S)是一个翻译模式，且这两个S是相关的(S是SDTS的开始符号)。 (aAb,aAb)是一个翻译模式，且两个A是相关的；此外，若Ag,g是R中的一条规则，那么(agb,agb)也是一个翻译模式。规则中g和g的非终结符之间的相关性也必须带进这种翻译模式之中。表示法 (aAb, aAb)=(agb,agb)表示一种翻译模式到另一种翻译模式的变换。第五章语法制导翻译和中间代码产生2022年5月10日星期二7u 树变换语法制导的翻译过程也可用语法树变换来说明。 从中剪掉终结符号节点； 根据适当的翻译规则，重排每个中间结点的孩子；添加对应于输出符号集中的中间符节点。第五章语法制导翻译和中间代码产生202

5、2年5月10日星期二8 如果在每一规则的翻译成分中，非终结符出现的次序与它们在源成分中出现的次序相同，则称一个SDTS是简单的简单的(simple)；但是，如果AA1+A2 , A2 A1 ADD是SDTS T 的一个规则，那么，该SDTS T就是不简单的。第五章语法制导翻译和中间代码产生2022年5月10日星期二9 如果T=(VN,VT,R,S)是其基础源文法为LL(k)的简单SDTS，那么，存在一个自上而下的确定的下推翻译器PDT(Push-Down Translater)，它接受T的输入语言中的任何符号串并产生对应的输出串。PDT P的定义如下：P的一个构形是一个四元组(q,x,y,z)

6、，其中，q是它的有穷控制器的状态，x是尚待扫描的输入串，y是下推栈，z是此时被打印出的输出符号串。于是，在某次移动中，便有(q,ax,Yy,z)(r,x,gy,zz)即，在状态q面临输入符号a且栈顶符号为Y时，P才允许移动到状态r，这一移动的结果是：输入符号a被去掉，栈顶符号Y被g所替换，而且串z已作为输出串打印出。第五章语法制导翻译和中间代码产生2022年5月10日星期二10称w是关于x的输出，如果对于某个状态q和栈符号串u，存在(q0,x,Z0,)(q,u,w)其中，q0是初态；Z0是栈的初始内容，为空串。若u，则称P停止于空栈；若q是某个终态，则称P停止于终态。如果P满足下述两个条件，则

7、称P是确定的确定的： 对所有的状态q，输入串a和栈符号Z，(q,a,Z)至多只包含一个元素；若(q,Z)非空，则不存在符号a(a)使得(q,a,Z)非空，即对于某个状态和栈符号，在空移动和非空移动之间不应存在冲突。第五章语法制导翻译和中间代码产生2022年5月10日星期二11PDT P的操作为：在一应用移动中，非终结符A已位于栈顶，借助于分析表，选定产生式Aw来进行归约。假定R中的翻译规则为Aw , z其中，w=a0B1a1B2a2Bkak，而z=b0B1b1B2Bkbk。其中，Bi是非终结符，ai是输入符号串，bi是输出符号串。 位于栈顶的A由下面的复合串b0a0B1b1a1B2Bkbkak

8、 所替代，而b0称为新栈顶符号。若栈顶符号是输出字母表的一个元素，则从栈中弹出，并将其作为输出符号打印出。若栈顶符号是输入字母表VT的一个元素，则它应与当前输入符号匹配。从栈顶弹出它，输入指针后移。第五章语法制导翻译和中间代码产生2022年5月10日星期二12如果一个SDTS是简单的，而且它的每个翻译规则都有下述形式：Aa0B1a1B2a2Bkak , B1B2Bkw也就是说，除了最右边的w之外，（输出）终结符不可能出现在翻译成分之中，那么，称这个SDTS为简单后缀的简单后缀的(Simple Post Fix)。定理定理：对其基础源文法为LR(k)的每一简单后缀的SDTS，存在一确定的LR(k

9、)PDT：它接受从该基础源文法可推导出的每一句子； 它将这种句子的翻译作为输出。 后缀翻译 IF-THEN-ELSE控制语句 函数调用第五章语法制导翻译和中间代码产生2022年5月10日星期二13抽象语法树抽象语法树AST(Abstract-Syntax tree)是某个语言结构的一种简洁的树形表示形式，它只需包含该结构尚须转换或归约的信息。语法树简化成一个AST：去掉于单非产生式（即右部为单一终结符的产生式）相关的子树，并上提相关分支上的终结符号节点。对于直接包含运算符的多个子树，上提运算符并让它取代其父节点。去掉括号，并上提运算符，让它取代其节点。 最后得到的语法树便是一个AST。第五章语

10、法制导翻译和中间代码产生2022年5月10日星期二14一般用来描述客观存在的事物或人的特性。例如，学生的姓名、年龄、性别等；商品的颜色、重量、单价等。编译技术中用属性来描述计算机处理对象的特征。例如：X Type , X Place , X val等分别描述X的类型，存储位置、值等不同的特征。属性分两类：综合属性：一般用于“自下而上”传递信息。继承属性：一般用于“自上而下”传递信息。第五章语法制导翻译和中间代码产生2022年5月10日星期二15对于某个压缩了的上下文无关文法，当为每个文法符号引进一组属性，且让该文法中的重写规则附加以语义规则时，称该上下文无关文法为属性文法。一个属性文法形式上定

11、义为一个三元组AG, AG=(G , V , E)。其中G表示一个上下文无关文法；V表示属性的有穷集；E表示属性的断言或谓词的有穷集。第五章语法制导翻译和中间代码产生2022年5月10日星期二16从语法分析树的角度来看，如果一个结点的某一属性，其值由子结点的属性之值来计算，则称该属性为综合属性。综合属性用于“自下而上”传递信息。 第五章语法制导翻译和中间代码产生2022年5月10日星期二17例例1：算术表达式求值的属性文法。：算术表达式求值的属性文法。规则式规则式语义规则语义规则1.LEprint(E.val)2.EE1+TE.val:=E1.val+T.val3.ETE.val:=T.val

12、4.TT1*FT.val:=T1.val*F.val5.TFT.val:=F.val6.F(E)F.val:=E.val7.FdigitF.val:=digit.lexval 第五章语法制导翻译和中间代码产生2022年5月10日星期二18LE.val=19F.val=5+T.val=4T.val=15F.val=4digit.lexval=4E.val=15T.val=3digit.lexval=5F.val=3digit.lexval=3*n第五章语法制导翻译和中间代码产生2022年5月10日星期二19语法树分析中，若一个结点的某个属性之值由该结点的兄弟结点和/或父结点的属性之值来计算，则此

13、结点的属性称为继承属性。 继承属性用于“自上而下”传递信息。第五章语法制导翻译和中间代码产生2022年5月10日星期二20例2、说明语句中简单变量类型信息的属性文法。规则式语义规则1.DTLL.in:=T.type2.TintT.type:=integer3.TrealT.type:=real4.LL1 ,idL1.in:=L.inaddtype(id.entry , L.in)5.Lidaddtype(id.entry , L.in)T有一个综合属性有一个综合属性type，其值为其值为integer或或real。L.in由由T.type确定确定后逐步传递到下边有关结点使用。后逐步传递到下边有

14、关结点使用。这种属性称为继承属性。这种属性称为继承属性。第五章语法制导翻译和中间代码产生2022年5月10日星期二21 终结符号只有综合属性，它们由词法分析器提供。 非终结符号既有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。第五章语法制导翻译和中间代码产生2022年5月10日星期二22语法制导翻译法的基本思想：语法制导翻译法的基本思想：对文法的每一条产生式，设计语义子程序。在语法分析的过程中，当使用一条产生式推导或归约时，调用该语义子程序进行属性计算，完成预定的翻译工作。语法制导翻译法：语法制导翻译法：在语法分析的过程中，依随分析过程，根据每个产生式添加的语义动作

15、进行翻译的方法。第五章语法制导翻译和中间代码产生2022年5月10日星期二23语义子程序也称为翻译子程序，语义动作。它描述了有关产生式所对应的翻译工作。语义动作一方面指出了产生式所对应的符号串的意义；另一方面又按照这种意义规定了对应的属性计算加工动作。语义动作：查填各种表格计算某变量的值生成某种中间代码打印错误信息等等第五章语法制导翻译和中间代码产生2022年5月10日星期二241、为文法产生式设计语义子程序。2、为文法构造一张无冲突的LR分析表。3、修改总控程序，归约时调用语义子程序。4、扩充LR分析栈，用来存放各文法符号对应的语义信息。例如：(1).EE1+E2E.val=E1.val+E

16、2.val(2).EE1*E2E.val=E1.val*E2.val(3). E(E1)E.val=E1.val(4).EdigitE.val=lex.digit第五章语法制导翻译和中间代码产生2022年5月10日星期二25#第五章语法制导翻译和中间代码产生2022年5月10日星期二26扩充的LR分析栈：?S0?#?-状态栈状态栈文法符号栈文法符号栈语义值栈语义值栈E.val=7E.val=1 + E.val=6 1 E.val=2 * E.val=3 2 3第五章语法制导翻译和中间代码产生2022年5月10日星期二27第五章语法制导翻译和中间代码产生2022年5月10日星期二28一、逆波兰式

17、二、三元式与间接三元式三、树形表示法四、四元式第五章语法制导翻译和中间代码产生2022年5月10日星期二291、逆波兰式（后缀式）：每一运算符都置于其运算对象之后。（无括号表达式）A*BAB*A+B*CABC*+(A+B)*(C+D)AB+CD+*(a=0&b3)|(e&x!=y)a0=b3&exy!=&|第五章语法制导翻译和中间代码产生2022年5月10日星期二30文法：0 EE空1EE(1)+E(2)print +2EE(1)*E(2)print *3E(E(1)空4Eiprint i步骤步骤状态栈状态栈符号栈符号栈输入符号输入符号输出区输出区10#a+b*c#203#a+b*c#301#

18、E+b*c#a4014#E+b*c#a50143#E+b*c#a60147#E+E*c#ab701475#E+E*c#ab8014753#E+E*c#ab9014758#E+E*E#abc100147#E+E#abc*1101#E#abc*+第五章语法制导翻译和中间代码产生2022年5月10日星期二31一般形式一般形式： （op，AG1，AG2）例如：a:=-b*(c+d)三元式为：（，b， ）（+，c， d ）（*，）（:=，a）第五章语法制导翻译和中间代码产生2022年5月10日星期二32例如：语句X:=(A+B)*CY:=D(A+B)间接代码opAG1AG2+AB*C:=XD:=Y第五章

19、语法制导翻译和中间代码产生2022年5月10日星期二33抽象语法树：抽象语法树：在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种变换后的语法树称为抽象语法树。+*4353*5+4 的抽象语法树第五章语法制导翻译和中间代码产生2022年5月10日星期二34 树形表示 A * B + C*D +C*A*BD 末端结点表示一个运算对象, 每一个内结点表示一个一元或二元运算符。树形表示是三元式的翻版(3)+(1)*(2)*CABD第五章语法制导翻译和中间代码产生2022年5月10日星期二35一般形式一般形式： (op，AG1，AG2，result)直观形式：直观形式： res

20、ult:=AG1 op AG2例如：求x:=a+b*c的四元式。(*，b，c，T1 )直观式： T1:=b*c(+，a，T1，T2)T2:=a+T1(:=，T2 ， ，x )x:=T2第五章语法制导翻译和中间代码产生2022年5月10日星期二36 采用自下而上的语法制导翻译法语义 动作的设计（1）搞清楚源结构和目标结构（2）自下而上的语法制导翻译特点： 栈顶形成句柄，归约时执行相应语义 动作（3）给出从源结构到目标结构的变换 方法第五章语法制导翻译和中间代码产生2022年5月10日星期二37例. 设文法及其相应的语义动作如下: Sa print “2” SbTc print “1” TR pr

21、int “3” RR/S print “4” RS print “5” 采用自下而上语法制导翻译,给出输入串bR / bTc / bSc / ac的翻译结果 第五章语法制导翻译和中间代码产生2022年5月10日星期二38分析: 首先对输入串 bR / bTc / bSc /ac画出语法树:ScTbRS/R/RS/RcTbaScTbRS再考虑归约时执行相应语义动作第五章语法制导翻译和中间代码产生2022年5月10日星期二39ScTbRS/R/RS/RcTbaScTbRS SbTc print “1” Sa print “2” TR print “3” RR/S print “4” RS prin

22、t “5” 14翻译结果为:53142431第五章语法制导翻译和中间代码产生2022年5月10日星期二40定义几个过程和函数：lookup()：检查是否出现在符号表中，如果在，则返回其指针；否则，返回 NULL 表示没有找到。emit（result:=AG1 op AG2）：产生一个四元式，并填入四元式表中。newtemp( )：该函数返回一个新的临时变量。第五章语法制导翻译和中间代码产生2022年5月10日星期二41文法：文法：P2161. S i= E p Lookup (); if (p = NULL) error( ); else emit(pE

23、.place 2. E E(1) E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).place ) 3. E E(1) * E(2) E.place newtemp( ); emit(E.placeE(1).place* *E(2).place ) 4. E （E(1)） E.place E(1).place；5. E i p Lookup (); if (p != NULL) E.place p; else error( ); 第五章语法制导翻译和中间代码产生2022年5月10日星期二42算术表达式a+b*c翻译到三地址语句的

24、过程： 030$a01$E014$E+0143$E+baaa状态栈符号栈语义栈输入串a+b*c$+b*c$+b*c$b*c$*c$ 第五章语法制导翻译和中间代码产生2022年5月10日星期二43*c$c$t1=b*c t2=a+t1 状态栈符号栈语义栈输入串014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E01$Eab abcat1ababt2acc第五章语法制导翻译和中间代码产生2022年5月10日星期二441、EE E2、EE E3、E E4、E(E)5、Eid rop id6、Eid第五章语法制导翻译和中间代码产生2022年5月10日星期

25、二45（求每个因子，再求表达式的值）例如：布尔表达式 ： a b c三地址序列： T1:= cT2:=b T1T3:=a T2第五章语法制导翻译和中间代码产生2022年5月10日星期二461. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 2. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 3. E E (1) E.place newtemp( )； emit ( E.place E(1).place4.

26、 E ( E (1) ) E.place E(1).place； 5. E i (1) rop i (2) E.place newtemp( )； emit (if i (1).place rop.op i (2).place goto next+3); emit ( E.place 0 ); emit ( goto next+2); emit ( E.place 1 ); 6. E i E.place i . place； 第五章语法制导翻译和中间代码产生2022年5月10日星期二47第五章语法制导翻译和中间代码产生2022年5月10日星期二48A Bif A then trun else

27、BA Bif A then B else false A if A then false else true对非终结符E赋予两个出口真出口：布尔表达式为真时，需转移的四元式地址。假出口：布尔表达式为假时，需转移的四元式地址。第五章语法制导翻译和中间代码产生2022年5月10日星期二49设置两个语义变量：E.ture : 用来记录表达式E对应的四元式需回填真出口的四元式的地址所构成的链。E.false:用来记录表达式E对应的四元式需回填假出口的四元式的地址所构成的链。定义三个函数：第五章语法制导翻译和中间代码产生2022年5月10日星期二50把以P1和P2为链首的两条链合并为一，返回合并后的链首

28、（当P2=0时，返回P1 ; 当P20时，返回P2）。int merge(int P1 , int P2 ) int P;if (! P2) return P1;else P=P2 ;while (P.result 0)P=P.result; P.result=P1;return P2 ; 第五章语法制导翻译和中间代码产生2022年5月10日星期二51把p所链接的每个四元式的第四分量都回填为t。void BP( int p , int t ) int q=p ;while (q) int q1=q.result ; q.result =t ;q=q1 ;return;创建一个仅含i的新链表。第

29、五章语法制导翻译和中间代码产生2022年5月10日星期二52定义三种四元式：(jnz , a ,- , p)if a goto p(当a为真时转向第p四元式）(jrop , x , y , p)if x rop y goto p(j , - , - , p)goto p (无条件转向第p四元式)四元式表的指针nextquad（nextq）：每执行一次emit后，nextq自动加1。 E.code：为及时回填转移地址, 使用语义变量 E.code 记录表达式E的第一个四元式语句序号。第五章语法制导翻译和中间代码产生2022年5月10日星期二531. E i E.tr= next ; E.fa=

30、next +1; E.code= next ; emit(if i.place goto -); emit( goto _ ) ;2. E i (1) rop i (2) E.tr= next ; E.code= next ; E.fa= next+1; emit ( if i (1).place rop.op i (2).place goto _ ) ; emit( goto _ ) ; 3. E ( E (1) ) E.code= E(1).code ; E.tr=E(1).tr ; E.fa= E(1).fa ; 4. E E (1) E.tr=E(1).fa ; E.fa= E(1).tr