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)skXkVkvals1X1V1vals0#状态文法符号 语义值TOP 图图5.1 扩充后的扩充后的LR分析栈分析栈 编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1010)产生式产生式 语义动作语义动作(0)SE print valTOP(1)EE(1)+E(2)valTOP=valTOP+valTOP+2(2)EE(1)*E(2)
11、valTOP=valTOP*valTOP+2(3)E(E(1)valTOP=valTOP+1(4)Ei valTOP=lexval (注：注：lexval为为i的整型内部值的整型内部值)这个文法的这个文法的LR分析见表分析见表5.1。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1111)扩充分析栈工作的总控程序功能扩充分析栈工作的总控程序功能 在完成语法分析的同时也能完成语义分析工作在完成语法分析的同时也能完成语义分析工作(这时这时的语法分析栈已成为语义分析栈的语法分析栈已成为语义分析栈)；即在用某一个规则进；即在用某一个规则进行归约之后，调用相应
12、的语义子程序完成与所用产生式行归约之后，调用相应的语义子程序完成与所用产生式相应的语义动作。相应的语义动作。将每次工作后的语义值保存在扩充后的将每次工作后的语义值保存在扩充后的“语义值语义值”栈中。栈中。图图5.2表示算术表达式表示算术表达式79*5#的语法树及各结点值。的语法树及各结点值。表表5.1则给出了用则给出了用LR语法制导翻译方法得到的该表达式语法制导翻译方法得到的该表达式的语义分析和计值过程。的语义分析和计值过程。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1212)Eval52Eval7Eval457Eval9*Eval595图图5.
13、2 语法制导翻译计算表达式语法制导翻译计算表达式 79*5#的语法树的语法树编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (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
14、#r2100147#E+E_7_45#r11101#E_52#acc编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1414)5.2 属性文法与属性翻译文法属性文法与属性翻译文法 5.2.1 语义属性与属性文法语义属性与属性文法 属性是指与文法符号的类型和值等有关的一些信息，在属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。随着编译的进展，对编译中用属性描述处理对象的特征。随着编译的进展，对语法分析产生的语法树进行语义分析，且分析的结果用中语法分析产生的语法树进行语义分析，且分析的结果用中间代码描述出来。对于一棵等待翻译
15、的语法树，它的各个间代码描述出来。对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号结点都是文法中的一个符号X，该，该X可以是终结符或非终结可以是终结符或非终结符。根据语义处理的需要，在用产生式符。根据语义处理的需要，在用产生式AX进行归约或进行归约或推导时，应能准确而恰当地表达文法符号推导时，应能准确而恰当地表达文法符号X在归约或推导在归约或推导时的不同特征。时的不同特征。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1515)例如：例如：判断变量判断变量X的类型是否匹配，要用的类型是否匹配，要用X的数据类型来描述；的数据类型来描述；判断变
16、量判断变量X是否存在，要用是否存在，要用X的存储位置来描述；的存储位置来描述；而对而对X的运算，则要用的运算，则要用X的值来描述。的值来描述。因此，语义分析阶段引入因此，语义分析阶段引入X的属性，如的属性，如X.type、X.place、X.val等来分别描述变量等来分别描述变量X的类型、存储位置以的类型、存储位置以及值等不同的特征。及值等不同的特征。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1616)文法符号的属性：继承属性与综合属性两类。文法符号的属性：继承属性与综合属性两类。（1）继承属性用于）继承属性用于“自上而下自上而下”传递信息传递信
17、息 继承属性由相应语法树中结点的父结点属性继承属性由相应语法树中结点的父结点属性计算得到，即沿语法树向下传递，由根结点到分枝计算得到，即沿语法树向下传递，由根结点到分枝(子子)结点；结点；继承属性反映了对上下文依赖的特性。继承属性反映了对上下文依赖的特性。继承属性可以很方便地用来表示程序语言上下继承属性可以很方便地用来表示程序语言上下文的结构关系。文的结构关系。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1717)（2）综合属性用于）综合属性用于“自下而上自下而上”传递信息传递信息 综合属性由相应语法分析树中结点的分枝综合属性由相应语法分析树中结点
18、的分枝结点结点(即子结点即子结点)属性计算得到，其传递方向与属性计算得到，其传递方向与继承属性相反，即沿语法分析树向上传递，从继承属性相反，即沿语法分析树向上传递，从分枝结点到根结点。分枝结点到根结点。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1818)5.2.2 属性翻译文法属性翻译文法 属性文法是一种适用于定义语义的特殊文法，即在属性文法是一种适用于定义语义的特殊文法，即在语言的文法中增加了属性的文法，它将文法符号的语义语言的文法中增加了属性的文法，它将文法符号的语义以以“属性属性”的形式附加到各个文法的符号上的形式附加到各个文法的符号上(如
19、上述与变如上述与变量量X相关联的属性相关联的属性X.type、X.place和和X.val等等)，再根据产，再根据产生式所包含的含义，给出每个文法符号属性的求值规则，生式所包含的含义，给出每个文法符号属性的求值规则，从而形成一种从而形成一种带有语义属性的上下文无关文法带有语义属性的上下文无关文法，即属性即属性文法。文法。属性文法也是一种翻译文法，属性有助于更详细属性文法也是一种翻译文法，属性有助于更详细地指定文法中的代码生成动作。地指定文法中的代码生成动作。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (1919)例如，简单算术表达式求值的属性文法如下
20、：例如，简单算术表达式求值的属性文法如下：产生式产生式 语义规则语义规则 (1)SE print(E.val)(2)EE(1)+T E.val=E(1).val+T.val (3)ET E.val=T.val (4)TT(1)*F T.val=T(1).val*F.val (5)TT(1)T.val=T(1).val (6)F(E)F.val=E.val (7)Fi F.val=i.lexval编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (2020)与产生式关联的每一个语义规则的左部符号与产生式关联的每一个语义规则的左部符号E、T、F等等的属性值的计
21、算由其各自相应的右部符号决定，这种属性的属性值的计算由其各自相应的右部符号决定，这种属性也称为也称为综合属性综合属性。与产生式与产生式SE关联的语义规则是一个函数关联的语义规则是一个函数print(E.val)，其功能是打印其功能是打印E产生式的值。产生式的值。S在语义规则中没有出现，在语义规则中没有出现，可以理解为其属性是一个虚属性。可以理解为其属性是一个虚属性。另一说明属性文法例：一简单变量类型说明的文法如另一说明属性文法例：一简单变量类型说明的文法如下：下：GD：Dint L float L LL,id id编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代
22、码生成 (2121)注意到与文法注意到与文法GD相应的说明语句形式可为相应的说明语句形式可为int id1，id2,，idn 或者或者 float id1，id2,，idn其对应的属性文法为：其对应的属性文法为：产生式产生式 语义规则语义规则 (1)DTL L.in=T.type (2)Tint T.type=int (3)Tfloat T.type=float (4)LL(1),id L(1).in=L.in;addtype(id.entry,L.in)(5)Lid addtype(id.entry,L.in)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码
23、生成 (2222)非终结符非终结符T有一个综合属性有一个综合属性type，其值为其值为int或或float。语义规则语义规则L.in=T.type表示表示L.in的属性值由相应的属性值由相应说明语句指定的类型说明语句指定的类型T.type决定；属性决定；属性L.in被确定被确定后将随语法树的逐步生成而传递到下边的有关结点后将随语法树的逐步生成而传递到下边的有关结点使用，这种结点属性称为继承属性。使用，这种结点属性称为继承属性。由此可见，标识符的类型可以通过继承属性的由此可见，标识符的类型可以通过继承属性的复写规则来传递。复写规则来传递。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生
24、成语法制导翻译和中间代码生成 (2323)图图5.3 属性信息传递情况示意属性信息传递情况示意DTLintL，id2id1例如，对输入串例如，对输入串int a,b，根据上，根据上述的语义规则，可在其生成的语述的语义规则，可在其生成的语法树中看到用法树中看到用“”表示的属性表示的属性传递情况，如图所示。传递情况，如图所示。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (2424)3*5+4的带注释的分析树的带注释的分析树只使用综合属性。只使用综合属性。SE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val
25、=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (2525)S-属性文法和自下而上翻译属性文法和自下而上翻译 一个一般的属性文法的翻译器是很难建立的，然而有一一个一般的属性文法的翻译器是很难建立的，然而有一大类属性文法的翻译器是很容易建立的，那就是大类属性文法的翻译器是很容易建立的，那就是L-属性文法。属性文法。S-属性文法（属性文法（L-属性文法的特例）属性文法的特例）S-属性文法是属性文法是只含有综合属性
26、只含有综合属性的属性文法。的属性文法。综合属性可以在分析输入符号的同时自下而上的来计算。综合属性可以在分析输入符号的同时自下而上的来计算。通常借助通常借助LR分析器实现。分析器实现。保存与栈中文法符号相关的综合属性值。保存与栈中文法符号相关的综合属性值。当归约时，新的属性值由正在归约的产生式右边符号当归约时，新的属性值由正在归约的产生式右边符号的的属性值来计算。属性值来计算。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (2626)G：EE E T+T E ToT T n T b编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和
27、中间代码生成 (2727)G：EE E T+T E ToT T n T b编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (2828)G：EE E T+T E ToT T n T b编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (2929)G：EE E T+T E ToT T n T b编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3030)L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现 L-属性文法属性文法，对于每一个产生式，对于每一个产生式A X1
28、 X2 Xn，其每个其每个语义规则中的每个属性或者是综合属性，或者是语义规则中的每个属性或者是综合属性，或者是Xj(1j n)的的一个继承属性且这个继承属性仅依赖于：一个继承属性且这个继承属性仅依赖于：（1）产生式产生式Xj在在左边符号左边符号X1，X2，Xj-1的的属性；属性；（2）A的继承属性。的继承属性。可以借助可以借助LL分析器实现。分析器实现。可以借助可以借助LR分析器实现。分析器实现。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3131)L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现例例5.3 将中缀表达式翻译成相应的
29、后缀表达式的属性文将中缀表达式翻译成相应的后缀表达式的属性文法法 E E addop T print(addop.Lexeme)T T num print(num.val)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3232)例例5.3 将中缀表达式翻译成相应的后缀表达是式的属性文法将中缀表达式翻译成相应的后缀表达是式的属性文法(LR)，其中其中addop表示表示或或。E E addop T print(addop.lexme)T T num print(num.val)对表达式对表达式2+3-5的分析：打印出的分析：打印出23 5 EET-pri
30、ntE+Tprint5print5Tprint232print3编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3333)上述文法含有左递归，如采用上述文法含有左递归，如采用LL(1)分析须改写如下：分析须改写如下：E TR R addop T print(addop.lexme)R1 T num print(num.val)对表达式对表达式2+3-5的分析：打印出的分析：打印出23+5-RRprint-+5-3print5Tprint22print3ETprint+TR编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码
31、生成 (3434)L-属性文法在自下而上分析中的实现属性文法在自下而上分析中的实现 自下而上计算继承属性有两种办法自下而上计算继承属性有两种办法（1）从）从翻译模式中去掉嵌入在产生式中间的动作；翻译模式中去掉嵌入在产生式中间的动作；（2）用）用综合属性代替继承属性。综合属性代替继承属性。为了使所有的嵌入的动作都出现在产生式的末尾，可为了使所有的嵌入的动作都出现在产生式的末尾，可以采用以采用方法：方法：引入一个新的非终结符引入一个新的非终结符N和产生式和产生式 N ，把嵌入在产生式中间的动作用非终结符把嵌入在产生式中间的动作用非终结符N代替，并把这个代替，并把这个动作放在产生式后面。动作放在产生
32、式后面。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3535)例如：例如：ET R ET RR+T print(+)R1 引入引入M和和N R+T MR1R-T print(-)R1 变换变换 R-TNR1R R T num print(num.val)T num print(num.val)M print(+)N print(-)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3636)用综合属性代替继承属性，改变基础文法是用综合属性代替继承属性，改变基础文法是一种可能的办法。一种可能的办法。例如例如Pa
33、scal标识符说明语句的文法如下标识符说明语句的文法如下：DL：T /L.in=T.type，继承自右部，不符合，继承自右部，不符合 L-属性文法属性文法Tinteger|charL L,id|id以综合属性代替继承属性，重新构造文法以综合属性代替继承属性，重新构造文法Did LL,id L|:TT integer|char编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3737)属性文法属性文法Did L addtype(id.entery,L.type)L,id L L.type:=L.type;addtype(id.entery,L.type)L
34、:T L.type:=T.typeT integer T.type:=intT char T.type:=ch编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3838)5.3 常见中间语言概述常见中间语言概述何谓中间代码何谓中间代码(Intermediate code)是源程序的一种内部表示。是源程序的一种内部表示。复杂性介于源语言和目标机语言之间。复杂性介于源语言和目标机语言之间。中间代码的作用中间代码的作用使编译程序的逻辑结构更加简单明确；使编译程序的逻辑结构更加简单明确；利于进行与目标机无关的优化；利于进行与目标机无关的优化；利于在不同目标机上实
35、现同一种语言的前端编译程利于在不同目标机上实现同一种语言的前端编译程序设计。序设计。中间代码的形式中间代码的形式逆波兰式逆波兰式、四元式四元式、三元式、间接三元式、树、三元式、间接三元式、树编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (3939)中间代码的层次中间代码的层次 中间代码按照其与高级语言和机器语言的接近程度，中间代码按照其与高级语言和机器语言的接近程度，分成三个层次。分成三个层次。高级高级：最接近高级语言，保留了大部分源语言的最接近高级语言，保留了大部分源语言的结构。结构。中级中级：介于二者之间，与源语言和机器语言都有：介于二者之间，与源
36、语言和机器语言都有一定差异。一定差异。低级低级：最接近机器语言，能够反映目标机的系统最接近机器语言，能够反映目标机的系统结构，因而经常依赖于目标机。结构，因而经常依赖于目标机。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4040)不同层次的中间代码举例不同层次的中间代码举例源语言源语言（高级语言）（高级语言）中间代码（高中间代码（高级）级）中间代码（中中间代码（中级）级）中间代码（低中间代码（低级）级）float a1020;aij+2;t1=ai,j+2t1=j+2t2=i*20t3=t1+t2t4=4*t3t5=addr at6=t5+t4t7
37、=*t6r1=fp-4r2=r1+2r3=fp-8r4=r3*20r5=r4+r2r6=4*r5 r7=fp 216f1=r7+r6编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4141)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4242)三三元元式式 (1)(-C D )(2)(*B (1)(3)(+A (2)(4)(-C D )(5)(4)N )(6)(/E (5)(7)(+(3)(6)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4343)5.4 简单算
38、术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译(1)对非终结符对非终结符E定义语义变量定义语义变量E.place，即用即用E.place表示表示存放存放E值的变量名在符号表中的入口地址或临时变量名值的变量名在符号表中的入口地址或临时变量名的整数码。的整数码。(2)定义语义函数定义语义函数newtemp()，即每次调用即每次调用newtemp()时时都将回送一个代表新临时变量的整数码；临时变量名都将回送一个代表新临时变量的整数码；临时变量名按产生的顺序可设为按产生的顺序可设为T1、T2、。(3)定义语义过程定义语义过程emit(op,arg1,arg2,result),emit的功能是的
39、功能是产生一个四元式并填入四元式表中。产生一个四元式并填入四元式表中。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4444)简单赋值语句的四元式翻译简单赋值语句的四元式翻译(4)定义语义函数定义语义函数lookup(i.name)，其功能是审查其功能是审查i.name是是否出现在符号表中，是则返回否出现在符号表中，是则返回i.name在符号表的入口指在符号表的入口指针，否则返回针，否则返回NULL。GA:Ai=E EE(1)+E(2)E(1)*E(2)E(1)(E(1)Ei 使用上述语义变量、过程和函数，可写出文法使用上述语义变量、过程和函数，可写
40、出文法GA中的每一个产生式的语义子程序。中的每一个产生式的语义子程序。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4545)(1)Ai=E p=lookup(i.name);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);编译原理编译原理 第
41、第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)Ei p=lookup(i.name);if(p!=NULL)E.place=p;/*另一种表示为另一种表示为E.place=entry(i)*/else error();编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4747)例例5.5 试分析赋值语句试分析赋值语句X=B*(C+D)的语法制
42、导翻译过程。的语法制导翻译过程。输入串输入串归约产归约产生式生式符号栈符号栈语义栈语义栈(place)四元式四元式X=B*(C+D#_=B*(C+D)#(6)#i_X B*(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_T1 Ai=E EE(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章章 语法制导
43、翻译和中间代码生成语法制导翻译和中间代码生成 (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_ _C D)#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_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_X Ai=E EE(1)+E(2)
44、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=E p=lookup(i.name);if(p=NULL)error();else emit(=,E.place,_,p);编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (4949)类型转换的语义处理类型转换的语义处理 产生式产生式
45、 语义动作语义动作 EE1+E2 E.place:=newtemp;if(E1type=int AND E2.type=int then begin emit(E.place“:=”E1.place“+”E2.place)E.type:=int;end;else if(E1type=real AND E2.type=real then begin emit(E.place“:=”E1.place“+”E2.place)E.type:=real;end;编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (5050)else if(E1type=int)the
46、n /两个运算量类型不同两个运算量类型不同 begin t:=newtemp;emit(t“:=”,itr,E1.place)/转换成实型转换成实型(real)emit(E.place“:=”t“+”E2.place)E.type:=real;end;else begin t:=newtemp;emit(t“:=”,itr,E2.place)emit(E.place“:=”E1.place“+”t)E.type:=real;end;编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (5151)5.5 布尔表达式的翻译布尔表达式的翻译程序设计语言中的布尔表达
47、式的作用程序设计语言中的布尔表达式的作用计算逻辑值；计算逻辑值；用做改变控制流语句中的条件表达式。用做改变控制流语句中的条件表达式。只考虑下面文法生成的布尔表达式只考虑下面文法生成的布尔表达式EE and E|E or E|not E|id rop id|true|false约定布尔运算符的优先顺序（从高到低）为：约定布尔运算符的优先顺序（从高到低）为：not、and、or，并且并且and和和or服从左结合。服从左结合。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (5252)布尔表达式的翻译方法布尔表达式的翻译方法计算布尔表达式的两种办法：计算布尔表
48、达式的两种办法：（1）非简洁）非简洁 （2）简洁）简洁布尔表达式翻成四元式的描述布尔表达式翻成四元式的描述 例如：例如：a or b and not c 翻译成的四元式序列为：翻译成的四元式序列为：(1)t1=not c (2)t2=b and t1 (3)t3=a or t2编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (5353)布尔表达式的翻译方法布尔表达式的翻译方法对于像对于像ab这一类的关系表达式，可以视为等价的条件语句这一类的关系表达式，可以视为等价的条件语句 if ab then 1 else 0 ,它翻译成的四元式序列为：它翻译成的四元
49、式序列为：(1)if ab goto(4)(2)t=0 (3)goto(5)(4)t=1 (5)其中：临时变量其中：临时变量 t 存放布尔表达式存放布尔表达式ab的值的值;(5)为后续的四元式序号。为后续的四元式序号。编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (5454)具体的布尔表达式翻译成四元式的描述如下：具体的布尔表达式翻译成四元式的描述如下：EE1 or E2 E.place:=newtemp;emit(E.place“:=”E1.place“or”E2.place)EE1 and E2 E.place:=newtemp;emit(E.pl
50、ace“:=”E1.place“and”E2.place)Enot E1 E.place:=newtemp;emit(E.place“:=”“”“not”E1.place)E(E1)E.place:=E1.place)编译原理编译原理 第第8 8章章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成 (5555)Eid1 rop id2 E.place:=newtemp;emit(if id1.place“rop”id2.place“goto”nextstart+3);emit(E.place“:=”“”“0”)emit(“goto”nextstart+2)emit(E.place“:=”
