<4D F736F F D B1E0D2EBD4ADC0EDA3A8B5DA32B0E6A3A9BFB1CEF3B1ED2E646F63>

Size: px

Start display at page:

Download "<4D F736F F D B1E0D2EBD4ADC0EDA3A8B5DA32B0E6A3A9BFB1CEF3B1ED2E646F63>"

濮谈
5 years ago
Views:

1 编译原理 ( 第 2 版 ) 勘误表第 2 页倒数第 2 行改成 : 分隔单词的空格通常在词法分析时被删去 2 第 3 页图 1.2 改成 : = = id, 1 + id, 1 + id, 2 id, 2 id, 3 60 id, 3 inttofloat (a) (b) 60 图 1.2 语义分析插入了类型转换 3 第 16 页倒数第 9 行开始的那段改成 : 上一节提到, 字符串集合由叫做模式的规则来描述正规式是表示这些规则的一种重要方法, 因此本节围绕正规式来介绍记号的描述与识别在介绍正规式前, 先给语言一个形式定义 4 第 18 页表 2.3 的第 4 行第 4 列改成 : 肯定出现在一个闭包中 5 第 26 页图 2.10 上面的那段改成 : -closure(t) 的计算是从给定的结点集合出发, 在图上搜索可达结点的典型过程该图只包含 NFA 的含标记的边,T 是给定的结点集合计算 -closure(t) 的简单算法是用栈来保存那些边还没有完成转换检查的状态图 2.11 描述了这样的过程 6 第 43 页倒数第 5 行第一句改成 : 正规式可以描述的语言都能用上下文无关文法来描述 7 第 61 页 5 行开始的那段改成 : (2) 仅使用 FOLLOW(A) 作为 A 的同步集合是不够的例如, 分号在 C 语言中作为语句的结束符, 那么作为语句开始符号的关键字没有出现在表达式非终结符的 FOLLOW 集合中这样, 仅按上面 (1) 来设定同步记号集合的话, 作为赋值结束的分号的遗漏会引起下一语句的开始关键字被跳过 8 第 74 页图 3.15 第 2 行改成 : C = {closure ({[S S ]})}; 9 第 80 页图 3.19 倒数第 7 行改成 :

