编译原理第三版 第七章 语义和中间代码产生

1、 n 任务任务: : 把语法单位翻译为中间代码把语法单位翻译为中间代码 n 内容内容: : 属性文法的属性文法的概念概念、语法制导翻译方法的语法制导翻译方法的 基本思想。基本思想。 典型的典型的中间代码中间代码: : 逆波兰式、三元式、四逆波兰式、三元式、四 元式、树等。元式、树等。 基本语法单位的基本语法单位的翻译翻译。包括：说明语句、。包括：说明语句、 表达式、赋值语句、控制语句、数组元表达式、赋值语句、控制语句、数组元 素素 引用、过程调用等的翻译。引用、过程调用等的翻译。 1、属性文法、属性文法 在上下文无关文法的基础上，在描述语义动作时，在上下文无关文法的基础上，在描述语义动作时，

2、为每个文法符号（终结符和非终结符）配备若干相为每个文法符号（终结符和非终结符）配备若干相 关的关的“值值”，如，如“类型类型”，“地址地址”等，等，称为属性称为属性。 对文法的对文法的每个产生式每个产生式配备一组属性计算规则称配备一组属性计算规则称 为为语义规则语义规则，它的描述形式为，它的描述形式为b:=f(c1,c2,ck),其中其中 b,c1,c2ck为文法符号的属性，为文法符号的属性，f是一个函数。是一个函数。 对每个产生式都给出其语义规则的对每个产生式都给出其语义规则的文法称为文法称为属性属性 文法。文法。 记号表示记号表示 n对于某个文法符号对于某个文法符号XVT VN，用用 X

