编译原理第三版 第九章 运行时存储空间组织.ppt

第九章 运行时存储空间组织 9.1 目标程序运行时的活动 算法大意 ① 按COMLIST中FT所指示的公用链逐一分配 ② 遇等价环: 入口 N1, N2, . . . , Nm 相对数 f1, f2 , . . . , fm 若N1的地址为a, 则Ni的地址为a + ( fi - f1 ) ③ 检查公用区是否冒头 ④ 等价环处理后公用区长度为: MAX( len, a+MAX (fi - f1+size(Ni)) N1:=N; f:=OFFSET[N]; WHILE EQ[N1] N DO {N1 := EQ[N1]; f := MIN ( f, OFFSET[N1] ) } len := -∞ ; N1 := N; REPEAT DA[N1] := 现行程序段的序号; ADDR[N1] := a + (OFFSET[N1] - f ); len := MAX (len, (OFFSET[N1] - f ) +size (N1 ) ); N1 := EQ[N1] UNTIL N1 = N; a := a + len 处理完等价元后下一个局部数据从最长等价元后的地址进行分配 等价环存储分配算法 (3) 临时变量的地址分配 特点: 放中间结果, 定值一次, 引用一次 方法: 用栈实现作用域的层次嵌套 [例] X := A*B - C * D + E * F 四元式 地址代真 ( *, A, B, T1 ) ( *, C, D, T2 ) ( - , T1, T2, T３) ( *, E, F, T4 ) ( +, T3, T4, T5) (:=, T5, _ , X ) ( *, A, B, $a ) ( *, C, D, $(a+1) ) ( - , $a, $(a+1), $a) ( *, E, F, $(a+1) ) ( +, $a, $(a+1), $a) (:=, $a, _ , X ) 临时变量名 地址 T1 a T2 a+1 T3 a T4 a+1 T5 a 实际只用两个存储单元 [例] SUBROUTION EXAMPLE (X, Y) INTEGER A, B(20), C(10, 15), D, E COMPLEX F, G COMMON /CBK/D, E, F EQUIVALENCE (G, B(2)), (D, B(1)) 试进行地址分配 解: 1. 符号表 SYMBOL TABLE NAME ATT ADDRESS CAT DIM TYPEOFFSETDA ADDR EQ CMP . . . X V 哑 0 0 Y V 哑 0 1 A V i 0 2 B a i - 1 129 0 k+6 C a i 0 3 D V i - 1 129 0 k+9 k+7 E V i 129 1 k+8 F V C 129 2 0 G V C 0 129 1