《第8章语法制导翻译和中间代码生成》由会员分享，可在线阅读，更多相关《第8章语法制导翻译和中间代码生成（67页珍藏版）》请在金锄头文库上搜索。
1、属性文法属性文法与属性翻译文法与属性翻译文法常见中间语言概述常见中间语言概述简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译布尔表达式的翻译布尔表达式的翻译程序流控制语句的翻译程序流控制语句的翻译说明语句的翻译说明语句的翻译第8章 语法制导翻译和中间代码生成编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2 2) )8.1概述概述1.语义分析的概念语义分析的概念一一个个源源程程序序经经过过词词法法分分析析、语语法法分分析析之之后后，表表明明该该源源程程序序在在书书写写上上是是正正确确的的，并并且且符符合合程程序序语语言言所所规规定定的的
2、语语法法。但但是是语语法法分分析析并并未未对对程程序序内内部部的的逻逻辑辑含含义义加加以以分分析析，因因此此编编译译程程序序接接下下来来的的工工作作是是语语义义分分析析，即即审审查查每每个个语语法法成成分分的的静静态态语语义义。若若静静态态语语义义正正确确，则则生生成成与与该该语语言言成成分分等等效效的的中中间间代代码码，或者直接生成目标代码。或者直接生成目标代码。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3 3) )直接生成机器语言或汇编语言形式的目标代码直接生成机器语言或汇编语言形式的目标代码优点：编译时间短且无需中间代码到目标代码的翻译
3、。优点：编译时间短且无需中间代码到目标代码的翻译。中间代码的优点中间代码的优点使使编编译译结结构构在在逻逻辑辑上上更更为为简简单单明明确确，特特别别是是使使目目标标代码的优化比较容易实现。代码的优化比较容易实现。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4 4) )如如同同在在进进行行词词法法分分析析、语语法法分分析析的的同同时时也也进进行行着着词词法法检检查查、语语法法检检查查一一样样，在在语语义义分分析析时时也也必必然然要要进进行行语语义义检检查查。动动态态语语义义检检查查需需要要生生成成相相应应的的目目标标代代码码，它它是是在在运运行行
4、时时进进行行的的；静静态态语语义义检检查查是是在在编编译译时时完完成成的的，它它涉涉及以下几个方面：及以下几个方面：(1)类型检查，如参与运算的操作数其类型应相容。类型检查，如参与运算的操作数其类型应相容。(2)控控制制流流检检查查，用用以以保保证证控控制制语语句句有有合合法法的的转转向向点点。如如C语语言言中中不不允允许许goto语语句句转转入入case语语句句流流；break语语句句需需寻寻找找包包含含它它的的最最小小switch、while或或for语语句句方方可可找找到到转转向点，否则出错。向点，否则出错。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代
5、码生成 ( (5 5) )(3)一一致致性性检检查查，如如在在相相同同作作用用域域中中标标识识符符只只能能说说明明一一次、次、case语句的标号不能相同等。语句的标号不能相同等。语语义义分分析析阶阶段段只只产产生生中中间间代代码码而而不不生生成成目目标标代代码码的的方方法法使使编编译译程程序序的的开开发发变变得得较较为为容容易易，但但语语义义分分析析不不像像词词法法分分析析和和语语法法分分析析那那样样可可以以分分别别用用正正规规文文法法和和上上下下文文无无关关文文法法描描述述。由由于于语语义义是是上上下下文文有有关关的的，因因此此语语义义的的形形式式化化描描述述是是非非常常困困难难的的，目目前
6、前较较为为常常见见的的是是用用属属性性文文法法作作为为描描述述程程序序语语言言语语义义的的工工具具，并并采采用用语法制导翻译的方法完成对语法成分的翻译工作。语法制导翻译的方法完成对语法成分的翻译工作。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6 6) )2.语法制导翻译方法语法制导翻译方法语法制导翻译的方法就是为每个产生式配上一个翻译子语法制导翻译的方法就是为每个产生式配上一个翻译子程序（称语义动作或语义子程序），并在语法分析的同时程序（称语义动作或语义子程序），并在语法分析的同时执行这些子程序。执行这些子程序。语义动作是为产生式赋予具体意义
7、的手语义动作是为产生式赋予具体意义的手段，段，它一方面指出了一个产生式所产生的符号串的意义，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。些基本动作。在语法分析过程中，当一个产生式获得匹配在语法分析过程中，当一个产生式获得匹配（对于自上而下分析）或用于归约（对于自下而上分析）（对于自上而下分析）或用于归约（对于自下而上分析）时，此产生式相应的语义子程序就进入工作，完成既定的时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。翻译任务。编译原理编译原理 第第8 8章章 语法制导
8、翻译和中间代码生成语法制导翻译和中间代码生成 ( (7 7) )语语法法制制导导翻翻译译分分为为自自下下而而上上语语法法制制导导翻翻译译和和自自上上而而下下语法制导翻译。语法制导翻译。本章重点介绍自下而上语法制导翻译。本章重点介绍自下而上语法制导翻译。假假定定有有一一个个自自下下而而上上的的LR分分析析器器，可可以以把把这这个个LR分分析析器器的的能能力力加加以以扩扩大大，使使它它能能在在用用某某个个产产生生式式进进行行归归约约的的同同时时调调用用相相应应的的语语义义子子程程序序进进行行有有关关的的翻翻译译工工作作；每每个个产产生生式式的的语语义义子子程程序序执执行行之之后后，某某些些结结果果
9、(语语义义信信息息)必必须须作作为为此此产产生生式式的的左左部部符符号号的的语语义义值值暂暂时时保保存存下下来来，以以便以后语义子程序引用这些信息。便以后语义子程序引用这些信息。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (8 8) )此此外外，原原LR分分析析器器的的分分析析栈栈也也加加以以扩扩充充，以以便便能能够够存存放放与与文文法法符符号号相相对对应应的的语语义义值值。这这样样，分分析析栈栈可可以以存存放放三三类类信信息息：分分析析状状态态、文文法法符符号号及及文文法法符符号号对对应应的的语义值。扩充后的分析栈如图语义值。扩充后的分析栈如图
10、5.1所示。所示。考查下面的文法及语义动作所执行的程序：考查下面的文法及语义动作所执行的程序：编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (9 9) ) 图图5.1扩充后的扩充后的LR分析栈分析栈 编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1010) )产生式产生式语义动作语义动作(0)SEprintvalTOP(1)EE(1)+E(2)valTOP=valTOP+valTOP+2(2)EE(1)*E(2)valTOP=valTOP*valTOP+2(3)E(E(1)valTOP=valTOP+
11、1(4)EivalTOP=lexval(注：注：lexval为为i的整型内部值的整型内部值)这个文法的这个文法的LR分析见表分析见表5.1。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1111) )扩充分析栈工作的总控程序功能扩充分析栈工作的总控程序功能在在完完成成语语法法分分析析的的同同时时也也能能完完成成语语义义分分析析工工作作(这这时时的的语语法法分分析析栈栈已已成成为为语语义义分分析析栈栈)；即即在在用用某某一一个个规规则则进进行行归归约约之之后后，调调用用相相应应的的语语义义子子程程序序完完成成与与所所用用产产生生式式相应的语义动作。
12、相应的语义动作。将每次工作后的语义值保存在扩充后的将每次工作后的语义值保存在扩充后的“语义值语义值”栈中。栈中。图图5.2表示算术表达式表示算术表达式79*5#的语法树及各结点值。的语法树及各结点值。表表5.1则则给给出出了了用用LR语语法法制制导导翻翻译译方方法法得得到到的的该该表表达达式式的语义分析和计值过程。的语义分析和计值过程。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1212) )图图5.2语法制导翻译计算表达式语法制导翻译计算表达式79*5#的语法树的语法树编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和
13、中间代码生成 ( (1313) )表5.1 表达式79*5#的语义分析和计值过程步骤步骤状态栈状态栈符号栈符号栈语义栈语义栈输入串输入串主要动作主要动作10#_79*5#s3203#7_9*5#r4301#E_79*5#s44014#E+_7_9*5#s350143#E+9_7_*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*5_7_9_#r49014758#E+E*E_7_9_5#r2100147#E+E_7_45#r11101#E_52#acc编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成
14、 ( (1414) )5.2属性文法与属性翻译文法属性文法与属性翻译文法5.2.1语义属性与属性文法语义属性与属性文法属性是指与文法符号的类型和值等有关的一些信息，在属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。随着编译的进展，对编译中用属性描述处理对象的特征。随着编译的进展，对语法分析产生的语法树进行语义分析，且分析的结果用中语法分析产生的语法树进行语义分析，且分析的结果用中间代码描述出来。对于一棵等待翻译的语法树，它的各个间代码描述出来。对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号结点都是文法中的一个符号X，该，该X可以是终结符或非终结可以是
15、终结符或非终结符。根据语义处理的需要，在用产生式符。根据语义处理的需要，在用产生式AX进行归约或进行归约或推导时，应能准确而恰当地表达文法符号推导时，应能准确而恰当地表达文法符号X在归约或推导在归约或推导时的不同特征。时的不同特征。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1515) )例如：例如：判断变量判断变量X的类型是否匹配，要用的类型是否匹配，要用X的数据类型来描述；的数据类型来描述；判断变量判断变量X是否存在，要用是否存在，要用X的存储位置来描述；的存储位置来描述；而对而对X的运算，则要用的运算，则要用X的值来描述。的值来描述。因因
16、此此，语语义义分分析析阶阶段段引引入入X的的属属性性，如如X.type、X.place、X.val等等来来分分别别描描述述变变量量X的的类类型型、存存储储位位置置以以及值等不同的特征。及值等不同的特征。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1616) )文法符号的属性：继承属性与综合属性两类。文法符号的属性：继承属性与综合属性两类。（1）继承属性用于）继承属性用于“自上而下自上而下”传递信息传递信息继继承承属属性性由由相相应应语语法法树树中中结结点点的的父父结结点点属属性性计计算算得得到到，即即沿沿语语法法树树向向下下传传递递，由由根根结
17、结点点到到分分枝枝(子子)结点；结点；继承属性反映了对上下文依赖的特性。继承属性反映了对上下文依赖的特性。继继承承属属性性可可以以很很方方便便地地用用来来表表示示程程序序语语言言上上下下文的结构关系。文的结构关系。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1717) )（2）综合属性用于）综合属性用于“自下而上自下而上”传递信息传递信息综综合合属属性性由由相相应应语语法法分分析析树树中中结结点点的的分分枝枝结结点点(即即子子结结点点)属属性性计计算算得得到到，其其传传递递方方向向与与继继承承属属性性相相反反，即即沿沿语语法法分分析析树树向向上
18、上传传递递，从从分枝结点到根结点。分枝结点到根结点。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1818) )5.2.2属性翻译文法属性翻译文法属属性性文文法法是是一一种种适适用用于于定定义义语语义义的的特特殊殊文文法法，即即在在语语言言的的文文法法中中增增加加了了属属性性的的文文法法，它它将将文文法法符符号号的的语语义义以以“属属性性”的的形形式式附附加加到到各各个个文文法法的的符符号号上上(如如上上述述与与变变量量X相相关关联联的的属属性性X.type、X.place和和X.val等等)，再再根根据据产产生生式式所所包包含含的的含含义义，给
19、给出出每每个个文文法法符符号号属属性性的的求求值值规规则则，从从而而形形成成一一种种带带有有语语义义属属性性的的上上下下文文无无关关文文法法，即即属属性性文文法法。属属性性文文法法也也是是一一种种翻翻译译文文法法，属属性性有有助助于于更更详详细细地指定文法中的代码生成动作。地指定文法中的代码生成动作。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (1919) )例如，简单算术表达式求值的属性文法如下：例如，简单算术表达式求值的属性文法如下：产生式产生式语义规则语义规则(1)SEprint(E.val)(2)EE(1)+TE.val=E(1).val
20、+T.val(3)ET E.val=T.val(4)TT(1)*FT.val=T(1).val*F.val(5)TT(1)T.val=T(1).val(6)F(E)F.val=E.val(7)FiF.val=i.lexval编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2020) )与与产产生生式式关关联联的的每每一一个个语语义义规规则则的的左左部部符符号号E、T、F等等的的属属性性值值的的计计算算由由其其各各自自相相应应的的右右部部符符号号决决定定，这这种种属属性性也称为也称为综合属性综合属性。与与产产生生式式SE关关联联的的语语义义规规则则是
21、是一一个个函函数数print(E.val)，其其功功能能是是打打印印E产产生生式式的的值值。S在在语语义义规规则则中中没没有有出出现现，可以理解为其属性是一个虚属性。可以理解为其属性是一个虚属性。另另一一说说明明属属性性文文法法例例：一一简简单单变变量量类类型型说说明明的的文文法法如如下：下：GD：DintL floatLLL,id id编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2121) )注意到与文法注意到与文法GD相应的说明语句形式可为相应的说明语句形式可为intid1，id2,，idn或者或者floatid1，id2,，idn其对应的
22、属性文法为：其对应的属性文法为：产生式产生式 语义规则语义规则(1)DTL L.in=T.type(2)TintT.type=int(3)TfloatT.type=float(4)LL(1),idL(1).in=L.in;addtype(id.entry,L.in)(5)Lidaddtype(id.entry,L.in)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2222) )非非终终结结符符T有有一一个个综综合合属属性性type，其其值值为为int或或float。语语义义规规则则L.in=T.type表表示示L.in的的属属性性值值由由相相应
23、应说说明明语语句句指指定定的的类类型型T.type决决定定；属属性性L.in被被确确定定后后将将随随语语法法树树的的逐逐步步生生成成而而传传递递到到下下边边的的有有关关结结点点使用，这种结点属性称为继承属性。使用，这种结点属性称为继承属性。由由此此可可见见，标标识识符符的的类类型型可可以以通通过过继继承承属属性性的的复写规则来传递。复写规则来传递。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2323) )图图5.3属性信息传递情况示意属性信息传递情况示意例如，对输入串例如，对输入串inta,b，根据上，根据上述的语义规则，可在其生成的语述的语义
24、规则，可在其生成的语法树中看到用法树中看到用“”表示的属性表示的属性传递情况，如图所示。传递情况，如图所示。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2424) )3*5+4的带注释的分析树的带注释的分析树只使用综合属性。只使用综合属性。SE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成
25、语法制导翻译和中间代码生成 ( (2525) )S-属性文法和自下而上翻译属性文法和自下而上翻译一一个个一一般般的的属属性性文文法法的的翻翻译译器器是是很很难难建建立立的的，然然而而有有一一大类属性文法的翻译器是很容易建立的，那就是大类属性文法的翻译器是很容易建立的，那就是L-属性文法。属性文法。S-属性文法（属性文法（L-属性文法的特例）属性文法的特例）S-属性文法是属性文法是只含有综合属性只含有综合属性的属性文法。的属性文法。综合属性可以在分析输入符号的同时自下而上的来计算。综合属性可以在分析输入符号的同时自下而上的来计算。通常借助通常借助LR分析器实现。分析器实现。保存与栈中文法符号相关
26、的综合属性值。保存与栈中文法符号相关的综合属性值。当归约时，新的属性值由正在归约的产生式右边符号的当归约时，新的属性值由正在归约的产生式右边符号的属性值来计算。属性值来计算。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2626) )G：EE E T+T E ToT T n T b编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2727) )G：EE E T+T E ToT T n T b编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2828) )G：E
27、E E T+T E ToT T n T b编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (2929) )G：EEET+TEToTTnTb编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3030) )L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现L-属性文法属性文法，对于每一个产生式，对于每一个产生式AX1X2Xn，其每个其每个语义规则中的每个属性或者是综合属性，或者是语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的的一个继承属性且这个继承属性仅依赖于：一个继承属性且这个继承属
28、性仅依赖于：（1）产生式产生式Xj在在左边符号左边符号X1，X2，Xj-1的的属性；属性；（2）A的继承属性。的继承属性。可以借助可以借助LL分析器实现。分析器实现。可以借助可以借助LR分析器实现。分析器实现。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3131) )L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现例例5.3将中缀表达式翻译成相应的后缀表达式的属性文将中缀表达式翻译成相应的后缀表达式的属性文法法EEaddopTprint(addop.Lexeme)TTnumprint(num.val)编译原理编译原理 第第8 8
29、章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3232) )例例5.3将中缀表达式翻译成相应的后缀表达是式的属性文法将中缀表达式翻译成相应的后缀表达是式的属性文法(LR)，其其中中addop表示表示或或。EEaddopTprint(addop.lexme) TTnumprint(num.val)对表达式对表达式2+3-5的分析：打印出的分析：打印出235EET-printE+Tprint5print5Tprint232print3编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3333) )上述文法含有左递归，如采用上述文法含有
30、左递归，如采用LL(1)分析须改写如下：分析须改写如下：ETRRaddopTprint(addop.lexme)R1 Tnumprint(num.val)对表达式对表达式2+3-5的分析：打印出的分析：打印出23+5-RRprint-+5-3print5Tprint22print3ETprint+TR编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3434) )L-属性文法在自下而上分析中的实现属性文法在自下而上分析中的实现自下而上计算继承属性有两种办法自下而上计算继承属性有两种办法（1）从）从翻译模式中去掉嵌入在产生式中间的动作；翻译模式中去掉嵌
31、入在产生式中间的动作；（2）用）用综合属性代替继承属性。综合属性代替继承属性。为了使所有的嵌入的动作都出现在产生式的末尾，可为了使所有的嵌入的动作都出现在产生式的末尾，可以采用以采用方法：方法：引入一个新的非终结符引入一个新的非终结符N和产生式和产生式N ，把嵌入在产生式中间的动作用非终结符把嵌入在产生式中间的动作用非终结符N代替，并把这个代替，并把这个动作放在产生式后面。动作放在产生式后面。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3535) )例如：例如：ETRETRR+Tprint(+)R1引入引入M和和NR+TMR1R-Tprint(
32、-)R1变换变换R-TNR1R R Tnumprint(num.val)Tnumprint(num.val)M print(+)N print(-)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3636) )用综合属性代替继承属性，改变基础文法是用综合属性代替继承属性，改变基础文法是一种可能的办法。一种可能的办法。例如例如Pascal标识符说明语句的文法如下标识符说明语句的文法如下：DL：T/L.in=T.type，继承自右部，不符合，继承自右部，不符合L-属性文法属性文法Tinteger|charLL,id|id以综合属性代替继承属性，重新构造
33、文法以综合属性代替继承属性，重新构造文法DidLL,idL|:TTinteger|char编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3737) )属性文法属性文法DidLaddtype(id.entery,L.type)L,idLL.type:=L.type;addtype(id.entery,L.type)L:TL.type:=T.typeTintegerT.type:=intTcharT.type:=ch编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (3838) )5.3常见中间语言概述常见中
34、间语言概述何谓中间代码何谓中间代码(Intermediatecode)是源程序的一种内部表示。是源程序的一种内部表示。复杂性介于源语言和目标机语言之间。复杂性介于源语言和目标机语言之间。中间代码的作用中间代码的作用使编译程序的逻辑结构更加简单明确；使编译程序的逻辑结构更加简单明确；利于进行与目标机无关的优化；利于进行与目标机无关的优化；利于在不同目标机上实现同一种语言的前端编译程利于在不同目标机上实现同一种语言的前端编译程序设计。序设计。中间代码的形式中间代码的形式逆波兰式逆波兰式、四元式四元式、三元式、间接三元式、树、三元式、间接三元式、树编译原理编译原理 第第8 8章章 语法制导翻译和中间
35、代码生成语法制导翻译和中间代码生成 ( (3939) )中间代码的层次中间代码的层次中间代码按照其与高级语言和机器语言的接近程度，中间代码按照其与高级语言和机器语言的接近程度，分成三个层次。分成三个层次。高级高级：最接近高级语言，保留了大部分源语言的最接近高级语言，保留了大部分源语言的结构。结构。中级中级：介于二者之间，与源语言和机器语言都有：介于二者之间，与源语言和机器语言都有一定差异。一定差异。低级低级：最接近机器语言，能够反映目标机的系统最接近机器语言，能够反映目标机的系统结构，因而经常依赖于目标机。结构，因而经常依赖于目标机。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成
36、语法制导翻译和中间代码生成 ( (4040) )不同层次的中间代码举例不同层次的中间代码举例源语言源语言（高级语言）（高级语言）中间代码（高中间代码（高级）级）中间代码（中中间代码（中级）级）中间代码（低中间代码（低级）级）floata1020;aij+2;t1=ai,j+2t1=j+2t2=i*20t3=t1+t2t4=4*t3t5=addrat6=t5+t4t7=*t6r1=fp-4r2=r1+2r3=fp-8r4=r3*20r5=r4+r2r6=4*r5r7=fp216f1=r7+r6编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4141)
37、 )编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4242) )编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4343) )5.4简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译(1)对对非非终终结结符符E定定义义语语义义变变量量E.place，即即用用E.place表表示示存存放放E值值的的变变量量名名在在符符号号表表中中的的入入口口地地址址或或临临时时变变量量名名的整数码。的整数码。(2)定定义义语语义义函函数数newtemp()，即即每每次次调调用用newtemp()时时都都将将回
38、回送送一一个个代代表表新新临临时时变变量量的的整整数数码码；临临时时变变量量名名按产生的顺序可设为按产生的顺序可设为T1、T2、。(3)定定义义语语义义过过程程emit(op,arg1,arg2,result),emit的的功功能能是是产生一个四元式并填入四元式表中。产生一个四元式并填入四元式表中。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4444) )简单赋值语句的四元式翻译简单赋值语句的四元式翻译(4)定义语义函数定义语义函数lookup(i.name)，其功能是审查其功能是审查i.name是否是否出现在符号表中，是则返回出现在符号表中，
39、是则返回i.name在符号表的入口指针，在符号表的入口指针，否则返回否则返回NULL。GA:Ai=EEE(1)+E(2)E(1)*E(2)E(1)(E(1)Ei使使用用上上述述语语义义变变量量、过过程程和和函函数数，可可写写出出文文法法GA中的每一个产生式的语义子程序。中的每一个产生式的语义子程序。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4545) )(1)Ai=Ep=lookup(i.name);if(p=NULL)error();elseemit(=,E.place,_,p);(2)EE(1)+E(2)E.place=newtemp()
40、;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);编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4646) )(4)EE(1)E.place=newtemp();emit(uminus,E(1).place,_,E.place);(5)E(E(1)E.place=E(1).place;(6)Eip=lookup(i.name);if(p!=NULL)E.place=p;/*另一种表示为
41、另一种表示为E.place=entry(i)*/elseerror();编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4747) )例例5.5试分析赋值语句试分析赋值语句X=B*(C+D)的语法制导翻译过程。的语法制导翻译过程。输入串输入串归约产归约产生式生式符号栈符号栈语义栈语义栈(place)四元式四元式X=B*(C+D#_=B*(C+D)#(6)#i_XB*(C+D)#i=_X_B*(C+D)#i=_X_*(C+D)#(6)#i=i_X_B*(C+D)#(4)#i=E_X_B(uminus,B,_,T1)*(C+D)#i=E_X_T1Ai=
42、EEE(1)+E(2)E(1)*E(2)E(1) (E(1)Ei(4)EE(1)E.place=newtemp();emit(uminus,E(1).place,_,E.place);编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4848) )(C+D)#i=E*_X_T1_C+D)#i=E*(_X_T1_+D)#(6)#i=E*(i_X_T1_C+D)#i=E*(E_X_T1_CD)#i=E*(E+_X_T1_C_)#(6)#i=E*(E+i_X_T1_C_D)#(2)#i=E*(E+E_X_T1_C_D(+,C,D,T2)#i=E*(E_X_
43、T1_T2#(5)#i=E*(E)_X_T1_T2_#(3)#i=E*E_X_T1_T2(*,T1,T2,T3)#(1)#i=E_X_T3(=,T3,_,X)#A_XAi=EEE(1)+E(2)E(1)*E(2)E(1) (E(1)Ei(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);(1)Ai=Ep=lookup(i.name);if(p=NULL)error();els
44、eemit(=,E.place,_,p);编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (4949) )类型转换的语义处理类型转换的语义处理产生式产生式语义动作语义动作EE1+E2E.place:=newtemp;if(E1type=intANDE2.type=intthenbeginemit(E.place“:=”E1.place“+”E2.place)E.type:=int;end;elseif(E1type=realANDE2.type=realthenbeginemit(E.place“:=”E1.place“+”E2.place)E.ty
45、pe:=real;end;编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5050) )elseif(E1type=int)then/两个运算量类型不同两个运算量类型不同begint:=newtemp;emit(t“:=”,itr,E1.place)/转换成实型转换成实型(real)emit(E.place“:=”t“+”E2.place)E.type:=real;end;elsebegint:=newtemp;emit(t“:=”,itr,E2.place)emit(E.place“:=”E1.place“+”t)E.type:=real;end
46、;编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5151) )5.5布尔表达式的翻译布尔表达式的翻译程序设计语言中的布尔表达式的作用程序设计语言中的布尔表达式的作用计算逻辑值；计算逻辑值；用做改变控制流语句中的条件表达式。用做改变控制流语句中的条件表达式。只考虑下面文法生成的布尔表达式只考虑下面文法生成的布尔表达式EEandE|EorE|notE|idropid|true|false约定布尔运算符的优先顺序（从高到低）为：约定布尔运算符的优先顺序（从高到低）为：not、and、or，并且并且and和和or服从左结合。服从左结合。编译原理编译原理
47、第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5252) )布尔表达式的翻译方法布尔表达式的翻译方法计算布尔表达式的两种办法：计算布尔表达式的两种办法：（1）非简洁）非简洁（2）简洁）简洁布尔表达式翻成四元式的描述布尔表达式翻成四元式的描述例如：例如：aorbandnotc翻译成的四元式序列为：翻译成的四元式序列为：(1)t1=notc(2)t2=bandt1(3)t3=aort2编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5353) )布尔表达式的翻译方法布尔表达式的翻译方法对于像对于像ab这一类的关系表达式，可
48、以视为等价的条件语句这一类的关系表达式，可以视为等价的条件语句ifabthen1else0,它翻译成的四元式序列为：它翻译成的四元式序列为：(1)ifabgoto(4)(2)t=0(3)goto(5)(4)t=1(5)其中：临时变量其中：临时变量t存放布尔表达式存放布尔表达式ab的值的值;(5)为后续的四元式序号。为后续的四元式序号。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5454) )具体的布尔表达式翻译成四元式的描述如下：具体的布尔表达式翻译成四元式的描述如下：EE1orE2E.place:=newtemp;emit(E.place“:
49、=”E1.place“or”E2.place)EE1andE2E.place:=newtemp;emit(E.place“:=”E1.place“and”E2.place)EnotE1E.place:=newtemp;emit(E.place“:=”“not”E1.place)E(E1)E.place:=E1.place)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5555) )Eid1ropid2E.place:=newtemp;emit(ifid1.place“rop”id2.place“goto”nextstart+3);emit(E.p
50、lace“:=”“0”)emit(“goto”nextstart+2)emit(E.place“:=”“1”)EtrueE.place:=newtemp;emit(E.place“:=”“1”)EfalseE.place:=newtemp;emit(E.place“:=”“0”)其中：其中：nextstat给出在输出序列中下一四元式序号。给出在输出序列中下一四元式序号。emit过程每被调用一次，过程每被调用一次，nextatat增加增加1。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5656) )5.6程序流程控制语句的翻译程序流程控制语句的翻
51、译控制语句控制语句SifEthenS1elseS2E的代码的代码E.trueE.falseE.true:S1的代码的代码gotooutE.false:S2的代码的代码out:编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5757) )作为条件转移的作为条件转移的E，仅把仅把E翻译成代码是一串条件转移和翻译成代码是一串条件转移和无条件转移的四元式。基本思路是对于无条件转移的四元式。基本思路是对于E为为aropb的形式生的形式生成代码为：成代码为：ifaropbgotoE.true和和gotoE.false例例8.5aborcf翻译如下：翻译如下：这
52、不是最优的，因为这不是最优的，因为(2)是不需是不需要的。由代码优化阶段解决。要的。由代码优化阶段解决。用用E.true和和E.false分别表示整个分别表示整个表达式表达式aborcf的真的真假出口。假出口。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5858) )语句语句ifaborcfthens1elses2的四元式序列：的四元式序列：(1)ifabgoto(7)/无法在产生此四元式时知道该转移的产生式号无法在产生此四元式时知道该转移的产生式号(2)goto(3)(3)ifcfgoto(7)/表达式为表达式为true时时,转到转到S1处处
53、(6)gotop+1/表达式为表达式为false时时,转到转到S2处处(7)(p)gotoq(p+1)(q)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (5959) )编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6060) )编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6161) )编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6262) )编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成
54、语法制导翻译和中间代码生成 ( (6363) )编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6464) )5.9说明语句的翻译说明语句的翻译一个程序或过程或分程序中的说明语句，以标识符的一个程序或过程或分程序中的说明语句，以标识符的形式定义了数据对象，如常量、变量、数组等，这就需要形式定义了数据对象，如常量、变量、数组等，这就需要为这些数据对象分配存储空间，同时，为了管理，将在符为这些数据对象分配存储空间，同时，为了管理，将在符号表中登记这些数据信息（名字、类型、分配的存储地址号表中登记这些数据信息（名字、类型、分配的存储地址等），用以检查名字
55、的引用和说明是否一致。许多说明语等），用以检查名字的引用和说明是否一致。许多说明语句的翻译并不生成目标代码。过程说明和动态数组的说明句的翻译并不生成目标代码。过程说明和动态数组的说明有相应的代码。有相应的代码。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6565) )简单说明语句的翻译简单说明语句的翻译程序设计语言中简单的说明语句的语法描述：程序设计语言中简单的说明语句的语法描述：Dinteger|real,id|id即使用关键字即使用关键字integer和和real定义一串名字的性质。定义一串名字的性质。对这种说明语句的翻译是指在符号表中登录
56、该名和性质。对这种说明语句的翻译是指在符号表中登录该名和性质。改写：改写：DD1，id|integerid|realid编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6666) )定义产生式所对应的语义动作定义产生式所对应的语义动作(1)Dintegeridenter(id,int);D.att:=int(2)Drealidenter(id,real);D.att:=real(3)DD1,identer(id,D1.att);D.att:=D1.attD.att记录说明语句所引入的名字的性质记录说明语句所引入的名字的性质int还是还是real使用
57、过程使用过程enter(id,A)把名字把名字id和性质和性质A登录在名表中。登录在名表中。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 ( (6767) )本章小结本章小结语义分析阶段的任务语义分析阶段的任务检查静态语义错误检查静态语义错误（类型相容、惟一性、控制流检查）（类型相容、惟一性、控制流检查）生成中间代码生成中间代码中间代码中间代码四元式四元式逆波兰式逆波兰式语义分析方法语义分析方法属性文法属性文法（L属性文法）属性文法）自下而上语法制导翻译自下而上语法制导翻译自上而下语法制导翻译自上而下语法制导翻译赋值语句、布尔表达式、说明语句的翻译赋值语句、布尔表达式、说明语句的翻译
