八语法制导翻译和中间代码生成PPT课件.ppt

第第8章章语法制导翻译和语法制导翻译和中间代码生成中间代码生成语义分析语义分析 (semantic analysis)(semantic analysis)编译程序的语义处理工作：编译程序的语义处理工作：静态语义分析静态语义分析静态语义是对程序约束的静态语义是对程序约束的描述。可分为类型规则和作用域描述。可分为类型规则和作用域/可见性可见性规则两大类。审查每个语法结构的静态语规则两大类。审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正义，即验证语法结构合法的程序是否真正有意义。有意义。动态语义动态语义程序单位描述的计算，执行翻程序单位描述的计算，执行翻译、生成目标代码。译、生成目标代码。翻译模式翻译模式(Translation schemes)(Translation schemes)两种翻译模式：生成中间代码形式、直接生两种翻译模式：生成中间代码形式、直接生成目标代码。成目标代码。中间代码中间代码(intermediate code)(intermediate code)中间语言：中间语言：是介于源程序语言和机器语言之间的一种表是介于源程序语言和机器语言之间的一种表示形式。示形式。The semantic rules govern what types are allowable in the various language constructs.语义分析语义分析(1)(1)类类型型检检查查。验验证证程程序序中中执执行行的的每每个个操操作作是是否遵守语言的类型系统的过程否遵守语言的类型系统的过程.(2)(2)控控制制流流检检查查。控控制制流流语语句句必必须须使使控控制制转转移移到合法的地方到合法的地方(3)(3)一一致致性性检检查查。在在很很多多场场合合要要求求对对象象只只能能被被定义一次。定义一次。(4)(4)相关名字检查。相关名字检查。(5)(5)名字的作用域分析名字的作用域分析semantic analysisThe parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules,type rules e.g.To relate each applied occurrence of an identifier in the source program to the corresponding declaration.语义学语义学语义形式化、语义建模语义形式化、语义建模文法模型文法模型属性文法属性文法命令式或操作式模型命令式或操作式模型操作语义学操作语义学公理式模型公理式模型公理语义学公理语义学应用式模型应用式模型指称语义学指称语义学目前在实际应用中比较流行的语义描述和语目前在实际应用中比较流行的语义描述和语义处理的方法主要是义处理的方法主要是属性文法属性文法和和语法制导翻语法制导翻译译 8.1 8.1 属性文法属性文法(attribute grammar)(attribute grammar)一个一个属性文法属性文法包括一个上下文无关文法和包括一个上下文无关文法和一系列语义规则，这些语义规则附在文法一系列语义规则，这些语义规则附在文法的每个产生式上。的每个产生式上。语法制导翻译是指在语法分析过程中，完语法制导翻译是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描成附加在所使用的产生式上的语义规则描述的动作。述的动作。属性文法属性文法一个一个属性文法属性文法是一个是一个三元组三元组 A=(G,V,F)A=(G,V,F)G G 上下文无关文法上下文无关文法 V V 属性的有穷集属性的有穷集 F F 关于属性的断言或谓词关于属性的断言或谓词(语义规则语义规则)的有穷集。的有穷集。每个属性和非终结符或终结符相联每个属性和非终结符或终结符相联每个断言与文法的某产生式相联，只引用该每个断言与文法的某产生式相联，只引用该产生式相联的属性。产生式相联的属性。属性文法属性文法这些属性代表与文法符号相关信息，如它的这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等。类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。性加工的过程即是语义处理的过程。属性的计算规则称为语义规则属性的计算规则称为语义规则属性文法属性文法表达式文法：表达式文法：E ET T1 1+T+T2 2|T|T1 1 or Tor T2 2 T Tnum|true|falsenum|true|false E E T T1 1+T+T2 2 TT1 1.t=int AND T.t=int AND T2 2.t=int.t=int E E T T1 1 or Tor T2 2TT1 1.t=bool AND T.t=bool AND T2 2.t=bool.t=bool T T numT.t:=intnumT.t:=int T T turetureT.t:=boolT.t:=bool T T falsefalseT.t:=bool T.t:=bool 属性文法属性文法使用使用 N.N.t t 的形式表示与非终结符的形式表示与非终结符N N相连的属相连的属性性t t。T.tT.t的值为的值为intint或或boolbool。与非终结符与非终结符E E的产生式相连的断言表明：两的产生式相连的断言表明：两个个T T的属性必须相同。的属性必须相同。继承的和综合的属性继承的和综合的属性属性通常分为两类：属性通常分为两类：综合属性综合属性和和继承属性继承属性综合属性用于综合属性用于“自下而上自下而上”传递信息，传递信息，继承属性用于继承属性用于“自上而下自上而下”传递信息。传递信息。非非终终结结符符既既可可有有综综合合属属性性也也可可有有继继承承属属性性，但文法开始符号没有继承属性。但文法开始符号没有继承属性。终结符只有综合属性。终结符只有综合属性。继承的和综合的属性继承的和综合的属性属性文法中，对应每一个产生式属性文法中，对应每一个产生式 A A 都都有一套与之相关联的语义规则，每条规则的有一套与之相关联的语义规则，每条规则的形式为：形式为：b:=f(cb:=f(c1 1,c,c2 2,c,ck k)其中：其中：f f是一个函数，是一个函数，b b和和c c1 1,c,c2 2,c,ck k是是该产生式文法符号的属性。该产生式文法符号的属性。(1)(1)如果如果b b是是A A的一个属性，的一个属性，c c1 1,c,c2 2,c,ck k是产是产生式右部文法符号的属性或生式右部文法符号的属性或A A的其它属性，的其它属性，则称则称b b是是A A的综合属性。的综合属性。继承的和综合的属性继承的和综合的属性(2)(2)如果如果b b是产生式右部某个文法符号是产生式右部某个文法符号X X的一个的一个属性，并且属性，并且c c1 1,c,c2 2,c,ck k是是A A或产生式右部或产生式右部任何文法符号的属性，则称任何文法符号的属性，则称b b是是X X的继承属性。的继承属性。在两种情况下，都称属性在两种情况下，都称属性b b依赖于属性依赖于属性c c1 1,c,c2 2,c,ck k属性文法的例属性文法的例产生式产生式 语语 义义 规规 则则L LE Print(E.val)E Print(E.val)E EE E1 1+T E.val:=E+T E.val:=E1 1.val+T.val.val+T.valE ET E.val:=T.valT E.val:=T.valT TT T1 1*F T.val:=T*F T.val:=T1 1.val.val F.valF.valT TF T.val:=F.valF T.val:=F.valF F(E)F.val:=E.val(E)F.val:=E.valF Fdigit F.val:=digit.lexvaldigit F.val:=digit.lexval 非终结符非终结符E E、T T及及F F都有一个综合属性都有一个综合属性valval符号符号digitdigit有一个综合属性，它的值由词法有一个综合属性，它的值由词法分析器提供。分析器提供。与产生式与产生式LELE对应的语义规则仅仅是打印由对应的语义规则仅仅是打印由E E产生的算术表达式的值的一个过程，我们产生的算术表达式的值的一个过程，我们可认为这条规则定义了可认为这条规则定义了L L的一个虚属性。的一个虚属性。某些非终结符加下标是为了区分一个产生式某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现中同一非终结符多次出现属性文法的例属性文法的例属性文法的例属性文法的例.LE.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的带注释的分析树的带注释的分析树设表达式为设表达式为 3 35+45+4，则则语义动作语义动作打印数值打印数值1919继承属性继承属性例例8.2 8.2 描述说明语句中各种变量的类型信息描述说明语句中各种变量的类型信息的语义规则，的语义规则，L.inL.in是继承属性。是继承属性。产产 生生 式式语语 义义 规规 则则D TLT intT realL L1,idL idL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)n 一个结点的继一个结点的继承属性值是由此结承属性值是由此结点的父结点和点的父结点和/或或兄弟结点的某些属兄弟结点的某些属性来决定的。性来决定的。继承属性继承属性Real id1,id2,id3DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.，8.2 8.2 语法制导翻译概论语法制导翻译概论一个翻译是符号串对的一个集合一个翻译是符号串对的一个集合。在一个编。在一个编译程序定义的翻译中，符号串对是源程序和译程序定义的翻译中，符号串对是源程序和目标程序。目标程序。各个编译阶段定义一个翻译各个编译阶段定义一个翻译 词法分析：词法分析：(字符串，单词串字符串，单词串)语法分析语法分析：(单词串，语法树单词串，语法树)代码生成：代码生成：(语法树，汇编语言语法树，汇编语言)翻译模式翻译模式翻翻译译模模式式（Translation Translation schemesschemes）适适合合语语法制导翻译的另一种描述形式。法制导翻译的另一种描述形式。翻翻译译模模式式给给出出了了使使用用语语义义规规则则进进行行计计算算的的次次序，可把某些实现细节表示出来。序，可把某些实现细节表示出来。在在翻翻译译模模式式中中，和和文文法法符符号号相相关关的的属属性性和和语语义义规规则则（这这里里我我们们也也称称语语义义动动作作），用用花花括括号号括括起起来来，插插入入到到产产生生式式右右部部的的合合适适位位置上置上。语法制导翻译语法制导翻译直观地说，一个直观地说，一个语法制导翻译语法制导翻译的基础是一个的基础是一个文法，其中翻译成分依附在每一产生式上。文法，其中翻译成分依附在每一产生式上。根据每个产生式所对应的语义子程序根据每个产生式所对应的语义子程序(或语义或语义规则描述的语义动作规则描述的语义动作)进行翻译进行翻译语法制导翻译实现语法制导翻译实现从从概概念念上上讲讲，语语法法制制导导翻翻译译基基于于属属性性文文法法的的处理过程，通常是这样的：处理过程，通常是这样的：输入符号串输入符号串 分析树分析树 属性依赖图属性依赖图 语义规则的计算顺序语义规则的计算顺序8.2.1 8.2.1 计算语义规则计算语义规则依赖图依赖图一个有向图，用于描述分析树中的一个有向图，用于描述分析树中的属性和属性间的相互依赖关系。属性和属性间的相互依赖关系。属性计算有树遍历和一遍扫描两种方法属性计算有树遍历和一遍扫描两种方法树遍历树遍历设已建立语法树，且树中带有开始设已建立语法树，且树中带有开始符号的继承属性和终结符的综合属性，以某符号的继承属性和终结符的综合属性，以某种次序遍历语法树，直到计算出所有属性。种次序遍历语法树，直到计算出所有属性。一遍扫描一遍扫描在语法分析的同时计算属性值在语法分析的同时计算属性值依赖图的构造算法依赖图的构造算法For For 分析树中的每一个结点分析树中的每一个结点n n do do For For 结点的文法符号的每一个属性结点的文法符号的每一个属性 a doa do 为为a a在依赖图中建立一个结点在依赖图中建立一个结点；For For 分析树中的每一个结点分析树中的每一个结点n n do doFor For 结点结点n n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则 b:=f(c1,c2,b:=f(c1,c2,ck)do,ck)do For i:=1 do For i:=1 do 从从cici结点到结点到b b结点构造一条有向边结点构造一条有向边 8.2.2 S-8.2.2 S-属性文法和自下而上翻译属性文法和自下而上翻译L-L-属性文法属性文法的一个特例：的一个特例：S-S-属性文法属性文法S-S-属性文法属性文法：只含有综合属性的属性文法：只含有综合属性的属性文法综合属性可以在分析输入符号串的同时自下综合属性可以在分析输入符号串的同时自下而上的计算而上的计算语法制导方式计算表达式语法制导方式计算表达式 2+3*52+3*52+3*52+3*5的分析和计值过程的分析和计值过程步骤步骤 动作动作 状态栈状态栈 语义栈语义栈(值栈值栈)符号栈符号栈 余留输入余留输入串串1)0 -1)0 -#2+3*5#2+3*5#2)05 -2)05 -#2+3*5#2+3*5#3)r6 03 -2 3)r6 03 -2#F +3*5#F +3*5#4)r4 02 -2 4)r4 02 -2#T +3*5#T +3*5#5)r2 01 -2 5)r2 01 -2#E +3*5#E +3*5#6)016 -2-6)016 -2E+3*5#E+3*5#7)0165 -2-7)0165 -2-#E+3#E+3 *5#*5#步骤步骤 动作动作 状态栈状态栈 语义栈语义栈(值栈值栈)符号栈符号栈 余留输入余留输入串串8)r6 0163 -2-3#E+F 8)r6 0163 -2-3#E+F *5#*5#9)r4 0169 -2-3#E+T9)r4 0169 -2-3#E+T *5#*5#10)01697 -2-3-#E+T*10)01697 -2-3-#E+T*5#5#11)016975 -2-3-#E+T*5 11)016975 -2-3-#E+T*5#12)r6 01697(10)-2-3-5#E+T*F 12)r6 01697(10)-2-3-5#E+T*F#13)r3 0169 -2-(15)#E+T 13)r3 0169 -2-(15)#E+T#14)r1 0114)r1 01 -(17)#E -(17)#E#15)15)接受接受2+3*52+3*5的分析和计值过程的分析和计值过程8.2.3 8.2.3 L-L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现一个属性文法称为一个属性文法称为L-L-属性文法属性文法，如果对于每，如果对于每个产生式个产生式 A A X X1 1X X2 2X Xn n，其每个语义规则中，其每个语义规则中的每个属性或者是的每个属性或者是综合属性综合属性，或者是，或者是X Xj j(1jn)(1jn)的一个的一个继承属性继承属性且仅依赖于：且仅依赖于：(1)(1)在在X Xj j左边的符号左边的符号X X1 1,X,X2 2,X Xj-1 j-1 的属性；的属性；(2)A(2)A 的继承属性的继承属性L-L-属性文法允许一次遍历就计算出所有属性属性文法允许一次遍历就计算出所有属性值值8.2.4 8.2.4 L-L-属性文法在自下而上分析中的实现属性文法在自下而上分析中的实现实现方法：从翻译模式中去掉嵌入在产生式实现方法：从翻译模式中去掉嵌入在产生式在中间的动作或者在中间的动作或者用综合属性代替继承属性用综合属性代替继承属性8.3 8.3 中间代码的形式中间代码的形式n 中间代码中间代码(Intermediate code)(Intermediate code)n 源程序的一种内部表示源程序的一种内部表示n 不依赖目标机的结构；易于机械生成目标代不依赖目标机的结构；易于机械生成目标代码；逻辑结构清楚；利于不同目标机上实现同码；逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化。一种语言；利于进行与机器无关的优化。n 中间代码的几种形式：中间代码的几种形式：逆波兰、四元式、三元式、间接三元式、树逆波兰、四元式、三元式、间接三元式、树中间代码生成中间代码生成(intermediate code(intermediate code generation)generation)-This is where the intermediate representation of the source program is created.We want this representation to be easy to generate,and easy to translate into the target program.The representation can have a variety of forms,but a common one is called three-address code or 4-tuple code.8.3.1 8.3.1 逆波兰记号逆波兰记号逆波兰表示逆波兰表示对表达式的后缀表示对表达式的后缀表示语言中的表示形式语言中的表示形式逆波兰表示逆波兰表示 a+b a+b*c (a+b)*c a:=b*c+b*d ab+abc*+ab+c*abc*bd*+:=逆波兰记号逆波兰记号例如：例如：-B+C*D-B+C*D 的逆波兰式为的逆波兰式为 BCD*BCD*+，采，采用堆栈方式，扫描表达式。计值过程为：用堆栈方式，扫描表达式。计值过程为：1.1.B B进栈进栈2.2.对对B B进行单目运算，栈顶置换为进行单目运算，栈顶置换为-B-B3.3.C C进栈进栈4.4.D D进栈进栈5.5.栈顶两元素栈顶两元素C C、D D相乘并退栈，结果进栈相乘并退栈，结果进栈6.6.栈顶两元素相加，退栈，结果进栈栈顶两元素相加，退栈，结果进栈 例例8.5 8.5 把下述产生式定义的算术表达式映把下述产生式定义的算术表达式映射到后缀射到后缀(逆波兰逆波兰)表示：表示：逆波兰记号逆波兰记号 产产 生生 式式 翻翻 译译 规规 则则 EE+T E T T T F T F F(E)F a E=ET+E=T T=TF T=F F=E F=a逆波兰记号逆波兰记号例：例：A+B*(C-D)+E/(C-D)NA+B*(C-D)+E/(C-D)N 逆波兰式：逆波兰式：A B C D-*+E C D A B C D-*+E C D N /+N /+例：例：if E then Sif E then S1 1 else S else S2 2作为三目运算符处理，用￥表示：作为三目运算符处理，用￥表示：E SE S1 1S S2 2￥8.3.2 8.3.2 三元式和树形表示三元式和树形表示三元式：三元式：(op,ARG1,ARG2)(op,ARG1,ARG2)其中：其中：op op 运算符运算符 ARG1 ARG1 第一运算对象第一运算对象 ARG2 ARG2 第二运算对象第二运算对象例例 :a:=b*c+b*d:a:=b*c+b*d 三元式：三元式：(1)(*(1)(*，b b，c )c )(2)(*(2)(*，b b，d)d)(3)(+(3)(+，(1)(1)，(2)(2)(4)(:=(4)(:=，(3)(3)，a)a)树形表示树形表示例例 :a:=b*c+b*d:a:=b*c+b*d二目运算对应二叉树，二目运算对应二叉树，:=*a+cb*bd三元式和树形表示三元式和树形表示例例 :A+B*(C-D)+E/(C-D)N:A+B*(C-D)+E/(C-D)N 三元式三元式:(1)(-C D :(1)(-C D )(2)(*B (2)(*B (1)(1)(3)(+A (3)(+A (2)(2)(4)(-C (4)(-C D )D )(5)(4)(5)(4)N )N )(6)(/E (6)(/E (5)(5)(7)(+(7)(+(3)(6)(3)(6)间接三元式间接三元式 间间接码表接码表(1)(-C D )(1)(-C D )(1)(1)(2)(*B (1)(2)(*B (1)(2)(2)(3)(+A (2)(3)(+A (2)(3)(3)(4)(1)N )(4)(1)N )(1)(1)(5)(/E (4)(5)(/E (4)(4)(4)(6)(6)(+(3)(5)(3)(5)(+(3)(5)(3)(5)三元式和树形表示三元式和树形表示8.3.3 8.3.3 四元式四元式四元式形式四元式形式：(op,ARG1,ARG2,RESULT)(op,ARG1,ARG2,RESULT)其中：其中：op op 运算符运算符 ARG1 ARG1 第一运算对象第一运算对象 ARG2 ARG2 第二运算对象第二运算对象 RESULT RESULT 运算结果运算结果 RESULT:=ARG1 op ARG2RESULT:=ARG1 op ARG2运算对象及运算结果是程序中定义的变量，运算对象及运算结果是程序中定义的变量，必要时可使用编译程序引进的临时变量。必要时可使用编译程序引进的临时变量。四元式四元式例例 :A+B*(C-D)+E/(C-D)N:A+B*(C-D)+E/(C-D)N 四元式四元式 :(1)(-C D :(1)(-C D T T1 1)(2)(*B T (2)B T1 1 T T2 2)(3)(+A T (3)(+A T2 2 T T3 3)(4)(-C D (4)(-C D T T4 4)(5)(T (5)(T4 4 N N T T5 5)(6)(/E T (6)(/E T5 5 T T6 6)(7)(+T (7)(+T3 3 T T6 6 T T7 7)四元式写成简单赋值形式四元式写成简单赋值形式(1)(1)t t1 1:=b*c:=b*c(2)(2)t t2 2:=b*d:=b*d(3)(3)t t3 3:=t:=t1 1+t+t2 2(4)(4)a:=t a:=t3 3其它语句直接写成：其它语句直接写成：(jump,-,-,L)goto L(jump,-,-,L)goto L(jrop,B,C,L)if B rop C goto L(jrop,B,C,L)if B rop C goto L8.4 8.4 简单赋值语句的翻译简单赋值语句的翻译在四元式中，用在四元式中，用t ti i表示中间或最后结果，实表示中间或最后结果，实际实现时，际实现时，t ti i或者是指向符号表项的指针，或者是指向符号表项的指针，或者是一个临时变量的整数码。或者是一个临时变量的整数码。属性属性 id.name,E.placeid.name,E.place，作为语义变量，作为语义变量E.placeE.place表示存放表示存放E E值的变量名在符号表中的值的变量名在符号表中的登录项，或临时变量的整数码。登录项，或临时变量的整数码。简单赋值语句的翻译简单赋值语句的翻译语义函数语义函数lookup(id.name)lookup(id.name)，审查，审查id.name id.name 是否出现在符号表中，返回指针值或是否出现在符号表中，返回指针值或nilnil。语义过程语义过程 emit(t:=arg1 op arg2)emit(t:=arg1 op arg2)表示表示输出四元式到输出文件。输出四元式到输出文件。语义过程语义过程 newtemp newtemp 表示每调用一次，生成表示每调用一次，生成一新的临时变量。一新的临时变量。对变量先定义后检查。对变量先定义后检查。(1)S(1)S id:=E p:=id:=E p:=lookup(id.name)lookup(id.name)if p if p nil nil thenthen emit(p emit(p :=:=E.place)E.place)else else errorerror(2)E(2)EE E1 1+E+E2 2 E.place:=newtemp;E.place:=newtemp;emit(E.place emit(E.place:=:=E E1 1.place.place+E E2 2.place).place)(3)E(3)E E E1 1*E*E2 2 E.place:=newtemp;E.place:=newtemp;emit(E.place emit(E.place:=:=E E1 1.place.place*E E2 2.place).place)产生式和语义动作描述产生式和语义动作描述(4)E(4)E -E-E1 1 E.place:=newtemp;E.place:=newtemp;emit(E.placeemit(E.place:=:=uminusuminus E E1 1.place).place)(5)E(5)E(E(E1 1)E.place:=E)E.place:=E1 1.place.place(6)E(6)Eid E.place:=newtemp;id E.place:=newtemp;P:=lookup(id.name);P:=lookup(id.name);if P if P nil then nil then E.place:=PE.place:=P else error else error产生式和语义动作描述产生式和语义动作描述类型转换的语义处理类型转换的语义处理在编译过程中应对表达式中的运算对象进行在编译过程中应对表达式中的运算对象进行语义检查。语义检查。对不同类型的运算对象进行混合运算，有两对不同类型的运算对象进行混合运算，有两种处理方式：指出错误或类型转换。种处理方式：指出错误或类型转换。语义变量语义变量E.typeE.type表示表示E E的类型信息，假定的类型信息，假定E.typeE.type的值为的值为intint或或realreal整型整型+整型整型*实型实型+实型实型*+i i *i i +r r *r r一目运算符一目运算符 itr itr 将整型转换成实型将整型转换成实型产生式产生式(3)(3)的语义动作描述的语义动作描述E E E E1 1*E*E2 2 E.place:=newtemp;E.place:=newtemp;if E if E1 1.type=int AND E.type=int AND E2 2.type=int then.type=int then begin begin emit(E.place emit(E.place:=:=E E1 1.place.place*E E2 2.place);.place);E.type:=int E.type:=int end end else else 产生式产生式(3)(3)的语义动作描述的语义动作描述 if E if E1 1.type=real AND E.type=real AND E2 2.type=real then.type=real then beginbegin emit(E.place,emit(E.place,:=:=,E,E1 1.place.place*E E2 2.place);.place);E.type:=real E.type:=real end end else else 产生式产生式(3)(3)的语义动作描述的语义动作描述if Eif E1 1.type=int/*and E.type=int/*and E2 2.type=real*/then.type=real*/then begin begin t:=newtemp;t:=newtemp;emit(t,emit(t,:=:=,itritr,E,E1 1.place);.place);emit(E.place,emit(E.place,:=:=,t,t,*r r,E,E2 2.place);.place);E.type:=real E.type:=real end endelse /*Eelse /*E1 1.type=real and E.type=real and E2 2.type=int*/.type=int*/产生式产生式(3)(3)的语义动作描述的语义动作描述 begin begin t:=newtemp;t:=newtemp;emit(t,emit(t,:=:=,itritr,E,E2 2.place);.place);emit(E.place,emit(E.place,:=:=,E,E1 1.place,.place,*r r,t);,t);E.type:=real E.type:=real end end 8.5 8.5 布尔表达式的翻译布尔表达式的翻译布尔表达式的作用：计算逻辑值、用做控制布尔表达式的作用：计算逻辑值、用做控制流语句中的条件表达式流语句中的条件表达式布尔表达式的形式：布尔表达式的形式：E E1 1 rop E rop E2 2 即：即：2按如下文法生成的布尔表达式：按如下文法生成的布尔表达式：E E E and E E and E|E or E E or E|not E not E|id and id and id id|true true|false false8.5.1 8.5.1 布尔表达式的翻译方法布尔表达式的翻译方法控制语句的翻译控制语句的翻译结构的翻译结构的翻译方法方法1 1：用：用1 1表示表示truetrue，用，用0 0表示表示falsefalse，计算，计算整个表达式的值。整个表达式的值。方法方法2 2：优化方法：优化方法 C C语言的方法，某些情语言的方法，某些情况下不需要计算整个表达式的值。况下不需要计算整个表达式的值。布尔表达式翻译成四元式布尔表达式翻译成四元式布尔表达式：布尔表达式：a or b and not a or b and not c c(1)(1)t t1 1:=not c:=not c(2)(2)t t2 2:=b and t:=b and t1 1(3)(3)t t3 3:=a or t:=a or t2 2关系式关系式 a b a b 等价的条件语句：等价的条件语句：if ab then 1 else 0if ab then 1 else 0(1)(1)if ab goto(4)if ab goto(4)(2)(2)t:=0 t:=0(3)(3)goto (5)goto (5)(4)(4)t:=1 t:=1(5)(5)用数值表示布尔值的翻译方案用数值表示布尔值的翻译方案E E E E1 1 or E or E2 2 E.place:=newtemp;E.place:=newtemp;emit(E.place,emit(E.place,:=:=,E,E1 1.placeplace or or E E2 2.place);.place);E E E E1 1 and E and E2 2 E.place:=newtemp;E.place:=newtemp;emit(E.place,emit(E.place,:=:=,E,E1 1.place.place and and E E2 2.place);.place);E E notnot E E1 1 E.place:=newtemp;E.place:=newtemp;emit(E.place,emit(E.place,:=:=not not E E1 1.place);.place);E E (E E1 1)Eplace:=E)E.place:=E1 1.place);.place);THANK YOUSUCCESS2024/3/9 周六57可编辑用数值表示布尔值的翻译方案用数值表示布尔值的翻译方案E E id id1 1 rop id rop id2 2 E.place:=newtemp;E.place:=newtemp;emit(emit(ififidid1 1.place.place rop rop idid2 2.place.place gotogotonextstat+3);nextstat+3);emit(E.place,emit(E.place,:=:=0 0););emit(goto emit(gotonextstat+2);nextstat+2);emit(E.place,emit(E.place,:=:=1 1););其中其中nextstatnextstat给出了在输出序列中下一四元给出了在输出序列中下一四元式序号。调用式序号。调用emitemit过程，每次加过程，每次加1 1。用数值表示布尔值的翻译方案用数值表示布尔值的翻译方案E E true true E.place:=newtemp;E.place:=newtemp;emit(E.place,emit(E.place,:=:=1 1););E E false false E.place:=newtemp;E.place:=newtemp;emit(E.place,emit(E.place,:=:=0 0););8.5.2 8.5.2 控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译三种控制语句的语法为：三种控制语句的语法为：S S if E then Sif E then S1 1|if E then S|if E then S1 1 else S else S2 2|While E do S|While E do S1 1E的代码的代码 S1的代码的代码if E then S1的代码结构的代码结构truefalse控制语句的代码结构控制语句的代码结构E.falseE的代码的代码E.true S1的代码的代码jump out S2的代码的代码out:if E then S1 else S2的代码结构的代码结构E的代码的代码 S1的代码的代码jump beginbeginWhile E do S1 代码结构代码结构n 把条件转移的布尔表达式把条件转移的布尔表达式 E E 翻译成仅含：翻译成仅含：条件真条件真转和无条件转和无条件转的四元式。转的四元式。n E E：a rop ba rop b if a rop b goto E.true if a rop b goto E.true goto E.false goto E.false控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译例：例：ab or cfab or cf 可翻译成如下四元式：可翻译成如下四元式：(1)(1)if ab goto E.true if ab goto E.true(2)(2)goto (3)goto (3)(3)(3)if cd goto (5)if cf goto E.true if ef goto E.true(6)(6)goto E.false goto E.false例：语句例：语句 if ab or cf if ab or cf then Sthen S1 1 else S else S2 2 的四元式序列为的四元式序列为(1)(1