编译原理第四章语法制导翻译生成中间代码

《编译原理第四章语法制导翻译生成中间代码》由会员分享，可在线阅读，更多相关《编译原理第四章语法制导翻译生成中间代码（66页珍藏版）》请在装配图网上搜索。

1、1 上 次 课 程 内 容 回 顾换 名 调 用嵌 套 定 义 的 过 程 中 信 息 的 存 储1. 作 用 域 信 息 的 保 存 过 程 的 作 用 域 (过 程 与 程 序 块 的 区 别 ) 过 程 嵌 套 的 层 次 符 号 表 的 组 织 与 符 号 表 中 的 作 用 域 信 息2. 语 法 制 导 翻 译 生 成 符 号 表 用 栈 保 留 各 符 号 表 节 点 信 息 进 入 过 程 声 明 D之 前 构 造 符 号 表 ， 分 析 D时 填 写 符号 表 ， 退 出 D后 在 外 层 符 号 表 中 加 入 此 过 程 条 目 2 4.5 简 单 算 术 表 达 式 与

2、 赋 值 句 简 单 算 术 表 达 式 和 赋 值 句 ， 是 指 表 达 式 和 赋 值 句 中 变 量是 不 可 再 分 的 简 单 变 量 。 讨 论 所 基 于 的 文 法 ：A id:=EE E + E | E * E | - E | ( E ) | id 3 4.5.1 简 单 算 术 表 达 式 的 语 法 制 导 翻 译 属 性 .place： 存 放 E的 变 量 地 址 (符 号 表 中 地 址 或 临 时 变 量 的 编 码 )；过 程 emit(result := arg1 op arg2)： 生 成 “ result:= arg1 op arg2” 的 三 地 址

3、码 。(1) A id:=E(2) E E1+E2 (3) E E1*E2(4) E -E1 (5) E (E1) (6) E id E.place:=entry(id.name) E.place:=newtemp； emit(E.place := E1.place + E2.place) E.place:=newtemp； emit(E.place := E1.place * E2.place) E.place:=newtemp； emit(E.place := - E1.place) E.place:= E1.place emit(entry(id.name) := E.place) 4

4、4.5.2 变 量 的 （ 内 部 ） 类 型 转 换 强 制 （ coercion） ： 按 照 一 定 的 原 则 ， 将 不 同 类 型 的 变 量 在内 部 转 换 为 相 同 的 类 型 ， 然 后 进 行 同 类 型 变 量 的 计 算 。 运 算 的 转 换 原 则 ： 赋 值 的 转 换 原 则 ： 属 性 .mode： 取 值 int或 real表 达 式 的 类 型 判 定 树 ： 5 4.5.2 变 量 的 （ 内 部 ） 类 型 转 换 （ 续 1）三 地 址 码 ： T := itr E： 将 E从 整 型 变 为 实 型 ， 结 果 存 放 T中T := rti E

5、： 将 E从 实 型 变 为 整 型 ， 结 果 存 放 T中语 义 规 则 ： A id := E tmode:=entry(id.name).mode; if tmode=E.mode then emit(entry(id.name) := E.place); else T := newtemp; emit(entry(id.name) := T); end if; if tmode=int then emit(T := rti E.place); else emit(T := itr E.place);end if;结 果 6 4.5.2 变 量 的 （ 内 部 ） 类 型 转 换 （

6、续 2）E E1 op E2 T:=newtemp； E.mode:=real; if E1.mode=int then else end if; E.place:=T; 其 他 语 义 规 则 看 教 材 P128 129if E2.mode=intthen emit(T := E1.place OPi E2.place); E.mode := int;else U:=newtemp; emit(U := itr E1.place); emit(T := U OPr E2.place);end if;if E2.mode=intthen U:=newtemp; emit(U := itr E

7、2.place); emit(T := E1.place OPr U);else emit(T := E1.place OPr E2.place);end if; 前 页 7 4.5.2 变 量 的 （ 内 部 ） 类 型 转 换 （ 续 3）例 4.17 x:=-a*b+c的 语 法 制 导 翻 译 ， x、 a、 b是 整 型 ， c是 实 型 。序 号 产 生 式 中 间 代 码 (1) E1 a(2) E2 -E1 t1:=-a(3) E3 b(4) E4 E2*E3 t2:=t1*ib(5) E5 c(6) E6 E4*E5 t4:=itr t2 t3:=t4+ rc(7) A x:

8、=E6 t5:=rti t3 x := t5 8 4.6 数 组 元 素 的 引 用 确 定 数 组 空 间 的 存 储 分 配 ： 以 第 一 个 元 素 地 址 为 首 地 址 ， 分 配 一 个 连 续 空 间 。多 维 到 一 维 存 储 空 间 的 映 射 方 法 ： 以 行 为 主 ， 以 列 为 主考 虑 三 行 、 三 列 的 二 维 数 组 a0.2, 2.4 ： a0,2 a0,3 a0,4a1,2 a1,3 a1,4a2,2 a2,3 a2,4 以 行 为 主 存 放 时 的 元 素 排 列 ： a0,2 a0,3 a0,4 a1,2 a1,3 a1,4 a2,2 a2,