3、. type（X的类型），的类型），X . cat（X的种的种 别），别），X .val（X的值或地址）等的值或地址）等表示它表示它 的属性。的属性。 n用下标（上角标）区分同一产生式中相用下标（上角标）区分同一产生式中相 同符号的多次出现。同符号的多次出现。 例：例：简单台式计算器的属性文法简单台式计算器的属性文法 产生式产生式 L En E E1+T E T T T1*F T F F (E) F digit 语义规则语义规则 Print(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val*F.val T.val:=F.val F.va

4、l:=E.val F.val:=digit.lexval n 属性文法属性文法可以看作是关于语言翻译的高级规可以看作是关于语言翻译的高级规 范说明，其中隐去了实现细节。范说明，其中隐去了实现细节。 n 翻译模式翻译模式是适合语法制导翻译的另一种语言是适合语法制导翻译的另一种语言 翻译的描述形式，它给出了使用语义规则进行翻译的描述形式，它给出了使用语义规则进行 计算的次序计算的次序，这样就把某些这样就把某些实现细节实现细节表示出来表示出来 了。在翻译模式中，和文法符号相关的属性和了。在翻译模式中，和文法符号相关的属性和 语义规则用语义规则用 括起来。也称括起来。也称语义动作，语义子语义动作，语义

5、子 程序程序 。 2、语法制导翻译方法、语法制导翻译方法 语法制导翻译的基本思想语法制导翻译的基本思想 n在在语法分析过程语法分析过程中，随着分析的步步进中，随着分析的步步进 展，在使用某个产生式进行推导或归约展，在使用某个产生式进行推导或归约 时便时便执行执行相应的相应的语义子程序语义子程序，完成既定，完成既定 的翻译工作，生成中间代码。的翻译工作，生成中间代码。 (1) (1) 扩大语法分析器的功能扩大语法分析器的功能, , 在使用某个产生式在使用某个产生式 进行归约进行归约( (或推导或推导) )时时, ,调用相应的子程序进行翻译调用相应的子程序进行翻译( ( 生成中间代码生成中间代码)

6、 (2) ) (2) 分析栈改为分析栈改为语义栈语义栈 。 Sm Xm.VAL Xm Sm-1 Xm-1.VAL Xm-1 . . . S0 / # . . . . . . STATE VAL SYM 语义栈语义栈 语法制导翻译方法的实现途径语法制导翻译方法的实现途径 1. 后缀式后缀式 后缀式表示法又称后缀式表示法又称逆波兰表示法逆波兰表示法，是一种表示表达式的是一种表示表达式的 方法，它把运算量（操作数）写在前面，算符写在后面方法，它把运算量（操作数）写在前面，算符写在后面 例：中缀表示例：中缀表示: a+b,a+b: a+b,a+b* *c,mc,m=1,(a+b)=1,(a+b)* *

7、c, (a+b)c, (a+b)* *(c-d) (c-d) 后缀表示后缀表示: ab+, abc: ab+, abc* *+, m1=,ab+c+, m1=,ab+c* *, ab+cd, ab+cd- -* * n 特点特点: : 运算分量的个数与先后次序不变；运算分量的个数与先后次序不变； 运算符的个数不变运算符的个数不变, , 但其出现顺序即为执行顺序但其出现顺序即为执行顺序 无括号；无括号； 一个表达式一个表达式E的后缀式可如下定义：的后缀式可如下定义： n(1)如果如果E是一个是一个变量或常数变量或常数，则，则E的后缀式是的后缀式是E 自身；自身； n(2)如果如果E是是E1opE

8、2形式的表达式，形式的表达式，op是二元操是二元操 作符，则作符，则E的的后缀式为后缀式为E1E2op, E1和和E2分分 别为别为E1和和E2的后缀式；的后缀式； n(3)如果如果E是是(E1)形式的表达式，则形式的表达式，则E1的后缀式的后缀式 就是就是E的后缀式的后缀式 二叉树遍历法即后序遍历二叉树二叉树遍历法即后序遍历二叉树 例如：例如：(a+b) / (c-d)） e / +- e a b c d 中序遍历中序遍历( 左左 中中 右右 ): (a+b) / (c-d) e 后序遍历后序遍历( 左左 右右 中中): ab+cd- / e 中缀到后缀的转换中缀到后缀的转换 后缀式的推广后

9、缀式的推广 例例 条件算术表达式条件算术表达式: if e then X else Y 三目运算三目运算 if - then - else : ￥ eXY ￥= X e0 即即e为为. T. Y e =0 即即e为为. F. 转移指令转移指令: 无条件转无条件转: p jump 小于转小于转: e1 e2 p jlt 为零转为零转: e p jez e p1 jez X p2 jump p1: Y P2: p1 p2 POST: e p1 jez X p2 jump Y . . . 例例 if (x+y)*z = 0 then (a+b)c else abc 后缀式后缀式: (1) xy+z*

10、0 = ab+c abc ￥ (2) xy+z*0 = p1 jez ab+c p2 jump p1: abc p2: 2、树、树: 也可以用也可以用树型结构树型结构表示表达式或语句。对表达式中表示表达式或语句。对表达式中 的的每个子表达式表式为一棵子树，每个子表达式表式为一棵子树，即简单变量或常即简单变量或常 数的树就是该变量或常数自身。如果表示数的树就是该变量或常数自身。如果表示e1和和e2的的 树为树为T1和和T2，那么，那么，e1+e2,e1*e2,-e1的树分别为：的树分别为： + * _(uminus) T1 T2 T1 T2 T1 e1 + e2 e1 * e2 - e1 + *

11、 * A B C D A*B+C*D的树的树 双目运算对应二叉子树，多目运算对应双目运算对应二叉子树，多目运算对应 多叉子树。多叉子树。 后缀式是树的后序遍历序列。后缀式是树的后序遍历序列。 3、三地址代码三地址代码 一般形式一般形式：x:=y op z 如：如： x:=y op z二元赋值二元赋值 x:= op y一元赋值一元赋值 x:=y复制赋值复制赋值 goto L无条件转移无条件转移 if x relop y goto L条件转移条件转移 if a goto L 条件转移条件转移 三地址代码在具体实现时常表示为记录结构，如四三地址代码在具体实现时常表示为记录结构，如四 元式、三元式、间

12、接三元式元式、三元式、间接三元式。 u 四元式四元式 一个四元式是一个带有四个域的记录结构一个四元式是一个带有四个域的记录结构 ( op, arg1, arg2, result ) op 运算符，运算符，arg1,arg2 运算数，运算数，result 运算结果运算结果 例例 a:= b*-c+b*-c 的四元式序列的四元式序列: : op arg1 arg2 result (1) ( c _ T1 ) (2) ( * b T1 T2 ) (3) ( c _ T3 ) (4) ( * b T3 T4 ) (5) (+ T2 T4 T5) (6) (:= T5 _ a) 四元式之间的联系通过四元

13、式之间的联系通过临时变量临时变量实现。实现。 单目运算只用单目运算只用arg1域，转移语句将目标标号放入域，转移语句将目标标号放入 result域。域。 arg1,arg2,result通常为通常为指针指针，指向有关名字的符号，指向有关名字的符号 表入口，且临时变量填入符号表。表入口，且临时变量填入符号表。 u 三元式三元式 一个三元式有三个域一个三元式有三个域 ( op, arg1, arg2 ),其中：其中：arg1,arg2 为指向符号表的指针（对程序中的名字或常量）或者是指为指向符号表的指针（对程序中的名字或常量）或者是指 向三元式表的指针（取代临时变量）。向三元式表的指针（取代临时变

14、量）。 例：例：a:= b*-c+b*-c 的三元式序列的三元式序列： op arg1 arg2 (1) ( c _ ) (2) ( * b (1) ) (3) ( c _ ) (4) (* b (3) ) (5) (+ (2) (4) ) (6) (:= a (5) ) u 间接三元式间接三元式 不直接使用三元式表，另设一张不直接使用三元式表，另设一张间接码表间接码表，按运算的先后次，按运算的先后次 序列出有关三元式在三元式表中的位置，序列出有关三元式在三元式表中的位置，相同的三元式无需相同的三元式无需 重填重填三元式表。三元式表。 例：例： a:= b*-c+b*-c 的间接三的间接三 元

15、式为元式为： 间接码表间接码表 op arg1 arg2 （1） (1) ( c _ ) （2） (2) ( * b (1) ) （1） (3) (+ (1) (2) ) （2) (4) (:= a (3) ) (3) (4) 三元式中使用了指向三元式的指针，优化三元式中使用了指向三元式的指针，优化 时修改较难。时修改较难。 间接三元式优化只需要更改间接码表，并间接三元式优化只需要更改间接码表，并 节省三元式表存储空间。节省三元式表存储空间。 修改四元式表也较容易，只是临时变量要修改四元式表也较容易，只是临时变量要 填入符号表，占据一定存储空间。填入符号表，占据一定存储空间。 四元式、三元式和

