语义分析与中间代码生成.ppt

S.P,O.P,第8章 语义分析与中间代码生成,要求明确语义分析的任务 明确属性文法和语法制导翻译的含义 明确自底向上和自顶向下语法制导翻译的区别和特点 明确生成中间代码的目的，中间代码的几种形式,教学目标,8.1 语义分析的任务 8.2 语法制导翻译 8.3 中间代码 8.4 简单赋值语句的翻译 8.5 布尔表达式的翻译,教学内容,词法分析，语法分析：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。 本章要介绍的是语义分析和中间代码生成技术。 程序语言 中间代码 目标代码,翻译,翻译,根据语义规则对识别出的各种语法成份分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。,（1）确定数据类型 （2）语义检查 动态语义检查：在运行时刻进行 静态语义检查：在编译时完成 （3）识别含义，进行真正的翻译,8.1 语义分析的任务,类型检查。 控制流检查，确保控制语句有合法的转向点。例如，C语言中的break语句使控制跳离包括该语句的最小的switch，while或for语句。如果不存在包括它的这样的语句，则应报错。,静态语义检查,静态语义检查,一致性检查。很多情况下要求对象只能被定义一次。例如，语言中规定一个标识符在同一作用域中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等。 相关名字检查。有的语言中有时规定，同一名字必须出现两次或多次。例如，Ada语言中，循环或程序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配对情况。,实际应用中比较流行的语义分析方法： 基于属性文法的语法制导翻译方法,8.2 语法制导翻译,属性文法是Knuth在1968年提出的 属性文法的特点 是一种接近形式化的语义描述方法 长于描述静态语义、短于描述动态语义 每个语法符号有相应的属性符号 每个产生式有相应计算属性的规则 属性变量:=属性表达式,8.2.1 属性文法,附加了一组属性和运算（语义）规则的文法,文法符号X的属性t常用X.t来表示,语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关 不同的产生式对应不同的语义规则 不同的分析目标也对应不同的语义规则,静态语义检查、符号表操作、代码生成及打印各种错误信息,非终结符E、T及F都有一个综合属性val,符号i有一个综合属性，它的值由词法分析器提供。 某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现,语 义 规 则,E E1+T,E T,T T1 * F,T F,F (E),F i,E.val=E1.val+T.val,E.val=T.val,T.val=T1.val F.val,T.val=F.val,F.val=E.val,F.val=i.lexval,产生式,例8.1,根据文法符号的语义，为文法符号设置属性，用来表示文法符号的语义 终结符使用单词的属性 （id.val） 保留字：if, begin, function, 常数：40.12, 232, 80, “TCP/IP” 标识符：sum, tcc, id 语法变量根据实际需要设定属性 表达式E：E.type， E.val,属性的设定,8.2.2 语法制导翻译的过程,语法制导翻译：将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。,自底向上语法制导翻译,自顶向下语法制导翻译,语法制导翻译的实现,语法制导翻译分为两种处理方法： （1）语法制导定义（自底向上）： 对每个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。 （2）翻译方案（自顶向下）： 在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种动作与分析交错的实现方案。,输入符号串 分析树 执行语义规则 翻译结果,翻译步骤,（）从分析树得到描述结点属性间依赖关系的依赖图，由依赖图得到语义规则的计算次序,（1）分析输入符号串，建立分析语法树,（）进行语义规则的计算，得到翻译结果,8.2.3 语法制导定义,对每个产生式编制一个语义子程序 在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译,自底向上传递信息,自顶向下（自左向右）传递信息,1、文法非终结符既有综合属性，也可有继承属性； 2、开始符号没有继承属性； 3、终结符只有综合属性，由词法分析器提供。,几点说明：,print(E.val)打印由E产生的算术表达式的值，可认为这条规则定义了L的一个虚属性。,L E,E E1+T,E T,T T1 * F,T F,F (E),F i,print(E.val),E.val=E1.val+T.val,E.val=T.val,T.val=T1.val F.val,T.val=F.val,F.val=E.val,F.val=i.lexval,例8. 综合属性,语 义 规 则,产生式,一个结点的综合属性值是其子结点的某些属性来决定的,+3*4的注释分析树,通常使用自底向上的分析方法 在每个结点处使用语义规则来计算综合属性值 当一个产生式获得匹配时，就调用相应的语义子程序 从叶结点到根结点进行计算,只含有综合属性的语法制导定义称为S属性定义,8.2.4 S属性定义与自底向上翻译,LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算 LR分析器增加属性值（语义）栈,例8.3 继承属性L.in,int id1,id2,id3,一个结点的继承属性值是由其父结点或兄弟结点的某些属性决定的,8.2.5 L-属性定义(L-属性文法),包含综合属性和继承属性的属性文法（语法制导定义） 如：算术表达式求值的属性文法、说明语句的属性文法,翻译思想,将语义动作插入到产生式的某个位置 特征 规定在语法分析中使用语义规则进行计算的次序 保证当动作使用某属性时，该属性必须是有效的最左派生 表示形式：,例8.4：建立说明语句的翻译方案,将语义动作中继承属性的计算前移，使它出现在其相应文法符号之前 D T L.in := T.type L T intT.type := integer T realT.type := real L L1.in := L.inL1 , idaddtype(id.entry, L.in) L idaddtype(id.entry, L.in),real id1,id2的处理过程 DTL.in:=T.typeL realT.type:=realL.in:=T.typeL realL.in=realL realL.in=real L1.in:=L.inL1,id2addtype(id2.entry,L.in) realL1.in=real L1,id2addtype(id2.entry,L.in) realL1.in=real id1addtype(id1.entry,L1.in),id2addtype(id2.entry,L.in) real id1(id1.entry,real),id2(id2.entry,real),D T L.in := T.type L T int T.type := integer T real T.type := real L L1.in := L.in L1,idaddtype(id.entry,L.in) L id addtype(id.entry, L.in),生成中间代码的目的 (1)便于优化 (2)便于移植,常见的中间代码形式： 后缀式 三地址代码（四元式、三元式和间接三元式 ）图形（抽象语法树、有向无环图）,中间代码：一种介于源语言和目标语言之间的中间语言形式,8. 中间代码,Java语言,.NET框架,GCC,中缀表示 后缀表示 a+b ab+ a+b*c abc*+ (a+b)*c ab+c* a:=b*c+b*d abc*bd*+:=,特点,1、运算对象出现的顺序和原有顺序（从左到右）相同 2、运算符按实际计算顺序（从左到右）出现 3、运算符紧跟在运算对象的后面出现，且没有括号,优点：简明、便于计值,8.3.1 后缀式,分别给出下列表达式的后缀表示,1. -a+b*(-c+d) 2. X:=-(a+b)/(c-d)-(a+b*c) 3. a=c b=d 4. ab+c ada+be,8.3.2 三地址代码,种类,（1）x = y op z形式的赋值语句，其中op是二元运算符。 （2）x = op y形式的赋值语句，其中op是一元运算符。 （3）x = y形式的赋值语句。 （4）无条件转移语句goto L，表示下一个要执行的语句是标号为L的语句。 （5）条件转移语句if x rop y goto L中，rop为关系运算符，如果x和y满足关系rop，就转而执行标号为L的语句，否则顺序执行下一个语句。,2具体实现,四元式,结果：通常是由编译引进的临时变量,例: X=(A+B)*(C+D)-E,T1,T2,T3,T4为临时变量，由四元式优化比较方便,表达式的三元式：,第三个三元 式中的操作数(1) (2)表示第(1)和第 (2)条三元式的计 算结果。,三元式,不便于代码优化：删除某些三元式后可能需作一系列的修改,例：x =y +yz + yz,抽象语法树,8.3.3 图形表示,有向无环图,8.4 表达式及赋值语句的翻译,简单表达式的文法如下： Ai=E EE+E|E*E|-E|(E)|i 非终结符A代表“赋值语句”，语义子程序所涉及到语义变量、语义过程及函数说明如下：,（1）对非终结符的E定义语义变量E.place，即E.place表示存放值的变量名在符号表中的入口地址或临时变量名的整数码。 （）定义语义函数newtemp( )，即每次调用newtemp()时都要回送一个代表新临时变量的整数码。临时变量按产生的次序为，。 （）定义语义过程emit(op,arg1,arg2,result)，其中的emit是产生一个四元式并填入四元式的表中。arg1、arg2是操作数，result 是运算结果。 （4）定义语义函数lookup( ),其功能是审查是否出现在符号表中，是则返回在符号表中的入口指针，否则返回空。,使用上述的语义变量、过程和函数，可以写出文法每个产生式的语义子程序。 （1）Ai=E p=lookup() if(p=NULL) error(); else emit(=,E. place,_,P); （2）EE(1)+E(2) E. place=newtemp( ); Emit(+,E(1).place, E(2).place, E. place) （3） EE(1)*E(2) E. place=newtemp( ); emit(*,E(1).place, E(2).place, E. place) （4） E-E(1) E. place=newtemp( ); emit(uminus,E(1).place,_ , E. place) （5） E(E(1) E. place= E(1). place （6） E i p=lookup() if (p!=NULL) E.place=p; else error();,在上面的语义分析过程中，没有考虑到静态语义检查。在实际应用中，要全面考虑语句的翻译。 例如：EE(1)*E(2) 该语句的语义子程序的翻译可以写成： EE(1)*E(2) E. place=newtemp( ); if E(1).type=int AND E(2).type=int then begin emit(E.place,= , E(1).place, *i, E(2).place); E.type=int end else if E(1).type=real AND E(2).type=real then begin emit(E.place, =, E(1).place, *r, E(2).place); E.type=real end,else if E(1).type=int /*and E(2).type=real*/ then begin t=newtemp; emit(t, =, itr, E(1).place); emit(E.place, =, t, *r, E(2).place); E.type=real end else /* E(1).type=real AND E(2).type=int*/ begin t=newtemp; emit(t,=, itr, , E(2).place); emit(E.place, =, E(1).place , *r,t); E.type=real end; ,例题8.7试分析赋值语句X=-B*(C+D)的语法制导翻译 解答：赋值语句X=-B*(C+D)#的语法制导翻译过程如表8-2所示。,8.4.2布尔表达式的翻译,布尔表达式的文法为：EEE| EE|E|(E)|i|i rop i 其中的rop为，=，运算符。 1布尔表达式值的计算 计算布尔表达式的值通常有两种方法。第一种方法和算术表达式的计算方法一样，根据顺序和优先级一步步计算出来。 例如：1（00）0=1（10）0=100=10=1,另一种方法就是根据布尔表达式的特点实施某种优化。即不必一步一步地计算布尔表达式中所有运算对象的值，而是省略不影响结果的运算。 例如：在计算AB时，若计算出A的值为1，则B的值就无须再计算；在计算AB时，若A的值为0，则B的值无须要再计算，因为AB的值一定为0,2布尔表达式的翻译方法,给出布尔表达式if ab then 1 else 0，根据布尔表达式的第一种计算方法，写出该表达式的四元式为： （1) if ab goto (4) （2） t=0 （3） goto (5) （4） t=1 （5） ,翻译方法如下： E(1) E(2)：E(1)为TRUE，则整个表达式为TRUE ，转向条件为“真”的出口。 E(1)为FALSE，则转向E(2)的判断，若E(2)为TRUE，则整个表达式为TRUE，转向条件为“真”的出口，用E.true指针代表真的出口； 若E(1)为FALSE，则转向E(2)的判断，若E(2)为FALSE，则整个表达式为 FALSE，则转向条件为“假”的出口，用E.false代表假的出口。,E(1) E(2)： E(1)为FALSE，则整个表达式为FALSE ，转向条件为“假”的出口。 E(1)为TRUE，则转向E(2)的判断，若E(2)为TRUE，则整个表达式为TRUE，转向条件为“真”的出口； 若E(1)为TRUE，则转向E(2)的判断。若E(2)为FALSE，则整个表达式为FALSE，转向条件为“假”的出口。 根据上述的思想将布尔表达式翻译成四元式的描述，其中nextstat 给出输出序列中下一个四元式序号，emit 过程每被调用一次，nextstat增加1。,E E(1) E(2) E.place=newtemp; emit(E.place = E(1).place E(2). place) E E(1) E(2) E.place=newtemp; emit(E.place = E(1). Place E(2). place) E E(1) E.place=newtemp; emit(E.place = E(1). place) E(E(1) E.place= E(1).place,Eid1 rop id2 E.place=newtemp; emit(if id1. place rop id2.place goto nextstat+3 ) emit(E. Place = 0) emit( goto nextstat+2) emit(E.place = 1) Etrue E.place=newtemp; emit(E.place = 1) Etrue E.place=newtemp; emit(E.place = 0) ,8.4.3在控制语句中布尔表达式的翻译,2019/6/8,56,S if E then S1 的翻译,代码结构,E.true,E.false,2019/6/8,57,例：if ab then a=a+a,if ab goto C.true (S1.begin) goto C.false (S.next) S1.begin: t1:=a+a a:=t1 S.next:,（1）EE(1) V E(2) backpatch(E(1).false, E(2).codebegin)； E.codebegin= E(1). codebegin E.true= merge(E(1).true, E(2).true ) E.false= E(2).false （2） EE(1)E(2) backpatch(E(1).true, E(2).codebegin); E.codebegin= E(1). codebegin E.true= E(2). true E.false= merge(E(1).false, E(2).false ) （3） EE(1) E.true= E(1). False; E.codebegin= E(1). Codebegin E.false= E(1).true ,（4） E(E(1) E.true= E(1). true; E.false= E(1).false E.codebegin= E(1). codebegin （5） E id1 rop id2 E.true= nextstat; E.codebegin= nextstat; E.false= nextstat+1; emit(if id1.place rop id2.place goto ); emit( goto ); ,（6） Etrue E.true= nextstat; E.codebegin= nextstat; emit( goto ) （7） Efalse E.false= nextstat; E.codebegin= nextstat; emit( goto ) ,代码结构,S if E then S1 else S2 的翻译,例题8.8给出布尔表达式if af then S1 else S2，它翻译成四元式序列为： （1) if af,例题8.8给出布尔表达式if af then S1 else S2，它翻译成四元式序列为： （1） if ab goto E.true （2） goto （3） （3） if cd goto (5) （4）goto E.false （5）if ef goto E.true （6） goto E.false （7） S1的四元式 （p） goto (q) （p+1）关于S2的的四元式 （q）,（7）,（p+1）,（7）,（p+1）,通过上面的例子可以看出，（7）是该条件语句的真出口，(p+1)是该条件语句的假出口。而E.true和E.false必须是在翻译到S1 或S2时才能确定它的语句编号是什么，所以需要回填。并且需要回填的语句很多，如四元式（1）和（5）需要回填E.true的值，（4）和（6）需要回填E.false的值。这些要回填的四元式标号需要记住。因此就采用“拉链”的技术，如果不能记住，则无法回填了。把需要回填E.true的值作为真链，把需要回填E.false的值作为“假“链。,2019/6/8,65,拉链回填,一遍扫描 先产生暂时没有填写目标标号的转移指令； 对于每一条这样的指令作适当的记录； 一旦转移的目标“标号”被确定下来，再将它“回填”到相应的指令中 布尔表达式E设属性E.turelist和E.falselist E.truelist对应真出口Etrue E.falselist对应假出口Efalse 两遍扫描,2019/6/8,66,拉链回填,翻译模式用到如下两个函数： 1merge(p1，p2)：将由p2指向的表接在p1所指向的链表后，返回p1 2backpatch（p，i）：把i作为目标标号回填到p所指向的链表中的每一个转移指令中去。 此处的“链表”都是为“回填”作准备的,2019/6/8,67,拉链回填举例拉链,P1:,n4 (j, , ,0), n5(j,a,b, n4), n6(j=,c,d,n5),n5,n6,n4,2019/6/8,68,拉链回填举例并链,n1 (j,0) n2(j,a,b, n1) n3(j=,c,d,n2),P2: n3,n4 (j, , , ) n5(j,a,b, n4) n6(j=,c,d,n5),P1: n6,0,n3,2019/6/8,69,n4,n2,n3,n5,n6,拉链回填回填,n1 (j, ) n2(j,a,b, ) n3(j=,c,d, ),n4 (j, ) n5(j,a,b, ) n6(j=,c,d, ),P1:,backpatch（p，i）,n5,n4,n3,n2,n1,i,0,i,i,i,i,i,n1,0,拉链的技术如下： （100）goto E.true (200) goto E.true (300) goto E.true 则链成： （100）goto （0） （200) goto（100） （300) goto （200） 把地址300作为链首，地址（100）为链尾，0为链尾标志。,根据上面的翻译思想，我们给出将布尔表达式翻译成四元式的描述，其中 （1）nextstat为给出序列中的下一个四元式的序号。emit过程每调用一次，nextstat的值就增加1。 （2）merge(p1,p2)：把以p1和p2为链首的两条链合并为一条以p2为链首的链。 （3）backpatch(p,t)：把链首p所链接的每个四元式的第四区段（即result）都改写为