9、3 a2,4以 列 为 主 存 放 时 的 元 素 排 列 ： a0,2 a1,2 a2,2 a0,3 a1,3 a2,3 a0,4 a1,4 a2,4确 定 数 组 元 素 地 址 的 两 个 要 素 ： 首 地 址 和 相 对 首 地 址 的 偏 移 量 不 同 的 映 射 方 式 ， 使 得 同 一 个 数 组 元 素 相 对 首 地 址 的 偏 移 量 不 同 例 如 ： a1,4， 偏 移 量 分 别 是 5和 7 9 确 定 映 射 方 式 的 两 种 方 法 1 由 声 明 时 的 语 法 确 定 映 射 方 式 ：a:arrayd1 of arrayd2of.arraydn o

10、f integer; 引 用 方 式 ： ai1,i2, .,in或 ai1i2.in2 由 编 译 器 确 定 映 射 方 式 ：a : array d1, d2, ., dn of integer;引 用 方 式 ： ai1,i2, .,in 数 组 元 素 引 用 时 地 址 的 确 定 ：1 根 据 映 射 方 式 求 出 计 算 公 式 ；2 根 据 计 算 公 式 设 计 语 义 规 则 。 10 4.6.1 数 组 元 素 的 地 址 计 算 三 个 假 设 条 件 ：1. 数 组 元 素 以 行 为 主 存 放 ， 推 广 到 n维 ， 就 是 数 组 的 第 i维是 di个

11、n-i维 的 数 组 (每 个 成 员 是 一 个 n-i维 的 数 组 ) ， 其中 di是 第 i维 成 员 的 个 数 ；2. 数 组 每 维 的 下 界 均 为 1； 3. 每 个 元 素 仅 占 一 个 标 准 存 贮 单 元 （ 可 以 认 为 是 一 个 字 或者 一 个 字 节 ） 。 约 定 ： 数 组 的 声 明 ： Ad 1, d2, ., dn 数 组 元 素 的 引 用 ： Ai1, i2, ., in 11 一 维 数 组 元 素 的 地 址 计 算 ：addr(Ai) = a + (i-1)*w二 维 数 组 元 素 的 地 址 计 算 ：addr(Ai1,i2)

12、=a+(i1-1)*d2+(i2-1)*w跳 过 前 i-1个 单 元跳 过 前 i1-1行跳 过 前 i 2-1个 单 元 12 n维 数 组 元 素 的 地 址 计 算addr(Ai1， i2， .， in)=a+(i1-1)*d2*d3*.*dn+(i2-1)*d3*d4*.*dn+.+ (in-1)*w=a-(d2*d3*.*dn+d3*d4*.*dn+.+dn+1)*w +(i1*d2*d3*.*dn+i2*d3*d4*.*dn+.+in-1*dn+in)*w=a c*w+v*w根 据 假 设 条 件 w=1: addr(Ai1， i2， .， in)=a c+v 其 中 ：c =

13、d2*d3*d4.*dn+d3*d4*d5.*dn+*d4*d5*d6.*dn.+dn+1 = (d 2+1)*d3*.*dn+d4*d5.*dn+.+dn+1 =(d2+1)*d3+1)*d4*d5.*dn+.+dn+1 . = (.(d2+1)*d3+1)*d4.+1)*dn+1同 理 ：v = (.(i1*d2+i2)*d3+i3)*d4.+in-1)*dn+in 13 n维 数 组 元 素 的 地 址 计 算 （ 续 1）c=(.(d2+1)*d3+1)*d4.+1)*dn+1v=(.(i1*d2+i2)*d3+i3)*d4.+in-1)*dn+in 令 ： v1 = i1则 ： v2

14、 = i1*d2+i2 = v1*d2+i2 v3 = (v1*d2+i2)*d3+i3 = v2*d3+i3.于 是 有 ： v1 = i1 vj = vj-1*dj+ij (j=2， 3， ., n) (4.4)同 理 可 得 ： c 1 = 1 cj = cj-1*dj+1 (j=2， 3， ., n) (4.3) 最 终 得 到 数 组 元 素 引 用 的 地 址 计 算 公 式 ：addr(Ai1， i2， .， in)=a-c+v=CONSPART+VARPART 注 意 ： 如 果 w 1,则 c和 v分 别 需 要 乘 一 个 w， 即 ：addr(Ai1， i2， .， in

15、)=a-cw+vw=CONSPART+VARPART 14 4.6.2 数 组 元 素 引 用 的 语 法 制 导 翻 译 数 组 元 素 的 寻 址 ： CONSPARTVARPART， 或 者 T1T取 值 的 三 地 址 码 ： X:=T1T 赋 值 的 三 地 址 码 ： T1T:=X 引 入 数 组 元 素 后 的 赋 值 句 文 法 A V := E V id | idEL (G4.4) EL E | EL ， E E E + E | ( E ) | V引 入 了 新 的 非 终 结 符 V， 使 得 分 析 树 增 高 。例 如 ai, j:=x的 分 析 树 ： 根 据 此 文

