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

1、语义分析语义分析n编译程序的语义处理工作：编译程序的语义处理工作：n静态语义分析静态语义分析审查每个语法结构的静态审查每个语法结构的静态语义，即验证语法结构合法的程序是否真语义，即验证语法结构合法的程序是否真正有意义。正有意义。n动态语义动态语义执行翻译、生成目标代码执行翻译、生成目标代码n两种翻译模式：生成中间代码形式、直接生两种翻译模式：生成中间代码形式、直接生成目标代码。成目标代码。n中间代码中间代码中间语言：是介于源程序语言和中间语言：是介于源程序语言和机器语言之间的一种表示形式。机器语言之间的一种表示形式。语义学语义学语义形式化、语义建模语义形式化、语义建模n文法模型文法模型属性文法

2、属性文法n命令式或操作式模型命令式或操作式模型操作语义学操作语义学n公理式模型公理式模型公理语义学公理语义学n应用式模型应用式模型指称语义学指称语义学n目前在实际应用中比较流行的语义描述和语目前在实际应用中比较流行的语义描述和语义处理的方法主要是义处理的方法主要是属性文法属性文法和和语法制导翻语法制导翻译译 8.1 属性文法属性文法(attribute grammar)n一个一个属性文法属性文法包括一个上下文无关文法和包括一个上下文无关文法和一系列语义规则，这些语义规则附在文法一系列语义规则，这些语义规则附在文法的每个产生式上。的每个产生式上。n语法制导翻译是指在语法分析过程中，完语法制导翻译

3、是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描成附加在所使用的产生式上的语义规则描述的动作。述的动作。属性文法属性文法n一个一个属性文法属性文法是一个是一个三元组三元组 A=(G,V,F)G 上下文无关文法上下文无关文法 V 属性的有穷集属性的有穷集 F 关于属性的断言或谓词关于属性的断言或谓词(语义规则语义规则)的的有穷集。有穷集。n每个属性和非终结符或终结符相联每个属性和非终结符或终结符相联n每个断言与文法的某产生式相联，只引用该每个断言与文法的某产生式相联，只引用该产生式相联的属性。产生式相联的属性。属性文法属性文法n这些属性代表与文法符号相关信息，如它的这些属性代表与文法

4、符号相关信息，如它的类型、值、代码序列、符号表内容等等。类型、值、代码序列、符号表内容等等。n属性与变量一样，可以进行计算和传递。属属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。性加工的过程即是语义处理的过程。n属性的计算规则称为语义规则属性的计算规则称为语义规则属性文法属性文法n表达式文法：表达式文法：ET1+T2|T1 or T2 Tnum|true|false E T1+T2 T1.t=int AND T2.t=int E T1 or T2T1.t=bool AND T2.t=bool T numT.t:=int T tureT.t:=bool T falseT.

5、t:=bool 属性文法属性文法n使用使用 N.t 的形式表示与非终结符的形式表示与非终结符N相连的属相连的属性性t。nT.t的值为的值为int或或bool。n与非终结符与非终结符E的产生式相连的断言表明：两的产生式相连的断言表明：两个个T的属性必须相同。的属性必须相同。继承的和综合的属性继承的和综合的属性n属性通常分为两类：属性通常分为两类：综合属性综合属性和和继承属性继承属性n综合属性用于综合属性用于“自下而上自下而上”传递信息，传递信息，n继承属性用于继承属性用于“自上而下自上而下”传递信息。传递信息。n非终结符既可有综合属性也可有继承属性，非终结符既可有综合属性也可有继承属性，但文法开

