第5章语法制导翻译和中间代码生成.ppt

文法和语言的基本知识文法和语言的基本知识编译概述编译概述词法分析与有穷自动机词法分析与有穷自动机语法分析语法分析语法制导翻译和中间代码生成语法制导翻译和中间代码生成 符号表的组织和管理符号表的组织和管理1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 6代码优化代码优化静态存储分配静态存储分配目标代码生成目标代码生成7 7 7 78 8 8 89 9 9 9编译中的语义处理是两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间边式形式（中间代码），要么生成实际的目标代码。5.1 5.1 属性文法属性文法 属属性性文文法法的的形形式式定定义义：一一个个属属性性文文法法形形式式上上可可定定义义为为一一个个三三元元组组A A，A=A=（G G，V V，F F）。其其中中G G表表示示一一个个上上下下文文无无关关文文法法；V V表表示示属属性性的的有有穷穷集集；F F表示有关属性的断言或谓词的有穷集。表示有关属性的断言或谓词的有穷集。属属性性可可以以分分为为综综合合属属性性和和继继承承属属性性两两类类。综综合合属属性性一一般般用用于于自自下下而而上上传传递递信信息息，而而继继承承属属性性常常用于自上而下传递信息。常常用于自上而下传递信息。简单算术表达式求值的属性文法。简单算术表达式求值的属性文法。规则 语义规则1.SE print（E.val）2.EE1T E.val:=E1.valT.val3.ET E.va1:=T.valv 4.TT1 F T.val:=T1.val F.val5.TT1 T.val:=T1.val6.F（E）F.val:=E.val7.Fdigit F.7.Fdigit F.valval:=digit.:=digit.lexvallexval 例例5.15.1：此此例例中中，每每一一个个非非终终结结符符都都有有一一个个表表示示整整数数值值的的属属性性valval，如如E.va1E.va1，表表示示E E的的整整数数值值。按按照照语语义义规规则则，每每个个规规则则的的左左部部符符号号如如E E，T T，F F等等的的属属性性值值的的计计算算取取决决于于各各自自相相应应的的右右部部非非终终结结符符，我我们们把把这这种种属属性性称称为为综综合合属属性性。单单词词digitdigit仅仅有有综综合合属属性性，它它的的值值是是由由词词法法分分析析程程序序提提供供的的。与与规规则则SESE关关联联的的语语义义规规则则是是一一个个过过程程printprint（E.E.vdvd），其其功功能能是是打打印印由由E E产产生生的的表表达达式式的的值值。对对于于在在语语义义规规则则中中并并没没有有出出现现文文法符号法符号S S，我们认为其属性是虚的或者空的。我们认为其属性是虚的或者空的。说明语句中各种变量的类型信息的语义描述。规则 语义规则1.DTL L.in:=T.type2.Tint T.type:=integer3.Treal T.type:=real4.LL1，id L1.in:=L.in addtype（id.entry，L.in）5.Lid addtype（id.entry，L.in）例例5.25.2：与例中对应的原文法可以表示为1.Dint Lreal L2.LL，idid下图是句子int id1，id2的语法树。用“”表示属性信息的传递情况。DTLLint，id1id2属性信息的传递情况属性信息的传递情况5.2 5.2 语法制导翻译概述语法制导翻译概述 语法制导翻译技术分为自底向上语法制导翻译和自顶向下语法制导翻译。下面以LR语法制导翻译为例，讨论如何具体实现语法制导翻译。假定有输入串34 5，这是一个简单的算术表达式，相应的文法及各产生式的语义规则见例5.1。表达式34 5的语法制导翻译法求值过程语法树描述图E.E.valval:=3:=33 35 5E.E.valval:=23:=234 4E.E.valval:20:20E.E.valval:=5:=5E.E.valval:=4:=4+SnSny.y.valvalY YSnSn-1-1x.x.valvalX XS0S0-#状态栈状态栈语义值栈语义值栈文法符号符号栈文法符号符号栈扩充的扩充的LRLR分析栈分析栈 状态状态actionactiongotogoto（）d d#E ET TF F0 0s4s4s5s51 12 23 31 1s6s6accacc2 2s7s7r2r2r2r2r2r23 3r4r4r4r4r4r4r4r44 4s4s4s5s58 82 23 35 5r6r6r6r6r6r6r6r66 6s4s4s5s59 93 37 7s4s4s5s510108 8s6s6s11s119 9s7s7r1r1r1r1r1r11010r3r3r3r3r3r3r3r31111r5r5r5r5r5r5r5r5LRLR分析表分析表 步骤状态栈语义栈符号栈剩余串主要动作10-#345#205-#345#303-3#F45#r6402-3#T45#r4501-3#E45#r26016-3-#E5#70165-3-#E45#80163-3-4#EF5#r690169-3-4#ET5#r41001697-3-4-#ET5#11016975-3-4-#ET5#120169（10）-3-4-5#ETFr6130169-3-20#ET#r31401-23#E#r115acc表达式3 4 5的语法语义分析和计值过程 5.3 5.3 中间语言中间语言 所谓中间语言，也称中间代码，是复杂性介于源程序语言和机器语言的一种记号系统。一般来说，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，使生成的的目标代码更为高效，通常采用中间语言。编译程序所使用的中间语言形式较多。常见的逆波兰式、三元式、四元式和树形表示等。逆波兰式是最简单的一种中间语言形式，用逆波兰式表示的表达式也称做后缀式。它的特点是将运算对象写在前面，把运算符号写在后面，比如把xy写成xy，把x y写成xy。对于简单表达式E，相应的逆波兰式E遵循下面的转换规则：表达式 逆波兰式 E E (E)E 5.3.1 逆波兰式逆波兰式 E E （负号“”是一元运算符，为了区别于减号“”，通常写成）E1 op E2 E1 E2 op如，表达式xy z的逆波兰式为x y z；赋值语句x:=x yy/z的逆波兰式为xxy yz/:=。用逆波兰式表示表达式，其最大的优点是从左至右扫描该算术表达式的逆波兰式：每碰到运运算算对对象象，就就把把它它推推进进栈栈；碰碰到到运运算算符符，若若该该运运算算符符是是k k目目运运算算符符，则则对对找找顶顶部部的的k k个个运运算算对对象象实实施施该该运运算算，并并用用运运算算结结果果代代替替这这k k个个运运算算对对象象并并入入钱钱。这这样样，当当将将整整个个后后缀缀式式扫扫描描完完毕毕，该该表表达达式式的的结结果果也也就就计计算出来了算出来了。t1:=xxt1yzt2:=y zt1t2t3:=t1t2同时同时y、z入栈入栈t3逆波兰式的计值过程逆波兰式的计值过程 算术表达式算术表达式x xy y z z 的逆波兰的逆波兰式为式为x x yz yz ，在栈中的计值过程如图在栈中的计值过程如图所示。所示。例例5.35.3：三元式是中间语言的另一种形式，每个三元式由三个部分组成:算符op，运算对象arg1，运算对象arg2。三元式的一般格式为：（i）（op，arg1，arg2）。其中（i）为序号。如表达式a bc d可用三元式表示为：（1）（，a，）（2）（，（1），b ）（3）（，c，d ）5.3.2 三元式和树形表示三元式和树形表示（4）（，（2），（3）“”是一目运算符（这里用表示），用来使a取反，只需选用一个运算对象，不妨规定只用arg1，至于多目算符，可采用多个相继的三元式表示。2.树形表示树形表示实际上是三元式的另一种表示形式，例如，表达式a bc d可用如下树形表示如下。3.间接三元式 4.为了尽量不改变三元式表，可以另设一张间接码表来表示有关三元式在三元式表的计值顺序。用这种方法获得的中间代码称为间接三元式。a a b bc c d d 的树形表示的树形表示 a a b b-d dc c例如，表达式a:=xy z b:=ty z的间接三元式表示如图所示。的间接三元式表示如图所示。三元式列表三元式列表间接码表间接码表（1 1）（）（，y y，z z）（2 2）（，）（，x x，（，（1 1）（3 3）（）（:=:=，a a，（，（2 2）（4 4）（，）（，t t，（，（1 1）（5 5）（）（:=:=，（，（4 4）（1 1）（2 2）（3 3）（1 1）（4 4）（5 5）间接三元式表示间接三元式表示 采用采用这这种表示方法，当种表示方法，当编译编译程序程序产产生一个三生一个三元式元式时时，就，就查查看三元式表中是否存在看三元式表中是否存在该该三元式，三元式，若存在，若存在，则则不再重复填入三元式表，而只是将不再重复填入三元式表，而只是将该该三元式的序号填入三元三元式的序号填入三元码标码标中。如上例中的三元中。如上例中的三元式（式（1 1）（）（，y y，z z），），其序号（其序号（1 1）在）在间间接接码码表中出表中出现现了两次，而了两次，而该该三元式在三元式表中三元式在三元式表中实实际际只出只出现现一次。一次。1.四元式在在编编译译过过程程产产生生的的各各种种中中间间语语言言中中，四四元元式式是是比比较较普普遍遍采采用用的的一一种种形形式。与三元式类似，四元式由四个部分组成，算符op，运算对象arg1和arg2，运算结果t。四元式的一般格式为：（i）（op，arg1，arg2，t）其中，（i）为序号，运算对象和运算结果可以是用户自己定义的变量，也可以是编译程序引进的临时变量，运算对象还可以是常数。例如a:=bc d的四元式表示如下:（1）（，c，d，t1）（2）（，b，t1，t2）（3 3）（）（:=:=，t2 t2，a a）四四元元式式和和三三元元式式在在形形式式上上很很相相似似，不不同同之之处处主主要要在在于于对对中中间间结结果果的的引引用用方方式式。也也就就是是说说，四四元元式式之之间间的的联联系系是是通通过过引引入入临临时时变变量量来来实实现现，而而三三元元式式则则是是通通过过三三元元式式编编号号来来传传递递中中间间结结果果的。的。2.三地址码就像树形表示和三元式一样，三地址代码也可以看成是四元式的另一种表示方式，它比四元式更直观、更易于理解。三地址码的一般格式为t:=arg1 op arg2其中t，arg1，arg2，op的含义与四元式同。这其实就是一个赋值语句，只是与赋值语句不同的是：在三地址码中赋值符号的右边最多只能有一个运算符。5.4 自底向上语法制导翻译自底向上语法制导翻译 语法制导翻译分为自底向上和自底向下两种。自底向上语法制导翻译方法就是在自底向上语法分析过程中逐步执行语义规则。也就是在每次归约的同时执行相应的语义动作。简单算术表达式和赋值语句是指不含数组元素、记录等复杂数据结构的算术表达式和赋值语句。5.4.1 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译布布尔尔表表达达式式也也叫叫逻逻辑辑表表达达式式，是是由由布布尔尔运运算算符符和和具具有有逻逻辑辑值值的的运运算算对对象象构构成成。布布尔尔运运算算符符有有三三个个，即即not、and和和or（或或者者表表示示为为、和和）。布布尔尔运运算算符符的的优优先先顺顺序序（从从高高到到低低）为为、和和，和和 服服从从左左结结合合，为为一一目目运运算算符符。具具有有逻逻辑辑值值的的运运算算对对象象可可以以是是逻逻辑辑表表达达式式，也也可可以以式式关关系系表表达达式式或或者者常常量量。关关系系表表达达式式是是最最简简单单的的逻逻辑辑表表达达式式，运运算算对对象为算术表达式。关系运算符有、象为算术表达式。关系运算符有、5.4.2 布尔表达式的翻译布尔表达式的翻译、等等等等，关关系系运运算算符符的的优优先先级级相同，但运算优先级较低。相同，但运算优先级较低。在在程程序序设设计计语语言言中中，布布尔尔表表达达式式的的作作用用有有两两个个方方面面，其其一一是是计计算算布布尔尔值值，其其二二是是作作为为控控制制流流语语句句（如如if if E E then then S S1 1 else else S S2 2，while while E E dodo等等）中中的的条条件件表表达达式式，用用来来控控制制程序程序转转向。向。计计算算布布尔尔表表达达式式的的计计值值方方法法一一般般有有两两种种，第第一一种种方方法法是是与与算算术术表表达达式式的的计计值值方方法法相相同同，即按照表达式的运算即按照表达式的运算顺顺序，逐步序，逐步计计算出各个算出各个部分的部分的值值，最后得出整个表达式的，最后得出整个表达式的值值。下面下面我们用我们用1 1表示逻辑值表示逻辑值truetrue，用用0 0表示逻辑值表示逻辑值falsefalse，那么布尔表达式那么布尔表达式1 1 or or（0 and not 0 and not 0 0）and 1and 1的计值过程为的计值过程为:1 1 or or（0 and not 0 0 and not 0）and 1and 1=1 or=1 or（0 and 10 and 1）and 1and 1=1 or 0 and 1=1 or 0 and 1=1 or 0=1 or 0=1=1 第第二二种种计计算算方方法法是是采采取取优优化化措措施施，只只计计算算部部分分表表达达式式，如如要要计计算算E E1 1 or or E E2 2，若若计计算算出出E E1 1的的值值为为1 1，那那么么E2E2值值就就无无需需计计算算，因因为为不管不管E E2 2的的值值如何，如何，E E1 1 or E or E2 2的的值值都都为为1 1。当然，对布尔表达式采用不同的计值方法，与之相应的翻译方法也不同。按照布尔表达式的第一种计值方法。布尔表达式E1 or E2 and not E3翻译成的四元式序列可以表示为（1）tl:=not E3（2）t2:=E2 and tl（3）t3:=E1 or t2 如如果果E1E1是是一一个个关关系系表表达达式式，如如A AB B，那那么我们可以把它看成与之等价的条件语句么我们可以把它看成与之等价的条件语句if if A AB B then then 1 1 else else 0 0来来进进行行处处理理，翻翻译译成成的四元式序列的四元式序列为为：（l l）if aif ab b goto goto（4 4）（2 2）t:=0t:=0（3 3）gotogoto（5 5）（4 4）t:=1t:=1（5 5）其其中中用用临临时时变变量量t t存存放放布布尔尔表表达达式式a ab b的的值值，（5 5）为后续的四元式序号。）为后续的四元式序号。当布尔表达式出现在控制语句（如if-then；if-then-else和while-do等）中用做条件控制时，布尔表达式的作用就不仅仅是计值了，更重要的是决定程序控制流的转向。三种控制语句的语法及其代码结构如下控制结构 语法if-then if E then S1if-then-else if E then S1 else S2while-do while E do S1布尔表达式E的值（真或假）决定着控制流的转向，我们把E取真值和取假值时的两个出口分别叫做真出口和假出口，出口的目标分别叫E.true和E.false。三种控制语句的代码结构三种控制语句的代码结构 E E的代码的代码S1S1的代码的代码E E的代码的代码S1S1的代码的代码S2S2的代码的代码E E的代码的代码S1S1的代码的代码T TF FF FF FT TT T if-thenif-then if-then-elseif-then-else while-dowhile-do那么，对于E为a rop b的形式生成代码为:if a rop b goto E.true goto E.false值得注意的是，对于值得注意的是，对于E E为为E1or E2E1or E2的形式的的形式的情况，如果情况，如果E1E1为真，则为真，则E E为真，即为真，即E1E1的真出口和的真出口和E E的真出口一样，无需考虑的真出口一样，无需考虑E2E2；如果如果E1E1为假，就为假，就必须计算必须计算E2E2的值，这时的值，这时E1E1的假出口就是的假出口就是E2E2代码代码的第一个四元式标号，这时的第一个四元式标号，这时E2E2和和E E具有相同的真、具有相同的真、假出口。假出口。例例5.4 5.4：布尔表达式ad可以翻译为如下四元式序列:（1）if ad goto E.truegoto E.false例例5.4 5.4：分分析析语语句句if if ab ad cd then then S1 S1 else S2else S2 分分析析可可知知，当当abadcd；但是，若但是，若abad是否为真，若cd为真，则执行S1语句序列，若cd为假，则执行S2语句序列。所以，当a d分别为真时，程序控制流的转向是一致的，即具有相同真出口。根据上述分析可得到如下四元式：（1）if ad goto（5）（4）goto（p1）（5）（关于S1的四元式序列）（p）goto（q）（p1）（关于S2的四元式序列）（q）（控制语句的后继四元式序列）分析可知，上述（5）是整个布尔表达式的真出口，但是在生成（1）（3）的时候，地址（5）是未知的，必须要等到将整个布尔表达式的四元式产生完毕后才知道。所以这个地址需要回填。同理，（p1）是假出口，在生成（4）的时候该地址也是未知的，因此也需要回填。为了记录需要回填地址的四元式，通常采用“拉链”的办法：把需要回填E.true和E.false的四元式分别形成一条链，分别叫做“真”链和“假”链。考虑上述四元式序列中，真链的形成过程：（1）if ad goto E.true则拉链如下（1）if ad goto（1）其中，地址（3）称作链首，0作为链尾标志，即地址（1）为链尾。在语法制导翻译中，为及时回填四元式中真假出口信息，需用到下列数据结构1.用E.true和E.false分别表示真链和假链；用next指向下一四元式的地址，next的初值为1，每生成一个四元式，其值自动累加1。2.用变量E.scode表示表达式E的第一个四元式序号。3.函数backpatch（p，t），功能是把p所链接的每个四元式的第四区段回填为t。4.函数merge（p1，p2），其功能是将以p1和p2为链首的两条链合并为1条，并返回合并后的链首值。控制语句是指程序设计语言中的if-then，if-then-else，while-do等含条件转移的语句。如将if 语句文法改写为GS：（1）SC S1 （2）STpS2 （3）Cif E then （4）TpCS1 else while-do语句文法可改写为GS:（1）SWdS15.4.5 简单说明语句的翻译简单说明语句的翻译 （2）WdW E do （3）Wwhile那么语句while（A B）do if（CD）then Y:=X1将被翻译成如下一组四元式:if AB goto（3）(1)goto（8）(2)if CD goto（5）(3)goto（1）(4)T:=X1(5)Y:=T(6)goto（1）比较常见的两种循环语句：while-dowhile-do语语句句和forfor循循环环语语句句。while-dowhile-do语语句句已已经经在在上上一节中介绍，一节中介绍，forfor循环语句，一般形式为循环语句，一般形式为:for i:=Efor i:=E1 1 step E step E2 2 until E until E3 3 do do S Sl lt t为为循循环环控控制制变变量量，E E1 1是是i i的的初初值值，E E2 2为为步步长长，E E3 3是是i i的的终终值值，S S1 1是是循循环环体体。语语句句代代码码结结构构见见下下图图：5.4.4 循环语句的翻译循环语句的翻译对于循环语句:for i:=1 step 2 untile n do x:=yz图图 5.16 5.16 forfor循环语句的代码结构循环语句的代码结构 i:=E1 i:=E1 i E3?i E3?F FT Ti:=i+E2 i:=i+E2 S1S1的代码的代码可以翻译成如下四元式序列：1i:=12goto 43i:=i24if in goto 65goto 1086t:=yz7x:=t8goto 3说明语句有常量说明语句、变量说明语句、类型说明语句、过程说明语句等等。说明语句的功能就是用来定义各种形式的有名实体，如常量、变量、过程、函数、数组、记录等等，在编译过程中，这些被定义的实体的名字和性质被登记在符号表中，以便编译程序及时检查实体的引用和说明是否一致。简单说明语句可用语法定义如下：Dintegernamelist 5.4.5 简单说明语句的翻译简单说明语句的翻译 Drealnamelist namelistnamelist，id namelistid 其中关键字integer和real分别表示整型、实型，用来定义后继列表中一组名字的性质（类型）。这里，对简单说明语句的翻译，就是要将被定义的实体的名字及其性质登录到符号表中去。按按照照自自底底向向上上的的方方法法对对上上述述形形式式的的文文法法进进行行制制导导翻翻译时，显然存在着这样一个问题，即我们必须译时，显然存在着这样一个问题，即我们必须首先用一个队列或者栈把所有的名字都保存下来形成一个串namelist，然后再把它们的性质成批登记到符号表。这样做，无疑给系统带来了额外的开销，增加了系统的负担。于是，我们把上述的文法进行如下改写:DD1，idDinteger idDreal id这样，每当读进一个id时，就可以及时地把它的性质登记到符号表中，从而避免了将id集中起来再成批登记所带来的麻烦。为改写后的文法中每个产生式定义相应的语义规则：定义一个一个过过程put（id，A），把名字id及性质A登录到符号表；给非终结符D定义语义变量D.ATT，来记录和传递说明语句引入的id性质，如real或integer。（1）Dinteger id put（id，integer）；D.ATT:=integer（2）Dreal id put（id，real）；D.ATT:=real（3）DD1，id put（id，D1.ATT）；D.ATT:=D1.ATT 数数组组是是用用来来存存储储逻逻辑辑上上相相关关的的同同类类型型数数据据的的数数据据结结构构。数数组组元元素素是是由由数数组组名名及及下下标标值值一一起起命命名名的的，也也称称下下标标变变量量，如如A1A1，22。所所需需存存储储空空间间的的大大小小在在编编译译时时确确定定的的数数组组称称为为静静态态数数组组；否否则，称之为动态数组。则，称之为动态数组。对于一个对于一个n n维数组，一般定义为维数组，一般定义为AlAl1 1:u:u1 1，l l2 2:u:u2 2，l lk k:u uk k，l ln n:u:un n 在在计计算算数数组组元元素素的的地地址址时时，会会产产生生两两组组四四元元式序列。一式序列。一组组用于用于计计算算VpartVpart，其其值值存放在存放在临时临时单单5.4.6 含数组元素的赋值语句的翻译含数组元素的赋值语句的翻译元元T T中；另一中；另一组计组计算算CpartCpart，其其值值存放在另一存放在另一个个临时单临时单元元P P中。中。这样这样我我们们就可以用就可以用PTPT表示表示该该数数组组元素的地址。那么，与之元素的地址。那么，与之对应对应，数，数组组元素的引元素的引用和数用和数组组元素元素赋值赋值也就有两种不同的四元式也就有两种不同的四元式:变变址存数和址存数和变变址取数：址取数：（1 1）变址存数变址存数（=，X X，PTPT）/*/*相当于相当于PT:=X */PT:=X */（2 2）变址取数变址取数（=，PTPT，X X）/*/*相当于相当于X:=PT */X:=PT */令有数组a3，4，即d1=3，d2=4。那么依据语义规则，赋值语句X:=ai，j的四元式序列为：（1）T1:=i 4 /*4为d2 */（2）T1:=T1j /*T1为Vpart */（3）T2:=a5 /*5为C */（4）T3:=T2T1 （5）X:=T3 例例5.65.6：为:（1）T1:=i2（2）T2:=j3（3）T3:=T1 2（4）T3:=T2T3（5）T4:=b5（6）T5:=mn（7）T4T:=T55.6 5.6 递归下降语法制导的翻译递归下降语法制导的翻译 递归下降分析法是自顶向下语法分析方法之一。它的实现思想是为对应文法中每个非终结符编写一个递归子程序，该子程序能够识别对应非终结符所推出的串。递归下降分析制导翻译方法就是在每个递归过程中嵌入相应的语义子程序，通过递归子程序内部的局部量和参数传递语义信息。小小 结结1、目目前前广广为为使使用用的的语语义义分分析析方方法法语语法法是是制导翻译制导翻译2、编编译译程程序序使使用用的的中中间间语语言言主主要要有有：逆逆波波兰兰式式、逆逆波波兰兰式式、三三元元式式、四四元元式式和和树树形形表表示等示等 3、语语法法制制导导翻翻译译分分为为自自底底向向上上和和自自底底向向下两种下两种