16、 法 进 行 语 法 制 导 翻 译有 困 难 ， 无 法 使 用 递 推 公 式 （ 因 为 d j需 要 知 道 数 组 名 a） 。 15 4.6.2 （ 续 ）修 改 文 法 以 适 应 递 推 公 式 的 同 步 计 算 ：A V := E (1)V id (2) | EL (3)EL id E (4) | EL , E (5)E E + E (6) | ( E ) (7) | V (8) - 得 到 数 组 名 和 第 一 维 下 标 和 v1- 递 归 计 算 第 i维 的 vi- 完 成 数 组 元 素 的 分 析 和 对 v的 计 算根 据 修 改 后 的 文 法 ，ai,

17、j:=x的 分 析 树 变 为 ： 16 属 性 和 函 数1. 属 性 .array： 数 组 名 在 符 号 表 中 的 入 口 和 数 组 首 地 址 a。2. 属 性 .dim： 数 组 维 数 计 数 器 ， 记 录 当 前 分 析 到 的 维 数 。3. 属 性 .place： 下 标 列 表 EL： 存 放 vj=vj-1*dj+ij (j=2， 3， ., n)的临 时 变 量 ， 简 单 变 量 id： 仍 然 表 示 简 单 变 量 的 地 址 ， 数 组 元 素 idEL： 存 放 不 变 部 分 ， 一 般 可 以 是 一 个 临时 变 量 。4. 属 性 .offse

18、t： 保 存 数 组 元 素 的 可 变 部 分 ， 简 单 变 量 的 offset为 空 ， 可 记 为 null。5. 函 数 limit(array, k)： 计 算 并 返 回 数 组 array中 第 k维 成员 个 数 d k。 17 语 义 规 则(4) EL idE EL.place:=E.place; EL.dim :=1; EL.array:=entry(id.name);(5) EL EL1,E T:=newtemp; k:=EL1.dim+1; dk:=limit(EL1.array, k); emit(T :=EL1.place * dk); emit(T := T

19、 + E.place); EL.array:=EL1.array; EL.place:=T; EL.dim:=k; (3) V EL V.place:=newtemp; emit(V.place := EL.array - c); V.offset:=newtemp;emit(V.offset := EL.place * w);(2) V id V.place:=entry(id.name); V.offset:=null; (1) A V:=E if V.offset=null then emit(V.place := E.place); else emit(V.placeV.offset

20、:= E.place); end if; - Vk-1*dk- T:=Vk-1*dk+ik结 束 （ 第 二 十 次 课 ） 18 上 次 课 程 内 容 回 顾简 单 算 术 表 达 式 与 赋 值 句 的 语 法 制 导 翻 译 内 部 类 型 转 换 ： 规 定 转 换 规 则 ， 按 规 则 转 换1. 数 组 元 素 的 引 用 数 组 元 素 地 址 的 两 个 要 素 ： 首 地 址 和 偏 移 量 地 址 计 算 公 式 （ 三 个 假 设 条 件 下 ） ：addr(Ai1, i2, ., in)=a-c+v（ 或 a-cw+vw）v1 = i1v j = vj-1*dj+i

21、j (j=2， 3， ., n) (4.4)2. 数 组 元 素 引 用 的 语 法 制 导 翻 译 文 法 设 计 （ 增 加 V， 并 可 以 进 行 递 推 计 算 ） 设 计 必 要 的 属 性 与 函 数 ： .array、 .dim、 .place、 .offset和 limit(a, k) 设 计 语 义 规 则 ， 重 点 是 递 推 公 式 vj=vj-1*dj+ij的 计 算 19 语 义 规 则(4) EL idE EL.place:=E.place; EL.dim :=1; EL.array:=entry(id.name);(5) EL EL1,E T:=newtemp

22、; k:=EL1.dim+1; dk:=limit(EL1.array, k); emit(T :=EL1.place * dk); emit(T := T + E.place); EL.array:=EL1.array; EL.place:=T; EL.dim:=k; (3) V EL V.place:=newtemp; emit(V.place := EL.array - c); V.offset:=newtemp;emit(V.offset := EL.place * w);(2) V id V.place:=entry(id.name); V.offset:=null; (1) A V

23、:=E if V.offset=null then emit(V.place := E.place); else emit(V.placeV.offset := E.place); end if; - Vk-1*dk- T:=Vk-1*dk+ik 20 语 义 规 则 （ 续 1）(6) E E1+E2 T:=newtemp; emit(T := E1.place + E2.place); E.place:=T; (7) E (E1) E.place:=E1.place;(8) E V if V.offset=null; then E.place:=V.place;else T:=newtem

