十一五规划计算机主干课程辅导丛书 编译原理 习题与解析 第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
录 61.8LALR分折表 136 62基本 136 6.2.1 填空题 6.2.2单项选择题 136 6.3习题解析 143 63,1优先分析方法 6.3.2LRk)分析方法 160 第7章语法制导翻译 200 7.1基本内容 .200 7.1.1语义分析概述 .200 7.12中间语言 7.13 目标代码结构的设 7.14语法制导翻译 203 72基本题 .205 721 填空题 7.2.2单项选择题 206 7.3习额解析 212 73.1 中间语言 212 7.32语法制导翻译。 218 第8章符号表 237 8.1基本内容 8.1】符号表的作用与生存期。 237 8.12符号表的内容 .237 8.13 符号表的数据结构与符号表的组织 8.14符号表的结构与符号表的操作 238 8.15 FORTRAN的符号表 230 8.1.6 SCALE的符号表】 230 82基本题 240 8.2.1填空题 240 822单项选择恩 240 8.3习题解析 第9章运行阶段的存储组织与分配 249 9.1基本内容 249 9.1.1概述 .249 9.12静表存储分配 .250 913 动态存储分配 351 9.1.4形实参数结合 .256 9.15关于本章的学习 256 92基本题 257
4 目录 9.2.1填空题 .257 92.2单项选择题 .257 9.3习题解析 261 931 存储分配 261 9.3.2参数传递… 270 第10章代码优化 286 10.1基本内容 …286 10.1.1优化的原则. .286 10.12代码优化的基本方法 .286 10.13基本块内的局部优化 .28 10.14循环优化 .290 10.15应丑优化 202 10.2蒸本题 29g 10.2.1填空题 293 1022单项选择题 293 ‘10.3习题解析 294 第11章代码生成 .309 111基本内容 .309 111.1 概述 309 11.1.2PL0抽象机 309 112基本题 310 112.1 填空题 310 11.2.2单项选择题 31 113习题解析。 .313 第12章错误的检测与处理 .315 12.1基本内容 315 12.1.1错误的种类… .315 12.12对错误的处理方法 315 12.13 词法分析阶段的错误检测与处理 315 12.1.4语法分析阶段的错误检测与处理 316 12.1.5语义错误的检测与处理 316 12.2基本题 317 122.1填空题. …317 12.2.2单项选择愿. 第13章综合题 319 13.1基本题 .319 132习题解折 .324 D 参考文献 337
第1章 预备知识 1.1基本内容 1.1.1程序设计语言与程序的翻译 一般程序设计语言的定义都涉及语法、语义和语用3个方面。 1.语法 程序设计语言的语法是指由程序设计语言的基本符号组成程序中各个语法成分包括 最大的语法成分“程序”)的一组规则。其中由基本符号构成符号（单词）的书写规则称 为词法规则，而由符号（单词）构成语法成分的规则称为语法规则。 2.语义 程序设计语言的语义是指程序设计语言中按语法规则构成的各个语法成分的意义，也 就是各语法成分在运行阶段被计算机执行时所做的工作及其结果。语义又分静态语义（编 译时刻可确定的语法成分含义)和动态语义（运行时刻才能理解与确定的语法成分含义）。 3.语用 程序设计语言的语用表示语言符号及其使用者之间的关系，涉及符号的来源、使用和 影响，如程序的设计风格等。 1.1.2程序设计语言语法的描述 1.语法图 语法图是用图解形式来描述程序设计语言语法规则的工具。这种表示简沽、直观。例 如非负整数的语法图如图1.1所示。 数字 数字 图1.！非负整数的构成规则
编译原理习题与解析（第2版）一— 2.BNF范式 使用BNF范式来描述程序设计语言的文法时，用尖括号括住待描述的语法成分，用“： =”或“→”表示语法成分“定义为”，“”表示“或者”。BNF范式具有简洁、严谨、 精确、无歧义等优点。 例如，赋值语句的语法可表示为： ：= 3.扩充的BNF-EBNF EBNF是在BNF的基础上增加了3组符号： (x表示x可以出现0到多次。{xm”表示x可以出现m到n次 [x表示x可能出现一次，也可能不出现。 ()表示x和y二者取。 例如简单算术表达式的语法可用EBNF表示为： ：=：={（因式>} <因式：=<变量<表达式y 4.自然语言 也可以用自然语言来描述程序设计语言的语法成分。这种表示方式显得不简洁，甚至 累赘，也不直观，且易导致定义不确切。 1.1.3程序的执行 只有正确的程序才能被执行. “一个程序是正确的”包括两层含义：一是书写正确，即合乎语法规则：二是含义正 确，即能够“正确理解与应用”程序中各种语法成分的语义定义，并在逻辑上体现了程序 书写者的意图，因而在正确地输入数据之后，就能获得预期的运行效果。 1.2基本.题 1.2.1填空题 1.一个程序是正确的，包括两层含义：一是(1)二是(2)。 答案：(1)书写正确（或合乎语法规则） (2)含义正确（或合乎语义规则和逻辑意义） 2.描述高级语言语法的常用方法有(1)一、(2)一、(3)等。 答案：(I)语法图(2)BNF范式(3)扩充的BNF范式 Page
第1章预备知识。 3.描述如何用语言基本符号组成程序中各个语法成分的一组规则称为(1)；对 程序中各个语法成分含义的描述称为(2)；而涉及语言符号及其使用者之间的关系的 内容称为(3)一· 答案：(1)语法(2)语义(3)语用 1.2.2单项选择题 1.一般程序设计语言的定义都涉及 3个方面。 ①语法②语义③语用④程序基本符号的确定 可达项有： a.①②③b.①②④c.①③④d.②③④ 答案：8 2.程序语言一般分为(1)和(2)·两大类，其中()通常又称为面向 机器的语言。面向机器的语言指的是(3)一，其特点是(4)一·在此基础上产生了 与人类自然语言比较接近的(2)。 可选喻有： (1)、(2)a高级语言b.专用程序语言c.低级语言d.通用程序语言 (3)a.用于解决机器硬件设计问题的语言 b.特定计算机系统所固有的语言 c.各种计算机系统都通用的语言 d.只能在一台计算机上使用的语言 (4)a.程序的执行效率低，编制效率低，可读性差 b.程序的执行效率高，编制效率高，可读性强 c.程序的执行效率低，编制效事高，可读性强 d.程序的执行效率高，编制效率低，可读性差 答案：(1)c(2)a (3)b(4)d 1.3习题解析 I.请用语法图、BNF范式、扩充的BNF范式、自然语言4种方式给出“标识符”的语 法描述。 解答：(1)标识符的构成规则可以用图12所示的语法图描述