编译原理4语义2表达式及赋值语句的翻译

第第 10 10 讲讲 第四章第四章 语义分析和中间代码生成语义分析和中间代码生成l4.1 4.1 语义分析概述语义分析概述l4.2 4.2 属性文法属性文法l4.3 4.3 几种常见的中间语言几种常见的中间语言l4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l4.5 4.5 控制语句的翻译控制语句的翻译l4.6 4.6 数组元素的翻译数组元素的翻译l4.7 4.7 过程或函数调用语句的翻译过程或函数调用语句的翻译l4.8 4.8 说明语句的翻译说明语句的翻译l4.9 4.9 递归下降语法制导翻译方法简介递归下降语法制导翻译方法简介u第四章第四章语义分析和中间代码生成语义分析和中间代码生成l4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译l布尔表达式的翻译布尔表达式的翻译(难点难点)u重点掌握重点掌握l算术表达式语义子程序算术表达式语义子程序l布尔表达式的真假出口布尔表达式的真假出口l布尔表达式的语义子程序布尔表达式的语义子程序l根据翻译图得到布尔表达式的四元式根据翻译图得到布尔表达式的四元式本讲目标本讲目标 4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译u4.4.1 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译l简单变量简单变量：普通变量和常数，不包括数组、结构体成员等复：普通变量和常数，不包括数组、结构体成员等复合型数据结构。合型数据结构。l简单算术表达式简单算术表达式：仅含简单变量的算术表达式：仅含简单变量的算术表达式u简单算术表达式与四元式简单算术表达式与四元式简单算术表达式的简单算术表达式的计值顺序与四元式出现的顺序相同计值顺序与四元式出现的顺序相同，因此很，因此很容易将其翻译成四元式形式。容易将其翻译成四元式形式。当然，这些翻译方法稍加修改也可用于产生三元式或间接三元当然，这些翻译方法稍加修改也可用于产生三元式或间接三元式。式。u1.3.3 1.3.3 语义分析和中间代码生成（续）语义分析和中间代码生成（续）简单算术表达式的计值顺序与四元式出现的顺序相同：简单算术表达式的计值顺序与四元式出现的顺序相同：例如，计算圆柱体表面积的例如，计算圆柱体表面积的C C语言程序：语言程序：s=2*3.1416*r*（h+r）;赋值语句的四元式中间代码：赋值语句的四元式中间代码：（1）（）（*，2,3.1416，T1）（2）（）（*，T1,r，T2）（3）（）（+，h,r，T3）（4）（）（*，T2,T3，T4）（5）（）（=，T4,_，s）回顾：回顾：表达式及赋值语句的翻译表达式及赋值语句的翻译考虑以下文法考虑以下文法GA:A i=E E E+E|E*E|E|(E)|i4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译显然，文法显然，文法GA 是一个二义文法，但通过确定运算符的结合是一个二义文法，但通过确定运算符的结合性及规定运算符的优先级就可避免二义性的发生。性及规定运算符的优先级就可避免二义性的发生。用该文法作为示例的目的：为了更简要地说明用该文法作为示例的目的：为了更简要地说明语义子程序的设语义子程序的设计过程计过程以及以及赋值语句的语法制导翻译过程赋值语句的语法制导翻译过程。如，对于赋值语句如，对于赋值语句x=-b*(c+d)，已经预先规定运算顺序，已经预先规定运算顺序非终结符非终结符A代表代表“赋值句赋值句”非终结符非终结符E代表代表“表达式表达式”4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l1.1.设计设计6 6个产生式的语义子程序个产生式的语义子程序(1)A i=E p=lookup(i.name);if(p=NULL)error();else emit(=,E.place,_,p);例如，赋值语句例如，赋值语句 x=b 刚开始读入到符号栈中，显示为刚开始读入到符号栈中，显示为i=i,使用使用E i规约，得到：规约，得到：i =E（符号栈）（符号栈）_ _ b（语义栈）（语义栈）(a)对非终结符对非终结符E定义语义变量定义语义变量E.place，即用，即用E.place表示存放表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码值的变量名在符号表中的入口地址或临时变量名的整数码所以，所以，E.Place中必须保存中必须保存b在符在符号表中的入口地址；号表中的入口地址；x=b 翻译为翻译为(=,b,_,x)4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l1.1.设计设计6 6个产生式的语义子程序个产生式的语义子程序(1)A i=E p=lookup(i.name);if(p=NULL)error();else emit(=,E.place,_,p);(b)定义语义函数定义语义函数lookup(i.name)，其功能是审查，其功能是审查终结符终结符i.name是否出现在符号表中，是则返回是否出现在符号表中，是则返回i.name在符号表的入口指针，在符号表的入口指针，否则返回否则返回NULL。(c)定义语义函数定义语义函数emit(op,arg1,arg2,result)，emit的功能是产的功能是产生一个四元式并填入四元式表中。生一个四元式并填入四元式表中。4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译(2)E E(1)+E(2)E.place=newtemp();emit(+,E(1).place,E(2).place,E.place);(d)定义语义函数定义语义函数newtemp()，即每次调用，即每次调用newtemp()时都将回时都将回送一个代表新临时变量的整数码；临时变量名按产生的顺序可送一个代表新临时变量的整数码；临时变量名按产生的顺序可设为设为T1、T2(3)E E(1)*E(2)E.place=newtemp();emit(*,E(1).place,E(2).place,E.place);(4)EE(1)E.place=newtemp();emit(uminus,E(1).place,_,E.place);4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译(5)E(E(1)E.place=E(1).place;(6)Ei p=lookup(i.name);if(p!=NULL)E.place=p;else error();例例4.2 试分析赋值语句试分析赋值语句X=-B*(C+D)的语法制导翻译过程。的语法制导翻译过程。解答解答 赋值语句赋值语句X=-B*(C+D)的语法制导翻译过程如表的语法制导翻译过程如表4.2所示所示(加工分析过程参考表加工分析过程参考表4.1)。其实，利用其实，利用带注释的语法树进行规约的同时，带注释的语法树进行规约的同时，就可以完成相应的语义分析就可以完成相应的语义分析（一起看黑板）。（一起看黑板）。表表4.2(1)赋值语句赋值语句X=B*(C+D)的翻译过程的翻译过程表表4.2(2)赋值语句赋值语句X=B*(C+D)的翻译过程的翻译过程4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译u4.4.2 布尔表达式的翻译布尔表达式的翻译 1 1、布尔表达式的组成、布尔表达式的组成l布尔表达式布尔表达式：由运算符与运算对象组成。：由运算符与运算对象组成。定义布尔变量定义布尔变量 A A、B B、C C、D D A=A=bop1bop1 B B bop2bop2 C C bop3bop3 D Dl(1)(1)运算符：非运算符：非（单目）、与（单目）、与（双目）、或（双目）、或（双目）（双目）注意：注意：1、优先级：、优先级：2、和和服从服从左左结合结合 3、运算符的优先级：算术、运算符的优先级：算术 关系关系 布尔布尔“=”4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l(2)(2)运算对象运算对象(三种三种)：l布尔变量布尔变量l布尔常量（布尔常量（false、true）l关系表达式关系表达式1 1、运算符、运算符rop：、=、2 2、运算对象：算术表达式、运算对象：算术表达式3 3、返回值类型：、返回值类型：boolbool类型类型例：例：bool a,b,c;int x,y,z a=b c true (x+y=z)a=b c true x+y=z思考：运算顺序？思考：运算顺序？4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译 2 2、布尔表达式的计算、布尔表达式的计算l了解了解1 1：对对布尔运算、关系运算、算术运算的运算对象的类型布尔运算、关系运算、算术运算的运算对象的类型可不区分布尔型或算术型，假定不同类型的变换工作将在需可不区分布尔型或算术型，假定不同类型的变换工作将在需要时强制要时强制执行。执行。l了解了解2：布尔表达式在程序语言中不仅用作布尔表达式在程序语言中不仅用作计算布尔值，计算布尔值，还作还作为为控制语句控制语句(如如if-else、while等等)的条件表达式的条件表达式，用以确定程序，用以确定程序的控制流向。无论布尔表达式的作用如何，按照程序执行的的控制流向。无论布尔表达式的作用如何，按照程序执行的顺序，都必须先计算出布尔表达式的值顺序，都必须先计算出布尔表达式的值。l计算布尔表达式的值有两种方法：计算布尔表达式的值有两种方法：l1、按照优先级和各变量的值，一步步求出结果；、按照优先级和各变量的值，一步步求出结果；l2、优化计算：、优化计算：b=true;a=b c;(不计算不计算c,a=true)b=false;a=b c;(不计算不计算c,a=false)思考：思考：C C语言的强制转换？语言的强制转换？4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译 2 2、布尔表达式的计算、布尔表达式的计算l所以，按照优化方式计算布尔表达式，需要给出整个表达式所以，按照优化方式计算布尔表达式，需要给出整个表达式的的真假出口真假出口。l(1)真出口：真出口：若若E(1)为真为真，则，则E为真；为真；若若E(2)为为真真，则则E为真为真；所以所以E的真出口有两个：的真出口有两个：E(1)的真出口和的真出口和E(2)的真的真出口。出口。l(2)假出口：假出口：E(1)的假出口并不是的假出口并不是E的假出口，的假出口，(1)如果为假，必须计算如果为假，必须计算E(2)，因此：，因此：E(2)的假出口是整个的假出口。的假出口是整个的假出口。(a)E=E(1)E(2)4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译 2 2、布尔表达式的计算、布尔表达式的计算l(1)假出口：假出口：若若E(1)为假，则为假，则E为为假假；若若E(2)为假，为假，则则E为为假假；所以所以E的的假假出口有两个：出口有两个：E(1)的的假假出口和出口和E(2)的的假假出口。出口。l(2)真出口：真出口：E(1)的的真真出口并不是出口并不是E的的真真出口，出口，(1)如果为如果为真真，必须计算，必须计算E(2)，因此：，因此：E(2)的的真真出口是整个的出口是整个的真真出口。出口。练习布尔表达式练习布尔表达式 abcd 的真假出口。的真假出口。(b)E=E(1)E(2)4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l布尔表达式中，每个布尔分量一般至少对应两个四元式。布尔表达式中，每个布尔分量一般至少对应两个四元式。例如例如：E=E(1)E(2)=ab if(a|b)c=1;对应对应:(1)(jnz,a,_,真出口真出口）(2)(j,_,_,3)(3)(jnz,b,_,真出口真出口)(4)(j,_,_,假假出口出口)(5)(=,c,_,1)(6)if (6)if语句后面的四元式语句后面的四元式 l在这个例子中，真出口和假出口不能在生成四元式的当时产在这个例子中，真出口和假出口不能在生成四元式的当时产生；假如生；假如a a和和b b并不是简单的布尔变量，或者条件语句后执行并不是简单的布尔变量，或者条件语句后执行的语句并不是仅仅一句，所有的真假出口都无法给定。的语句并不是仅仅一句，所有的真假出口都无法给定。4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译 3 3、布尔表达式的文法：、布尔表达式的文法：l(1)普通布尔表达式文法：普通布尔表达式文法：l(2)优化的布尔表达式文法：优化的布尔表达式文法：好处：在句子中，如果出现好处：在句子中，如果出现“ab”或或“a b”之类的表之类的表达式，当扫描到达式，当扫描到“a”或或“a”之后就立即可以进行规约，之后就立即可以进行规约，不用去关系不用去关系b的取值。的取值。GE:EEE|EE|E|(E)|i|i rop iGE：EEAE|EBE|E|(E)|i|i rop i EAE EBE4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译 4 4、解决、解决“真真”、“假假”出口问题的方法：拉链和回填出口问题的方法：拉链和回填l(1)拉链：在同一个表达式内，每个四元式产生的时候，强制拉链：在同一个表达式内，每个四元式产生的时候，强制其出口为其出口为0，若后面一个四元式和它出口相同，用，若后面一个四元式和它出口相同，用前面产生式前面产生式的序号的序号去填充去填充后面产生式的跳转位置后面产生式的跳转位置（result），从而将不同），从而将不同的的四元式四元式链接起来，俗称链接起来，俗称“拉链拉链”。假如下面三个四元式都是真出口：假如下面三个四元式都是真出口：(i)(_,_,_,0)(j)(_,_,_,0)(k)(_,_,_,0)注意：注意：(k)为链首，为链首，(i)为链尾，链尾为链尾，链尾result=0(i)(_,_,_,0)(j)(_,_,_,i)(k)(_,_,_,j)4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l(1)拉链拉链算法算法：p1,p2各自是两个链首，将它们合并成一个以各自是两个链首，将它们合并成一个以p2为链首的新链为链首的新链 merge(p1,p2)if(p2=0)return(p1);else p=p2;while(四元式四元式p的第四区段内容不为的第四区段内容不为0)p=四元式四元式p的第四区段内容；的第四区段内容；把把p1填进四元式填进四元式p的第四区段；的第四区段；return(p2);/else /merge(r1)(_,_,_,0)(q1)(_,_,_,r1)(p1)(_,_,_,q1)(r2)(_,_,_,0)(q2)(_,_,_,r2)(p2)(_,_,_,q2)算法执行完，其实就是将算法执行完，其实就是将(r2)中的中的result变为变为p1，最终形成一个链，最终形成一个链4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l(2)回填回填算法算法：把链首：把链首p所链接的每个四元式的第四区段所链接的每个四元式的第四区段(result)都改写为地址都改写为地址t。(r)(_,_,_,0)(q)(_,_,_,r)(p)(_,_,_,q)Backpatch(p,int t)Q=p;while(Q!=0)q=四元式四元式Q的第四区段内容；的第四区段内容；把把t填进四元式填进四元式Q的第四区段；的第四区段；Q=q;/while/Backpatch(r)(_,_,_,t)(q)(_,_,_,t)(p)(_,_,_,t)4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l(3)其它需要说明的问题：其它需要说明的问题：1、对于每个非终结符、对于每个非终结符E，我们需要为它赋予两个语义值，我们需要为它赋予两个语义值 E.tc和和E.fc，分别用来记录，分别用来记录E所对应的四元式的所对应的四元式的真链和假链真链和假链。也就是说，也就是说，为每个非终结符为每个非终结符E添加两个属性：添加两个属性：tc和和fc；因此，；因此，规约的时候，再次扩充语义栈，添加规约的时候，再次扩充语义栈，添加tc栈和栈和fc栈；栈；2、nxq:这是一个这是一个int变量，翻译工作开始之前，初始值变量，翻译工作开始之前，初始值 是是1，翻译工作开始之后，每执行一次，翻译工作开始之后，每执行一次emit()，nxq自自增增1，即：即：nxq=四元式个数四元式个数+1；4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译 5 5、布尔表达式的翻译、布尔表达式的翻译l1、文法：、文法：l2、语义子程序：、语义子程序：例如例如 if(a)b;GE：EEAE|EBE|E|(E)|i|i rop i EAE EBE(1)Ei（布尔值布尔值）E.tc=nxq;E.fc=nxq+1;emit(jnz,entry(i),_,0);emit(j,_,_,0);(2)Ei(1)rop i(2)E.tc=nxq;E.fc=nxq+1;emit(jrop,entry(i(1),entry(i(2),0);emit(j,_,_,0);4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译说明说明(5):如果如果E(1)为真，表达式的值取决于为真，表达式的值取决于之后，可以回填之后，可以回填 E(1)的的tc链，跳转到链，跳转到nxq;如果如果E(1)为假，那么不必计算后面，为假，那么不必计算后面，EA直接为假。直接为假。(3)E(E(1)E.tc=E(1).tc;E.fc=E(1).fc;(4)EE(1)E.tc=E(1).fc;E.fc=E(1).tc;(5)EAE(1)Backpatch(E(1).tc,nxq);EA.fc=E(1).fc;(6)EEAE(2)E.tc=E(2).tc;E.fc=merge(EA.fc，E(2).fc);4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译(7)EBE(1)Backpatch(E(1).fc，nxq);EB.tc=E(1).tc;(8)EEBE(2)E.fc=E(2).fc;E.tc=merge(EB.tc，E(2).tc);说明说明(8):能使用能使用(8)规约，说明规约，说明E(1)为假，为假，E(1)的真出口必须链的真出口必须链接到接到E(2)，因此要拉链操作；，因此要拉链操作；E的真假出口都必须依赖于的真假出口都必须依赖于E(2)，因此因此E.fc=E(2).fc;E.tc=E(2).tc;4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l3、步骤：、步骤：l(1)首先规约布尔表达式，如首先规约布尔表达式，如“abcd”，通过语义子程，通过语义子程序翻译出初始的四元式；序翻译出初始的四元式；l(2)添加真假出口的四元式标记添加真假出口的四元式标记l(3)回填真假出口，经判断得知，回填真假出口，经判断得知，整个布尔表达式的真出口是整个布尔表达式的真出口是106，假出口是假出口是q(回填链回填链尾为尾为0的的tc、fc)100(jnz，a，_，102)101(j，_，_，104)102(jnz，b，_，0)103(j，_，_，104)104(j，c，d，102)105(j，_，_，0)T:106 F:qif (abcd)else 4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译例例4.3 试给出布尔表达式试给出布尔表达式abcd作为控制条件的四元式中作为控制条件的四元式中间代码。间代码。解答解答 设四元式序号从设四元式序号从100开始，则布尔表达式开始，则布尔表达式abcd的的 分析过程为：分析过程为：j规则：Ei Ebcd初始输入：abcd语义栈(tc/fc)：E.tc=100E.fc=101四元式：100(jnz,a,_,0)101(j,_,_,0)Ei（布尔值布尔值）E.tc=nxq;E.fc=nxq+1;emit(jnz,entry(i),_,0);emit(j,_,_,0);规则：EAE(1)EA bcd语义栈(tc/fc)：EA.fc=101四元式：100(jnz,a,_,102)101(j,_,_,0)nxq=1024.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译规则：Ei EA E(2)cd语义栈(tc/fc)：E.tc=102E.fc=103EA.fc=101四元式：102(jnz,b,_,0)103(j,_,_,0)规则：EEAE(2)Ecd语义栈(tc/fc)：E.tc=102E.fc=103四元式：101(j,_,_,0)103(j,_,_,101)4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译规则：EBE(1)EB cd语义栈(tc/fc)：EB.tc=102四元式：101(j,_,_,104)103(j,_,_,104)规则：Ei rop i EB E语义栈(tc/fc)：四元式：104(j,c,d,0)105(j,_,_,0)E.tc=104E.fc=105EB.tc=102规则：E EBE(2)E语义栈(tc/fc)：四元式：104(j,c,d,102)E.tc=102E.fc=1054.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译第一步结束，得到第一步结束，得到 abcd 的四元式如下：的四元式如下：100(jnz，a，_，102)101(j，_，_，104)102(jnz，b，_，0)103(j，_，_，104)104(j，c，d，102)105(j，_，_，0)第三步，回填真假出口第三步，回填真假出口:检查真假链尾仍然是检查真假链尾仍然是0的四元式，进行回填。的四元式，进行回填。第二步，定义真假出口：第二步，定义真假出口：T：106 F:q最终得到：最终得到：100(jnz，a，_，102)101(j，_，_，104)102(jnz，b，_，106)103(j，_，_，104)104(j，c，d，106)105(j，_，_，q)T：106 F:q4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译l重点内容：如何不进行规约和语义子程序，得到布尔表达式的四重点内容：如何不进行规约和语义子程序，得到布尔表达式的四元式？元式？解答：根据布尔表达式的语义子程序，可以发现解答：根据布尔表达式的语义子程序，可以发现(规律规律)：只有两个文法产生四元式：只有两个文法产生四元式：(1)Ei（布尔值布尔值）所以，每个布尔变量所以，每个布尔变量a产生产生：(jnz,a,_,0);(j,_,_,0);(2)Ei(1)rop i(2)同样每个关系表达式同样每个关系表达式 x rop y产生产生：(jrop,x,y,0);(j,_,_,0);四元式的四元式的result字段填写变量的真假出口便能翻译布尔表达式字段填写变量的真假出口便能翻译布尔表达式解答解答 该布尔表达式的翻译图如图该布尔表达式的翻译图如图4-9所示，所对应的四元式所示，所对应的四元式代码如下：代码如下：例例4.4 试给出布尔表达式试给出布尔表达式amncxy的四元式代码的四元式代码 100(jnz，a，_，108)101(j，_，_，102)102(j，m，n，108)103(j，_，_，104)104(jnz，c，_，106)105(j，_，_，q)106(j，x，y，108)107(j，_，_，q)T:108 F:q 图图4-9 例例4.4的翻译图的翻译图4.4 4.4 表达式及赋值语句的翻译表达式及赋值语句的翻译课堂练习：试着课堂练习：试着通过翻译图通过翻译图给出布尔表达式给出布尔表达式abcd作为作为控制条件的四元式中间代码。控制条件的四元式中间代码。解答解答