24、p; emit(T := V.place V.offset)； E.place:=T;end if; 21 分 析 举 例例 4.18： 对 于 数 组 ： arr:array10,20 of int 赋 值 句 arri+x,j+y:=m+n的 语 法 制 导 翻 译 （ 令 w=4） 。解 ： c=(c1*d2+1)*w=(1*20+1)*4=84。 分 析 树 ：A V := E (1)V id (2) | EL (3)EL id E (4) | EL , E (5)E E + E (6) | ( E ) (7) | V (8) 22 数 组 元 素 引 用 的 语 法 制 导 翻 译(

25、1) A V:=E if V.offset=null then emit(V.place := E.place); else emit(V.placeV.offset := E.place); end if; (2) V id V.place:=entry(id.name); V.offset:=null; (3) V EL V.place:=newtemp; emit(V.place := EL.array - c); V.offset:=newtemp;emit(V.offset := EL.place * w);(4) EL idE EL.place:=E.place; EL.dim :

26、=1; EL.array:=entry(id.name);(5) EL EL1,E T:=newtemp; k:=EL1.dim+1; dk:=limit(EL1.array, k); emit(T :=EL1.place * dk); emit(T := E.place + T); EL.array:=EL1.array; EL.place:=T; EL.dim:=k; (6) E E1+E2 T:=newtemp; emit(T := E1.place + E2.place); E.place:=T; (7) E (E1) E.place:=E1.place;(8) E V if V.of

27、fset=null; then E.place:=V.place; else T:=newtemp; emit(T := V.place V.offset)； E.place:=T; end if; 23 主 要 分 析 步 骤 ： 分 析 举 例 （ 续 1）产 生 式 属 性 计 算 结 果 中 间 代 码V1 i V1.place=i, V.offset=nullE1 V1 E1.place=V1.place=iE2 V2 E2.place=V2.place=xE3 E1+E2 E3.place=t1 t1:=i+xEL1 arrE3 EL1.place=t1, EL1.dim=1EL1

28、.array=arrE6 E4+E5 E6.place=t2 t2:=j+yEL2 EL1,E6 EL2.array=arr, EL2.dim=2 t3:=t1*20EL2.place=t3, d2=20 t3:=t3+t2V5 EL2 V5.place=t4, V5.offset=t5 t4:=arr-84t5:=t3*4E9 E7+E8 E9.place=t6 t6:=m+nA V5:=E9 t4t5:=t6 24 4.7 布 尔 表 达 式4.7.1 布 尔 表 达 式 的 作 用 与 结 构 布 尔 表 达 式 的 应 用 ：1. 逻 辑 运 算 ， 如 ： x:=a or b2. 控

29、 制 语 句 的 控 制 条 件 ， 如 if C then .，while C do .等布 尔 表 达 式 与 其 他 表 达 式 的 关 系 （ 文 法 约 定 优 先 级 与 结 合 性 ） ： BE BE or BE|BE and BE|not BE|(BE)|RE|true|false RE RE relop RE|(RE)|E E E op E|-E|(E)|id|num 25 布 尔 运 算 的 优 先 级 与 结 合 性从 高 到 低 ： not and or例 如 ： a*by or not z等 价 于 ： (a*b)y) or (not z)简 化 的 布 尔 表 达

30、式 文 法 ：E E or E | E and E | not E | ( E ) | id relop id | id | true | false 26 4.7.2 布 尔 表 达 式 的 计 算 方 法 数 值 表 示 的 直 接 计 算 可 以 用 1表 示 true， 0表 示 false or、 and、 not与 +、 *、 -(一 元 )对 应 看例 如 ： A or B and not C的 三 地 址 码 ：T1 := not CT2 := B and T1T3 := A or T2 对 于 关 系 运 算 的 表 达 式 ab的 计 算 ， 可 以 翻 译 成 如 下 固

31、 定的 三 地 址 码 序 列 ：(1) if ab goto (4)(2) t1 := 0(3) goto (5) (4) t1 := 1(5) . 27 逻 辑 表 示 的 短 路 计 算 短 路 计 算 以 if-then-else的 方 式 解 释 布 尔 表 达 式 ， 具 体控 制 逻 辑 如 下 ： A or B ： if A then true else B A and B ： if A then B else false (4.7) not A ： if A then false else true 对 布 尔 表 达 式 A or B and not C采 用 短 路 计

32、算 ， 则 等 价于 下 述 解 释 ： if A then trueelse if Bthen if C then false else true else false 28 短 路 计 算 的 必 要 性 对 于 语 句 ： while ptrnil and ptr.data=x do . 短 路 计 算 可 以 回 避 指 针 为 空 时 对 ptr.data=x的 判 断 ， 从而 避 免 程 序 运 行 时 错 误 。 可 以 用 语 法 规 定 短 路 计 算 。 如 Ada语 言 中 提 供 两 组 运 算 ：and 和 and thenor 和 or else 短 路 计 算