2 置 C 的初值为 {closure({[s S, $]})}; 10 第 111 页倒数第 4 行开始的那段改成 : 语法树作为一种中间表示, 允许把翻译从分析中分离出来, 形成先分析后翻译的方式, 即先分析生成语法树, 然后再基于语法树进行翻译即使是边分析边翻译, 语法树作为一种概念上的中间表示, 也是有用的 C 和 Java 的编译器通常显式构造语法树 11 第 119 页图 4.9 下第 1 行第 1 句改成 : 图 4.10 给出了图 4.9 的动作是怎样为 a 5 b 构造语法树的 12 第 128 页倒数第 9 行开始的那段改成 : (a) 写一个翻译方案, 它输出每个 a 的嵌套深度例如, 对于句子 ( a, ( a, a) ), 输出的结果是第 134 页倒数第 11 行和倒数第 7 行, 第 135 页第 7 行 ( 两处 ) 第 9 行, 第 136 页倒数第 3 行, 第 137 页第 2 行, 第 149 页倒数第 6 行 : 形式化的都改成形式的 14 第 139 行倒数第 3 条规则改成 : (Exp Index) G E1 : array( N, T ), G E2 : integer G E[ E ]: T 1 2 (0 E 2.val N 1) 15 第 141 页倒数第 12 行改成 : S id := E {if (id.type==e.type && E.type {boolean, integer}) 16 第 154 页图 5.13 改成 : cell = record, : : cell = record, : : info integer next pointer info integer next pointer (a) cell 图 5.13 递归定义的类型名 (b) 17 第 157 页表 5.4 右栏的倒数第 4 行改成 : S = {s s E 2.types and s t E 1.types} ( 备注 : 改成斜体 ) 18 第 170 页图 6.9 最后一行左栏改成 :

3 m r q(1,9) p(1,9) p(1,3) q(1,3) q(1,0) 19 第 172 页第 7 行开始的那段改成 : (4)q 根据局部数据域和临时数据域的大小来减小 top_sp 的值, 也就是进行局部数据和临时数据的空间分配, 并初始化它的局部数据, 开始执行过程体, 如图 6.10 所示 20 第 203 页中间那段改成 : 静态单赋值形式 (static single-assignment form, 简称 SSA) 是一种便于某些代码优化的中间表示 SSA 有两个显著特点可区别它和三地址代码第一个特点是,SSA 中所有赋值指令都是对不同名字变量的赋值, 所有才有静态单赋值这个术语图 7.4 是用三地址代码和静态单赋值形式写的同一个中间语言程序, 注意, 在 SSA 表示中, 下标用来区别变量 p 和 q 的每个定义 21 第 204 页图 7.5 最后 1 行改成 : T T 1 {T.type = pointer (T 1.type); T.width = 4;} 22 第 206 页第 2 行改成 : M {t = mktable(nil); push(t, tblptr); push(0, offset);} 23 第 207 页图 7.8 中最后 1 行改成 : L {t = mktable(nil); push(t, tblptr); push(0, offset);} 24 第 210 页倒数第 2 段前 2 行改成 : 使用 Elist 的综合属性 array 来传递符号表中数组名条目的指针并使用 Elist.ndim 来记录已分析过的下标表达式的个数函数 limit(array, j) 返回 n j, 它是 array 指向数组第 j 维的大小 25 第 211 页倒数第 6 行改成 : (7) Elist Elist 1, E {t = newtemp(); m = Elist 1.ndim + 1; 26 第 215 页图 7.12 下面那段改成 : 图 7.12 中的 B.true,B.false,S.begin 和 S.next 都是三地址指令的标号, 它们都是继承属性图 (a) 为 if-then 的结构图, 由于 B.code 究竟有多少条指令需等 B 翻译结束才知道, 因此在翻译 B 的过程中难以知道 B.true 在三地址指令序列中的准确位置, 为便于翻译, 采用给三地址指令加标号的方式, 函数 newlabel 每次调用时返回一个新的标号 27 第 230 页第 13 行改成 : 的二地址指令, 其中 op 是操作码, 源和目的都是数据域该机器有如下的操作码 :

4 28 第 241 页表 8.4 最后 1 行改成 : p = a MOV a, Rp 2 MOV Mp, R MOV a, R 4 MOV a, Sp(Rs) 3 29 第 259 页倒数第 2 段改成 : 通常, 明了所有路径上的所有程序状态是不可能的数据流分析不区分到达一个程序点的不同路径, 也不掌握完整的状态, 而且它提炼出某些细节, 以获取用于分析目的的数据下面两个例子说明怎样从一个点的状态中提炼出不同的信息 30 第 261 页倒数第 1 段改成 : 如果存在从对 x 的定值 d 之后那个点到点 p 的一条路径, 并且在这条路径上没有对 x 的定值, 那么称定值 d 到达点 p 如果在这条路径上其他某个地方有对 x 的定值, 那么称变量 x 在 d 的定值被注销直观上说, 如果某个变量 x 在 d 的定值到达点 p, 并且运行时在点 p 引用 x, 则 d 可能是 x 最近一次定值的位置 31 第 270 页倒数第 2 行改成 : 半格可能还有底元, 它用来指称, 使得下式成立 : 32 第 275 页倒数第 6 行改成 : (3) 如果框架单调并且半格的高度有限, 那么可以保证算法收敛 33 第 277 页倒数第 11 行第 1 句改成 : 注意, 如果一个流图包含环的话,MOP 解所考虑的路径数是无界的 34 第 277 页倒数第 1 行最后 1 句改成 : 从某种意义上说, 可以认为代表没有任何信息 35 第 280 页第 2 行开始的那段改成 : 下面证明常量传播框架是单调的首先考虑 f s 在一个变量上的影响除了 s 的右部是 y + z 种情况以外, 对于其他所有情况,f s 不改变 m(x) 的值, 或者改变这个映射到返回一个常量在这些情况下,f s 肯定是单调的 36 第 281 页第 1 行改成 : f 3 (f 1 (m 0 ) f 2 (m 0 )) f 3 (f 1 (m 0 )) f 3 (f 2 (m 0 )) 37 第 286 页倒数第 16 行开始的第 1 句改成 : 总的来说, 表达式的预期用来约束表达式的最早放置, 表达式的放置不能再提早到它不具备预期性质的位置 38 第 286 页倒数第 2 段改成 : 下面给出完整的惰性代码移动算法为了使算法简洁, 假定最初每个语句构成一个只含本身的基本块, 并且只在块的入口放置表达式计算的副本为了保证这种简化不会降低这种技术的效力, 将新基本块添加在一条边的源结点和目的结点之间, 如果该目的结点的前驱多

5 于一个这样做明显关照到了程序中所有的关键边 39 第 288 页图 9.25 改成 :( 注意左图中 B 3 和 B 5 改成灰色 ) B 1 B 1 B 2 c = 2 a = b + c B 5 B 2 c = 2 t = b + c B 5 a = t B 3 B 6 B 3 B 6 B 4 预期的 B 4 t = b + c 最早的 B 7 d = b + c 不可用的 B 7 d = t 可延迟的 B 8 B 8 B 9 e = b + c B 9 e = t B 10 B 10 B 11 B 11 (a) (b) 图 9.25 例 9.18 的流图 40 第 288 页倒数第 9 行开始的那段改成 : 在第二步的结尾, 表达式的副本将被放置在该表达式最早被期望的程序点要做到这一点, 需要定义可用表达式数据流问题一个表达式在点 p 可用, 如果在到达点 p 的所有路径上它都被期望这里定义的问题和节描述的可用表达式类似, 区别在于迁移函数一个表达式在一个基本块的出口可用, 如果该表达式在入口可用或者在入口的预期表达式集合中 ( 即如果选择在这里计算它, 则它就成为可用的了 ), 并且没有被该基本块注销 41 第 289 页第 4 行开始的那段改成 : 例 9.20 在图 9.25(a) 中, 有黑阴影的块表示表达式 b + c 在入口不可用, 它们是 B 1,B 2, B 3 和 B 5 最早放置由带黑阴影的灰色块表示, 它们是 B 3 和 B 5 例如,b + c 在 B 4 的入口是可用的, 因为存在路径 B 1 B 2 B 3 B 4, 并且 b + c 在 B 3 是被预期的, 还有从 B 3 的入口开始,b 和 c 都没有被重新计算 42 第 306 页倒数第 6 行第 1 句改成 :

6 本章最后一节简要介绍使用数组的计算密集型程序在多处理器系统上的优化问题 43 第 307 页第 12 行第 1 句改成 : 在考虑指令级并行时, 通常想象成一个处理器在单个时钟周期内发射几个操作 44 第 308 页倒数第 1 行第 1 句改成 : 更复杂的代码调度器能够乱序执行指令 45 第 309 页第 12 行开始的第 1 和 2 句改成 : 这些调度约束保证优化程序和原程序产生同样的结果但是, 因为代码调度会改变操作执行的次序, 因此在一个程序点的内存状态可能与顺序执行的任何内存状态都不匹配 46 第 312 页最后 1 句改成 : 10.5 节将讨论在特定调度算法中, 寄存器分配和代码调度之间的相互影响 47 第 314 页第 1 行改成 : 许多高性能处理器提供专门的特性来支持投机地访问内存, 下面介绍其中最重要特性 48 第 314 页第 12 行开始的那段改成 : 由于分支的花费很大, 尤其是在分支预测出现错误时判定指令 (predicated instruction) 可用来减少程序中的分支数判定指令与普通指令类似, 但是有一个额外的判定操作数来看守它的执行只有在判定为真的情况下, 判定指令才执行 49 第 314 页倒数第 9 行开始的那段改成 : 判定执行伴随着一些代价的发生判定指令被预取和译码, 即使它们有可能最后不被执行静态调度必须预留所有需要用于它们执行的资源, 并保证所有潜在的数据相关都满足判定执行不应该被大量使用, 除非机器有足够的资源 50 第 318 页第 11 行第 1 句改成 : 对于有适度指令级并行的机器, 仅考虑紧凑单个基本块的调度会引起许多资源空闲 51 第 321 页倒数第 12 行开始的那段改成 : 例 10.9 在图 10.8 中的流图中, 两个对 x 的赋值中的一个可以移动到最上面的那个基本块, 因为该变换能维持原来程序中的所有相关性但是, 如果其中一个对 x 的赋值被上移, 则另一个就不能移动了具体来说, 移动前变量 x 在最上面块的出口不是活跃的, 移动后成为活跃的如果一个变量在某个程序点活跃, 则不能把对该变量的投机定值移到该程序点的上面 52 第 322 页第 8 行开始的那段改成 : 在一些全局调度算法中, 循环迭代的边界是代码移动的一种屏障一次迭代中的操作不可以和另一次迭代中的操作有任何重叠打破这种屏障的一种简单而非常有效的技术是在代码调度前把循环展开几次迭代, 使循环体中有更多的指令, 从而全局调度算法有机会发现更多的并行性图 10.9 给出了 for 循环展开的示例

7 53 第 322 页节的标题改为 ( 目录中也应相应修改 ): 静态调度器和动态调度器的相互影响 54 第 324 页第 6 行开始的那段改成 : 例在例的例子中, 虽然很难发现在一次迭代中的并行性, 但是却有很多穿越迭代的并行性循环展开把循环中几次迭代的代码放在一个大基本块中, 然后使用表调度算法使这些操作并行执行如果先把循环展开 4 次迭代, 然后把算法 10.1 用到展开后的代码, 得到的调度表见图 10.11( 为简单起见, 忽略了寄存器分配的细节 ) 展开后每次迭代的执行用 13 周期, 即原来的每次迭代仅需要 3.25 周期 55 第 326 页前 3 行改成 : 用局部最优调度, 启动间隔就不得不加长到 4 周期, 以避免资源冲突, 那么吞吐能力就降到一半该例说明流水线调度的一个重要原则 : 必须仔细安排调度以最优化吞吐能力局部紧凑的调度虽然极小化了单次迭代的时间, 但把它流水化时可能得不到最理想的吞吐能力 56 第 329 页倒数第 5 行的那句改成 : 如何解决这两者之间的相互依赖? 57 第 331 页倒数第 8 行开始的那段改成 : 本节首先介绍并行计算机系统结构的概况, 然后给出并行化的基本概念程序循环的变换和对并行化有用的概念, 再讨论类似的考虑怎样用于优化数据局部性, 最后以矩阵乘算法的优化为例 58 第 332 页倒数第 8 行开始的那句改成 : 类似于存取速度越快则容量越小的内存分层设计原则, 支持处理器之间快速通信的机器只有少量处理器 59 第 335 页例改成 ( 调整缩进 ): for (i = 0; i < n; i++) { Z[i] = X[i] Y[i]; } for (i = 0; i < n; i++) { Z[i] = Z[i] Z[i]; } 60 第 335 页倒数第 3 行的第 1 句改成 : 例被融合循环的性能较好, 因为它有较好的数据局部性每个差计算出来后就立即计算它的平方 61 第 337 页倒数第 10 行第 1 句改成 : 但是, 当使用 X 的完整一行时, 该算法需要逐列访问 Y 的所有元素 62 第 339 页倒数第 18 行改成 : 每一块实际只需要取到缓存中一次, 所以和小节对基本算法的分析一样, 在这里不考

8 虑由 63 第 339 页倒数第 14 行改成 : 阵乘法需要 n 3 次乘加计算, 所以取一对块到缓存的操作的总次数是 n 3 /b 3 由于对于 X 和 Y 的一对块 64 第 339 页倒数第 11 行改成 : 整的矩阵都能装到缓存, 那么缓存未命中的数量是 O(n 2 /c) 在这种情况下, 可以取 b = n, 即让整第 129 页第 10 行改成 : 4.14 参照节, 给出例 4.10 中对应非终结符 T 的翻译函数 2 第 204 页倒数第 9 行改成 : D ; S 3 第 205 页第 4 行改成 : P D ; S 4 第 206 页第 1 行改成 : P M D ; S {addwidth(top(tblptr), top(offset)); pop(tblptr); pop(offset);} 5 第 271 页第 9 行改成 : 对 V 中所有的 x 和 y,x y 当且仅当 x y = x 6 第 274 页倒数第 13 行改成 : G ((y z) K) = (G (y K)) (G (z K)) 7 第 274 页倒数第 9 行改成 : (y z) K = (y K) (z K) 8 第 278 页第 3 行改成 : MOP[B 4 ] = ( f f )(v ENTRY ) ( B3 B1 f f )(v ENTRY ) B3 B2 9 第 299 页倒数第 4 行改成 : 试问应该怎样修改 9.4 节的框架? 第 25 页图 2.8 改成 s = s 0 ; c = nextchar( );

9 while (c!= eof) { if (move(s, c) 未定义 ) return no ; else s = move (s, c); c = nextchar(); } if (s 属于 F) return "yes"; else return "no" ; 第 56 页第 2 行改成如果显式地维持一个栈, 而不是隐式地通过递归调用, 那么可以构造非递归的预测分析器 2 第 64 页第 3 行改成 E rm E E 3 第 64 页第 13 行改成 rm E E + id 第 79 页第 2 行改成 S V = E E = E), 第二项目使得 action[2, = ] 为按 E V 归约 2 第 80 页图 3.19 第 5 行改成 for(first( a) 的每个终结符 b) 3 第 71 页倒数第 3 行改成 LL 方法和 LR 方法有明显的区别 4 第 102 页倒数第 6 行改成 3.17 为习题 3.3 的文法构造 SLR 分析表 5 第 52 页第 6 行本节首先介绍自上而下分析的基本概念和一般方法, 然后定义适合于自上而下分析的 LL(1) 6 第 142 页图 5.3 的名称改成图 5.3 从整型到实型的类型转换 7 第 160 页习题 5.18 第 1 行改成 5.18 对于下面的 C 语言程序, 在 x86/linux 机器上, 编译器报告第 11 行有错误 : 8 第 152 页图 5.12 的第 11 行改成 return sequiv(s 1, t 1 ) && sequiv(s 2, t 2 );

10 9 第 172 页第 3 行改成在这些操作过程中,top_sp 的值在不断减小 10 第 182 页最后一段改成无用单元收集是一个在堆上寻找空间的过程, 它寻找程序不再使用因而可以重新分配给其他数据项的空间对 Java 语言来说, 存储块的释放靠无用单元收集器来完成的, 因此无用单元收集器是 Java 运行系统中完成内存管理的重要子系统, 它将在 11.3 节介绍 11 第 200 页第 12 行改成例如,(8 4) + 2 的后缀表示是 , 而 8 (4 + 2) 的后缀表示第 218 页的前 6 行改成例 7.3 考虑语句 while a < b do if c < d then x := y + z else x := y z 第 56 页算法 3.1 的前两行改成输入串 w 和文法 G 的分析表 M 输出如果 w 属于 L(G), 则输出 w 的最左推导, 否则报告错误 2 第 96 页倒数第 15 行改成 lines : lines expr '\n' {printf ( "%g \ n", $2 );} 3 第 105 页习题 3.41 的程序改成 ( 变成 8 行 ) long gcd(p,q) long p,q; { if (p%q == 0) return q else return gcd(q, p%q); } 4 第 169 页第 7 行改成因此它们的生存期不遵守栈式规则 5 第 182 页倒数第 9 行改成生存期没有被约束在创建它们的过程活动的生存期之内 6 第 201 页表 7.1 最后 1 行左栏改成

11 E id 7 第 209 页第 8 行改成二维数组通常用两种形式之一存储 : 行为主 ( 一行接一行 ) 或列为主 ( 一列接一列 ) 8 第 221 页第 20 行改成 emit( call, id.place, n) } 9 第 237 页第 1 行改成假如反向扫描到达三地址语句 i : x = y op z, 执行下面几步 : 第 51 页倒数第 6 行改成 (3)CB BC 用 n (n-1)/2 次, 交换相邻的 CB, 得到 S + a n B n C n ; 2 第 64 页第 6 行改成 rm E id 2 + id 3 3 第 70 页两张表之间的第 6 行改成动作是按 F id 归约这时两个符号 ( 状态符号 5 和文法符号 id) 弹出栈, 状态 0 显露出来 4 第 84 页第 14 行改成并后变成 {[A c, d/e], [B c, d/e]}, 出现归约 - 归约冲突, 因为面临 e 或 d 时, 不知道应该 5 第 100 页倒数第 2 行改成 S ( L ) a 第 268 页倒数第 8 行改成用 I j 和 O j 分别表示 IN[B 2 ] 和 OUT[B 2 ] 的第 j 次近似, 这些方程可以重写成递推的形式 2 第 268 页倒数第 4 行改成以 O 0 = 开始, 则得到 I 1 = OUT[B 1 ] O 0 = 但是, 如果从 O 0 = U 开始, 则得到 I 1 = OUT[B 1 ] O 0 = OUT[B 1 ], 这才是应该得到的直观上说, 以 O 0 = U 开始, 所得到的解更有希望, 因为它正确反映了一个事实 :OUT[B 1 ] 中没有被块 B 2 注销的表达式在块 B 2 的出口可用第 293 页第 8 行改成一个图的深度优先搜索访问该图所有结点各一次, 它从图的起点开始并且尽快地访问离起点尽可能远的结点

