《《编译原理课程教案》第5章：中间代码生成.ppt》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第5章：中间代码生成.ppt（81页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、语义分析和中间代码生成语义分析和中间代码生成第五章第五章本章要求本章要求主要内容主要内容：语义分析和中间代码的功能，语义分析和中间代码的功能，中间代码的形式，属性文法及语法制导中间代码的形式，属性文法及语法制导的翻译程序，各种语句的语法制导的翻的翻译程序，各种语句的语法制导的翻译过程译过程重点掌握：重点掌握：属性文法，属性文法，语义分析与处理语义分析与处理的方法的方法,中间代码的表示形式，各种语句中间代码的表示形式，各种语句的代码结构，各种语句的翻译方法的代码结构，各种语句的翻译方法语义分析和中间代码生成所处的位置：5.1 概述概述.语义分析和中间代码生成在编译器中的位置：语义分析和中间代码生
2、成在编译器中的位置：静态语义检查：如：类型、运算、数组维数、越界等的检查语义处理：如：变量的存储分配、表达式的求值、语句的翻译(中间代码的生成)总目标：生成等价的中间代码语法分析语义分析和中间代码生成编译的后续阶段语法树中间代码.功能及任务：功能及任务：P166输入-语法分析单位输出 -用中间代码形式表示的文本 -出错处理:定位、继续编译3.为什么要此阶段为什么要此阶段?逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化，这些内部形式也能用于解释。4.什么是中间代码什么是中间代码(Intermediate code)源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标
3、代码的中间表示。5.中间代码的几种形式中间代码的几种形式逆波兰、三元式、间接三元式、四元式、树1 1、逆波兰式、逆波兰式：运算对象写在前，运算符写在后(后缀后缀表示形式)例：a+b ab+(a+b)*c ab+c*a+b*c abc*+a:=b*c+b*d abc*bd*+:=5.2中间代码的几种形式中间代码的几种形式+ab优点：易于计算机处理 利用栈，将扫描到的运算对象入栈，碰到运算符：若是双目运算符，则对栈顶的两个运算对象实施该运算并将运算结果代替这两个运算对象进栈；若是单目运算符，对栈顶元素，执行该运算，将运算结果代替该元素进栈，最后结果即栈顶元素。练习练习写出下列算式的逆波兰表示a+b
4、*(c+d/e)a:=b*(-c)+b*(-34)a:=b*(-c)+b*(-34)notAornot(CornotD)abcde/+*+a b c-*b 34-*+:=a b c-*b 34-*+:=AnotCDnotornotor+a *b +c /d e后缀式的推广后缀式的推广(1)赋值语句A:=E，后缀式为：AE:=(2)转向语句GOTOL的后缀式为：Ljmp(3)条件语句ifxythenm:=xelsem:=y123456789101112 13 14xy11 jezmx:=14jmy:=2 2、三元式、三元式编号（运算符，第一运算数，第二运算数）编号（运算符，第一运算数，第二运算数
5、）如：a：=b*c+b*d(1)（*，b，c）(2)（*，b，d）(3)（+，(1)，(2)）(4)（：=，(3)，a）对于单目运算符，只有一个运算对象，另一个为空对于单目运算符，只有一个运算对象，另一个为空注意：在三元式中的编号既代表了序号，又代表了结注意：在三元式中的编号既代表了序号，又代表了结果的存放位置。果的存放位置。3 3、四元式、四元式P172P172 是目前最常用的中间代码形式:(运算符，第一运算数，第二运算数，结果运算符，第一运算数，第二运算数，结果)例：a:=b*c+b*d(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,a
6、)也可以写成赋值语句形式：(1)t1:=b*c (2)t2:=b*d(3)t3:=t1+t2 (4)a:=t3练习练习求-B+C*D-B+C*D 的逆波兰表示形式、三元式和四元式逆波兰：BCD*+三元式：(1)(-,B,)(2)(*,C,D)(3)(+,(1),(2)四元式：(1)(-,B,t1)(2)(*,C,D,t2)(3)(+,t1,t2,t3)到目前为止，已知到目前为止，已知 输入的语法单位输入的语法单位，又知道又知道 要翻译的结果的形式要翻译的结果的形式，翻译的方法翻译的方法是什么？是什么？语义分析和翻译的方法：语义表示较流行的方法仍然是属性文法，翻译方法是语法属性文法，翻译方法是语
7、法制导的翻译制导的翻译。属性文法属性文法属性文法属性文法:是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。属性属性：代表与文法符号相关的信息，如类型、值、代码序列、符号表的内容等。与变量一样，可以进行计算和传递，属性的加工过程就是语义的处理过程。属性分两类：综合属性：用于自下而上传递信息继承属性：用于自上而下传递信息注意：终结符只有综合属性，它由词法分析器提供；非终结符可有综合属性，也可有继承属性，它由词法分析器提供；文法的开始
8、符号的所有继承属性作为属性计算前的初始值综合属性综合属性继承属性继承属性产生式右边的文法符号的继承属性可以继承左边的文法符号的继承属性产生式左边的文法符号可以通过综合右边的文法符号的综合属性而得到但必须提供一个计算规则：计算规则中只能使用相应产生式中的文法符号的属性。实际应用中，一个结点的综合属性的值由其子结点的综合属性值决定(产生式右边)。一个结点的继承属性由此结点的父结点和/或兄结点的某些属性决定(产生式左边)。但产生式左边的继承属性和右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性计算规则提供。digitlexval:=3Fval:=3Tval:=3Fval:
9、=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln0LEn1EE1+T2ET3TT1*F4TF5F(E)6Fdigitprint(E.val)E.val:=E1.val+t.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexvaldigitlexval:=5若输入符号串为：若输入符号串为：3*5+4n例例：综合属性的计算综合属性的计算C语言中变量定义：语言中变量定义：int id1,id2,id3综合属性的传递继承属性的传递例例：继
10、承属性的计算继承属性的计算产生式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realaddtype(id.entry,L.in)L1.in:=L.inaddtype(id.entry,L.in)语法制导的翻译方法语法制导的翻译方法基于属性文法的处理过程通常是基于属性文法的处理过程通常是：对单词符号串进行语法分析对单词符号串进行语法分析；构造语法树；构造语法树；根据需要遍历语法树；根据需要遍历语法树；在语法树的各结点处按语义规则进行计算。在语法树的各结点处按语义规则进行计算。语义规则描述的工作：语义规则描述的工作：属性计算
11、、静态语义检查、符号表的操作、代码生成等，通常写成过程和函数调用，称为语义子程序语义子程序。语法制导翻译的基本思想：语法制导翻译的基本思想：在语法分析过程中，根据语言的语义定义，随时翻译已识别的那部分语法成分的全部含义。语法制导的翻译方法：语法制导的翻译方法：如果遍历语法树的操作和建立语法树的操作同时进行，称为语法制导的翻语法制导的翻译方法。译方法。语法制导翻译的两种方法语法制导翻译的两种方法（1）在自下而上的语法分析中，使用在自下而上的语法分析中，使用和语法分析栈同步操作的和语法分析栈同步操作的语义栈语义栈进行进行语法制导翻译；语法制导翻译；（2）在自上而下的语法分析中（如递）在自上而下的语
12、法分析中（如递归下降分析），利用归下降分析），利用隐含的堆栈隐含的堆栈存储存储各递归子程序中的局部变量所表示的各递归子程序中的局部变量所表示的语义信息。语义信息。自下而上分析的语法制导翻译自下而上分析的语法制导翻译语法分析是自下而上的情况时，语义计语法分析是自下而上的情况时，语义计算的时机是：算的时机是：在用某一产生式进行在用某一产生式进行规约规约的同时，的同时，执行相应的语义动作。在分析完一个执行相应的语义动作。在分析完一个句子时，这个句子的句子时，这个句子的“值值”也就同时也就同时产生了。产生了。例：属性文法如下，输入串为：3*5+4，其语法树如下图：0LEn1EE1+T2ET3TT1*F
13、4TF5F(E)6Fdigitprint(E.val)E.val:=E1.val+t.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval产生式语义规则EE1+TTT*FF35F4在第一步规约时使用产生式6，执行的语义动作是将F.val的值置为单词digit的值3。把语法树中每个结点得语义值写在结点后的括号中，则第一步完成规约后的情形如右图所示：E1+TTT*FF（3）5F4E第一步规约第一步规约继续进行分析，逐步向上规约，得到下图所示的情形，最后用EE1+T规约到E时，它的值19就计算出来了
14、。E1（15）+T（4）E在自下而上的LR语法分析过程中，首先把它的把它的分析分析栈栈进行扩充进行扩充，使得每个文法符号都带有语义值。修改后栈的结构如下图所示：状态栈S0S1Sm符号栈X0(#)X1Xm语义栈X1.valXm.val栈顶栈顶同时把把LR分析器分析器的能力扩大的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行规约的同时进行相应的语义处理，完成属性文法中定义的语义动作。每步工作后的语义值保存在扩充的语义栈中。例：在例：在3*5+4的的LR分析过程中增加了语义栈后的语分析过程中增加了语义栈后的语法制导的实现过程。法制导的实现过程。LR分析表分析表文法文法0LEn1EE1+T
15、2ET3TT1*F4TF5F(E)6Fdigitprint(E.val)E.val:=E1.val+t.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval序号状态栈 符号栈语义栈语义栈归约产生式输入串10#-3*5+4#205#3-*5+4#303#F-3Fi*5+4#402#T-3TF*5+4#5027#T*-3-5+4#60275#T*5-3-+4#702710#T*F-3-5Fi+4#802#T-15TT*F+4#901#E-15ET+4#10016#E+-15-4#110165#E+
16、4-15-#120163#E+F-15-4Fi#130169#E+T-15-4TF#1401#E-19EE+T#15接受0LEn1EE1+T2ET3TT1*F4TF5F(E)6Fdigitprint(E.val)E.val:=E1.val+t.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval0LEn1EE1+T2ET3TT1*F4TF5F(E)6Fdigitprint(E.val)E.val:=E1.val+t.valE.val:=T.valT.val:=T1.val*F.valT.val
17、:=F.valF.val:=E.valF.val:=digit.lexval启示：启示：在刚才的翻译过程中有如下特点：句柄归约在先，语义动作在后。句柄归约在先，语义动作在后。归约时，栈内句柄各符号的语义信息与该句柄归约时，栈内句柄各符号的语义信息与该句柄同时出栈同时出栈，整个句柄所表示的语义信息则赋给，整个句柄所表示的语义信息则赋给相应产生式左部非终结符的语义变量，并让该相应产生式左部非终结符的语义变量，并让该非终结符及其语义变量非终结符及其语义变量同时入栈同时入栈。为了在某处调用语义动作，就必须先归约，因为了在某处调用语义动作，就必须先归约，因此，有时需要此，有时需要改写文法改写文法。常见语
18、句的语法制导翻译常见语句的语法制导翻译高级语言的两大类语句：说明语句说明语句：用于定义各种形式的有名实体及其属性，如常量、变量、数组、记录（结构）、过程、子程序等。可执行语句可执行语句：用于完成程序指定的功能。语义处理也按两大类处理：（1）说明语句的处理：把说明语句中定义的名字和属性登记在符号表中，用以检查名字的引用和说明是否一致，以便在翻译可执行语句时使用。一般说明语句的语义处理不生成目标代码，过程说明和动态数组的说明有相应的代码。（2）可执行语句：首先根据各源语句的语法结构和语义设计它的目标代码结构，找出源与目标的对应关系，然后根据语义规则进行翻译，生成四元式序列。语义翻译过程中涉及的数据
19、结构语义翻译过程中涉及的数据结构语义翻译过程中涉及的数据结构有符号表、四元式表和临符号表、四元式表和临时变量区时变量区。符号表符号表：语义翻译过程中，在产生四元式时，通常不使用变量的名字，而是使用它们在符号表中的入口位置，一般用ENTRY(i)表示变量i在符号表中的入口。因此语义子程序需要查阅符号表，而在翻译说明语句时需要填写符号表中的相关项。四元式表四元式表：四元式表是按翻译过程中四元式产生的顺序组成的。通常设置一个专门的过程GENCODE(OP,ARG1,ARG2,Ti)来产生一个四元式，将该四元式输出到四元式列表中，并使四元式的编号加1。临时变量区临时变量区：用于存放翻译过程中建立的临时
20、语义变量。假设过程newt用来生成临时变量，每调用一次，生成一个新的临时变量，第一次调用生成的是T1，第二次调用生成T2说明语句的翻译说明语句的翻译说明语句的作用：就是说明类型等属性信息，在翻译时主要是填符号表说明语句分多种，此处举例两种的翻译：变量说明语句的翻译常量说明语句的翻译变量说明语句的翻译变量说明语句的翻译.变量说明语句的文法描述变量说明语句的文法描述.变量说明语句的翻译变量说明语句的翻译例如：vara,b,c:integer;策略：先翻译第，产生式，再翻译，产生式，以便记录的类型，即在写程序时，读完读完一个说明语句，开始归约，再开始翻译，变量的类型朝前传递。1var 2i,(1)3
21、i:integer4i:char.翻译的语义动作翻译的语义动作NameTYPEKINDVALADDRa4integer符号表：符号表：1var 2i,(1)3i:integer4i:char(nop)FILL(ENTRY(i),(1).TYPE).TYPE:=(1).TYPEFILL(ENTRY(i),integer).TYPE:=integerFILL(ENTRY(i),char).TYPE:=charFILL(entry(i),Type)表示表示将类型将类型Type填入符号表中填入符号表中entry(i)表示变量名表示变量名i在符号表中的入口在符号表中的入口VARid1,id2,id3:i
22、nteger;的归约过程integer:id3,id2id2,id1id1id1VARVARVARVAR(a)(b)(c)(d)(e)1var 2i,(1)3i:integer4i:char(nop)FILL(ENTRY(i),(1).TYPE).TYPE:=(1).TYPEFILL(ENTRY(i),integer).TYPE:=integerFILL(ENTRY(i),char).TYPE:=char常量说明语句的翻译常量说明语句的翻译.常量说明语句的文法描述常量说明语句的文法描述.常量说明语句的翻译常量说明语句的翻译策略：和变量说明一样，先翻译后面的产生式，再翻译前面的产生式，以便在归约
23、时，执行语义动作，将常量的值、类型、种属填入符号表。例：例：ConstantA=123.翻译的语义动作翻译的语义动作将常量将常量INT在符号表中的入在符号表中的入口或值直接填入常量符号口或值直接填入常量符号i所指符号表的所指符号表的VAL栏栏将常数的类型填将常数的类型填入符号表的入符号表的Type栏栏3，4产生式的翻译与5，6产生式的翻译相同1，2产生式没有语义动作NameTYPEKINDVALADDRA4integer数值常数数值常数 123将常数的种属填将常数的种属填入符号表的入符号表的Kind栏栏可执行语句的翻译可执行语句的翻译定义的一些语义变量和过程GENCODE(OP,ARG1,AR
24、G2,RESULT)：语义过程，产生一个四元式，并填入四元式表，编号自动增1。NEWT：函数，返回一个临时变量序号。在翻译可执行语句的过程中，可能需要使用临时变量，假定用NEWT过程来申请临时变量Ti，每申请一次，i增1。ENTRY(i)：函数，查找变量i的入口地址；检查id.name是否在符号表中，如在则返回一指向该登陆项的指针，否则返回NULLE.PLACE：与给终结符E相联系的语义变量，可能是某变量的入口地址，或者为临时变量序号。简单赋值语句的翻译简单赋值语句的翻译.简单赋值语句的文法描述简单赋值语句的文法描述2.简单赋值语句的代码结构简单赋值语句的代码结构例如：例如：x:=2+3*2;
25、1.Ai=E2.EE+T3.ET4.TT*F5.TF6.F-P7.P(E)8.Pi3.简单赋值语句的翻译简单赋值语句的翻译 此处只假定是整数运算此处只假定是整数运算1.Ai=E2.EE(1)+T3.ET4.TT(1)*F5.TF6.F-P7.P(E)8.PiGENCODE(:=,E.PLACE,_,ENTRY(i)E.PLACE:=NEWT;GENCODE(+,E(1).PLACE,T.PLACE,E.PLACE)E.PLACE:=NEWT;E.PLACE:=T.PLACET.PLACE:=NEWT;GENCODE(*,T(1).PLACE,F.PLACE,T.PLACE)T.PLACE:=N
26、EWT;T.PLACE:=F.PLACEF.PLACE:=NEWT;GENCODE(-,P.PLACE,_,F.PLACE)P.PLACE:=NEWT;P.PLACE:=E.PLACEP.PLACE:=NEWT;P.PLACE:=ENTRY(i)例：赋值句A:=B+C*(-D)的自底向上分析1.Ai=E2.EE(1)+T3.ET4.TT(1)*F5.TF6.F-P7.P(E)8.PiGENCODE(:=,E.PLACE,_,ENTRY(i)E.PLACE:=NEWT;GENCODE(+,E(1).PLACE,T.PLACE,E.PLACE)E.PLACE:=NEWT;E.PLACE:=T.PL
27、ACET.PLACE:=NEWT;GENCODE(*,T(1).PLACE,F.PLACE,T.PLACE)T.PLACE:=NEWT;T.PLACE:=F.PLACEF.PLACE:=NEWT;GENCODE(-,P.PLACE,_,F.PLACE)P.PLACE:=NEWT;P.PLACE:=E.PLACEP.PLACE:=NEWT;P.PLACE:=ENTRY(i)1.Ai=E2.EE(1)+T3.ET4.TT(1)*F5.TF6.F-P7.P(E)8.PiGENCODE(:=,E.PLACE,_,ENTRY(i)E.PLACE:=NEWT;GENCODE(+,E(1).PLACE,T.
28、PLACE,E.PLACE)E.PLACE:=NEWT;E.PLACE:=T.PLACET.PLACE:=NEWT;GENCODE(*,T(1).PLACE,F.PLACE,T.PLACE)T.PLACE:=NEWT;T.PLACE:=F.PLACEF.PLACE:=NEWT;GENCODE(-,P.PLACE,_,F.PLACE)P.PLACE:=NEWT;P.PLACE:=E.PLACEP.PLACE:=NEWT;P.PLACE:=ENTRY(i)因此，四元式表中增加了因此，四元式表中增加了4条四元式：条四元式：K（翻译此赋值语句之前的四元式）K+1(i，FDPLACE，_，FDPLACE
29、)K+2(*i，TcPLACE，FDPLACE，TPLACE)K+3(+i，EBPLACE，TPLACE，EPLACE)K+4(:=，EPLACE，_，ENTRY(iA)简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译(1)Sid:=Ep:=lookup(id,name);ifpnilthenemit(p:=E.place)elseerror(2)EE1+E2E.place:=newtemp;emit(E.place:=E1.place+E2.place)(3)EE1*E2E.place:=newtemp;emit(E.place:=E1.place*E2.place)(4)E-E
30、1E.place:=newtemp;emit(E.place:=uminusE1.place)(5)E(E1)E.place:=E1.place)(6)Eidp:=lookup(id,name);ifpnilthenE.place:=pelseerror张素琴编编译原理（清华大学版）布尔表达式的翻译布尔表达式的翻译1.布尔表达式的基本概念布尔表达式的基本概念布尔表达式布尔表达式是将布尔运算符（and、or、not）作用到布尔变量或关系表达式上组成的表达式。关系表达式形如E1ropE2，其中E1和E2是算术表达式，rop表示关系运算符、或。Sample语言规定布尔运算符的优先级从高到低为not、
31、and、or，and和or都是左结合。2.布尔表达式的两个基本作用布尔表达式的两个基本作用l用作布尔赋值语句中的布尔运算。l用作控制语句如if-then、if-then-else、whiledo等之中的条件表达式，其作用是选择下一个执行点选择下一个执行点。3.布尔表达式的文法描述布尔表达式的文法描述（1）or（2）（3）and（4）（5）not（6）()（7）rop（8）iropi（9）i例如：例如：x:=not a and(yz)是符合上述文法的布尔表达式是符合上述文法的布尔表达式计算布尔表达式的值有两种方法：计算布尔表达式的值有两种方法：l一种是像计算算术表达式那样，对布尔表达式中的每个因
32、子都计算其布尔值，最后求得整个表达式的布尔值。l另一种计算方法是根据布尔运算的特殊性采取某些优化措施，只计算部分表达式。例如要计算AorB，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，AorB的值都为1。如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。例如，用数值1表示true，用0表示false。那么布尔表达式1or(not0and0)or0的计算过程是：1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=14.用于布尔赋值语句中布尔表达式的翻译用于布尔赋值语句中布尔表达式的翻译使用这种翻译方法，可以参
33、照算术表达式的赋值语句文法的语义动作，为布尔表达式文法配上合适的语义动作。张素琴编编译原理（清华大学版）给出的方案如下：(1)EE1orE2E.place:=newtemp;emit(E.place:=E1.placeorE2.place)(2)EE1 andE2E.place:=newtemp;emit(E.place:=E1.placeandE2.place)(3)EnotE1E.place:=newtemp;emit(E.place:=notE1.place)(4)E(E1)E.place:=E1.place(5)Eid1ropid2E.place:=newtemp;emit(ifid1
34、.placeropid2.place)gotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1);(6)Etrue E.place:=newtemp;emit(E.place:=1);(7)Efalse E.place:=newtemp;emit(E.place:=0);布尔量布尔量的代码结构的代码结构每个布尔量(布尔变量或关系表达式)的目标结构有两个出口，真出口真出口指向布尔量为真时应跳转的位置；假出口指向布尔量为假时应跳转的位置。5.控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译AA.TCA.FC布尔量
35、翻译为两条四元式：布尔量翻译为两条四元式：(jnz,A,_,P):真出口，当A为真时跳转到四元式P；(j,_,_,Q):假出口，无条件跳转到四元式Q。转移四元式的第4个分量表示转移去向（即P、Q为某个四元式的编号）。关系表达式也翻译为两条四元式：关系表达式也翻译为两条四元式：(jrop,i1,i2,P):真出口，当i1ropi2为真时转四元式P；(j,_,_,Q):假出口，无条件跳转到四元式Q。问题：问题：在翻译布尔表达式时，后面的语句在翻译布尔表达式时，后面的语句未翻译，未翻译，P，Q如何知道？如何知道？解决方法：回填技术回填技术在由多个因子组成的布尔表达式中，可能有多个因子的真出口或假出口
36、的转移去向相同，但又不知道具体转向位置。在这种情况下，需要把这些转移方向相同的出口链在一起，形成真/假出口链，以便后续知道转移地址后再回填回填。对于给定的控制语句中的布尔表达式，翻译方法如下：若已知转移地址就直接填入；若不知道，时先填0，等知道后再返填。如果多个因子的转移去向相同，但又不知道具体位置，应该用链将这些未知且出口相同的四元式链在一起。例：写出布尔表达式例：写出布尔表达式:A and B and CD 的四元的四元式序列。式序列。当扫描到A后的and时，对A进行规约，产生两个四元式(1)和(2)，四元式(1)的第4分量表示真出口，由于A为真时应计算B，因此A的真出口的值为3（即A为真
37、时转向3）；四元式(2)的第4个分量表示假出口，目前其值未知，先填入0。当扫描到B后的and时，对B进行规约，产生四元式(3)、(4)，四元式(3)的第4分量表示真出口，由于B为真时应计算CD，因此B的真出口的值为5（即B为真时转向5）；四元式(4)的第4个分量表示假出口，目前其值未知，但可以知道它与A的假出口相同，因此需将它与四元式(2)链接起来，即将(4)的第4个分量填入2；当扫描到最后，对关系表达式CD进行规约，产生两个四元式(5)、(6)，此时(5)的第4个分量表示真出口，其值未知（即暂时不知道CD时转向哪里），填入0；(6)的第4个分量表示假出口，其值未知，但它与A和B的假出口相同，
38、因此需将它与四元式(4)链接起来，即将(6)的第4个分量填入4。假出口未知，填入假出口未知，填入0当扫描到当扫描到and时，对时，对A进行进行归约，产生两个四元式归约，产生两个四元式1，2，其中真出口已知，为，其中真出口已知，为3当扫描到当扫描到B后的后的and时，时，对对B进行归约，又产生两进行归约，又产生两个四元式个四元式3，4，其中真，其中真出口已知，为出口已知，为5假出口仍未知，但它与假出口仍未知，但它与A的假出口相同，则链接的假出口相同，则链接起来，填起来，填2当扫描到最后，对当扫描到最后，对CD进行归进行归约，又产生两个四元式约，又产生两个四元式5，6，此时真出口未知，填此时真出口
39、未知，填0假出口仍未知，但假出口仍未知，但它与上两个布尔量它与上两个布尔量的假出口相同，则的假出口相同，则链接起来，填链接起来，填4生成了真、假出口两个链，其中(1)、(3)、(5)形成一条真出口链真出口链；(6)、(4)、(2)形成一条假出口链假出口链。每个链尾的四元式的第4个分量都为0，为结束标记，同时也是待填部分，等到以后翻译到后面再填入。一旦出现具体的转向目标，即把转向的目标四元式编号回填到链上对应四元式的第4个分量处。最后的四元式列表如下：最后的四元式列表如下：控制语句中布尔表达式的语义处理控制语句中布尔表达式的语义处理Sample语言中，在为布尔表达式设计语义动作时，提供了以下语义
40、变量和语义过程：（1）为每个非终结符X设置两个出口：真出口真出口X.TC和假出口假出口X.FC，它们同时分别表示真、假出口链的链首。例：对于E1orT的目标代码结构，只要E1为真，后面的表达式就不必计算，就知道E1orT为真；只有当E1为假，才读取T，E1orT的值由T值决定，目标结构如下图(a)所示。对于E1andT的目标代码结构，只要E1为假，后面的表达式就不必计算，就知道E1andT为假；只有当E1为真，才读取T，E1andT的值由T值决定，目标结构如下图(b)所示。（2）变量变量NXQ，指代下一个即将形成的四元式编号。NXQ的初值为1，每执行一次GENCODE过程，产生一条新的四元式，
41、NXQ就自动加1。（3）函数）函数MERG(P1,P2)。将P1,P2为链首两个真出口链或假出口链合并在一起，返回合并后的链首。MERG(P1，P2)if(P2=0)return(P1);elseP:=P2;while(四元式P的第4分量内容不为0)P:=四元式P的第4分量内容；把P1填进四元式P的第4分量；return(P2);（4）函数）函数BACKPATCH(P，t)。把以P为链首的真出口链或假出口链中每个四元式的第4分量都改写为已知地址t。（回填回填）BACKPATCH(P，t)Q:=P;while(Q!=0)dom:=四元式Q的第4分量内容；把t填进四元式Q的第4分量；Q:=m;布尔
42、表达式文法的改造布尔表达式文法的改造为语义翻译服务为语义翻译服务分析E1orT和E1andT的目标代码结构：从上图(a)可以看出，E1的假出口应转向布尔表达式T的第一个四元式的位置，由于语法分析程序分析到运算符or时才能知道E1已分析完毕，开始生成T的四元式。这样，当分析程序扫描到or时，应执行一个语义动作，把下一个四元式的编号（即T的入口）回填给E1的假出口。为此，产生式or应改造为：oror or这样，当用产生式oror进行规约时，就能立即执行回填回填动作，及时把的第一个四元式的编号回填回填给的假出口链。类似的产生式and也应改造为下面两个产生式：andand and这样，当用产生式and
43、and进行规约时，就能及时把的第一个四元式的编号回填回填给的真出口链。布尔表达式的文法改造方案：布尔表达式的文法改造方案：（1）or（2）oror（3）（4）and（5）andand（6）（7）()（8）not（9）rop（10）i rop i（11）i改造后的文法改造后的文法（1）or（2）（3）and（4）（5）not（6）()（7）rop（8）iropi（9）i改造前的文法改造前的文法布尔表达式文法的语义翻译方案：布尔表达式文法的语义翻译方案：NXQ表示当前产生表示当前产生的四元式的编号的四元式的编号单个的布尔量单个的布尔量关系运算关系运算Not逻辑运算逻辑运算带算术运算的关系运算带算术
44、运算的关系运算产生式产生式6:，3:的翻译与的翻译与7相似，都是将右边的真假相似，都是将右边的真假出口直接赋值到左边出口直接赋值到左边(5)(4)构成构成and逻辑运算逻辑运算(2)(1)构成构成or逻辑运算逻辑运算控制语句的翻译控制语句的翻译控制语句包括：if语句While语句Repeat语句For语句IF语句的翻译语句的翻译1.IF语句的文法语句的文法(S是开始符号是开始符号)产生式产生式(1),(4)生成无生成无else 的的IF语句结构语句结构产生式产生式(1),(2),(3)生成生成if then else 的的语句结构语句结构（1）SCS(1)（2）CifEthen（3）STS(2
45、)（4）TCS(1)else2.IF语句的目标结构及其翻译语句的目标结构及其翻译无无else的结构的结构C.Chain的作用：由于在用第一个的作用：由于在用第一个产生式进行归约时，只生成了条产生式进行归约时，只生成了条件式件式E的代码，的代码，then时可以回填时可以回填E.TC,E.FC必须向后传递到下一必须向后传递到下一各产生式中。各产生式中。if ab then x:=3;（1）SC S(1)SCHAIN:=MERG(CCHAIN，S(1)CHAIN)（2）Cif E then BACKPATCH(ETC，NXQ);CCHAIN:=EFC 2.IF语句的目标结构及其翻译语句的目标结构及其
46、翻译有有else的结构的结构if ab then x:=3 else x:=5;(1)Cif E then BACKPATCH(ETC，NXQ);CCHAIN:=EFC (2)ST S(2)SCHAIN:=MERG(TCHAIN，S(2)CHAIN)(3)TC S(1)else q:=NXQ;GENCODE(j，_，_，0);BACKPATCH(CCHAIN，NXQ);TCHAIN:=MERG(S(1)CHAIN，q)例：将下面的例：将下面的IF语句翻译为四元式序列语句翻译为四元式序列if A and B and(CD)then if A,C,D,7)/*CD的四元式*/6.(j,_,_,13
47、)7.(j,A,B,9)/*AB的四元式*/8.(j,_,_,11)9.(:=,1,_,F)/*F:=1的四元式*/10.(j,-,-,15)11.(:=,0,_,F)/*F:=0的四元式*/12.(j,_,_,15)13.(+,G,1,T)/*G:=G+1的四元式*/14.(:=,T,_,G)15.练习:将下面的语句翻译为四元式序列if(AC)and(BD)then if A=1 then C:=C+1elseifADthenA:=A+2;1.(j,A,C,3)1.(j,A,C,3)2.(j,-,-,14)2.(j,-,-,14)3.(j,B,D,5)3.(j,B,D,5)4.(j,-,-,
48、14)4.(j,-,-,14)5.(j=,A,1,7)5.(j=,A,1,7)6.(j,-,-,10)6.(j,-,-,10)7.(+,C,1,T7.(+,C,1,T1 1)8.(:=,T,-,C)8.(:=,T,-,C)9.(j,-,-,14)9.(j,-,-,14)10.(j=,A,D,12)10.(j10;3.翻译翻译（1）Rrepeat RHEAD:=NXQ （2）URS(1)until UHEAD:=RHEAD;BACKPATCH(S(1)CHAIN，NXQ)（3）SUE BACKPATCH(EFC，UHEAD);SCHAIN:=ETC 将下面的语句翻译为四元式序列Ifw1thena
49、:=b*c+delserepeata:=a-1untila0;1.(j,w,1,3)2.(j,7)3.(*,b,c,t1)4.(+,t1,d,t2)5.(:=,t2,a)6.(j,11)7.(-,a,1,t3)8.(:=,t3,a)9.(j，FPLACE，T1，0)(2)SF S(1)BACKPATCH(S(1)CHAIN，FAGAIN);GENCODE(j，_，_，FAGAIN);SCHAIN:=FCHAIN 将下面的语句翻译为四元式序列fori:=a+b*2toc+d+10doifhgthenp:=p+1;1(*,b,2,t1)2(+,a,t1,t2)3(+,c,d,t3)4(+,t3,1
50、0,t4)5(:=,t2,i)6(:=,t4,t)7(j,10)8(+,I,1,t5)9(:=,t5,i)10(j,I,t,12)11(j,17)12(j,h,g,14)13(j,8)14(+,p,1,t6)15(:=,t6,p)16(j,8)17自顶向下的语法制导翻译自顶向下的语法制导翻译优点：不需要改造文法在需要的任何位置调用语义动作自顶向下的语法分析有两种：递归下降分析LL(1)分析递归下降的语法制导翻译递归下降的语法制导翻译例：对如下文法进行递归例：对如下文法进行递归下降的分析，并增加语义下降的分析，并增加语义只包含两个语句：赋只包含两个语句：赋值句和值句和REPEAT语句语句需要翻译