16、间接三元式比较四元式、三元式和间接三元式比较 n说明语句作用说明语句作用: 用关键字定义名字的性质用关键字定义名字的性质 （数据类型）（数据类型） n 简单类型说明简单类型说明 n 数组、记录说明数组、记录说明 n 语义动作语义动作: 填符号表、信息向量表、除填符号表、信息向量表、除 动态数组外不生成四元式。动态数组外不生成四元式。 (1) 文法文法 integer i1 , i2, . . . , in Dinteger namelist real namelist namelistnamelist, i i 问题问题: : 必须把所有名字都归约为必须把所有名字都归约为namelist后才能

17、把各个名字的后才能把各个名字的 类型填入符号表类型填入符号表, ,需要使用队列或栈保存这些名字需要使用队列或栈保存这些名字 (2) 改写文法改写文法integer i1 , i2 , . . . , in Dinteger i real i D, i D 1. 简单类型说明简单类型说明 namelist namelist namelist . . . D D D D (3) 语义变量与语义过程语义变量与语义过程 D.att: 记录说明语句记录说明语句D规定的类型；规定的类型； fill (p, a):填表过程填表过程, 把属性把属性a填入符号表入口填入符号表入口p的有关栏中；的有关栏中； en

18、try(i): 回送标识符回送标识符i在符号表中的入口（在符号表中的入口（lookup(); ( (4) 翻译模式翻译模式 (1) Dinteger i (2) Dreal i (3) DD1, i p:=entry(i); fill (p , int ); D.att := int p:=entry(i); fill (p , real ); D.att := real p:=entry(i); fill (p ,D1.att); D.att :=D1.att 例：例： integer i1 , i2 , i3 2. 数组说明数组说明 (1) 文法文法 Darray i l1 :

19、u1 , l2: u2 , . . . , ln:un (2) 信息向量表信息向量表 l 1 u1 d1 . . . ln un dn n C type a A array . . . 符号表符号表 信息向量表信息向量表 说明说明: : 对于固定数组对于固定数组, , 将有关说明信息依次填入符号表信息向将有关说明信息依次填入符号表信息向 量表；对于可变数组，需要形成中间代码量表；对于可变数组，需要形成中间代码 。 (3) 可变数组的处理可变数组的处理 编译时编译时: 分配信息向量表区。分配信息向量表区。 产生运行时建立信息向量表和分配数组空间的四元式。产生运行时建立信息向量表和分配数组空间的四

20、元式。 运行时运行时: 填写信息向量表。填写信息向量表。 分配数组存贮空间。分配数组存贮空间。 子程序子程序: 功能功能: 建立信息向量表和分配数组空间建立信息向量表和分配数组空间 参数参数: n, type, li, ui, 信息向量表首址信息向量表首址 BEGIN i := 1; N := 1; C :=0; /* i为维数为维数,N为体积为体积, C为为a - C中的中的C*/ WHILE i n DO BEGIN di := ui - li + 1; N := N * di ; C := C * di + li ; 把把 li, ui , di 填入信息向量表填入信息向量表; i :=

21、 i + 1 END; 申请申请N个单元的数组空间个单元的数组空间,令其首址为令其首址为a; 把把n, C, type, a 填入信息向量表填入信息向量表 END 3. 记录说明的翻译记录说明的翻译 (1) ftype i (2) ftype I n (3) f1f (4) f1f1(1); f (5) typerecord (6) typechar (7) typenteger (8) typepointer f. NAME := i .NAME; f.LEN:=type.LEN; FILN ( i . NAME, f. LEN) f. NAME := i .NAME; f . LEN :=

22、 type. LEN * n .VAL; FILN ( i . NAME, f . LEN) FILO ( f . NAME, 0 ); f1 . LEN := f . LEN FILO ( f . NAME, f1(1). LEN ); f1 . LEN := f1(1). LEN+ f . LEN type . LEN := f1.LEN type . LEN := 1 type . LEN := 4 type . LEN := 4 # 7.4 7.4 简单算术表达式和赋值语句的翻译简单算术表达式和赋值语句的翻译 只含整型变量的简单算术表达式，并符合运只含整型变量的简单算术表达式，并符合运

23、 算符的结合规则和优先级规定。算符的结合规则和优先级规定。 1. . 文法描述文法描述 (1) Si := E (2) EE1 + E2 (3) EE1 * E2 (4) E - E1 (5) E(E1 ) (6) Ei 2. . 语义变量和语义过程语义变量和语义过程 E. place : 存放存放E值的变量名在符号表的入口值的变量名在符号表的入口 或临时变量的编号或临时变量的编号 ； :表示表示i所代表的名字本身，或直接用所代表的名字本身，或直接用i表示；表示； newtemp: 函数过程函数过程, 生成一个新的临时单元生成一个新的临时单元, 返回其编号；返回其编号； entry

24、 (i) : 函数过程函数过程, 返回返回i 在符号表的入口（或在符号表的入口（或 lookup() ； gen ( op, arg1, arg2, result ) :语义过程，语义过程， 生成一个四元式并将它送到四元式表中；生成一个四元式并将它送到四元式表中； 或或emit(x,”:=“, y, op, z):语义过程，把三地址语句语义过程，把三地址语句 x:=y op z发送到输出文件。发送到输出文件。 (1) Si := E gen(:=, E.place, _ , entry(i) (2) EE1 + E2 T:= newtemp; gen( +, E1. place,

25、E2. place, T); E. place:=T (3) EE1 * E2 T:= newtemp; gen(* , E1. place, E2. place, T);E. place:=T (4) E - E1 T:= newtemp; gen( , E1. place, _ , T);E. place:=T (5) E(E1 ) E.place:= E1. place (6) Ei E. place:= entry (i) 3. 语义子程序语义子程序 产生式产生式语义动作语义动作 例例: : a:= - b*(c+d) 的语法制导翻译过程的语法制导翻译过程 栈栈输入串输入串i.plac

26、e 四元式四元式 #a:= -b*(c+d)# #i := -b*(c+d)# a #i:= -b*(c+d)# a_ #i:=- b*(c+d)# a_ _ #i:=- i *(c+d)# a_ _ b #i:= - E *(c+d)# a_ _ b #i:= E *(c+d)# a_ T1 #i:= E* (c+d)# a_ T1_ #i:= E*( c+d)# a_ T1_ _ #i:= E*(i +d)# a_ T1_ _ c #i:= E*(E +d)# a_ T1_ _ c #i:= E*(E+ d)# a_ T1_ _ c _ #i:= E*(E+i )# a_ T1_ _ c

27、_ d #i:= E*(E+E )# a_ T1_ _ c _ d #i:= E*(E )# a_ T1_ _ T2 #i:= E*(E ) # a_ T1_ _ T2_ #i:= E*E # a_ T1_ T2 #i:= E # a_ T3 #S # (, b, _ ,T1) (+, c , d, T2) (*, T1, T2 ,T3) (:=, T3 ,_ , a ) 4. 类型转换类型转换 若若i i 的类型不同的类型不同, ,则拒绝或做类型转换则拒绝或做类型转换 运算符运算符: 实型实型 +r , r , r 整型整型 +i , i , i 语义变量语义变量E. type = 转换指令

28、转换指令( itr,A1, _ , T ) int real EE1 op E2 的语义子程序的语义子程序( ( 带有语义转换功能带有语义转换功能 ) ) T:= NEWTEMP； IF E1.type=int AND E2.type=int THEN BEGIN GEN(opi , E1.PLACE, E2.PLACE, T ); E. type:= int END ELSE IF E1.type=real AND E2.type=real THEN BEGIN GEN(opr , E1.PLACE, E2.PLACE, T ); E. type:= real END ELSE IF E1.

29、type=int /*and E2.type=real*/ THEN BEGIN U:= NEWTEMP GEN(itr , E1. PLACE, _ , U ); GEN(opr , U , E2. PLACE, T ); E. type:= real END ELSE /* E1.type=real and E2.type=int*/ THEN BEGIN U:= NEWTEMP; GEN(itr , E2. PLACE, _ , U ); GEN(opr, E1. PLACE, U, T ); E. type:= real END ； E. PLACE:= T 7. 5 7. 5 布尔表

30、达式的翻译布尔表达式的翻译 1. 布尔表达式的定义布尔表达式的定义 (1)构成构成:用用布尔运算符布尔运算符把把布尔量布尔量、关系表达式关系表达式联结起联结起 来的式子。来的式子。 布尔运算符：布尔运算符：and, or, not ；关系运算符关系运算符 , ， , (2) 作用作用: 控制语句的条件控制语句的条件 计算逻辑值计算逻辑值 (3) 文法文法: EE and EE or Enot E(E)i i1 relop i2 运算符优先级运算符优先级:布尔运算由高到低布尔运算由高到低:not and or ,同级左结合同级左结合. 关系运算符同级关系运算符同级,且高于布尔运算符且高于布尔运算

31、符 (4) 计值计值: 按优先级按优先级 (与算术表达式相同与算术表达式相同) 2. 数值表示法的布尔式翻译数值表示法的布尔式翻译： 与算术表达式翻译相同与算术表达式翻译相同 将将 and or not 看作运算符看作运算符 关系表达式翻译为含转移语句的序列关系表达式翻译为含转移语句的序列: 即：即：ab表示表示if ab then 1 else 0 例例：关系表达式关系表达式ab 翻译为翻译为 四元式四元式: 100（j,a, b, 103) 101 (:= , 0, _ ,T) 102 (j , _ ,_ , 104) 103 (:=, 1,_ , T) 104 例例:布尔表达式布尔表达式

32、a or b and not c 翻译为四元式翻译为四元式: (not , c, _ , T1) (and , b , T1 , T2) (or , a , T2, T3) 产生以上结果的语义子程序为产生以上结果的语义子程序为： E E1 or E2 T:=newtemp; gen( or E1.place, E2.place,T); E.place:=T E E1 and E2 T:=newtemp; gen( and E1.place, E2.place, T);E.place:=T E not E1 T:=newtemp; gen( not E1.place, _, T);E.place

33、:=T E ( E1) E.place:= E1.place E id1 relop id2 T:=newtemp; gen(jrelop, id1.place, id2.place,nextstart+3); gen (:=, 0, _ , T); gen (j, _, _,nextstart+2); gen (:=, 1, _ , T); E.place:=T; E id E.place:=id.place nextstart为四元式序为四元式序 列中下一条四元式地列中下一条四元式地 址索引，每产生一条址索引，每产生一条 四元式，过程四元式，过程gen将将 nextstart加加1 例例：

34、布尔表达式布尔表达式ab or cd and ef 的四元的四元 式序列：式序列： 100（j,a,b,103) 101 ( :=,0,_, T1) 102 (j, _, _, 104) 103 (:=, 1, _, T1) 104（j,c,d,107) 105 ( :=,0,_, T2) 106 (j, _, _, 108) 107 (:=, 1, _, T2) 108（j,e,f,111) 109 ( :=,0,_, T3) 110 (j, _, _, 112) 111 (:=, 1, _, T3) 112 (and, T2,T3,T4) 113(or , T1, T4, T5) # 3.