33、时 使 用 and then/or else， 否 则 使 用 and/or。于 是 上 述 语 句 可 以 改 写 为 ： while ptr/=null and then ptr.data/=x loop . 但 是 许 多 的 程 序 设 计 语 言 没 有 规 定 （ 怎 么 做 ？ ） 。 29 4.7.3 数 值 表 示 与 直 接 计 算 的 语 法 制 导 翻 译 全 程 量 nextstat： 可 用 的 三 地 址 码 序 号 ， 调 用 一 次 emit加 1语 义 规 则 ：(1)E E1 or E2 E.place := newtemp; emit(E.place :

34、= E1.place or E2.place);(2) |E1 and E2 E.place := newtemp; emit(E.place := E1.place and E2.place);(3) |not E1 E.place := newtemp; emit(E.place := not E1.place);(4) |(E1) E.place := E1.place;(5) |id1 relop id2(6) |id E.place:=entry(id.name);(7) |true E.place:=newtemp; emit(E.place := 1);(8) |false E.

35、place:=newtemp; emit(E.place := 0); 30 4.7.3 数 值 表 示 与 直 接 计 算 的 语 法 制 导 翻 译 （ 续 1）(5) E id1 relop id2 E.place := newtemp; emit(if id1.place relop.op id2.place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place := 1); (1) if ab goto (4)(2) t1 := 0(3) goto (5)(4) t1 := 1(5) .布

36、尔 表 达 式 ab or cd and ef的 直 接 计 算 31 4.7.3 数 值 表 示 与 直 接 计 算 的 语 法 制 导 翻 译 （ 续 2）布 尔 表 达 式 ab or cd and ef的 直 接 计 算 序 号 产 生 式 三 地 址 码(1) E1 ab (1) if ab goto (4)(2) t1 := 0(3) goto (5)(4) t1 := 1(2) E2 cd (5) if cd goto (8)(6) t2 := 0(7) goto (9)(8) t2 := 1(3) E3 ef (9) if ef goto (12)(10) t3 := 0 (1

37、1) goto (13)(12) t3 := 1(4) E4 E2 and E3 (13) t4 := t2 and t3(5) E5 E1 or E4 (14) t5 := t1 or t4 32 4.7.4 短 路 计 算 的 语 法 制 导 定 义属 性 .true： 表 达 式 的 真 出 口 ， 它 指 向 表 达 式 为 真 时 的 转 向 ；属 性 .false： 表 达 式 的 假 出 口 ， 它 指 向 表 达 式 为 假 时 的 转 向 ；函 数 newlable： 与 newtemp相 似 ， 但 它 产 生 的 是 一 个 标 号 而 不是 一 个 临 时 变 量 。

38、33 4.7.4 短 路 计 算 的 语 法 制 导 定 义 (续 1)三 地 址 码 序 列 与 .true、 .false的 关 系 ： 考 虑 布 尔 表 达 式 E E1 or E2， 它 应 该 有 下 述 代 码 序 列 ：E1.code E1.false: E2.code 根 据 布 尔 表 达 式 短 路 计 算 的 逻 辑 （ 4.7） ， 上 述 表 达 式 真 、假 出 口 之 间 存 在 下 述 关 系 ：E1.true = E2.true = E.true 和 E2.false = E.false 即 首 先 生 成 计 算 表 达 式 E1的 中 间 代 码 ， 然

39、 后 在 计 算 表 达 式 E2的 中 间 代 码 之 前 设 置 一 个 标 号 E1.false， 使 得 当 表 达 式 E1为假 时 ， 转 而 计 算 表 达 式 E2。 34 语 义 规 则 ： 4.7.4 短 路 计 算 的 语 法 制 导 定 义 (续 2) (1)E E1 or E2 E1.true:= E.true; E1.false:=newlabel; E2.true:= E.true; E2.false:=E.false; E.code := E1.code|emit(E1.false :)|E2.code;(2) |E1 and E2 E1.false:= E.f

40、alse; E1.true:=newlabel; E2.false:= E.false; E2.true:=E.true; E.code := E1.code|emit(E1.true:)|E2.code; (3) |not E1 E1.false:=E.true; E1.true:=E.false;(4) |(E1) E1.false:=E.false; E1.true:=E.true; 35 4.7.4 短 路 计 算 的 语 法 制 导 定 义 (续 3)(5) |id1 relop id2 E.code := emit (ifid1.place relop.op id2.placego

41、toE.true) | emit(goto E.false); (6) |id E.code := emit(if id.place goto E.true) | emit(goto E.false);(7) |true E.code := emit(goto E.true);(8) |false E.code := emit(goto E.false); 36 4.7.4 短 路 计 算 的 语 法 制 导 定 义 (续 4)例 4.20： 再 考 虑 布 尔 表 达 式 ab or cd and ef的 短 路 计 算 ： if ab goto LT goto L2L2: if cd go

42、to L1 goto LFL1: if ef goto LT goto LF drive me crazy!分 析 树 ：注 释 分 析 树 ： 三 地 址 码 序 列 ： 37 4.7.5 拉 链 与 回 填 翻 译 方 案 需 要 解 决 的 两 个 问 题 ： 如 何 实 现 表 达 式 的 真 、 假 出 口 ； 如 何 在 语 法 分 析 的 同 时 正 确 生 成 三 地 址 码 序 列 ， 即 所有 的 转 向 均 可 确 定 。 换 句 话 讲 ， 设 计 一 种 什 么 样 的 翻 译 方 案 ， 使 得 仅 对分 析 树 进 行 一 次 遍 历 （ LR分 析 中 就 是

43、对 分 析 树 的 一 次 自下 而 上 的 遍 历 ） 即 可 生 成 所 需 的 中 间 代 码 序 列 。拉 链 与 回 填 的 基 本 思 想 ： 当 三 地 址 码 中 的 转 向 不 确 定 时 ， 将 所 有 转 向 同 一 地 址的 三 地 址 码 拉 成 一 个 链 ； 一 旦 所 转 向 的 地 址 被 确 定 ， 则 沿 此 链 将 所 有 的 三 地 址码 中 回 填 入 此 地 址 。 结 束 （ 第 十 二 一 次 课 ） 38 上 次 课 程 内 容1. 数 组 元 素 引 用 的 语 法 制 导 翻 译2. 布 尔 表 达 式 的 计 算 数 值 表 示 的 直

44、 接 计 算 和 逻 辑 表 示 的 短 路 计 算 短 路 计 算 的 必 要 性 ： 避 免 运 行 时 错 误 数 值 表 示 与 直 接 计 算 的 语 法 制 导 翻 译3. 短 路 计 算 的 语 法 制 导 翻 译 语 法 制 导 定 义 ： 设 计 属 性 (.true、 .false)和 属 性 之 间 的 关 系 问 题 ： 在 自 下 而 上 分 析 中 如 何 计 算 语 义 规 则 39 4.7.5 拉 链 与 回 填 翻 译 方 案 需 要 解 决 的 两 个 问 题 ： 如 何 实 现 表 达 式 的 真 、 假 出 口 ； 如 何 在 语 法 分 析 的 同 时

45、 正 确 生 成 三 地 址 码 序 列 ， 即 所有 的 转 向 均 可 确 定 。 换 句 话 讲 ， 设 计 一 种 什 么 样 的 翻 译 方 案 ， 使 得 仅 对分 析 树 进 行 一 次 遍 历 （ LR分 析 中 就 是 对 分 析 树 的 一 次 自下 而 上 的 遍 历 ） 即 可 生 成 所 需 的 中 间 代 码 序 列 。拉 链 与 回 填 的 基 本 思 想 ： 当 三 地 址 码 中 的 转 向 不 确 定 时 ， 将 所 有 转 向 同 一 地 址的 三 地 址 码 拉 成 一 个 链 ； 一 旦 所 转 向 的 地 址 被 确 定 ， 则 沿 此 链 将 所

46、有 的 三 地 址码 中 回 填 入 此 地 址 。 40 短 路 计 算 的 翻 译 方 案 新 增 函 数 与 属 性 ：1. 属 性 .tc： 真 出 口 链 ， 链 接 所 有 转 向 真 出 口 的 三 地 址 码 ；2. 属 性 .fc： 假 出 口 链 ， 链 接 所 有 转 向 假 出 口 的 三 地 址 码 。3. 函 数 mkchain(i)： 为 序 号 是 i的 三 地 址 码 构 造 一 个 新 链 ，且 返 回 指 向 该 链 的 指 针 ；4. 函 数 merg(P1， P2)： 合 并 链 P1和 P2， 且 P2成 为 合 并 后 的链 头 ， 并 返 回 链

47、 头 指 针 ；5. 过 程 backpatch(P， i)： 将 P链 中 所 有 三 地 址 码 中 的 链 均回 填 为 i值 。 41 例 4.21： 三 地 址 码 ： (i) goto - .(j) goto - .(k) p1:=mkchain(i)和 p2:=mkchain(j)操 作 之 后 ： p2:=merge(P1, P2)操 作 之 后 ： backpatch(P2, k)操 作 之 后 的 三 地 址 码 ： (i) goto k .(j) goto k . (k) 42 属 性 与 语 义 规 则 ：属 性 .stat： 记 录 当 前 第 一 个 可 用 三 地

48、 址 码 的 序 号 。 短 路 计 算 的 翻 译 方 案 （ 增 加 M产 生 式 ， 以 适 应 LR分 析 ） ： (1)M (2)E E1 or M E2 (3) |E1 and M E2(4) |not E1(5) |(E1) M.stat:=nextstat; backpatch(E1.fc, M.stat); E.tc:=merge(E1.tc, E2.tc); E.fc:=E2.fc; E1.tc:=E.fc; E1.fc:=E.tc;E1.tc:=E.tc; E1.fc:=E.fc;（ 将 或 产 生 式 中 的 .tc与 .fc交 换 即 得 ） 下 一 张 43 属 性