6、始符号没有继承属性。但文法开始符号没有继承属性。n终结符只有综合属性。终结符只有综合属性。继承的和综合的属性继承的和综合的属性n属性文法中，对应每一个产生式属性文法中，对应每一个产生式 A 都有都有一套与之相关联的语义规则，每条规则的形一套与之相关联的语义规则，每条规则的形式为：式为：b:=f(c1,c2,ck)其中：其中：f是一个函数，是一个函数，b和和c1,c2,ck是该是该产生式文法符号的属性。产生式文法符号的属性。(1)如果如果b是是A的一个属性，的一个属性，c1,c2,ck是产是产生式右部文法符号的属性或生式右部文法符号的属性或A的其它属性，的其它属性，则称则称b是是A的综合属性。的

7、综合属性。继承的和综合的属性继承的和综合的属性(2)如果如果b是产生式右部某个文法符号是产生式右部某个文法符号X的一个的一个属性，并且属性，并且c1,c2,ck是是A或产生式右部或产生式右部任何文法符号的属性，则称任何文法符号的属性，则称b是是X的继承属的继承属性。性。n在两种情况下，都称属性在两种情况下，都称属性b依赖于属性依赖于属性c1,c2,ck属性文法的例属性文法的例产生式产生式 语语 义义 规规 则则LE Print(E.val)EE1+T E.val:=E1.val+T.valET E.val:=T.valTT1*F T.val:=T1.val F.valTF T.val:=F.v

8、alF(E)F.val:=E.valFdigit F.val:=digit.lexval n非终结符非终结符E、T及及F都有一个综合属性都有一个综合属性valn符号符号digit有一个综合属性，它的值由词法有一个综合属性，它的值由词法分析器提供。分析器提供。n与产生式与产生式LE对应的语义规则仅仅是打印由对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们产生的算术表达式的值的一个过程，我们可认为这条规则定义了可认为这条规则定义了L的一个虚属性。的一个虚属性。n某些非终结符加下标是为了区分一个产生式某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现中同一非终结符多次出现属

9、性文法的例属性文法的例属性文法的例属性文法的例.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的带注释的分析树的带注释的分析树设表达式为设表达式为 35+4，则则语义动作语义动作打印数值打印数值19继承属性继承属性例例8.2 描述说明语句中各种变量的类型信息描述说明语句中各种变量的类型信息的语义规则，的语义规则，L.in是继承属性。是继承属性。产产 生生 式式语语 义义 规规 则则D TLT intT realL L1,id

10、L 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 语法制导翻译概论语法制导翻译概论n一个翻译是符号串对的一个集合一个翻译是符号串对的一个集合。在一

11、个编。在一个编译程序定义的翻译中，符号串对是源程序和译程序定义的翻译中，符号串对是源程序和目标程序。目标程序。n各个编译阶段定义一个翻译各个编译阶段定义一个翻译 词法分析：词法分析：(字符串，单词串字符串，单词串)语法分析语法分析：(单词串，语法树单词串，语法树)代码生成：代码生成：(语法树，汇编语言语法树，汇编语言)语法制导翻译语法制导翻译n直观地说，一个直观地说，一个语法制导翻译语法制导翻译的基础是一个的基础是一个文法，其中翻译成分依附在每一产生式上。文法，其中翻译成分依附在每一产生式上。n根据每个产生式所对应的语义子程序根据每个产生式所对应的语义子程序(或语义或语义规则描述的语义动作规则

12、描述的语义动作)进行翻译进行翻译语法制导翻译实现语法制导翻译实现n从概念上讲，语法制导翻译基于属性文法的从概念上讲，语法制导翻译基于属性文法的处理过程，通常是这样的：处理过程，通常是这样的：输入符号串输入符号串 分析树分析树 属性依赖图属性依赖图 语义规则的计算顺序语义规则的计算顺序8.2.1 计算语义规则计算语义规则n依赖图依赖图一个有向图，用于描述分析树中的一个有向图，用于描述分析树中的属性和属性间的相互依赖关系。属性和属性间的相互依赖关系。n属性计算有树遍历和一遍扫描两种方法属性计算有树遍历和一遍扫描两种方法n树遍历树遍历设已建立语法树，且树中带有开始设已建立语法树，且树中带有开始符号的

