高等学校 电子信息 规划教材 程序设计语言 编译原理 (第3版) 陈火旺 刘春林 编著 谭庆平赵克佳刘越 国莎一草8散
程序设计语言 编译原理 (第3版) 陈火旺刘春林 谭庆平起克佳刘越编著 图防·革名服升 ·北京
图书在版编目(C亚)数据 程序设计语言编译原理/陈火旺等编著。一3版，一北京： 国防工业出版社，2000. 1SBN7-118-02207-1 】.程.Ⅱ.陈.Ⅲ.编译程序-程序设计N.T314 中国版本图书馆CP数据核字(1999)第6830号 闲防·素：瓶社出版发行 (北京市海证区紫竹院南路23号) (郎政编码100044) 三河市聘飞胶印厂印制 新华书店经售 开本787×10921/16印张2575千字 2000年1月第3额 2000年1月北京第23次印刷 印数：213701-218700册定价：31.00元 【本书如有印装错误，我社负责调换)】
出版说明 为做好全国电子信息类专业“九五”教材的规划和出版工作，根据国家教委《关于“九 五”期间普通高等教育教材建设与改革的意见》和《普通高等教育“九五”国家级重点教材 立项、管理办法》，我们组织各有关高等学校、中等专业学校、出版社，各专业教学指导委员 会，在总结前四轮规划教材编审，出版工作的基础上，根据当代电子信息科学技术的发展 和面向21世纪教学内容和课程体系改革的要求，编制了《1996一2000年全国电子信息类 专业教材编审出版规划》。 本轮规划教材是由个人申报，经各学校、出版社推荐，由各专业教学指导委员会评选， 并由我部教材办商各专指委、出版社后，审核确定的。本轮规划教材的编制，注意了将教 学改革力度较大、有创新精神，特色风格的教材和质量较高，教学适用性较好、需要修订的 教材以及教学急需，尚无正式教材的选题优先列人规划。在重点规划本科、专科和中专教 材的同时，选择了一批对学科发展具有重要意义，反映学科前沿的选修课，研究生课教材 列入规划，以适应高层次专门人才培养的需要。 限于我们的水平和经验，这批教材的编审、出版工作还可能存在不少缺点和不足，希 望使用教材的学校，教师、同学和广大读者积极提出批评和建议，以不断提高教材的编写、 出版质量，共同为电子信息类专业教材建设服务。 电子工业部教材办公室
前 言 本教材系按电子工业部的1996一2000年全国电子信息类专业教材编审出版规划》 由全国高校计算机专业教学指导委员会编审、推荐出版。本教材由国防科技大学陈火旺 院士担任主编，主审侯文永教授、赵雄芳教授。 本教材的参考学时数80学时，其主要内容包括词法分析、语法分析、属性文法与语法 制导翻译，语义分析与中间代码产生、符号表与运行时存储空间组织，优化与目标代码生 成、并行编译技术。本书将编译技术的最新发展，例如属性文法、面向对象语言的编译技 术、并行编译技术，编译程序自动构造工具等内容系统地融合到材中。本书的主要例 和习题均以C,Pscl为语言背景，并在一些重要的章节中增加了必要的例题，以帮助读者 理解和自学。使用本教材时应注意，在学这门课之前，学生必须预修计算引论（程序设计 方法)和高级语言(PASCAL、C或C++),并且最好具有数据结构和离散数学方面的基本 知识。 本书是在陈火旺，钱家骅、孙永强三位教授1980年编写的《程序设计语言编译原理》 的基础上，结合编译技术的最新研究成果和作者多年的教学经验编写而成的。本书由陈 火旺院士确定内容的选取和组织，由刘春林、潭庆平、赵克佳、刘越具体执笔，最后由陈火 旺院土定稿。刘春林编写第一、二四、五、六、七、十章以及十一章部分内容：谭庆平编写 第三章；刘越编写第八、九章以及十一章部分内容；赵克佳编写第十二章：翟桂英负责全书 文字及图表的录人工作。侯文永教授和赵雄芳教授认真审阅了本书的全部初稿，提出了 很多宝贵的意见，在此表示诚挚的感谢。由于编者水平有限，书中难免还存在一些缺点和 错误，般切希望广大读者批评指正。 编者
目 录 第一章引论 1.】什么叫编译程序. 12编强过程指球 1.3 编译程序的结构. 1.3.1编译程序总框 1.3.2表格与表格管理 1.3.3出蜡处理 13.4满 1.3.5编译前端与后端 1.4编译程序与程序设计环境 15绵译程序的生成. 第二章 高级语言及其语法描述 2.1程序语言的定义： 12 211语法. 2.1.2语义 .13 2.2高级语言的 一般特性 2.2,】高级语的分类.++*.15 2.2.2程序结构. 4415 2.2.3数据类型与操作. 之.之4语句与控制结构. 2 2.3程序语言的语法描述. 25 2.3,1上下文无关文法. 426 2.3.2语法分析树与二义性 4431 2.3.3形式语言鸟瞰. 35 第三章词法分析， 4437 3.1对于词法分析器的要求 37 31.1词法分折的功能和输出形式 .3 31.2 词法分析器作为一个独立子程序 3.2词法分析器的设计· 3.2.1输人预处理 3.22单词符号的识别：超前搜家 0 状态转换图 41 状态转换图的实现
3.3正规表达式与有限自动机 33.】正规武与正提集 确定有限自动机(DFA) 非确定有限自动机(NFA) 3.3.4 正规文法与有限自动机的等价性 3.3.5正规武与有限自动机的等价性 3.3.6确定有限自动机的化简 3.4词法分析器的自动产生 3.41 语言X的一般述 3.4.2超前搜索 60 3.4.31X的实现 63 第四章 语法分析 自上而下分析 4.1语法分析器的功能 42自上而下分析面临的间问额 66 4.3 山(1)分析法 4,3.1左递归的清除 4.3.2消除回溯、提左因子 4.3.31.(1)分析条件. 4.4 递归下降分析程序构造 4.5 预测分析程序 76 4.5,】预测分析程序工作过程 4.5.2预测分析表的构造 44 4.6(1)分析中的错误处理 秀 第五章语法分析 自下而上分析 .R3 5.1自下而上分析基本问题 5.1. 归约 5.1.2 规范归约简述 5.1,3符号栈的使用与语法树的表示 87 52算符优先分析 5.2. 算符优先 法及优先表构造 5.2.2 算符优先分析算法+ 5.2.3优先函数 5.2.4算符优先分析中的出错处理 9% ·5.3【分折洪 53.1 R分析器 5.3.2R(0)项日集族和LR(O)分析表的构造 5.33SLR分析表的构造 110 53.4搜范R分析表的构造 114 5.3,5LA1R分析表的构造 117
536 二义文法的应用 123 5.3.7R分析中的出错处理. 126 5.4语法分析器的自动产生工具YACC, 129 到 第六章 黑性文法和语法制导翻译 136 6.1属性文法 136 62 基于属性文法的处理方法 139 62.1 依横图 140 6.2.2 树遍历的属性计算方法 6.2.3 一遍扫措的处理方法 144 6.2.4抽象语法树 144 6.3S-属性文法的自下而上计算 147 6.4L-属性文法和自顶向下翻译 6.4.1翻译模式 10 6.4.2自顶向下翻译 153 6.4.3递归下降翻译器的设计 156 6.5 自下而上计算继承属性 15 6.5.1 从翻译模式中去掉嵌人在产生式中间的动作. 6.5.2 分析栈中的继承属性. 58 6.5.3棋拟继承属性的计算 160 6.5,4用综合属性代特维承属性 163 164 第七章 语义分析和中间代码产生 166 71中间语言 167 7.1.2图表示法 167 7.1.3 地址代码 69 7.2说明语句 74 7.2.】过理电的说明语句： 174 7.2.2 留补 用城信息。 115 7.2.3 记录中的域名 7.3威值语句的翻译， 7.3.】简单算术表达式及赋值语句 7.32数组元款的引用 179 7.3.3 记录： 的引用 185 7.4布尔表达式的科 7.41数值表示法： 了.4.2作为条件控制的布尔式翻译， 187 7.5控制语句的翻译 12 7.5.1 控制流语句 7.5.2标号与0如语句
7.5.3CASE语的蔬译 7.6过程调用的处理 42D0 7.7类型检查. 7.7.】类型系统 0 7.7.3 函数和运算符的重载 7.7.4 多态函数 209 练 习 217 第八章符号表 8.1符号表的组织与作用 21 8.1.1符号表的作用. 221 81.2符号表的组织方式. 22 82被理与杏找， 2 线性表 8.2.2 对折查找与二叉树· 8.2.3杂凑铍术 228 8.3名字的作用范围 20 831 FORTRAN的符号表组织 8.3.2 的符 组 8.4符号表的内容· 23 习 226 第九童 运行时存储空间组织 230 9.1目标程序运行时的活动 239 9.1.1过程的活动. 239 9上2卷数传增. 241 9.2运行时存储器的划分 2A3 9.2.1运行时存储器的划分 9.2.2括动记录. 244 9.2.3存储分配策略 245 9.3静态存储分配 93.1 数据 “9.3.2公用语句的处理 ·93.3等价语句的处理*. 9.3.4地址分 251 9.3.5临时变量的地址分配 253 9.4简单的栈式存储分配 25 9.4.1C的活动记录 9.4,2C的过程调用、过程进人、数组空间分配和过程返同回 9.5嵌套过程语言的钱式实现 257 9.5.1 非局部名字的访问的实现， 29 9.5.1 参数 专递的实现：
9.6堆式动态存储分配. 26 9.6.1堆式动态存储分配的实现 9.6.2隐式存储同收. 26 268 第十章优化. 44.27 10.1概述 10.2 27 局部优化 279 10.2.1 基本块及流图 279 10.2.2 基本块的DAG表示及其应用· 281 10.3循环优化. 287 103.1代码外提. 10.32 强度制弱 0.33 除归纳变量 292 10.4数据流分析 204 10.41任意路格数据海分析 294 10.4,2全路径数据流分析 10.43数据流问题的分米 其它主 数据流问题 29% 0.4 利用数据流信息进行全局优化 301 习 05 第十一章目标代码生成 309 基本问题 309 112目标机器模到 311 11.3 一个简单的代码生成界 32 113.1待用信息 11.3.2 寄存器描 述和地址描述 35 11.3.3 代码生成算法 315 11.4寄存器分配. 317 11.5DAC的目标代码 321 11.6 窥孔优化 324 练 习 327 第十二章并行编译基础 12.1 并行计算机及其编译系统： 329 21.1向量计算机 330 12.1.2共享存储器多外理机 。:321 12.13分布存储器大规模并行什算机 235 12.1.4 并行编译系统的结构 336 12.2 基本概念 339 12.2.1向量与向量的次序 339 2.2之循环板型与煮引空间 340 12.2.3输人与轴出集合 342