35、 作为条件控制的布尔表达式的翻译作为条件控制的布尔表达式的翻译 (1) 考察考察条件语句条件语句: : if E then S1 else S2 E E的作用的作用: : 控制对控制对S1和和S2 的选择的选择, 其值无需保留。其值无需保留。 (2) 代码结构代码结构: : E的代码的代码 S1的代码的代码 S2的代码的代码 (3) E的四元式形式的四元式形式: 全部为条件或无条件转移指令全部为条件或无条件转移指令 ( jnz, A1, _ , p )A1为真转为真转p ( j , A1, A2, p ) A1A2为真转为真转p （为关系运算符）为关系运算符） ( j, _ , _ , p )

36、 无条件转无条件转p 真出口真出口 假出口假出口 (4) (4) E的真、假出口的确定的真、假出口的确定 E 形如形如ab时，时， 生成四元式生成四元式 (j, a, b,E.true) (j,_, _, E.false) E形如形如E1or E2 E1 为真为真: E1 的真出口即为的真出口即为E的真出口，不必求的真出口，不必求E2； E1 为假为假: E2 需要计值需要计值, 其第一个四元式为其第一个四元式为E1 的假出口；的假出口； E2 的真假出口为的真假出口为E的真假出口。的真假出口。 E形如形如E1and E2 E1 为假为假: E1 的假出口即为的假出口即为E的假出口的假出口,不