49、 与 语 义 规 则 （ 续 1）(7) |id E.tc:=mkchain(nextstat); E.fc:=mkchain(nextstat+1); emit(if id.place goto -); emit(goto -); (8) |true E.tc:=mkchain(nextstat); emit(goto -);(9) |falseE.fc:=mkchain(nextstat); emit(goto -); (6) E id1 relop id2 E.tc:=mkchain(nextstat); E.fc:=mkchain(nextstat+1); emit(if id1.pl

50、ace relop.op id2.place goto -); emit(goto -); 上 一 张 下 一 张 44 再 考 虑 布 尔 表 达 式 ab or cd and ef 上 一 张 45 再 考 虑 布 尔 表 达 式 ab or cd and ef（ 续 ）对 照 ： if ab goto LT goto L2L2: if cd goto L1 goto LFL1: if ef goto LT goto LF 序 号 产 生 式 三 地 址 码(1) E1 ab (1) if ab goto -(2) goto 3(2) M1 (3) E2 cd (3) if cd goto

51、 5(4) goto -(4) M2 (5) E3 ef (5) if ef goto -(6) goto -(6) E4 E2 and M2 E3(7) E5 E1 or M1 E4 其 中 ： E5.tc=(1,5) E5.fc=(4,6) 46 4.8 控 制 语 句 四 类 控 制 语 句 ：无 条 件 转 移 ： goto （ 转 向 某 标 号 所 在 位 置 ） exit、 break（ 退 出 某 个 范 围 ）条 件 转 移 ： if_then_else， while_do： 判 断 布 尔 表 达 式循 环 ： for_loop： 设 定 下 限 、 上 限 与 循 环 步

52、 长分 支 ： case、 switch： 根 据 不 同 的 取 值 执 行 不 同 的 分支 47 控 制 语 句 基 于 的 文 法 :S id:S (1) / 带 标 号 的 语 句 | goto id (2) / goto语 句 | if E then S (3) | if E then S else S (4) | while E do S (5) | A (6) / 赋 值 语 句 | begin L end (7) / 组 合 语 句L L;S (8) / 语 句 序 列 | S (9) 48 4.8.1 标 号 与 无 条 件 转 移 标 号 所 标 记 的 位 置 和 go

53、to所 转 向 的 标 号 。 起 标 记 位 置作 用 的 标 号 被 称 为 标 号 的 定 义 出 现 ； 用 于 goto转 向 的 标 号被 称 为 标 号 的 引 用 出 现 。 在 一 定 的 作 用 域 内 ， 标 号 仅 可 以 定 义 一 次 ， 而 可 以 引用 多 次 。 当 标 号 定 义 出 现 时 ， 将 有 关 信 息 填 写 进 符 号 表 中 ， 而当 标 号 引 用 出 现 时 ， 根 据 符 号 表 中 的 信 息 生 成 正 确 转 移 的三 地 址 码 。 但 在 有 些 情 况 下 标 号 的 引 用 先 于 标 号 的 定 义 。 解 决 的方

54、法 是 借 助 于 符 号 表 的 拉 链 与 回 填 。无 条 件 转 移 的 两 个 要 素 ： 49 4.8.1 标 号 与 无 条 件 转 移 （ 续 1）在 符 号 表 中 为 标 号 设 置 以 下 信 息 域 ： type： 记 录 标 识 符 的 类 型 ， 如 标 号 或 未 知 ； def： 若 是 标 号 ， 记 录 是 否 已 定 义 ， 如 未 定 义 或 已定 义 addr： 标 号 定 义 前 作 为 链 头 ， 标 号 定 义 后 作 为 此 标 号 对 应三 地 址 码 的 序 号 。定 义 过 程 ： fill(entry(id.name), a, b, c

55、)， 将 a, b, c分别 填 写 到 符 号 表 中 标 识 符 id的 .type、 .def、 .addr域 中 。 50 4.8.1 标 号 与 无 条 件 转 移 （ 续 2）翻 译 方 案 ：(1)S goto id if entry(id.name).type=未 知 - 标 识 符 第 一 次 出 现 then fill(entry(id.name),标 号 , 未 定 义 , nextstat); emit(goto -); else if entry(id.name).type =标 号 - 已 出 现 且 是 标 号 then emit(goto, entry(id).

56、addr)； if entry(id.name).def= 未 定 义 - 尚 未 定 义 ， 拉 链 then fill(entry(id.name),标 号 ,未 定 义 ,nextstat-1); end if; else error； - 标 识 符 已 出 现 且 类 型 不 是 标 号 ， 出 错 end if; end if; (2)S LAB S - 略 （ 根 据 S是 何 种 语 句 ， 进 行 相 应 的 翻 译 ） 下 一 页 51 4.8.1 标 号 与 无 条 件 转 移 （ 续 3）(3) LAB id ： if entry(id.name).type=未 知 -

57、 标 识 符 第 一 次 出 现 then fill(entry(id.name), 标 号 , 已 定 义 , nextstat); else if entry(id.name).type=标 号 and entry(id.name).def=未 定 义 - 还 未 定 义 出 现 then q:=entry(id.name).addr; fill(entry(id.name), 标 号 , 已 定 义 , nextstat); backpatch(q, nextstat); else error; - 其 它 情 况 均 出 错 end if; end if; lab: x := a+b;

