十一五规划计算机主干课程辅导丛书 编译原理 习题与解析 第2版 伍春香 编著 -xercise Analysis 清华大学出版社
前 言 《编译原理》是计算机专业的一门重要专业基础课，它介绍了编译过程中的一些基本 原理、技术及其实现方法。学习这方面的知识，对计算机专业许多问题的理解能够起到融 会贯通的作用。但由于《编译原理》课程涉及内容广，具有较强的理论性，所以学生掌握 起来有一定的难度，解答习题也往往需要花大量的时间。 编著者总结多年的教学实践，收集和整理大量的资料，于2001年在清华大学出版社出 版了《编译原理习题与解析》，目的不仅仅是对习题给出答案，更多的是想通过对习题的 分析与解答，帮助学生充分理解编译的基本原理，了解和掌握基本的编译方法，提高分析 问题、解决问题的能力。 修订感言 《编译原理习题与解析》出版后，得到了不少读者的关注，大家也对该书存在的问题 提出了许多建议和意见，在此由衷地表示感谢！ 本书初版时，编著者尚年轻气盛，初生牛犊不怕虎，书稿完成后匆匆校订即送交给了 出版社。等到书印刷成型拿到手后，才感到书中还有许多不当之处。几年来为此心中一直 耿歌，担心会因此误人，总希望能有机会对该书进行彻底的修订，以解自己心中的款意并 答谢曾经给予关注的读者 本书重新修订，主要进行了如下工作： 增加了对习题（包括部分填空题、选择题、判断题）的解答分析过程； 对部分章节进行了合并： 别去了部分繁琐、重复的内容； 更正了部分错漏之处： 统一了部分名词的描述方式： 增加了近几年国内重点高校硕士研究生入学考试试题。 此外，书中保留了每章的“基本内容”介绍部分，主要是为了方便读者使用本书时对 有关知识点的查阅。 本书内容 本书共分13章。第1章是编译课程的预备知识。第2章涉及程序的翻译和编译程序的组 成。第3章是对文法、语言的形式定义及编译过程中一些基本概念的综合，第4章介绍有穷 自动机理论和词法分析的基本方法。第5章介绍自上而下语法分析。第6章是自下而上语法 分析。第7章是语法制导翻译，介绍了编译过程中常用的一些中间语言及属性文法的构造 第8章总结了符号表及符号表在编译过程中的作用，第9章讲解运行阶段的存储组织与分配， 景鞋建建■国覆
第10章总结了中间代码优化的方法。第11章是代码生成的简介。第12章是编译程序对源程 序中错误的检测和处理方法概述。最后在第13章给出了一些综合题。根据教学大纲要求， 本书内容重点在第3、4、5、6、7章。 讲解安排 每章在基本内容中精选了相关的概念、方法和原理，并附有大量的习题。习题分为基 本题和习题解析：基本题又分为填空题与单项选择题：习题解析部分既收录了一些较容易 的题目，也有相当一部分是取自高校、科研院所的研究生入学试题（每顺颗号后有标注， 并根据内容需要对某些题目作了改动)，有一定难度。基本题都给出了相应的答案，习题 解析部分的每一道题基本上都给出了求解思路和解答过程，以适应不同层次学生的需要。 适用对象 本书难易适当，不仅可作为计算机专业本科生的学习用书，也适合作为课程考试和研 究生考试辅导书，任课教师可以作为教学参考书使用。对于参加计算机软件专业技术水平 考试的应试者，也有一定的参考价值。 编写本书时，编著者力求将自己多年教学积累下来的一些想法以及教学中发现的学生 难以理解的问题融于各章习题解答中，希望能有助于读者对编译课程所涉及知识的理解。 由于习题较多，时间仓促，加上编著者水平有限，虽然希望自己能将书中所有的错误全都 改过，但仍可能存在本人认识错误之处以及错漏之处，内容编排上也一定存在不够合理的 地方，希望读者发现后能与编著者联系以便再版时改进。诚请广大读者批评指正。 联系方式：wu_chx@sina.com 编著者 2006年8月
目 录 第1章预备知识 .1 11基本内容 11.1程序设计悟言与程序的翻译 1.12程序设计语言语法的描述 113 程序的执行 12基本题， 12.1填空题 2 1,2.2单项选择题 1 13习题解析 第2章编译程序概述， 21基本内容 2.1.1程序的翻译… 2.12编译程序的组成 6 2.2基本题 22.1填空题. 222,单项选择题」 8 2.3习题解析 .13 第3章文法和语言的形式定义 3.1基本内容. 15 3,1.1符号串和符号串集合 1 3.12文法和文法的分类 .16 3.13语言的形式定义 17 314与语法分析有关的瓶之 3.1.5语法树和二义性. 3.1.6文法的实用限制和文法变换 19 32 基本题 10 3.2.1填空题 2 32.2单项选择题， 22 33习题解析】 30 33.1文法、语言的形式定义 30 3.3.2短语、直接短语（简单短语）、句柄 .33 3.3.3 文法的递归 36 3.34文法描述的语言和语言文法的构造 38 可金鞋接法速声魅村理青
目录 3.3.5 文法的分类 3.3.6规范推导与规范归约. 3.3.7语法树与二义性 33.8 文法变换 52 第4章词法分析与有穷自动机 …54 4.1基本内容 411词法分析程序的任务。 54 412状本转换图 54 4.13正规表达式和有穷自动机 55 4.1.4 词法分析程序的设计。 5 4.2基本题… 421填空题 422 单项选择题 4.3习题解析 43.1词法分析 .62 432 正规表达式的构造 63 4.3.3 正规文法的构造 6的 4.3.4DFA的构造 71 第5章自上而下语法分析 103 5.1基本内容… 103 5.11自上而下语法分析 103 512 递归子程序法 104 5.13(1)方法（预测分析方法） 106 5.2基本题 107 52.1填空题 107 5.2.2单项选择题： 53习题解折 111 53.1白上面下语法分析 111 53.2递归子程序法 5.331)分析法 .116 第6章自下而上语法分析 125 6.1基本内容 125 6.1.1自下而上语法分析概述 125 6.12简单优先分析算法 126 6.13算符优先分析算法 .128 6.14LRk分析程序， 130 61.5 LRO分析表的构造 .131 6.1.6 SLR(1)分析表的构造 3 6.1.7LR(1)分析表的构造 134