37、必求不必求E2； E1 为真为真: E2 需要计值需要计值, 其第一个四元式为其第一个四元式为E1 的真出口；的真出口； E2 的真假出口为的真假出口为E的真假出口。的真假出口。 E形如形如not E1 E1 的真出口为的真出口为E的假出口；的假出口； E1 的假出口为的假出口为E的真出口。的真出口。 (5) 回填技术回填技术 问题问题: 在自下而上语法分析中在自下而上语法分析中, 真假出口往往不能在真假出口往往不能在 生成四元式的同时填上。生成四元式的同时填上。 解决：解决：一种一种解决方法解决方法是两遍扫描；另一种是两遍扫描；另一种解决方法解决方法是是 采用一遍扫描，这时需要把相应四元式的

38、地址保存采用一遍扫描，这时需要把相应四元式的地址保存, 到到 适当的时机再填入。这就是适当的时机再填入。这就是回填回填技术。技术。 实现：实现：建立一个建立一个链表链表，把跳转到相同目标的四元式，把跳转到相同目标的四元式 标号链在同一个表中，当目标确定后，再将它回填到标号链在同一个表中，当目标确定后，再将它回填到 有关的指令中。有关的指令中。 可以有可以有两种方式组织链表两种方式组织链表：利用需要回填的跳转四：利用需要回填的跳转四 元式的第四个域元式的第四个域(result)构造链表；或者建立单独链表构造链表；或者建立单独链表 记录需要回填的跳转四元式的标号。记录需要回填的跳转四元式的标号。

