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

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

T=(VT,VN,△,R,S)。VT是一个有穷的输入字母表，包含源语言中的符号；VN是一个有穷的非终结符号集合；△是一个有穷的输出字母表，包含出现在翻译串中的那些符号；R是形如A→w,y的规则的有穷集合，w是由终结符或非终结符组成的串，y是由VN或△中的符号组成的串；S∈VN是一个开始符号。第五章语法制导翻译和中间代码产生03二月20235例如：SDTST1=({a,b,c,+,-,[,]},{E,T,A},{ADD,SUB,NEG,x,y,z},R,E)，其中R由下列翻译规则组成：

E→E+T,TEADDE→E-T,ETSUBE→–T,TNEGE→T,TT→[E],ET→A,AA→a,xA→b,yA→c,zT1的基础源文法是E→E+T|E-T|-T|TT→[E]|AA→a|b|cT1的基础目标文法是E→TEADD|ETSUB|TNEG|TT→E|AA→x|y|z第五章语法制导翻译和中间代码产生03二月20236一个翻译模式是一个形如(u,v)的串对，其中，u是SDTS基础源文法的一个句型，而v称为与其对应的翻译，它是由VN和△中元素组成的串。翻译模式的定义如下：(S,S)是一个翻译模式，且这两个S是相关的(S是SDTS的开始符号)。(aAb,a’Ab’)是一个翻译模式，且两个A是相关的；此外，若A→g,g’是R中的一条规则，那么(agb,a’g’b’)也是一个翻译模式。规则中g和g’的非终结符之间的相关性也必须带进这种翻译模式之中。表示法(aAb,a’Ab’)=>(agb,a’g’b’)表示一种翻译模式到另一种翻译模式的变换。第五章语法制导翻译和中间代码产生03二月20237树变换语法制导的翻译过程也可用语法树变换来说明。从中剪掉终结符号节点；根据适当的翻译规则，重排每个中间结点的孩子；添加对应于输出符号集中的中间符节点。第五章语法制导翻译和中间代码产生03二月202385.2简单SDTS和自上而下翻译器

如果在每一规则的翻译成分中，非终结符出现的次序与它们在源成分中出现的次序相同，则称一个SDTS是简单的(simple)；但是，如果A→A1+A2,A2A1ADD是SDTST的一个规则，那么，该SDTST就是不简单的。第五章语法制导翻译和中间代码产生03二月20239如果T=(VN,VT,△,R,S)是其基础源文法为LL(k)的简单SDTS，那么，存在一个自上而下的确定的下推翻译器PDT(Push-DownTranslater)，它接受T的输入语言中的任何符号串并产生对应的输出串。PDTP的定义如下：P的一个构形是一个四元组(q,x,y,z)，其中，q是它的有穷控制器的状态，x是尚待扫描的输入串，y是下推栈，z是此时被打印出的输出符号串。于是，在某次移动中，便有(q,ax,Yy’,z)┟(r,x,gy’,zz’)即，在状态q面临输入符号a且栈顶符号为Y时，P才允许移动到状态r，这一移动的结果是：输入符号a被去掉，栈顶符号Y被g所替换，而且串z’已作为输出串打印出。第五章语法制导翻译和中间代码产生03二月202310称w是关于x的输出，如果对于某个状态q和栈符号串u，存在(q0,x,Z0,ε)┟(q,ε,u,w)其中，q0是初态；Z0是栈的初始内容，ε为空串。若u＝ε，则称P停止于空栈；若q是某个终态，则称P停止于终态。如果P满足下述两个条件，则称P是确定的：对所有的状态q，输入串a和栈符号Z，δ(q,a,Z)至多只包含一个元素；若δ(q,ε,Z)非空，则不存在符号a(a≠ε)使得δ(q,a,Z)非空，即对于某个状态和栈符号，在空移动和非空移动之间不应存在冲突。第五章语法制导翻译和中间代码产生03二月202311PDTP的操作为：①在一应用移动中，非终结符A已位于栈顶，借助于分析表，选定产生式A→w来进行归约。假定R中的翻译规则为A→w,z其中，w=a0B1a1B2a2…Bkak，而z=b0B1b1B2…Bkbk。其中，Bi是非终结符，ai是输入符号串，bi是输出符号串。位于栈顶的A由下面的复合串b0a0B1b1a1B2…Bkbkak