58、 goto lab;和 goto lab; lab: x := a+b; goto lab; 标 号 未 定 义 1标 号 已 定 义 2结 果 ：(1) t1:=a+b (1) goto 2 (2) x:=t1 (2) t1:=a+b(3) goto 1 (3) x:=t1 (4) goto 2 上 一 页 52 4.8.2 条 件 转 移 三 地 址 码 序 列 和 语 法 制 导 定 义 属 性 .begin： 语 句 S开 始 的 三 地 址 码 序 号属 性 .next： 语 句 S结 束 后 的 三 地 址 码 序 号S if E then S1 ： E.codeE.true: S

59、1.codeE.false: .(1) S if E then S1 E.true:=newlabel; E.false:=S.next; S1.next:=S.next; 已 有 属 性 ： .true .tc .false .fcS.code:=E.code|emit(E.true :)|S1.code; 53 三 地 址 码 序 列 和 语 法 制 导 定 义 （ 续 1）S if E then S1 else S2 ： E.codeE.true: S1.code goto S.nextE.false: S2.codeS.next: .(2) S if E then S1 else S2

60、 E.true :=newlabel; E.false:=newlabel; S1.next:=S.next; S2.next:=S.next; S.code := E.code | emit(E.true :) | S1.code | emit(goto S.next)| emit(E.false :) | S2.code; 54 三 地 址 码 序 列 和 语 法 制 导 定 义 （ 续 2）S while E do S1 ：S.begin: E.codeE.true: S1.code goto S.beginE.false: . (3) S while E do S1 S.begin :

61、= newlabel; E.true := newlabel; E.false := S.next; S1.next := S.begin; S.code := emit(S.begin :) | E.code | emit(E.true :) | S1.code | emit(goto S.begin) | emit(E.false :); 55 上 次 课 程 内 容1. 短 路 计 算 的 语 法 制 导 翻 译 拉 链 回 填 技 术 短 路 计 算 的 语 法 制 导 翻 译2. 控 制 流 语 句 控 制 流 语 句 的 种 类 goto语 句 的 语 法 制 导 翻 译 （ 利

62、用 符 号 表 和 拉 链 与回 填 技 术 ）3. 条 件 转 移 语 句 的 语 法 制 导 翻 译 if-then、 if-then-else、 while-do语 句 的 控 制流 与 语 法 制 导 定 义 56 4.8.2 条 件 转 移 三 地 址 码 序 列 和 语 法 制 导 定 义 属 性 .begin： 语 句 S开 始 的 三 地 址 码 序 号属 性 .next： 语 句 S结 束 后 的 三 地 址 码 序 号S if E then S1 ： E.codeE.true: S1.codeE.false: .(1) S if E then S1 E.true:=newl

63、abel; E.false:=S.next; S1.next:=S.next; 已 有 属 性 ： .true .tc .false .fcS.code:=E.code|emit(E.true :)|S1.code; 57 三 地 址 码 序 列 和 语 法 制 导 定 义 （ 续 1）S if E then S1 else S2 ： E.codeE.true: S1.code goto S.nextE.false: S2.codeS.next: .(2) S if E then S1 else S2 E.true :=newlabel; E.false:=newlabel; S1.next:

64、=S.next; S2.next:=S.next; S.code := E.code | emit(E.true :) | S1.code | emit(goto S.next)| emit(E.false :) | S2.code; 58 三 地 址 码 序 列 和 语 法 制 导 定 义 （ 续 2）S while E do S1 ：S.begin: E.codeE.true: S1.code goto S.beginE.false: . (3) S while E do S1 S.begin := newlabel; E.true := newlabel; E.false := S.ne

65、xt; S1.next := S.begin; S.code := emit(S.begin :) | E.code | emit(E.true :) | S1.code | emit(goto S.begin) | emit(E.false :); 59 条 件 转 移 的 控 制 流 与 翻 译 方 案问 题 ： 一 条 语 句 的 多 个 出 口例 1：if E1 then if E2 then S1 else S2 else S3 的 控 制 流 ：S1、 S2、 S3的 结 束 均 使 得 整 个 条 件 语 句 结 束 。采 用 什 么 方 法 ， 让 S1、 S2、 S3结 束

66、后 均 转 向 条 件 语 句 的 结 束 ？换 句 话 说 ， 如 何 在 一 遍 分 析 中 确 定 语 句 中 所 有 可 能 的 正 确 转 向 ？ 60 条 件 转 移 的 控 制 流 与 翻 译 方 案 （ 续 1）例 2：while E3 do while E4 do S4的 控 制 流 ：同 样 问 题 ： 如 何 在 一 遍 分 析 中 确 定 语 句 中 所 有 可 能 的 正 确 转 向 ？解 决 方 案 ： 拉 链 与 回 填 61 条 件 转 移 的 控 制 流 与 翻 译 方 案 （ 续 2）语 义 规 则 ：(1)M (2)S if E then M S1(3)N (4)S if E then M1 S1 N else M2 S2(5)S while M1 E do M2 S1 (6)S A b a c k p a t c h ( E . t c , M 1 . s t a t ) ; backpatch(E.fc,M2.stat); S.nc:=merge(S1.nc,merge(N.nc,S2.nc); b a c k p a t c h ( S 1