39、链表的组织方式链表的组织方式 设链表的头指针为设链表的头指针为E.truelist（需回填（需回填E的真值的的真值的 的链），的链），E.falselist（需要回填（需要回填E的假值的链）的假值的链） E.truelist(r) (x, x, x, q) (q) (x, x, x, p) (p) (x, x, x, 0) E.truelist r q p null (5)语义变量和过程、函数语义变量和过程、函数 nextquad: 变量，下一个将形成的四元式地址，变量，下一个将形成的四元式地址， 初值为初值为1, 每执行一次每执行一次GEN 自动加自动加1. makelist(i): 函数，

40、创建一个仅含函数，创建一个仅含i的新链表，的新链表，i为四元式地为四元式地 址（标号）址（标号）. merge(p1, p2 ): 函数过程函数过程, 把以把以p1,p2 为为 链首的两个链合并回送合并后的链首链首的两个链合并回送合并后的链首. backpatch ( p, t ) : 过程过程,把链首把链首p 所指所指 链中的四元式第链中的四元式第4域回填为域回填为 t。 merge ( p1, p2 ); if p2 = 0 then merge= p1 else p := p2; while p.result0 do p=p.result; p.result=p1; merge= P2;

41、 0 0 p2 p1 p1 (6) 语义子程序语义子程序 对文法产生式稍作修改，引入对文法产生式稍作修改，引入标记非终结符标记非终结符M，以便在适当的时候，以便在适当的时候 执行一个语义动作，记下下一个要产生四元式标号。执行一个语义动作，记下下一个要产生四元式标号。 (1)E i E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); gen(jnz, i.place,_,0); gen(j, _, _, 0) (2) E i1 relop i 2 E.truelist:=makelist(nextquad); E.