12 2 第 293 页第 12 行开始的那一段改成深度优先排序是一种对流图分析来说很重要的排序, 它是后序遍历的逆深度优先排序先访问一个结点, 然后从它的最右子结点开始, 逐步向左遍历各结点, 直到最左子结点在为流图构建相应的树之前, 需要确定流图中每个结点的后继中, 哪个被看成该树上它的最右子结点, 哪个次之, 直到哪个是最左子节点 3 第 174 页第 2 行改成而不是堆上的理由是避免垃圾收集器收集它们的开销, 只有那些局部于一个过程并在该过程返回后不可访问的数据对象才能分配在栈上第 14 页表 2.1 第 4 行改成 relation <, >, <=, >=, =, <> < 或 > 或 <= 或 >= 或 = 或 <> 2 第 9 页倒数第 4 行改成因为现在计算机系统的性能不仅仅取决于它的原始速度 (raw speed) 3 第 122 页第 15 行改成 T char {T.type = char;} 第 109 页第 2 段图 4.2 给出句子 int id 1, id 2, id 3 的注释分析树这些属性值的计算次序是, 首先计算根的左子结点的属性 T.type, 然后在根的右子树中自上而下地计算三个 L 结点的 L.in 在每个 L 结点还调用过程 addtype, 在符号表中将右子结点上标识符的类型记为整型改成图 4.2 给出句子 int id 1, id 2, id 3 的注释分析树 ( 仅注释了部分属性 ) 这些属性值的计算次序是, 首先计算根的左子结点的属性 T.type, 然后在根的右子树中自上而下地计算三个 L 结点的 L.in 在每个 L 结点还调用过程 addtype, 在符号表中将 id 子结点上标识符的类型记为整型第 121 页图 4.12 的第 2 行改成 syntaxtreenode nptr, i1, s1, s; 2 第 185 页倒数第 12 行即使知道了哪些指令会被频繁执行, 最快的缓存也可能无法把它们同时放在其中改成即使知道了哪些指令会被频繁执行, 最快的缓存也可能没有大到足以把它们同时放在其中

13 3 第 200 页倒数第 12 行改成后缀表示也可以拓广到表示赋值语句和控制语句, 但很难用栈来描述控制语句的计算第 147 页倒数第 11 行改成 : (2) 对任何其他满足 S (t 1 ) = S (t 2 ) 的代换 S, 代换 S (t 1 ) 是 S (t 1 ) 的实例

Microsoft PowerPoint - ch7.ppt [兼容模式]

Microsoft PowerPoint - ch7.ppt [兼容模式] 第七章中间代码生成静态中间代码记号分析检查代码中间生成流器器生成代码器器本章内容介绍几种常用的中间表示 (intermediate representation): 后缀表示图形表示和三地址代码用语法制导定义和翻译方案来说明源语言的各种用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式 7.1.1 后缀表示 7.1 中间语言 E E ope uope (E) id num