13、继承属性和终结符的综合属性，以某符号的继承属性和终结符的综合属性，以某种次序遍历语法树，直到计算出所有属性。种次序遍历语法树，直到计算出所有属性。n一遍扫描一遍扫描在语法分析的同时计算属性值在语法分析的同时计算属性值依赖图的构造算法依赖图的构造算法For 分析树中的每一个结点分析树中的每一个结点n do For 结点的文法符号的每一个属性结点的文法符号的每一个属性 a do 为为a在依赖图中建立一个结点在依赖图中建立一个结点；For 分析树中的每一个结点分析树中的每一个结点n doFor 结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则 b:=f(c1,c2,ck)do

14、For i:=1 do 从从ci结点到结点到b结点构造一条有向边结点构造一条有向边 8.2.2 S-属性文法和自下而上翻译属性文法和自下而上翻译nL-属性文法属性文法的一个特例：的一个特例：S-属性文法属性文法nS-属性文法属性文法：只含有综合属性的属性文法：只含有综合属性的属性文法n综合属性可以在分析输入符号串的同时自下综合属性可以在分析输入符号串的同时自下而上的计算而上的计算n语法制导方式计算表达式语法制导方式计算表达式 2+3*52+3*5的分析和计值过程的分析和计值过程步骤步骤 动作动作 状态栈状态栈 语义栈语义栈(值栈值栈)符号栈符号栈 余留输入串余留输入串1)0 -#2+3*5#2

15、)05 -#2+3*5#3)r6 03 -2#F +3*5#4)r4 02 -2#T +3*5#5)r2 01 -2#E +3*5#6)016 -2-#E+3*5#7)0165 -2-#E+3 *5#步骤步骤 动作动作 状态栈状态栈 语义栈语义栈(值栈值栈)符号栈符号栈 余留输入串余留输入串8)r6 0163 -2-3#E+F *5#9)r4 0169 -2-3#E+T *5#10)01697 -2-3-#E+T*5#11)016975 -2-3-#E+T*5#12)r6 01697(10)-2-3-5#E+T*F#13)r3 0169 -2-(15)#E+T#14)r1 01 -(17)#E

16、#15)接受接受2+3*5的分析和计值过程的分析和计值过程8.2.3 L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现n一个属性文法称为一个属性文法称为L-属性文法属性文法，如果对于每，如果对于每个产生式个产生式 A X1X2Xn，其每个语义规则中，其每个语义规则中的每个属性或者是的每个属性或者是综合属性综合属性，或者是，或者是Xj(1jn)的一个的一个继承属性继承属性且仅依赖于：且仅依赖于：(1)在在Xj左边的符号左边的符号X1,X2,Xj-1 的属性；的属性；(2)A 的继承属性的继承属性nL-属性文法允许一次遍历就计算出所有属性属性文法允许一次遍历就计算出所有属性值值8.

17、2.4 L-属性文法在自下而上分析中的实现属性文法在自下而上分析中的实现n实现方法：从翻译模式中去掉嵌入在产生式实现方法：从翻译模式中去掉嵌入在产生式在中间的动作或者在中间的动作或者用综合属性代替继承属性用综合属性代替继承属性8.3 中间代码的形式中间代码的形式n 中间代码中间代码(Intermediate code)n 源程序的一种内部表示源程序的一种内部表示n 不依赖目标机的结构；易于机械生成目标代不依赖目标机的结构；易于机械生成目标代码；逻辑结构清楚；利于不同目标机上实现同码；逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化。一种语言；利于进行与机器无关的优化。n

18、中间代码的几种形式：中间代码的几种形式：逆波兰、四元式、三元式、间接三元式、树逆波兰、四元式、三元式、间接三元式、树 8.3.1 逆波兰记号逆波兰记号n逆波兰表示逆波兰表示对表达式的后缀表示对表达式的后缀表示语言中的表示形式语言中的表示形式逆波兰表示逆波兰表示 a+b a+b*c (a+b)*c a:=b*c+b*d ab+abc*+ab+c*abc*bd*+:=逆波兰记号逆波兰记号n例如：例如：-B+C*D 的逆波兰式为的逆波兰式为 BCD*+，采用堆栈方式，扫描表达式。计值过程为：采用堆栈方式，扫描表达式。计值过程为：n B进栈进栈n 对对B进行单目运算，栈顶置换为进行单目运算，栈顶置换为

19、-Bn C进栈进栈n D进栈进栈n 栈顶两元素栈顶两元素C、D相乘并退栈，结果进栈相乘并退栈，结果进栈1.栈顶两元素相加，退栈，结果进栈栈顶两元素相加，退栈，结果进栈 n例例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)N 逆波兰式：逆波兰式：A B C D-*+E C D N /+例：例：if E t

20、hen S1 else S2作为三目运算符处理，用￥表示：作为三目运算符处理，用￥表示：E S1S2￥8.3.2 三元式和树形表示三元式和树形表示三元式：三元式：(op,ARG1,ARG2)其中：其中：op 运算符运算符 ARG1 第一运算对象第一运算对象 ARG2 第二运算对象第二运算对象例例:a:=b*c+b*d 三元式：三元式：(1)(*，b，c )(2)(*，b，d)(3)(+，(1)，(2)(4)(:=，(3)，a)树形表示树形表示n例例:a:=b*c+b*dn二目运算对应二叉树，二目运算对应二叉树，:=*a+cb*bd三元式和树形表示三元式和树形表示例例:A+B*(C-D)+E/(

21、C-D)N 三元式三元式:(1)(-C D )(2)(*B (1)(3)(+A (2)(4)(-C D )(5)(4)N )(6)(/E (5)(7)(+(3)(6)间接三元式间接三元式 间接码表间接码表(1)(-C D )(1)(2)(*B (1)(2)(3)(+A (2)(3)(4)(1)N )(1)(5)(/E (4)(4)(6)(+(3)(5)(3)(5)三元式和树形表示三元式和树形表示8.3.3 四元式四元式四元式形式四元式形式：(op,ARG1,ARG2,RESULT)其中：其中：op 运算符运算符 ARG1 第一运算对象第一运算对象 ARG2 第二运算对象第二运算对象 RESUL

22、T 运算结果运算结果 RESULT:=ARG1 op ARG2运算对象及运算结果是程序中定义的变量，运算对象及运算结果是程序中定义的变量，必要时可使用编译程序引进的临时变量。必要时可使用编译程序引进的临时变量。四元式四元式例例:A+B*(C-D)+E/(C-D)N 四元式四元式:(1)(-C D T1)(2)(*B T1 T2)(3)(+A T2 T3)(4)(-C D T4)(5)(T4 N T5)(6)(/E T5 T6)(7)(+T3 T6 T7)四元式写成简单赋值形式四元式写成简单赋值形式n t1:=b*cn t2:=b*dn t3:=t1+t2n a:=t3n其它语句直接写成：其它语

23、句直接写成：(jump,-,-,L)goto L(jrop,B,C,L)if B rop C goto L8.4 简单赋值语句的翻译简单赋值语句的翻译在四元式中，用在四元式中，用ti表示中间或最后结果，实表示中间或最后结果，实际实现时，际实现时，ti或者是指向符号表项的指针，或者是指向符号表项的指针，或者是一个临时变量的整数码。或者是一个临时变量的整数码。属性属性 id.name,E.place，作为语义变量，作为语义变量E.place表示存放表示存放E值的变量名在符号表中的值的变量名在符号表中的登录项，或临时变量的整数码。登录项，或临时变量的整数码。简单赋值语句的翻译简单赋值语句的翻译语义函

24、数语义函数lookup(id.name)，审查，审查id.name 是否出现在符号表中，返回指针值或是否出现在符号表中，返回指针值或nil。语义过程语义过程 emit(t:=arg1 op arg2)表示输表示输出四元式到输出文件。出四元式到输出文件。语义过程语义过程 newtemp 表示每调用一次，生成表示每调用一次，生成一新的临时变量。一新的临时变量。对变量先定义后检查。对变量先定义后检查。(1)S id:=E p:=lookup(id.name)if p nil then emit(p:=E.place)else error(2)EE1+E2 E.place:=newtemp;emit(

25、E.place:=E1.place+E2.place)(3)E E1*E2 E.place:=newtemp;emit(E.place:=E1.place*E2.place)产生式和语义动作描述产生式和语义动作描述(4)E-E1 E.place:=newtemp;emit(E.place:=uminus E1.place)(5)E(E1)E.place:=E1.place(6)Eid E.place:=newtemp;P:=lookup(id.name);if P nil then E.place:=P else error产生式和语义产生式和语义动作动作描述描述类型转换的语义处理类型转换的语

26、义处理n在编译过程中应对表达式中的运算对象进行在编译过程中应对表达式中的运算对象进行语义检查。语义检查。n对不同类型的运算对象进行混合运算，有两对不同类型的运算对象进行混合运算，有两种处理方式：指出错误或类型转换。种处理方式：指出错误或类型转换。n语义变量语义变量E.type表示表示E的类型信息，假定的类型信息，假定E.type的值为的值为int或或realn整型整型+整型整型*实型实型+实型实型*+i *i +r *rn一目运算符一目运算符 itr 将整型转换成实型将整型转换成实型产生式产生式(3)的语义动作描述的语义动作描述E E1*E2 E.place:=newtemp;if E1.ty

27、pe=int AND E2.type=int then begin emit(E.place:=E1.place*E2.place);E.type:=int end else 产生式产生式(3)的语义动作描述的语义动作描述 if E1.type=real AND E2.type=real then begin emit(E.place,:=,E1.place*E2.place);E.type:=real end else 产生式产生式(3)的语义动作描述的语义动作描述if E1.type=int/*and E2.type=real*/then begin t:=newtemp;emit(t,:

28、=,itr,E1.place);emit(E.place,:=,t,*r,E2.place);E.type:=real endelse /*E1.type=real and E2.type=int*/产生式产生式(3)的语义动作描述的语义动作描述 begin t:=newtemp;emit(t,:=,itr,E2.place);emit(E.place,:=,E1.place,*r,t);E.type:=real end 8.5 布尔表达式的翻译布尔表达式的翻译n布尔表达式的作用：计算逻辑值、用做控制布尔表达式的作用：计算逻辑值、用做控制流语句中的条件表达式流语句中的条件表达式n布尔表达式的形

29、式：布尔表达式的形式：E1 rop E2 即：即：2n按如下文法生成的按如下文法生成的布尔表达式：布尔表达式：E E andand E|E oror E|notnot E|id andand id|true|false8.5.1 布尔表达式的翻译方法布尔表达式的翻译方法控制语句的翻译控制语句的翻译结构的翻译结构的翻译方法方法1：用：用1表示表示true，用，用0表示表示false，计，计算整个表达式的值。算整个表达式的值。方法方法2：优化方法：优化方法 C语言的方法，某些情语言的方法，某些情况下不需要计算整个表达式的值。况下不需要计算整个表达式的值。布尔表达式翻译成四元式布尔表达式翻译成四元式

30、n布尔表达式：布尔表达式：a or b and not cn t1:=not cn t2:=b and t1(1)t3:=a or t2n关系式关系式 a b 等价的条件语句：等价的条件语句：if ab then 1 else 0n if ab goto(4)n t:=0n goto (5)n t:=1(1)用数值表示布尔值的翻译方案用数值表示布尔值的翻译方案E E1 or E2 E.place:=newtemp;emit(E.place,:=,E1.place or E2.place);E E1 and E2 E.place:=newtemp;emit(E.place,:=,E1.place

31、 and E2.place);E not E1 E.place:=newtemp;emit(E.place,:=not E1.place);E (E1)E.place:=E1.place);用数值表示布尔值的翻译方案用数值表示布尔值的翻译方案E id1 rop id2 E.place:=newtemp;emit(ifid1.place rop id2.place gotonextstat+3);emit(E.place,:=0);emit(gotonextstat+2);emit(E.place,:=1);n其中其中nextstat给出了在输出序列中下一四元给出了在输出序列中下一四元式序号。调

32、用式序号。调用emit过程，每次加过程，每次加1。用数值表示布尔值的翻译方案用数值表示布尔值的翻译方案E true E.place:=newtemp;emit(E.place,:=1);E false E.place:=newtemp;emit(E.place,:=0);8.5.2 控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译n三种控制语句的语法为：三种控制语句的语法为：S if E then S1|if E then S1 else S2|While E do S1E的代码的代码 S1的代码的代码if E then S1的代码结构的代码结构truefalse控制语句的代码结构控制语句

33、的代码结构E.falseE的代码的代码E.true S1的代码的代码jump out S2的代码的代码out:if E then S1 else S2的代码结构的代码结构E的代码的代码 S1的代码的代码jump beginbeginWhile E do S1 代码结构代码结构n 把条件转移的布尔表达式把条件转移的布尔表达式 E 翻译成仅含：翻译成仅含：条件真条件真转和无条件转和无条件转的四元式。转的四元式。n E：a rop b if a rop b goto E.true goto E.false控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句中布尔表达

34、式的翻译n例：例：ab or cf 可翻译成如下四元式：可翻译成如下四元式：n if ab goto E.true n goto (3)n if cf goto E.true(1)goto E.false例：语句例：语句 if ab or cf then S1 else S2 的四元式序列为的四元式序列为 if ab goto (7)转移至转移至(E.true)goto (3)if cf goto (7)转移至转移至(E.true)(6)goto (p+1)转移至转移至(E.false)控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译(7)S1的四元式的四元式 (E.true)入口入口 (

35、p)goto (q)(E.false)入口入口(p+1)(S2的四元式的四元式)(q)控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译 四元式四元式(1)(5)(4)(6)中的转移地址，在整中的转移地址，在整个布尔表达式的四元式产生完毕之后回填。个布尔表达式的四元式产生完毕之后回填。采用采用“拉链拉链”方式，记录回填地址的四元式。方式，记录回填地址的四元式。真链真链：需回填：需回填E.true的四元式拉成的链的四元式拉成的链 假链假链：需回填：需回填E.false的四元式拉成的链的四元式拉成的链n若有四元式序列若有四元式序列(10)got

36、o E.true (20)goto E.true (30)goto E.true把地址把地址(30)称作称作“真真”链链首链链首，0为链尾标为链尾标志，即地址志，即地址(10)为为“真真”链链尾链链尾。控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译则链成则链成 goto (0)goto (10)(30)goto (20)控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译nnextstat 指向下一四元式的地址指向下一四元式的地址nemit 输出四元式输出四元式nmerge(p1,p2)把把p1和和p2为链首的两条链合为链首的两条链合并为一条。返回合并后的链首值。将并为一条。返回合并后的

37、链首值。将p2的链的链尾第四区段改为尾第四区段改为p1，合并后的链首为，合并后的链首为p2。nbackpatch(p,t)把链接的每个四元式的第把链接的每个四元式的第四区段都填为四区段都填为t。ncodebegin 与非终结符与非终结符E相连，表示表达式相连，表示表达式E的第一个四元式语句序号。的第一个四元式语句序号。自下而上分析中的一种翻译方案自下而上分析中的一种翻译方案(1)EE1 or E2 backpatch(E1.false,E2.Codebegin);E.Codebegin:=E1.codebegin E.true:=merge(E1.true,E2.true)E.false:=E

38、2.false(2)EE1 and E2 backpatch(E1.true,E2.codebegin);E.Codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false);(3)E not E E.true:=E1.false;E.Codebegin:=E1.codebegin;E.false:=E1.true自下而上分析中的一种翻译方案自下而上分析中的一种翻译方案(4)E(E1 1)E.true:=E1.codebegin E.Codebegin:=E1.codebegin;E.false:=E1.fals

39、e(5)Eid1 rop id2 E.true:=nextstat;E.Codebegin:=nextstat;E.false:=nextstat+1;emit(ifid1.place ropid2.place goto);emit(goto)自下而上分析中的一种翻译方案自下而上分析中的一种翻译方案(6)E true E.true:=nextstat;E.codebegin:=nextstat;emit(goto)(7)E false E.false:=nextstat;E.codebegin:=nextstat;emit(goto)布尔表达式的翻译布尔表达式的翻译n表达式表达式 ab or

40、cd and efn在归约在归约ab到到E时，产生时，产生2个四元式：个四元式：100：if ab goto 101：goto nextstat初值为初值为100E.codebegin为为100E.true的值为的值为100E.false的值为的值为101布尔表达式的翻译布尔表达式的翻译n由由cd归约到归约到E时产生：时产生：102：if cd goto 103：goto n由由ef归约到归约到E时产生：时产生：104：if ef goto 105：goto E.codebegin为为104E.true的值为的值为102E.false的值为的值为103布尔表达式的翻译布尔表达式的翻译n用用E

41、E1 and E2 归约，完成的语义动作是归约，完成的语义动作是backpatch(102,104102,104)和和 merge(103,105103,105)合并合并E1 和和 E2的假链的假链 102：if cd goto 104 105：goto 103布尔表达式的翻译布尔表达式的翻译n用用E E1 or E2 归约，完成的语义动作是归约，完成的语义动作是backpatch(101,102101,102)和和 merge(100,104100,104)合并合并E1 和和 E2的真链的真链 101：goto 102 104：if ef goto 100n真链首真链首E.true为为104

42、n假链首假链首E.false为为105布尔表达式的翻译布尔表达式的翻译n最后形成：最后形成：100：if ab goto 101：goto 102102：if cd goto 104103：goto 104：if ef goto 100105：goto 103n一旦真假出口确定，则可沿真假链回填。一旦真假出口确定，则可沿真假链回填。8.6 控制结构的翻译控制结构的翻译n控制结构的语句包括：控制结构的语句包括：n条件控制转移语句：条件控制转移语句：if-then、if-then-else、while-do等等n开关语句：开关语句：case、swith(C语言语言)n循环语句：循环语句：forn跳

43、转出口语句：跳转出口语句：C语言的语言的exit和和breakn无条件转移：无条件转移：goto8.6.1 条件转移条件转移n文法文法GS定义：定义：S if E then S|if E then S else S|while E do S|begin L end|A|LL：S|S其中：其中：S 语句语句L 语句串语句串A 赋值语句赋值语句E 布尔表达式布尔表达式条件转移语句的转移目标条件转移语句的转移目标n对于语句：对于语句：if E then S1 else S2n在扫描到在扫描到then时确定时确定E的的“真真”出口，扫描出口，扫描到到else时确定时确定E的的“假假”出口。出口。n在完

44、成在完成S1的翻译之后，的翻译之后，goto ，但在完成，但在完成S2的翻译之前，无法确定其转移地址。的翻译之前，无法确定其转移地址。n对非终结符对非终结符S和和L，给定语义值，给定语义值S.chain和和L.chain，需回填的四元式形成一条链，在，需回填的四元式形成一条链，在转移目标的四元式形成后回填。转移目标的四元式形成后回填。条件转移语句的翻译条件转移语句的翻译n语句语句 while(AB)do if(CD)then X:=Y+Z100 if AB goto 102101 goto 107102 if CD goto 104103 goto 100104 T:=Y+Z105 X:=T1

45、06 goto 1001078.6.2 开关语句开关语句n假定假定case语句或语句或switch语句形式为：语句形式为：switch E of case V1:S1 case V2:S2 case V n-1:S n-1 default:Sn endn 计算表达式计算表达式E，测试符，测试符合哪一个合哪一个case，相当于，相当于多个条件转移语句。多个条件转移语句。开关语句的翻译开关语句的翻译n扫描到扫描到switch时，产生标号时，产生标号test、next和和临时变量临时变量t。n计算计算E的结果代码值，存放到的结果代码值，存放到t中。中。n分析到分析到of时则产生四元式时则产生四元式g

46、oto test Li：S i的中间代码的中间代码 test：if t=Vi goto Li next：n Li为与为与case Vi对应对应的语句序列的语句序列Si的标号的标号开关语句的翻译开关语句的翻译n将将(if t=Vi goto Li)改写成改写成(case,Vi,Li,)的四元式形式：的四元式形式：(case,V1,L1,)(case,V2,L2,)(case,Vn-1,Ln-1,)(case,t,Ln,)(Lable,next,)8.6.3 for循环语句循环语句nfor i:=E 1 step E 2 until E 3 do S 1n对应的产生式如下：对应的产生式如下：F1

47、for i:=E1 F2 F1 step E2 F3 F2 until E3 S F3 do S1for循环语句循环语句nfor I:=1 step 1 until N do M:=M+In翻译成如下的四元式序列：翻译成如下的四元式序列：n I:=1n goto 103n I:=I+1n if I=n goto 105100 goto 108105 T:=M+I106 M:=T107 goto 102108 C语言的语言的for循环语句循环语句nfor(i=1;i=n;i+)s=s+i;n对应的产生式如下：对应的产生式如下：F1 E1 F2 F1;E2 F3 F2;E3 F4 for(F3)S

48、 F4 S1n四元式序列：四元式序列：100 i=1101 if i=n goto 103102 goto 107103 t=s+i104 s=t105 i=i+1106 goto 1011078.6.4 出口语句出口语句nexit语句和语句和break语句语句n无条件转移到结构的出口无条件转移到结构的出口终止本层循环、终止本层循环、switch语句等。语句等。n转移的目标在分析转移的目标在分析break或或exit语句所在的语句所在的循环后面的语句时确定。循环后面的语句时确定。n一遍扫描使用回填技术给出转移目标一遍扫描使用回填技术给出转移目标出口语句出口语句n对每个循环可使用对每个循环可使用

49、“循环描述符循环描述符”记录循环记录循环的有关信息：指向外层循环的指针、循环的的有关信息：指向外层循环的指针、循环的名字、在符号表中的位置、转移的目标等。名字、在符号表中的位置、转移的目标等。n多层循环是用堆栈方式进行处理的多层循环是用堆栈方式进行处理的n使用使用currentloop作为指向直接外层循环描作为指向直接外层循环描述符的指针。述符的指针。8.6.5 goto语句语句n通过标号和通过标号和goto语句实现语句实现n标号标号L在程序中定义在程序中定义n两种情况：两种情况：qgoto L向上转移向上转移标号已处理：登记地址标号已处理：登记地址q向下转移向下转移标号未处理：未定义标号未处

50、理：未定义符号表及未定义标号的引用链符号表及未定义标号的引用链符号表：符号表：name type def addL label not r 四元式：四元式：(p)goto 0(q)goto p(r)goto q建链的方法建链的方法n若若goto L中的标号中的标号L 尚未在符号表中出现，尚未在符号表中出现，则把则把 L 填入表中，置填入表中，置 L 的的“定义否定义否”标志为标志为“未未”，把，把nextstat填进填进L的地址栏中作为新的地址栏中作为新链首，然后，产生四元式链首，然后，产生四元式(goto 0)，其中，其中0为链尾标志。为链尾标志。n若若L已在符号表中出现已在符号表中出现(但