42、falselist:=makelist(nextquad+1); gen(jnz, i.place,_,0); gen(j, _, _, 0) (3) E(E1) E.truelist:=E1.truelist; E.falselist:=E1.falselist (4) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist (5) E E1 and ME2 backpatch(E1.truelist,M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist

43、,E2.falselist) (6) EE1 or ME2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist,E2.truelist); E.falselist:=E2.falselist) (7) M M.quad:=nextquad 例：例：将布尔式将布尔式ab or cd and ef 翻译为四元式翻译为四元式 E E1orM1E4 i1i2E2 and M E3 i1i1i1 i1 100 (j, a, b, 0) 101 (j, _, _,0 ) 102 (j, c , d, 0) 103 (j, _, _,

44、0) 104 (j, e, f, 0) 105 (j,_ ,_ ,0) 链表链表： E1.truelist=100,E1.falselist=101 Nextquad=102 M1.quad=102 E2.truelist=102,E2.falselist=103 nextquad=104 M.quad=104 E3.truelist=104,E3.falselist=105 nextquad=106 E4.truelist=104 E4.falselist=103,105 E.truelist=100,104 E.falselist=103,105 104 102 四元式：四元式： # 7.

45、6 控制语句的翻译控制语句的翻译 1.控制流语句控制流语句 考察考察if - then , if - then - else ,while do 语句的翻译语句的翻译, 三种语句的形式三种语句的形式为为:if E then S1, if E then S1 else S2, While E do S1, 其中其中E为布尔表达式为布尔表达式. (1)三种语句的代码结构三种语句的代码结构 If-then 语句代码结构语句代码结构 E.code S1.code E.true E.false If-then语句的代码就是语句的代码就是E的代码的代码 后跟后跟S1的代码。的代码。 If-then语句只是

46、语句只是控制了控制了这些代这些代 码中的码中的转移目标转移目标。即。即E为为”真真” 时时,执行执行S1第一条语句第一条语句,E的真出的真出 口口E.true为为S1的第一条指令的第一条指令,E中中 某些四元式得到回填某些四元式得到回填;E为为”假假 ”时时,执行执行IF语句后的第一条指语句后的第一条指 令令,设用设用S.next表示表示,该值待定。该值待定。 S.next: while-do 语句的代码结构语句的代码结构If-then-else语句代码结构语句代码结构 E.code S1.code goto S.next S2.code E.true E.false E.code S1.co