所替代，而b0称为新栈顶符号。②若栈顶符号是输出字母表的一个元素，则从栈中弹出，并将其作为输出符号打印出。③若栈顶符号是输入字母表VT的一个元素，则它应与当前输入符号匹配。从栈顶弹出它，输入指针后移。第五章语法制导翻译和中间代码产生03二月2023125.3简单后缀SDTS和自下而上翻译器如果一个SDTS是简单的，而且它的每个翻译规则都有下述形式：A→a0B1a1B2a2…Bkak,B1B2…Bkw也就是说，除了最右边的w之外，（输出）终结符不可能出现在翻译成分之中，那么，称这个SDTS为简单后缀的(SimplePostFix)。定理：对其基础源文法为LR(k)的每一简单后缀的SDTS，存在一确定的LR(k)PDT：它接受从该基础源文法可推导出的每一句子；它将这种句子的翻译作为输出。后缀翻译

IF-THEN-ELSE控制语句函数调用第五章语法制导翻译和中间代码产生03二月2023135.4抽象语法树的构造抽象语法树AST(Abstract-Syntaxtree)是某个语言结构的一种简洁的树形表示形式，它只需包含该结构尚须转换或归约的信息。语法树简化成一个AST：去掉于单非产生式（即右部为单一终结符的产生式）相关的子树，并上提相关分支上的终结符号节点。对于直接包含运算符的多个子树，上提运算符并让它取代其父节点。去掉括号，并上提运算符，让它取代其节点。最后得到的语法树便是一个AST。第五章语法制导翻译和中间代码产生03二月202314§5.5属性文法

一、属性一、属性：一般用来描述客观存在的事物或人的特性。例如，学生的姓名、年龄、性别等；商品的颜色、重量、单价等。编译技术中用属性来描述计算机处理对象的特征。例如：X.Type,X.Place,X.val等分别描述X的类型，存储位置、值等不同的特征。 属性分两类： 综合属性：一般用于“自下而上”传递信息。 继承属性：一般用于“自上而下”传递信息。第五章语法制导翻译和中间代码产生03二月202315二、属性文法

对于某个压缩了的上下文无关文法，当为每个文法符号引进一组属性，且让该文法中的重写规则附加以语义规则时，称该上下文无关文法为属性文法。

形式定义：一个属性文法形式上定义为一个三元组AG,AG=(G,V,E)。其中G表示一个上下文无关文法；V表示属性的有穷集；E表示属性的断言或谓词的有穷集。第五章语法制导翻译和中间代码产生03二月202316三、综合属性

从语法分析树的角度来看，如果一个结点的某一属性，其值由子结点的属性之值来计算，则称该属性为综合属性。

综合属性用于“自下而上”传递信息。第五章语法制导翻译和中间代码产生03二月202317例1：算术表达式求值的属性文法。规则式 语义规则1.L→E print(E.val)2.E→E1+T E.val:=E1.val+T.val3.E→T E.val:=T.val4.T→T1*F T.val:=T1.val*F.val5.T→F T.val:=F.val6.F→(E) F.val:=E.val7.F→digit F.val:=digit.lexval

与规则式关联的每一个语义规则的左部符号E,T,F等的属性值的计算由右部非终结符决定，这种属性称为综合属性。第五章语法制导翻译和中间代码产生03二月202318LE.val=19F.val=5+T.val=4T.val=15F.val=4digit.lexval=4E.val=15T.val=3digit.lexval=5F.val=3digit.lexval=3*n求：3*5+4第五章语法制导翻译和中间代码产生03二月202319四、继承属性 语法树分析中，若一个结点的某个属性之值由该结点的兄弟结点和/或父结点的属性之值来计算，则此结点的属性称为继承属性。 继承属性用于“自上而下”传递信息。第五章语法制导翻译和中间代码产生03二月202320例2、说明语句中简单变量类型信息的属性文法。 规则式 语义规则 1.D→TL L.in:=T.type 2.T→int T.type:=integer 3.T→real T.type:=real 4.L→L1,id L1.in:=L.in addtype(id.entry,L.in) 5.L→id addtype(id.entry,L.in)过程addtype把每一个标识符id的类型信息(由L.in继承)登录在符号表的相关项id.entry中。DTLintL,ididT有一个综合属性type，其值为integer或real。L.in由T.type确定后逐步传递到下边有关结点使用。这种属性称为继承属性。第五章语法制导翻译和中间代码产生03二月202321五、属性的初始值①终结符号只有综合属性，它们由词法分析器提供。②非终结符号既有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。第五章语法制导翻译和中间代码产生03二月202322§5.6

语法制导翻译法语法制导翻译法的基本思想：对文法的每一条产生式，设计语义子程序。在语法分析的过程中，当使用一条产生式推导或归约时，调用该语义子程序进行属性计算，完成预定的翻译工作。

语法制导翻译法：在语法分析的过程中，依随分析过程，根据每个产生式添加的语义动作进行翻译的方法。第五章语法制导翻译和中间代码产生03二月202323语义子程序语义子程序也称为翻译子程序，语义动作。它描述了有关产生式所对应的翻译工作。语义动作一方面指出了产生式所对应的符号串的意义；另一方面又按照这种意义规定了对应的属性计算加工动作。 语义动作： 查填各种表格 计算某变量的值 生成某种中间代码 打印错误信息等等第五章语法制导翻译和中间代码产生03二月202324LR分析制导的具体实现方法1、为文法产生式设计语义子程序。2、为文法构造一张无冲突的LR分析表。3、修改总控程序，归约时调用语义子程序。4、扩充LR分析栈，用来存放各文法符号对应的语义信息。例如：(1).E→E1+E2 {E.val=E1.val+E2.val}(2).E→E1*E2 {E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}第五章语法制导翻译和中间代码产生03二月202325#第五章语法制导翻译和中间代码产生03二月202326扩充的LR分析栈：׃׃׃S0׃׃׃#׃׃׃-状态栈文法符号栈语义值栈E.val=7E.val=1+E.val=61E.val=2*E.val=323(1).E→E1+E2

{E.val=E1.val+E2.val}(2).E→E1*E2

{E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}第五章语法制导翻译和中间代码产生03二月202327步骤状态栈语义栈符号栈输入符号动作10-#1+2*3#S3203-#1+2*3#r4301-1#E+2*3#S44014-1-#E+2*3#S350143-1-#E+2*3#R460147-1-2#E+E*3#S5701475-1-2#E+E*3#S38014753-1-2-#E+E*3#R49014758-1-2-3#E+E*E#R2100147-1-6#E+E#R11101-7#E#acc第五章语法制导翻译和中间代码产生03二月202328§5.7中间语言常用的中间语言有:一、逆波兰式二、三元式与间接三元式三、树形表示法四、四元式第五章语法制导翻译和中间代码产生03二月202329一、逆波兰式1、逆波兰式（后缀式）：每一运算符都置于其运算对象之后。（无括号表达式）

中缀表示 后缀表示

A*B AB* A+B*C ABC*+ (A+B)*(C+D) AB+CD+*

(a==0&&b>3)||(e&&x!=y) a0==b3>&&exy!=&&|| 第五章语法制导翻译和中间代码产生03二月2023302、LR分析制导生成逆波兰式文法：0 E′→E {空}1 E→E(1)+E(2) {print+}2 E→E(1)*E(2) {print*}3 E→(E(1)) {空}4 E→i {printi}步骤状态栈符号栈输入符号输出区10#a+b*c#203#a+b*c#301#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*+第五章语法制导翻译和中间代码产生03二月202331二、三元式与间接三元式一般形式：（op，AG1，AG2）例如：a:=-b*(c+d)三元式为：①（－，b，

）②（+，c，d）③（*，①，②）④（:=，③，a）第五章语法制导翻译和中间代码产生03二月202332间接三元式例如：语句 X:=(A+B)*C Y:=D^(A+B)间接代码⑴⑵⑶⑴⑷⑸opAG1AG2⑴+AB⑵*⑴C⑶:=X⑵⑷^D⑴⑸:=Y⑷第五章语法制导翻译和中间代码产生03二月202333三、树形表示法抽象语法树：在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种变换后的语法树称为抽象语法树。+* 43 5 3*5+4的抽象语法树

第五章语法制导翻译和中间代码产生03二月202334树形表示

A*B+C*D+C*A*BD末端结点表示一个运算对象,每一个内结点表示一个一元或二元运算符。树形表示是三元式的翻版(3)+(1)*(2)*CABD第五章语法制导翻译和中间代码产生03二月202335四、四元式

一般形式：(op，AG1，AG2，result)

直观形式：result:=AG1opAG2例如：求x:=a+b*c的四元式。(*，b，c，T1) 直观式： T1:=b*c(+，a，T1，T2) T2:=a+T1(:=，T2，，x) x:=T2第五章语法制导翻译和中间代码产生03二月202336

采用自下而上的语法制导翻译法语义动作的设计（1）搞清楚源结构和目标结构（2）自下而上的语法制导翻译特点：栈顶形成句柄，归约时执行相应语义动作（3）给出从源结构到目标结构的变换方法§5.8自底向上语法制导翻译第五章语法制导翻译和中间代码产生03二月202337例.设文法及其相应的语义动作如下:S→a{print“2”}S→bTc{print“1”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}采用自下而上语法制导翻译,给出输入串bR/bTc/bSc/ac的翻译结果第五章语法制导翻译和中间代码产生03二月202338分析:首先对输入串bR/bTc/bSc/ac画出语法树:ScTbRS/R/RS/RcTbaScTbRS再考虑归约时执行相应语义动作第五章语法制导翻译和中间代码产生03二月202339ScTbRS/R/RS/RcTbaScTbRSS→bTc{print“1”}S→a{print“2”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}14翻译结果为:53142431第五章语法制导翻译和中间代码产生03二月202340一、简单算术表达式和赋值语句的翻译定义几个过程和函数：lookup()：检查是否出现在符号表中，如果在，则返回其指针；否则，返回NULL表示没有找到。emit（result:=AG1opAG2）：产生一个四元式，并填入四元式表中。newtemp()：该函数返回一个新的临时变量。第五章语法制导翻译和中间代码产生03二月202341文法：P2161.S→i=E{p＝Lookup();if(p==NULL)error();elseemit(p’＝’E.place}2.E→E(1)＋E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}3.E→E(1)*E(2){E.place＝newtemp();emit(E.place’＝’E(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;elseerror();}第五章语法制导翻译和中间代码产生03二月202342 算术表达式a+b*c翻译到三地址语句的过程：

030$$a01$E014$E+0143$E+b－a－a－－a－－状态栈符号栈语义栈输入串a+b*c$+b*c$+b*c$b*c$*c$－－－第五章语法制导翻译和中间代码产生03二月202343*c$c$$$$$t1=b*ct2=a+t1

状态栈符号栈语义栈输入串014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E01$E－a－b－－－a－b－c－a－t1－a－b－－a－b－t2acc第五章语法制导翻译和中间代码产生03二月202344二、布尔表达式的翻译 1、E→E∨E 2、E→E∧E 3、E→E 4、E→(E) 5、E→idropid 6、E→id第五章语法制导翻译和中间代码产生03二月2023451、类似算术表达式的翻译方法 （求每个因子，再求表达式的值）例如： 布尔表达式： a∨b∧c

三地址序列： T1:=c T2:=b∧T1 T3:=a∨T2第五章语法制导翻译和中间代码产生03二月2023461.E→E(1)∨E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∨’E(2).place)}2.E→E(1)∧E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∧’E(2).place)}3.E→E(1){E.place＝newtemp()；emit(E.place’＝’’’

E(1).place}4.E→(E(1)){E.place＝E(1).place；}5.E→i(1)ropi(2){E.place＝newtemp()；emit(‘if’i(1).placerop.opi(2).place‘goto’next+3);emit(E.place’＝’‘0’);emit(gotonext+2);emit(E.place’＝’‘1’);}6.E→i

{E.place＝i.place；}第五章语法制导翻译和中间代码产生03二月202347EE∨Ea<bE∧Ec<de<f第五章语法制导翻译和中间代码产生03二月2023482、根据布尔表达式的特殊性采取某种优化措施A∨B ifAthentrunelseBA∧B ifAthenBelsefalseA ifAthenfalseelsetrue①对非终结符E赋予两个出口真出口：布尔表达式为真时，需转移的四元式地址。假出口：布尔表达式为假时，需转移的四元式地址。第五章语法制导翻译和中间代码产生03二月202349②设置两个语义变量：E.ture:用来记录表达式E对应的四元式需回填真出口的四元式的地址所构成的链。E.false:用来记录表达式E对应的四元式需回填假出口的四元式的地址所构成的链。③定义三个函数：第五章语法制导翻译和中间代码产生03二月202350链接函数merge(P1,P2)：把以P1和P2为链首的两条链合并为一，返回合并后的链首（当P2=0时，返回P1;当P2≠0时，返回P2）。

intmerge(intP1,intP2){ intP; if(!P2)returnP1; else{ P=P2; while(P.result<>0) P=P.result; P.result=P1; returnP2;}第五章语法制导翻译和中间代码产生03二月202351回填函数backpatch(p,t)：把p所链接的每个四元式的第四分量都回填为t。 voidBP(intp,intt){ intq=p; while(q){ intq1=q.result; q.result=t; q=q1; } return; }建链函数makelist(i)：创建一个仅含i的新链表。第五章语法制导翻译和中间代码产生03二月202352④定义三种四元式：(jnz,a,-,p) ifagotop(当a为真时转向第p四元式）(jrop,x,y,p) ifxropygotop(j,-,-,p) gotop(无条件转向第p四元式)⑤四元式表的指针nextquad（nextq）：每执行一次emit后，nextq自动加1。⑥E.code：为及时回填转移地址,使用语义变量E.code记录表达式E的第一个四元式语句序号。第五章语法制导翻译和中间代码产生03二月2023531.E→i {E.tr=next; E.fa=next+1; E.code=next;emit(ifi.placegoto-);emit(goto_);}2.E→i(1)ropi(2){E.tr=next; E.code=next; E.fa=next+1;emit(ifi(1).placerop.opi(2).placegoto_); emit(goto_);

}3.E→(E(1)){E.code=E