内容简介 本书系统全面地介绍经典、广泛应用的高级程序设计语言编译程序的构造原理、实现技术、方法和工 具。本书包含了现代编译程设计的基础理论和技术,并在语义分析、代码优化,面向对象语言的编译及 高级优化技术等方面反映了20世纪90年代后的一些重要研充成果,特别兼顺近年来编译原理及技术的 发展和发生的一-些重要变化,专辟“编译技术高级专题”予以介绍。本书的组织注重提炼精华、循序渐进 深入浅出、每章开头提炼了该章涉及的主要内容、要点和关键概念,全书精编、精选了近300道各种类型的 习题和思考题,还提供了编译程序实现的具体实例,能够辅助读者更好地学习和掌握编译原理。 本书可以作为计算机学科类专业及相关专业本科和研究生编译原理的教科书,也可以作为软件技术 人员的参考用书。 本书封面贴有清华大学出版社防伪标签,无标签者不得销售。 版权所有,侵权必究。侵权举报电话:Q106278298913701121993 图书在版编負(CP)数据 编译原理/陈英等编著.一北京:清华大学出版社,2009.4 (计算机系列教材 ISBN978-7-302-19744-7 .编...II.陈...III.编译程序一程序设计IV.TP314 中国版本图书馆CIP数据核字(2009)第039084号 责任编辑;谢琛薛阳 贲任校对:焦丽丽 贲任印制:王秀菊 出版发行:清华大学出版社 地址:北京清华大学学研大厦A座 htp:∥www.tup.com.cn 邮编;100084 社总机:010-62770175 邮购:010-6286544 投稿与读者服务:010-62776969,C-sery1ce@tup.tsinghua.edu.cn 质量反馈:010-62772015,zhiliang@tup.tsinghua.edu.cn 印刷者:北京国马印刷厂 装订者:北京鑫海金澳胶印有限公司 经销:全国新华书店 开本:185×260 印张:22 字数:536千字 版次:2009年4月第1版 印次:2009年4月第】次印刷 印数:1~4000 定价:32.00元 本书如存在文字不清、漏印、缺页、倒页、脱页等印装质量问题请与清华大学出版社出版部联系调换。 联系电话:010-62770177转3103产品编号:029731~01 《编译原理》前言 编译原理作为计算机学科的一门重要专业基础课,列人国际ACM教程和IEEE计算 机学科的正式主干课程,并提高该课程内容的课时比重,这充分体现了其在计算机科学中的 地位和作用 编译程序是计算机系统软件的主要组成部分,是计算机科学中发展迅速、系统、成熟的 个分支,其基本原理和技术也适用于一般软件的设计和实现,而且在语言处理、软件工程 软件自动化、逆向软件工程、再造软件工程等诸多领域有着广泛的应用。 本书旨在介绍编译程序设计的基本原理、实现技术、方法和工具。本书的前驱版本系陈 萸教授主编,获得北京市2008年高校精品教材。在此基础上,规划、整合为“编译原理”课程 的系列丛书,包括作为教材的本书及后续即将推出的《编译原理学习指导与习题解析》和《编 译原理课程设计》。全书分为11章,第1章作为仝书的开场白,介绍了编译程序有关的概 念,编译过稈、编译程序的结构与组织等要点。第2章作为后续各章的基础知识,也是学习 编译原理应起码具备的理论基础,对形式语言与自动机理论作了基本的介绍。第3章以正 则文法、正规式、有限自动桃为工具,讨论了词法分析器的设计与实现。第4章和第5章对 常规的语法分析方法,即自上前下和自下而上分析中的几种经典方法展开了较深入的讨论 并结合流行、实用、高效的LR分析方法,介绍了二义文法的分析应用,编译程序的出错处 理。第3章和第5章还讨论了流行的词法分析和语法分析自动生成工具Lex及Flex, YACC及 Bison的构造原理与应用,并以 ANSI C语言为例,给出了其Lex和YACC的描 述。第6章涉及语义分析方法和属性翻译文法,中间语言,符号表及类型检查技术,流行的 高级程序设计语言中典型语句的翻译。第7章介绍编译程序运行时环境的有关概念和存储 组织与分配技术。第8章介绍中间代码级上的优化,展开讨论了优化的基本概念,优化涉及 的控制流分析和数据流分析技术,以及中间代码上的局部优化和循环优化技术及实现。第 9章简单介绍了代码生成的有关知识点及吕标代码级可实施的窥孔优化技术。第10章以 PL/0语言为源语言,提供了一个短小、精悍的编译程序实现的范例,以弥补编译程序从原理 到工程实现的鸿沟。第11章反映了20世纪90年代后本领域的一些重要研究成果,如面向 对象语言的翻译、GLR分析。另外,高性能体系结构的发展与技术对编译技术提出新的挑 战。本章针对主流并行处理器体系结构及与之相关的编译优化技术进行简要介绍,如并行 优化技术、存储层次及其优化技术等。 纵观本书的组织,注重循序渐进,深人浅出,每章开头提炼了该章涉及的主要内容提要 和关键概念,全精编、精选∫近300道各种类型的习题和思考题,还提供了编译程序实现 的具体实例,辅助读者更好地学习和掌握编译原理 本书是作者多年教学实践和科硏工作的汇集、提炼和整理,特别是北京理工大学“编译 原理”课程组老师们奉献了他们教学实践的汇集和积累。本书芫成的责任编著和辅助编著 的直接承担者是:陈英第1,3,4,5,6,9和11章;王贵珍第2,10,4和11章;李侃第6,7,11 和2章;计星第8,9,11,1和5章;陈朔鹰第3,7和8章。本书参考了国内外一些专著、论 文和资料,参考、借鉴了一些专家学者的研究成果,对所有这些前辈和同行的引导和帮助表 示衷心的感谢。另外,本书过去多个不同版本通过数届学生和读者的使用,亦得到了他们许 多宝贵的反馈意见和建议。本书完成过程中,得到了清华大学出版社的鼎力协助,尤其是编 审谢琛高效的工作和非常专业的指导,作者在此一并深为致谢 鉴于作者水平有限,本书稿虽经审慎校阅,仍堆免存在疏误,敬请读者不吝赐教 编者 2009年1月于北京 ○ R t WOR D 《编译原理》目录 第1章编译引论/1 1.1程序设计语言与编译程序/1 1.1.1编译程序鸟瞰1 1.2源程序的执行/2 1.2编译程序的表示与分类 2.1T型图/2 1.2.2编译程序的分类/3 1.3编译程序的结构与编译过程/4 3.1编译程序的结构与编译过程/4 3.2编译程序结构的公共功能与编译程序的 组织/9 1.4语言开发环境中的伙伴程序/10 5编译程序结构的实例模型/11 1.5.1一遍编译程序结构/11 1.5.2 PRIME机上AHPL语言的两遍编译 程序/11 1.5.3PDP11计算机上C语言的三遍编译 程序/11 5.4 Tiger编译程序结构/12 1.5.5GCC编译程序结构框架/13 6编译程序的构造与实现14 1.6.1如何构造一个编译程序/4 1.6.2编译程序的生成方式/15 1.6.3编译程序的构造工具15 习题1116 第2章形式语言与自动机理论基础/18 2.1文法和语言/18 2.1.1话言的语法和语义/18 2.1.2文法和语言的定义/19 2.1.3文法的表方法/25 2.1.4语法分析树与二义性/2 2.1.5文法和语言的类型/29 目录《编译原理》 2有限自动机30 2.2.1确定的有限自动机/31 22.2非确定的有限自动机/33 2.2.3确定的有限自动机与非确定的有限自动 机的等价/35 22.4确定的有限自动机的化简/38 3正规式与有限自动机42 2.3.1有限自动机与正则文法/42 2.3.2正规式与正规集/43 2.3.3正规式与有限自动机/44 习题2/52 第3章词法分析/58 3.1词法分析与词法分析程序/58 3.2词法分析程序设计与实现/59 3.2.1词法分析程序的输入与输出/59 3.2.2源程序的输入与预处理/60 3.2.3单词的识别/6 3.2.4词法分析程序与语法分析程序 的接口/62 词法分析器的设计与实现62 3.3词法分析程序的自动生成68 3.3.1词法分析自动实现思想与自动生成 器Lex/Flex/68 3.3.2Iex运行与应用过程68 3.3Lex语 69 词祛分析器产生器的实现73 3.3.5Iex应用74 习题3/78 第4章语法分析——自上而下分析/9 4.1语法分析综述/79 4.1.1语法分析程序的功能9 《编译原理》冒录 4.1.2语法分析方法/80 4.2不确定的自上而下语法分析/81 4.2.1一般自上而下分析/8 4.2.2不确定性的原因与解决方法/82 4.2.3消除回溯/85 4.3递归下降分析法与递归下降分析器86 生.3.1递归下降分析器的实现86 4.3.2递归下降分析器设计工具--状态转 换图/87 4.4LL(1)分析法与LI(1)分析器89 4.4.1LL(1)分析器的逻辑结构与动态 实现/89 4.4.2LL(1)分析表的构造/91 4.4.3关于ML(1)文法/94 习题495 第5章语法分析—自下而上分析99 5.1基于“移进归约”的自下而上分析/99 5.1.1“移进归约”分析/99 1.2规范归约与句柄/101 5.2算符优先分析法与算符优先分析器103 直观的算符优先分析法/103 5.2.2算符优先文法和算符优先分析表的 构造/1 5.2.3算符优先分析法实现的理论探讨/109 5.2.4优先函数表的构造/112 5.3LR分析/114 3.1LR分析法与LR文法114 5.3.2IR(0)分析及LR(0)分析表的 构造/119 5.3.3SLR(1)分析及SLR(1)分析表的 构造128 3.4LR(1)分析及LR(1)分析表的 构造/130 目录《编译原理》 5.3.5LALR(1)分析及LAIR(1)分析表的 构造/135 5.4LR分析对二义文法的应用/138 5.5LR分析的错误处理与恢复/140 .6语法分析程序自动生成器/142 6.1YACC综述与应用/143 6.2YACC语言144 56.3YACC处理二义文法/145 6.4YACC的错误恢复/147 56.5YACC应用148 习题5/158 第6章语义分析与中问代码生成/163 6.1语法制导翻译/163 6.1.1语法制导定义164 6.1.2综合属性165 6.1.3继承属性166 6.1.4依赖图/166 6.1.5语法树的构造/168 6.1.6S属性定义与自下而上计算/168 6.1.7L属性定义与翻译模式/169 6.2符号表/172 6.2.1符号表的组织/173 6.2.2分程序结构的符号表/174 6.3类型检查17 6.3.1类型体制/17 6.3.2一个简单的类型检查程序/179 6.4中间语言183 6.4.1逆波兰表示法/183 64.2N-元式表法184 6.4.3图表示法/186 6.5中间代码生成/186 6.5.1说明类语句的翻译/186 VI 《编译原理》目录 6.5.2赋值语句与表达式的翻译189 6.5.3控制流语句的緲译190 6.5.4数组说明和数组元素引用的翻译/96 6.5.5过程、函数说明和调用的翻译/198 习题6/199 第7章运行环境203 7.1程序运行时的存储组织与分配/203 7.1.1关于存储组织203 1.2过程的活动记录/204 存储分配策略/205 7.2静态运行时环境与存储分配/206 7.3基于栈的运行时环境的动态存储分配/208 7.3.1简单的栈式存储分配的实现/208 7.3.2嵌套过程语言的栈式存储分配的 实现/210 7.4基于堆的运行时环境的动态存储分配212 7.4.1基于堆的运行时环境的动态存储分配的 实现/212 7,4.2关于悬空引用/21 习题?/216 第8章代码优化/221 8.1代码优化概述/221 8.1.1代码优化的概 221 8.1.2优化技术分类/222 8.1.3优化编译程序的组织/227 8.2局部优化/227 8.2.1基本块的定义与划分227 8.2.2程序的控制流图/228 8.2.3基本块的DAG表示及应用/229 8.3控制流分析与循环查找/236 8.4数据流分析/239