47、de goto S.begin E.true E.false 由分析可知由分析可知,if-then-else语句多增加了一条跳转语句多增加了一条跳转 指令指令goto S.next. while-do语句增加了一条语句增加了一条goto S.begin指令指令. 两条语句所做的其他工作也是回填布尔式两条语句所做的其他工作也是回填布尔式E或其或其 它语句中指令地址它语句中指令地址. 对于语句也需要一个未填写目标标号而以后需对于语句也需要一个未填写目标标号而以后需 要回填的转移指令链要回填的转移指令链,用用S.nextlist指示指示. S.next: S.begin: S.next: (2)(2

48、)文法描述文法描述 Sif E then S if E then S else S while E do S begin L end A LL;S S 其中其中, S:语句语句 L:语句串语句串 A:赋值语句赋值语句 E:布尔表达式布尔表达式 (3)语义子程序语义子程序( (翻译模式翻译模式) ) 使用有关链表操作的使用有关链表操作的语义变量、函数和过程语义变量、函数和过程（ nextquad, makelist（）（）, merge( ), backpatch( ) ), E.truelist,E.falselist,S.nextlist,L.nextlist指向需回填的指向需回填的指令链表

49、指令链表。 对文法稍做修改：对文法稍做修改：1 1）引入标记非终结符）引入标记非终结符M M，以记录某些位，以记录某些位 置的四元式标号；置的四元式标号；2 2）引入标记非终结符）引入标记非终结符N N，以生成一条跳转，以生成一条跳转 指令和一个链。指令和一个链。 改写后的文法及语义动作改写后的文法及语义动作 1) Sif E then M S1 backpatch(E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1.nextlist) 2) Sif E then M1 S1 N else M2 S2 backpatch(E.truelis

50、t,M1.quad); backpatch(E.falselist,M2.quad); S.nextlist:=merge(S1.nextlist,N.nextlist,S2.next) 3) N N.nextlist:=makelist(nextquad); gen( j,_ ,_ ,0) 4) M M.quad:= nextquad 5) Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad); backpatch (E.truelist, M2.quad); S.nextlist:=E.falselist; gen( j, _ ,_ ,M

51、1.quad) 6)S begin L end S.nextlist:=L.nextlist 7) S A S.nextlist:=makelist() 8) L L1;MS backpatch(L1.nextlist, M.quad); L.nextlist:= S.nextlist 9) L S L.nextlist:=S.nextlist 例例: :while a b do if c d then x:= y+z 翻译为四元式翻译为四元式 100 ( j, a, b, 0 ) 101 ( j , _ , _ , 0 ) 102 ( j, c, d, 0 ) 103 ( j , _ , _

52、 , 0 ) 104 ( +, y, z, T1 ) 105 ( := , T1, _ , x ) 106 ( j, _ , _ , 100 ) S1 whileM1E1 doM2S2 i1 i2ifE2 then M3 S3 A i:= E i+ i i1 10 时时 Sn-1 的的 代代 码码 Sn 的的 代代 码码 计算计算T：=E的代码的代码 S1 的的 代代 码码 S2 的的 代代 码码 判断判断T 的的 代代 码码 T=C1 L1: T=C2 L2: T=Cn-1 Ln-1: T=其它其它 Ln: TEST: NEXT: (4) 代码生成过程代码生成过程: 遇到遇到case 遇到遇

53、到E of 遇到遇到Ci 遇到遇到Si 遇到遇到end 利用队列利用队列QUEUE 4. for语句语句 (1) 文法文法: : Sfor i := E(1) step E(2) until E(3) do S(1) (2) 代码结构代码结构: : 增量部分增量部分: i:= i + E(2) 测试部分测试部分: i = E(3) 循环体循环体: S(1) 初值部分初值部分: i := E(1) 例例 for i := 1 step 1 until N do M:=M+1 AGAIN: OVER: 假出口假出口 真出口真出口 100 (:= , 1 , _ , I ) 101 ( j, _ , _ , 0 103 ) 102 ( +, I, 1 , I ) 103 ( j, I , N , 0 105 ) 104 ( j , _ , _ , 0 108) 105 (+, M , 1 , T ) 106 (:= , T , _ , M ) 107 ( j , _ , _ , 102) AGAIN: OVER: