编译原理学习指导与习题解析
第一章：
1-1选择、填空题
(1)构造一个编译程序的三要素是 ， ， 。 答案：源语言、目标语言和编译方法、技术及工具
(2)被编译的语言为A语言，编译的最终结果为B语言代码，编写编译程序的语言为C语言。那么， 语言是源语言， 语言是宿主语言， 语言是目标语言。 答案：A、C、B
(3)下面对编译原理的有关概念描述正确的是 。
A．目标语言只能是机器语言 B．编译程序处理的对象是源语言
C．Lex是语法分析自动生成器 D．解释程序属于编译程序 答案：c
(4) 是编译程序的组成部分。
A．词法分析程序 B．代码生成程序
c．设备管理程序 D．语法分析程序 答案：C
(5)下面对编译程序分为“遍”描述正确的是
A．分“遍”可以使编译程序结构清晰 B．可以提高程序的执行效率
C．可以提高机器的执行效率 D．可以增加对内存容量的要求 答案：A
(6)编译程序各阶段的工作都涉及到 ， 。
A．表格管理 B．语法分析 C．出错处理 D．代码优化 答案：A、C
(7)编译程序的生成方式可以是 ， ， 。 A．自编译 B．高级程序设计语言编写 C．完全自动生成 D．汇编语言缩写 答案：ABD
(8)设有表达式a*b—c，将其中a*b识别为表达式的编译阶段是 。 A．词法分析 B．语法分析 C．语义分析 D．代码生成 答案：B
(9)设一个编译器接收的源语言A，目标语言为B，宿主语言为C，则该编译器的符号表示是 。 答案：
(10)下面对编译程序分“遍”应考虑的因素描述不正确的是 。 A．源语言的特征和约束 B．代码优化的因素 C．编译程序的功能 D．目标代码的选择 答案：C I-2判断题
(I)解释执行与编译执行的根本区别在于解释程序对源程序没有真正进行翻译。 ( ) 答案：错
(2)宿主语言是目标机的目标语言。 ( ) 答案：错
(3)具有优化功能的编译器可以组织为一遍扫描的编译器。 ( ) 答案：错
(4)编译程序是将用某一种程序设计语言编写的源程序翻译成等价的另一种语言程序(目标程序。 ( ) 答案：错
(5)编译程序是应用软件。 ( ) 答案：错
(6)编译程序的基本组成中，词法分析、语法分析和语义分析应该是有序的。( ) 答案：对
(7)“遍”是指对源程序的从头到尾扫描。 ( ) 答案：错
(8)用高级语言书写的源程序都必须通过翻译，产生目标代码后才能运行。 ( ) 答案：对
(9)含有优化功能的编译程序执行效率高。 ( ) 答案：错
(10)解释程序和编译程序的不同在于，解释程序根据语法翻译成目标代码并立即执行之，而编译程序需产生中间代码及优化。 ( ) 答案：错 1-3简答题
(I)什么是编译程序? 答：把用某一种程序设计语言编写的源程序翻译成等价的另一种语言程序(目标程序)的程序，称之为编译程序。
(2)源程序的编译执行和解释执行的主要区别是什么?
答：一般编译程序从对源程序执行途径的角度不同，可分为解释执行和编译执行。所谓解释执行是借助于解释程序完成，即按源程序语句运行时的动态结构，直接逐句地边分析边翻译并执行。像自然语言翻译中的口译，随时进行翻译。所谓编译执行，是将源程序先翻译成一个等价的目标程序，然后再运行此目标程序，故编译执行分为编译阶段和运行阶段。
两种执行方式的主要区别是：编译执行是由编译程序生成一个与源程序等价的目标程序，它可以完全取代源程序，目标程序可运行任意多次，不必依赖编译程序。正像自然语言翻译中的笔译，一次翻译可多次阅读。而解释执行不生成目标程序，对源程序的每次执行都伴随着重新翻译的工作，而且不能摆脱翻译程序。
(3)典型的编译程序在逻辑功能上由哪几部分组成?各部分的功能是什么?
答：典型的编译程序在逻辑功能上由词法分析、语法分析、语义分析与中间代码生成、代码优化及目标代码生成五部分组成。各部分的简要功能是：
①词法分析的任务是对输入的符号串形式的源程序进行最初的加工处理。它依次扫描读入的源程序中的每个字符，根据源语言的词法规则识别出源程序中有独立意义的单词，用某种特定的数据结构对它的属性予以表示和标注。
②语法分析的任务是：在词法分析基础上，依据源语言的语法规则，对词法分析的结果进行语法检查，并识别出单词符号串所对应的语法范畴。 ③语义分析与中间代码生成的任务是：依据源语言的语义规则对语法分析所识别的语法范畴
进行语义检查并分析其含义，翻译成与其等价的中间代码。
④代码优化是为了改进目标代码的质量而在编译过程中进行的工作。代码优化可以在中间代码或目标代码级上进行，其实质是在不改变源程序语义的基础上对其进行加工变换，以期获得更高效的目标代码。而“高效”一般是指，对所产生的目标程序缩短其运行时间和节省存储空间。
⑤目标代码生成的功能是：根据中间代码及编译过程中产生的各种表格的有关信息，最终生成所期望的目标代码程序。
(4)编译程序实现的途径有哪些?
答：编译程序的实现途径即实现方式一般可以用高、中级程序设计语言编程实现，可以通过移植的方式实现，可以通过自编译的方式，还可以通过部分自动生成的方式实现。
(5)为不同目标机编写相同源语言的编译器时，其设计变化最大的是后端，为什么?
答：在编译程序构成的经典划分中，词法分析、语法分析及语义分析中间代码生成称为编译程序的前端，代码优化及代码生成称为后端。涉及前端的功能仅与源语言的词法、语法及语义相关适于自动生成。对后端实现的代码优化和代码生成，鉴于不同的目标机具有不同的体系结构和指令系统，代码优化和代码生成需要基于特定的目标机来设计和实现。
(6)简述编译程序中“出错处理”程序的作用。 答：“出错处理”作为编译程序的一个不可或缺的公共程序，其主要作用是对在编译过程中扫描、翻译源程序时根据文法规则和语义规则诊断源程序中存在的错误，对错误进行定性、定位和必要的容错处理。这样可以协助程序员及时准确地发现源程序中的错误，以提高调试程序的效率，方便用户修改程序，并能把错误限制在尽可能小的范围里。
(7)为不同目标机编写相同源语言的编译器时，其设计变化最大的是后端，为什么？
答：在编译程序构成的经典划分中，词法分析、语法分析及语义分析中间代码生成称为编译程序的前端，代码优化及代码生成称为后端。涉及前端的功能仅与源语言的词法、语法及语义相关适于自动生成。对后端实现的代码优化和代码生成，鉴于不同的目标机具有不同的体系结构和指令系统，代码优化和代码生成需要基于特定的目标机来设计和实现。
(8)简述编译程序中“出错处理”程序的作用。 答：“出错处理”作为编译程序的一个不可或缺的公共程序，其主要作用是对在编译过程中扫描、翻译源程序时根据文法规则和语义规则诊断源程序中存在的错误，对错误定性、定位和必要的容错处理。这样可以协助程序员及时准确地发现源程序中的错误，以提高调试程序的效率，方便用户修改程序，并能把错误限制在尽可能小的范围里。
第二章： 2．2 习题
2-1)选择、填空题
设有字母表A={0}，A˙={ 答案：，0，00，000 ．．．
用于描述另一种语言的语言称为 答案：元语言
(3)一个文法所描述的语言是一个无限集合,则该文法一定是 文法。 答案：递归
(4)下面不能用于对文法进行描述的是 。
A．源语言 B.EBNF C.BNF D.语法图 答案：A
(5)设有文法G的符号集V，非终结符集 ，终结符集，下列叙述中正确的是 。 A．V= B.V= C.V=
D. V=
答案：D
(6设文法G(S)为： S 0A A 1B B 0|0S 则L(G(S))为 。 A. B. C.
D.
答案：B
(7)设有文法G(S)为： S (B)a B Bb|b|
下列叙述错误的是 。 A.G是2型文法 B.
C.
D.有文法G'为S （）a|(B)a B bB|b，则G'=G
答案：C
(8)给定文法G(S)： S 0S|1A|0 A 1|1S|0B B 1A|0B
下列符号串是L(G)中元素的是 。
A．10100010011011 B. 0101001110010010 C．1101010011110111 D. 1010011101101010 答案：A
(9)设有文法G(S)：S S1|S0|Sa|Sc|a|b|c ，下列符号串中不是该文法的句子的是 A.ab0 B.a0c01 C.aaa D.bc10 答案：A
(10)设有文法G(S)：
。 S Bs|Aa| A bA|Ac C bCaS|a
下列符号串是L(G)中元素的是 。 A.
B.
C.
D.
答案：D
(11)设有文法G(S)： S aA|bC|a A aS|Bb B aC|bA|b C aB|bS
下述不为L(G)的句子的是 。 A.C.
B. D.
答案：B
(12)文法G(S)为： S aA A bB B a|aS 则L(G)为 。 A.C.答案：C
(13)设有文法G，满足
的文法G为 。
B. D.
A. S aSd|T T bcT|bc
B.S aSd|T T bTc|bc
C. S AB|B A aAd|ad B bBc|bc D. S Abc|A A aAd|ad 答案：B (14)语言
的文法G是 。
A. S Abb A aB|a B bB|b B.S Abb A Ba|a B aBb|b C. S Ab A aAb|a D. S aAb A Ab|aAb| 答案：D
(15)给出语言，其相应的文法G为 和 。
A. S aS|T T bcT|bc
B. S aS|T T bTc|bc
C. S AB|B A aA|a B bBc|bc D. S Abc|A A aA|a 答案：B、C (16)给出语言
L(G)=
，其相应的文法G为 。
A. S aSc|B B bB|b
B.S aS|T T bTc|bc C. S Abc|A A aA|a
D. S AB|A A aA|a B bBc|bc
答案：D
(17)设有语言L(G(S))={a}˙{b} ,下面描述该语言正确的文法是 。 A. S AB A Aa| B Bb|b B.S AB|AS A Aa|a B b C. S AB|AS A aA|a B Bb|
D. S SA|A A aAb|a 答案：B
(18)设有语言L(G)={由于相同个数(0或n)的a和b组成的句子}，满足对L(G)描述的正确的文法是 和 。
A. S abS| B. S aSbS|bSaS| C.S aSb|ab| D. S SS|aSb|bSa|
答案：B、D
(19)设定义在字母表{a,b,c,x,y,z}上的正规式r=(a|b|c)(x|y|z),则L(r)中元素有 个。 A. 9 B. 6 C. 18 D. 27 答案：A
(20)正规集L={a˙|n0}相应的正规式是 。 答案：
(21)设正规式r=(a|b)(x|y)˙,则下面错误的正规集元素是 。 A. abx B. bxxx C. a D.bxyyxxy 答案：A
(22)下述正规式中与(a˙|b˙)(c|d)等价的是 。 A.a˙(c|d)|b(c|d) B.a˙(c|d)˙|b(c|d) C.a˙(c|d)|b˙(c|d) D.(a|b)˙c|(a|b)˙d 答案：C
(23)有文法G(S):
S Ax|By A y|Ay B x|y
下面与文法G(S)表示相同语言的正规式是 。 A. y˙x|xy|y B. y˙x|x|xy C.yy˙X|xy|y D. yy˙x|xy|xy 答案：D
(24)有文法G(S)： S dA A a|aB
B aB|a|b|Bc C bC|b
下面与文法G(S)表示相同语言的正规式是 。 A. daa˙bb˙ B. daa˙b˙ C. daa˙ 答案：B
(25)设有文法G(S)： S AB|AS A aA|a B b
文法G(S)与下面正规式等价的是 。
A. aa˙bb˙ B. aa˙b˙ C. (ab)˙ 答案：B
(26)设文法G(S)： S aS|Sb|a|b
则文法G(S)所识别语言的正规式为 。 答案：
(27) 设文法G(A)： S Sab|bR R S|a
G(S)的语言L(G(S))={ }。 答案：
(28)设文法G(A)： A [B B X]|BA
X Xa|Xb|a|b
则文法G(A)所识别语言的正规式为 。 答案：
(29)设文法
G(V)：V aaV|bc
D. daa˙b D. a(ab)˙b
该文法对应的语言L(G)= 。 答案：
(30)已知语言：
则文法G(S)是 。 答案：S aaSb|ab|bb (31)设有语言：答案：S Sc|A A aAb|ab
(32)已知2型文法G(S)相对应的2型语言为：的文法G(S)可描述为 。 答案：S aSb|A A bAa|ba
(33) 不是DFA的构成成分。
A．有穷字母表 B．初始状态集合 C．终止状态集合 D．有限状态集合 答案：B
(34)有限自动机M和N等价是指 。
A．M和N的字母表相同 B．M和N状态数和有向边数相等 C．M和N状态数或有向边数相等 D．M和N识别的字符串集合相同 答案：D
(35)如果一个正规式所代表的集合是无穷的，则该正规式必含有的运算是 。 A．连接运算“.” B．或运算“|” C．闭包运算“*” D．括号“（）” 答案：C 2-2 判断题
（1）设有文法符号集V，则答案：错
（2）一部文法G的文法符号不属于。 （）
答案：对
（3）有文法G1=G2，则L(G1)=L(G2)。 （） 答案：对
（4）一个语言的文法是不唯一的。 （） 答案：对
（5）元语言是描述另一种语言的语言。 （） 答案：对
（6）BNF是一种广泛被采用的描述文法的工具。 （） 答案：对
。 （ ）
，则它
，则文法G(S)是 。
（7）文法G所描述的语言就是G的终结符号集的闭包。 （） 答案：错
（8）对于文法G（S）=（
，P,S），V=
，r是文法Ｇ（Ｓ）的句型当且仅当S=>r，
（）
且rV˙，ｒ是文法Ｇ（Ｓ）的句子当且仅当S=>，且r
答案：对
（９）文法Ｇ的一个句子对应于多个推导，则Ｇ是二义的。 （） 答案：错
（１０）对给定的文法Ｇ（Ｓ），若至少有一个句型存在两个或两个以上不同的最左（或最右）推导，这是判断Ｇ是二义文法的充分非必要条件。 （） 答案：错
（１１）对给定的文法Ｇ（Ｓ），若至少有一个句型存在两棵或两棵以上的不同的树，是判断Ｇ是二义文法的充分必要条件。 （） 答案：对
（１２）一棵分叉树反映了其叶节点从左向右连接形成的句型的任意推导情况。 （） 答案：错
（１３）ＮＦＡ和ＤＦＡ的区别之一是映射函数是否唯一。 （） 答案：对
（１４）一个正规式只能等价于一个确定的有限状态自动机。 （） 答案：错
（１５）任意有限自动机都鞥转化为一等价的特殊自动机；其状态图中初态无射入弧，终态无射出弧。 （） 答案：对
（１６）对任何正规集Ｌ，都有正规式Ｌ（ｒ）＝Ｌ。 （） 答案：对
（１７）设有ｒ和ｓ都是非∈的正规式，则有Ｌ（ｒｓ）＝Ｌ（ｓｒ）。 （） 答案：错
（１８）使用正规式运算能够描述定义在字母表上的所有符号串集合。 （） 答案：错
（１９）乔姆斯基把文法分为四种类型，即０型、１型、２型、３型。３型文法也称为正规文法，２型文法是短语文法。 （） 答案：错
（２０）正规式产生的语言都可以用上下文法来描述。 （） 答案：对
（２１）对任何正规式ｒ，都存在一个ＮＦＡＭ，满足Ｌ（Ｍ）＝Ｌ（ｒ）。 （） 答案：对
（２２）正规文法、正规式、ＮＦＡ和ＤＦＡ在接受语言的能力上是相互等价的。（） 答案：对
（２３）自动机Ｍ１和Ｍ２状态数不同，则二者必不等价。 （） 答案：错 （２４）一个有限自动机只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 （）
答案：错 （２５）一个有限自动机识别的语言是一个无限集合，则该有限自动机的状态图一定含有回路。 （） 答案：对
（２６）如果一个有限自动机接受空串∈，则他的状态转换图一定含有∈弧。（） 答案：错
（２７）一个确定的有限自动机，可以通过多条路识别一个符号串。 （） 答案：错
（２８）ＮＦＡ的确定化算法具有消除∈弧的功能。 （） 答案：对
（２９）正则文法一定不是二义文法。 （ ） 答案：错
（３０）对每一个左线性文法（ ） 答案：对
２－３ 简答题
（１）乔姆斯基分类法按照什么原则对文法进行分类？分成了几类？各有什么样的特点？ 答：按产生式的不同对文法进行分类。分为４类： ０型：产生式无限制。 １型：产生式限制为形如
，一定存在一个有线性文法
，使得Ｌ（
）＝Ｌ（
）。
２型：产生式限制为形如A 。 ３型：产生式限制为形如A
或A 或者(A B或A )。
（２）简要概述分析树的概念及其作用。
答：分析树的根节点是文法的开始符号，结点间的父子关系为产生式规则，即若父节点标识为Ａ，子结点从左到右依次标识为，
，则在文法中存在一产生式Ａ→
，
一棵分析树的从左到右的叶结点，就形成了由该分析树表示的推导出的句型。 分析树的生长过程是一个句子的推导过程，分析树额可以直观形象的表示经推导而产生的句子结构，有助于理解句子的语法结构层次。
（３）如何判断一部文法是二义文法？
答：对一部文法Ｇ，如果至少存在一个句子，对应两棵（或两棵以上）不同的分析树或有两个不同的最左推导，则这个文法是二义性的。
（４）简述正则表达式与有限自动机的等价性的证明思路，并简要说明每步要完成的基本工作或要解决的关键问题是什么？ 答：正则表达式与有限自动机的等价性的证明思路为正规式的合成与分解，或状态转换函数的合成与分解。
正则表达式→有限自动机：每步的基本工作是完成正规式的分解，即分解状态转换函数，增加状态图中的状态或弧。
有限自动机→正则表达式：每步的基本工作是完成正规式的合成，即合成状态转换函数，减少状态图中的状态或弧。
（５）简述ＮＦＡ和ＤＦＡ的区别。 答：ＮＦＡ和ＤＦＡ的区别是：
ＮＦＡ 的状态转换函数值是一个状态子集，反映在状态转换图上即从一状态结点出发可以有不止一条同一标记的弧。
ＮＦＡ可以带∈转换（不处理任何符号，就进行状态转换）。
第三章： 3.2 习题
3-1选择、填空题
（1）词法分析器的输入是 。
A、单词符号串 B、源程序 C、语法单位 D、目标程序 答案：B
（2）设有C语句的程序如下： while(i&&++j) {
c=2.19; j+=k; i++; }
则经过词法分析后可以识别的单词个数是 个。
A、19 B、20 C、21 D、23 答案：B
（3）下列选项中，不属于预处理程序要完成的功能的是 。
A、滤掉源程序中的注释 B、查找源程序中无用字符
C、运行宏替换 D、实现文件包含的嵌入和条件编译的嵌入 答案：B
（4）编译过程中扫描器的任务包括 。 1、组织源程序的输入
2、按词法规则分隔单词，识别出其属性，并转换成token串输出 3、删除注释
4、删除空格或无用字符 5、行计数，列计数 6、发现并定位词法错误 7、建立符号表
A、2 3 4 7 B、2 3 4 6 7 C、1 2 3 4 6 7 D、1 2 3 4 5 6 7
答案：D
（5）将识别各类单词的有限自动机合并后得到的有限自动机 。 A、可能是NFA 也可能是DFA B、一定是DFA
C、一定是NFA D、是最小的DFA 答案：A
（6）属性字是词法分析器对源程序中各单词处理后的 形势，也是单词在编译程序处理过程中的一种内部表示。
A、输入 B、内部 C、输出 D、外部 答案：C
（7）算术表达式123+45.6，词法分析后，下面的合法单词是 和 。 A、十进制数123 B、符号串123 C、数字串123 D、十进制数45.6 答案：AD
（8）C语言中的表达式a+++++++=1，词法分析后，能识别出的单词个数是 。 Ａ、１０ Ｂ、９ Ｃ、７ Ｄ、６ 答案：D
（９）在词法分析阶段不能识别的是 。
Ａ、标示符 Ｂ、运算符 Ｃ、四元式 Ｄ、常数 答案：C
（１０）词法分析程序的输入是 ，输出是 。 答案：源程序字符串、属性字符流
（１１）单词就是语言中具有独立意义的最小 单位。 答案：语法
（１２）属性字的二元组的表示式为 。 答案：<属性，值> （１３）构造识别单词的有限自动机时一般先对单词进行分类，构造识别各类单词的有限自动机，然后 各类有限自动机，构成一个能识别语言所有单词的有限自动机。 答案：合并
（１４）程序设计语言的单词符号一般分为：关键字、 、 、运算符和界符。 答案：标识符 、 常量
（１５）词法分析基于 型文法进行，即识别的单词是该类文法的句子。 答案：3
３－２ 判断题
（１）Ｌｅｘ是典型的词法分析程序。 （） 答案：错
（２）词法分析的依据是源语言的文法规则。 （） 答案：错
（３）源程序中的单词是具有独立意义的短语。 （） 答案：错
（４）单词的属性字一般应该包括单词类别和单词。 （） 答案：错
（５）编译的预处理程序的处理对象是源程序。 （） 答案：对
（６）在Ｃ语言中的一个语句 ｉｎｔ ｉｎｔｌ；词法分析后识别出ｉｎｔ、ｉｎｔ、ｌ
和；四个单词。 （） 答案：错
（７）一个字母或数字在Ｃ语言中不一定是单词，因为他们不一定具有独立的意义。 （） 答案：对 （８）构造识别单词的有限自动机时，先要对程序语言的单词按类构造出相应的有限自动机。 （） 答案：对
３－３ 简答题
（１）词法分析的任务是什么？
答：词法分析的任务是对输入的字符串形势的源程序按顺序进行扫描，在扫描的同时，根据源语言的词法规则识别具有独立意义的单词，并产生与其等价的属性字流作为输出。
（２）词法分析程序的基本功能有哪些？词法分析的实质是什么？ 答：词法分析的基本功能是读入字符串形势的源程序并识别出具有独立意义的最小语法单位-------单词，然后将单词变换成带有单词性质且定长的属性字。
词法分析的实质是依据词法规则，从读入的源程序中识别出具有独立意义的最小语法单位。
（３）词法分析中识别的单词具有什么特征？识别的依据是什么？ 答：词法分析中识别的单词具有的特征是具有独立意义并是最小语法单位，不满足任何一个条件都不是单词，识别的依据是词法规则。
（４）简述构造识别单词的有限自动机的方法与步骤。 答：构造识别单词的有限自动机的方法与步骤如下： 对程序语言的单词按类构造出相应的状态转换图。
对各类状态转换图进行合并，构成一个能识别语言所有单词的状态转换图，其合并方法为： 将各类单词的状态转换图的初始状态合并为一个唯一的初态。 化简并调整冲突的状态编号。
（５）实际的词法分析程序一般带有预处理子程序，简述预处理子程序的主要功能。
答：预处理子程序一般完成的主要功能是滤掉源程序中的注释、删除源程序中无用字符、进行宏替换、实现文件包含的嵌入和条件编译的嵌入登。
（６）何为超前搜索技术？ 答：在对源程序扫描过程中，比一般单词的识别超前搜索了多个符号后才得以确认为一单词的搜索技术成为超前搜索技术。
3－4 有如下Ｃ语言源程序段 int m; m=33;
printf(“ m=%d\\n”,m); 合法单词有哪些？
答：合法单词共14个，他们是int , m , ; , m , = , 33 , ; , printf , ( , “m=%d\\n” , , , m ,) 和；。
3-5 设计C语言全部运算符的属性字。
答：设计属性字的方法并不唯一，可以有多种方法。C语言全部运算符的属性字可简单设计如下：
(0,+) (1,-) (2,*) (3,/) (4,++) (5,--) (6,+=) (7,-=) (8,&) (9,&&) (10,<) (11,>) (12,=) (13,>>) (14,<<)。 第四章：
4.2习题
4-1 选择、填空
（1）自上而下语法分析主要分析动作是______。
A.移进 B. 推导 C. 归约 D.匹配 答案：B
（2）下面_______不属于LL（１）分析器的组成部分。 Ａ．LL（１）总控程序 B. LL（1）分析表 C. 分析栈 D. 源程序串 答案：D
（3）语法分析方法中的LL（1）分析方法属于_____分析方法。
A. 自左至右 B. 自上而下 Ｃ．自下而上 Ｄ．自右至左 答案：B
(4)设有文法的产生式：A 是 。 A． C．答案：A
(5)设有产生式：A 溯的条件是 。 A．B． C． D．
，且
。则在自上而下语法分析中对A推导不带回
B．
D．上述3个都不是
，则在自上而下语法分析中对A推导不带回溯的条件
答案：B
(6)下列文法中， 是LL(1)文法。（S是公理） A． S aSb|ab B．S ab|Sab C． S As|b D．S As|a 答案：C
(7)设有文法G(S)为： S AB|bC A |b B |aD C AD|b D aS|c
则FOLLOW(A)={ }，FIRST(S)={ }。 答案：FOLLOW(A)={ a ，c，# }，FIRST(S)={ a，b， } (8)设有文法G(S为开始符号)： S Ap|Bq A cA
B b|dB
FIRST(Ap)={ }。
A．a，c B．b，d C．p，q D其他答案． 答案：A
4-２判断题
(1)语法分析的任务是分析语句是如何构成的。 （ ） 答案：错
(2)语法分析必须在语义分析之前完成。 （ ） 答案：对
(3)自上而下语法分析实施的是最左推导。 （ ） 答案：对
(4)设有文法G： S Qq|q Q cQd|
该文法是LL(1)文法。 （ ） 答案：错
(5)LL(1)分析法中的“１”是指扫描源程序当前指针P++所指的源程序串的字符。 （ ） 答案：错
(6)自上而下分析及自下而上分析中的“下”指的是被分析的源程序串 （ ） 答案：对
(7)自上而下分析及自下而上分析中的“上”指的是分析树的根结点或文法的开始号。
（ ） 答案：对
(8)语法分析方法中的递归下降分析法属于自上而下分析方法。（） 答案：对
(9)文法若存在左递归，则在自上而下语法分析过程中会因为假匹配造成算法的回溯。 （ ） 答案：错
(10)LL（1）分析器必须满足文法不含左公因子和不含左递归。（） 答案：对
(11)LL（1）分析过程中使用的分析栈存放的是已经扫描且分析过的源程序串。 （ ） 答案：对
(12)LL（1）分析过程中使用的分析栈只能存放文法的终结符。（） 答案：错
(13)LL（1）分析的主要依据是LL（1）分析表。 （ ） 答案：对
(14)LL（1）中的“1”通过求FIRST得到。 （ ） 答案： 错
(15)设文法中有产生式T ，若采用递归下降分析方法，则T对应的函数是空函数。（） 答案：对
简答题
（1） 语法分析程序的功能及语法分析中要解决的基本问题是什么？
答：语法分析的任务是，按照语法的语法规则，对单词串形式的源程序进行语法检查，并识别出相应的语法成分。按照词法分析程序模型，语法分析程序处理的对象是此法分析器的输出，即属性字流形式的源程序，它的处理依据是语言的语法，其分析结果是识别出的无语法错误的语法成分（可以用分析树的形式来表示）。 语法分析程序要解决的问题是： 对给定的文法G和输入串
，判定
?即判定是否是文法G所能产生的句子，
同时处理语法错误。
（2）什么是自上而下分析？什么是自下而上分析？
答：自上而下分析是从文法Ｇ的开始符号Ｓ出发，通过反复使用文法的产生式，逐步推导得到输入串，则可以确认输入串是文法G的句子。
自下而上分析的过程是：从给定的输入串开始，逐步进行“归纳”，直至归约到文法的开始符号
（3）构造一个不带回溯的自上而下语法分析器对文法有何要求？为什么？
答：文法不含左递归，不含左公因子。因为文法含左递归会导致在自上而下分析中的最左推导无止境进行，使得分析算法陷入死循环；而文法含左公因子会导致分析过程要穷尽所有可能的推导，分析过程有回溯，使得分析器开销大，效率低。 （4）什么是LL（k）分析？
答：LL（k）分析是一种自上而下的分析方法。所谓LL（k）是指语法分析是按自左（第一个“L”）至右的顺序扫描输入字符串，并在分析过程中产生句子的最左推导（第二个“L”）。k则表示在分析过程中，每一步推导，最多只要向前查看（向右扫描）k个输入字符，既能确定当前推导所应选用的文法规则。
（6）LL（1）中的“1”的含义是什么？
答：LL（1）中的“1”表示在分析过程中，每一步推导，最多只要向前查看一个字符，既能确定当前推导所应选用的文法规则。 设有文法产生式：A ，当
时，LL(1)中的：“1”通过求FIRST()得到；当
时，
LL(1)中的“1”通过求FOLLOW(A)得到。
（7）递归下降分析方法的实现思想。
答：递归下降分析器的 基本构造方法是，对文法的每个非终结符号，都根据其产生的各个候选式的结构，为其编写一个对应的子程序（或函数），该子程序完成相应的非终结符对应的语法成分的识别和分析任务。因此，递归下井分析器的语法分析子程序的功能是，对某个非终结符，用规则的右部符号串去匹配输入串。分析过程是文法规则自上而下一级一级地调用有关子程序来完成的。
（8）自上而下分析和自下而上分析的异同是什么？ 答：自上而下分析和自下而上分析的扫描模式是一样的，都是对源程序实施从左向右的扫描。不同的是分析模式：自上而下分析是推导过程，二自下而上分析是归约的过程。
4—4 设有文法G和该文法的某个句子，如何判定$是文法G的合法语句？
解答：从文法G的开始符号，运用文法的产生式规则逐步推导出$,则可以判定$是合法语句。或从句子$开始不断运用文法的产生式规则进行归约，直至归约到文法的开始符号，则可以判定$是合法语句。 4—5 设有文法G(T)： T Qc|c Q Rb|b R Ta|a
说明文法G(T)是否为递归文法，为什么？
解答：根据文法G(T)，存在推导序列：T=Qc=Rbc=Tabc呈现出文法是左递归文法。 4—6 将下面的左递归文法G(S)改为非左递归的 S SaP|Sf|P P QbP|Q Q cSd|e
解答：改写后的文法： S PS' S' aPS'|fS'|e P QbP|Q Q cSd|e
4—7 设有文法G(A)： A BaC|CbB
B Ac|c C Bb|b
试消除G(A)的左递归。
解答：令文法G(A)的非终结符为A，B，C。
对于A，不存在直接左递归，将A带入B，代换后的B的规则变为： B BaCc|CbBc|c
B存在直接左递归，消除B的直接左递归有： B CbBcB'|cB' B' aCcB'|
将B代入C，代换后的C的规则变为： C CbBcB'b|cB'b|b
C存在直接左递归，消除C的直接左递归有; C cB'bC'|bC'
C' bBcB'bC'|
消除G(A)的左递归后的文法为： A BaC|CbB
B CbBcB'|cB' B' aCcB'| C cB'bC'|bC' C' bBcB'bC'| 4—8 设有文法G(A)： A Aab|a B Bb|d
(1)证明文法G(A)是否为LL(1) 文法？说明为什么？ (2)试改写文法为LL(1)文法。
解答：(1)文法G(A)不是LL(1)文法。因为G(A)含有左递归，含有左公因子。 (2)改写后的文法： A aA' A' AB| B dB' B' bB'|
验证：对A'有FIRST(AB)={a}FOLLOW(A')={#}= 对B'有FIRST(bB')={b}FOLLOW(B')={#}= 改写后的文法是LL(1) 文法。
第五章：
5.2 习题
5-1 选择、填空题
（1）自下而上语法分析的主要分析动作是_______。
A、 移进-归约 B、推导 C、归约 D、匹配 答案：A
（2）在“移进-归约”分析过程的每一步骤（出去到达接受状态），栈中的文法符号加上剩余输入符号恰好构成一个________。 答案：规范句型
（3）在算符优先分析过程中，终结符a 和b存在优先关系a 答案：当前输入指针指向的符号或输入串的当前符号 （4）下例文法中，_______是算符优先文法。 A.: S Aa A bB B a B. C. D. : S Aa A Bb B a : S aAB A b B a : S aSb|a 答案：B （5）算符优先分析中，可归约串是________。 A、句柄 B、活前缀 C、最左素短语 Ｄ、素短语 答案：C （6）设有文法（Ａ为开始符号）： A A+T|T T B|B B (A)|i 句型A+B˙i的所有短语有 ， ， ， 。 句型A+B˙i的所有素短语有 。 答案：句型A+B *i 的短语是：B，i，B*i，A+B*i；素短语是：i （７）下面对自下而上分析描述正确的是 。 Ａ、自下而上分析过程是对句子实施推导的过程 Ｂ、自下而上分析是从给定的输入串$开始，逐步进行“归约”，直至归约到文发的开始符号 Ｃ、自下而上分析是面向目标的 Ｄ、自下而上分析是规范归约的过程 答案：B （８）已知文法G（E）： E ET+IT T TF˙|F F F |a 文法的句型FF *中关于非终结符F的短语为 、 、 和 ；直接短语为 和 ；该句型的句柄为 ；素短语为 。 答案：短语为F、F 和 FF *；直接短语为FF ；该句型的句柄为F；素短语为F （9）YACC是用于_____ 的工具。 答案：LALR（1）语法分析器自动生成 （10）一个LR分析器的逻辑结构包括______、_______、和________三个部分。 答案：分析栈、LR 分析表、LR总控程序 （11）设有文法G=（{S}，{a}，{S SaS|}，S），该文法是 。 A．LL(1)文法 B．二义性文法 C．SLR(1)文法 D．算符优先文法 答案：B （12）采用LR分析时，若分析栈中有10个文法符号（不包括句子的左界符），则栈中应有______个状态。 A、8 B、9 C、10 D、11 答案：D （13）设有如下文法G（S是G的开始符号）： G：S A； A A B|BB； B c|c； 且有句型：B；c；c； ①请给出该句型的全部短语 ， ， 和 。 ②给出该句型的最左素短语 。 ③如果将该句型归约到文法的开始符号S，按照归约的先后次序，请写出依次规范归约的柄 ， ， ， 和 。 答案：①句型B；c；c；的全部短语为B、c；、c；、c；c；、B；c；c； ②句型B；c；c；的最左素短语为c；。 ③句型B；c；c；的一次归约的句柄为B、c；、c；、BB和A；A。 （14）设有文法G(E)=({E}，{i}，{E E+E|E *E|(E)|i}，E)，该文法是 。 ①算符文法 ②上下文无关文法 ③3型文法 ④二义性文法 可选项有： A．①② B．①②④ C．②④ D．①②③④ 答案：B （15）下列的LR(0)项可以在一个LR项目集中共存的是 、 、 。 A．A P·Q和B QP· B．A P·Q 和B PQ· C．A · 和B · D．A P ·Q 和B P·Q E．A P·和A · Q 答案：A、D、E 5-2判断题 （1） 算符优先分析法每次归约的都是句型的最左素短语。（） 答案：对 （2）最左素短语一定是短语。 （） 答案：对 （3）算符优先关系表不一定存在对应的优先函数。 （） 答案：对 （4）LR分析法每次归约的是当前句型的句柄 （） 答案：对 （5）LR（1）和SLR（1）中的“1”的含义无区别。 （） 答案：错 （6）LR分析中的活前缀一定包含某句型的句柄的一部分或全部。（） 答案：错 （7）自下而上分析的“上”指的是被分析的源程序串 （） 答案：错 （8）文法G若是LALR（1）文法，则文法G必是LR（1）文法（） 答案：对 （9）一个LR（0）的项目集可以对多个句型的活前缀有效。 （） 答案：对 （10）二义文法一定不是LR文法。 （） 答案：对 （11）YACC是编译程序自动生成工具。 （） 答案：错 （12）算符优先分析器每次归约的都为当前句型的素短语，二LR分析器归约的为当前句型的句柄。（） 答案：错 （13）采用LR分析时，使用右递归定义文法：L I，L|I 比使用左递归定义文法：L L， i|i更有效。 （） 答案：错 （14）LR的项目集中待约项目不会引起冲突。 （） 答案：对 （15）LALR（1）项目集中可以存在“移进-归约”或“归约-归约”冲突 （） 答案：错 5-3简答题 （1） 简述语法分析方法之一的自下而上分析的概念。 答：语法分析的任务是，按照语法的语法规则，对单词串形式的源程序进行语法检查，并识别出相应的语法成分。按照词法分析程序模型，语法分析程序处理的对象是此法分析器的输出，即属性字流形式的源程序，它的处理依据是语言的语法，其分析结果是识别出的无语法错误的语法成分（可以用分析树的形式来表示）。 语法分析程序要解决的问题是： 对给定的文法G和输入串 ，判定 ？即判定是否是文法G所能产生的句 子，同时同时处理语法错误。 （2） 自下而上分析技术的关键是什么？ 答：自上而下分析是从文法Ｇ的开始符号Ｓ出发，通过反复使用文法的产生式，逐步推导得到输入串$，则可以确认输入串$是文法G的句子。 自下而上分析的过程是：从给定的输入串$开始，逐步进行“归纳”，直至归约到文法的开始符号。 （3） 简述LR分析器的结构。 答：文法不含左递归，不含左公因子。因为文法含左递归会导致在自上而下分析中的最左推导无止境进行，使得分析算法陷入死循环；而文法含左公因子会导致分析过程要穷尽所有可能的推导，分析过程有回溯，使得分析器开销大，效率低。 （4） 不同的语法分析方法仅仅是分析识别的模式不同，而扫描模式都是一样的。 答：LL（k）分析是一种自上而下的分析方法。所谓LL（k）是指语法分析是按自左（第一个“L”）至右的顺序扫描输入字符串，并在分析过程中产生句子的最左推导（第二个“L”）。k则表示在分析过程中，每一步推导，最多只要向前查看（向右扫描）k个输入字符，既能确定当前推导所应选用的文法规则。 （5）构造一个算符优先分析器对文法有何要求？ 答：要求文法必须是算符优先文法，即文法的任何产生式中均不含两个相邻的非终结符，文法中不含A 形式规则，且文法中所有终结符号之间若存在优先关系则最多满足 这三种关系之一。 （6）什么是规范句型的活前缀？其引进的一样是什么？ 答：规范句型的一个不含句柄之后任何符号的前缀，成为该句型的一个活前缀。引入活前缀的目的是为了在LR分析过程中，始终使当前栈顶（或包含栈顶一下的若干符号）呈现某个规范句型的活前缀，当前栈顶刚好包含含有句柄的活前缀（也称为可归前缀）即可事实归约。所以引入活前缀的概念是为了查找LR分析中的可归约串句柄。 （7）什么是LR项目集规范族？ 答：识别文法G可归前缀的DFA项目集的全体称为文法G的LR项目集规范族。 （8）简述LR（0）项目中的“.”在LR分析中的含义。 答：LR（0）项目中的圆点可看成是分析栈栈顶与符号串的分界线，圆点左边进入分析栈的部分，即已经扫描并已分析了的符号串；圆点右边是尚未扫描分析的符号串或继续扫描的符号串。因此圆点标识了对于某个特定的候选式的识别状态。 （9）SLR（1）与LR（1）中的“1”有何区别？ 答：LR分析法是自下而上的语法分析方法。其中“L”是指对源程序的扫描式为自左向右扫描，“R”是指对源程序的分析模式，即实施最后推导（“R”）的逆序。 ＳＬＲ（１）与LR（1）中的“1”的区别是，是否是经规范归约得到的句型再向前查看一个输入符号即可决定当前分析动作。ＬＲ（１）要求一定是经规范归约得到的句型再向前查看一个输入符号，而ＳＬＲ（１）不一定是规范归约得到的句型再向前查看一个输入符号。SLR（1）中的“1”是通过FOLLOW集合求出的，ＬＲ（１）中的“１”是通过求搜索求出的。 （10）下述LR（0）项目可以成为一个LR的项目集吗？ 说明没有超前扫描的情况下答 不存在冲突。 ： （11）怎样构造识别文法活前缀的ＬＡＬＲ（１）项目规范族？ 答：构造识别文法活前缀的ＬＡＬＲ（１）项目集规范族方法和步骤如下： 首先，构造文法的LR（1）项目集规范族；然后判断LR（1）项目集规范族是否存在冲突，则该文法不是ＬＲ（１）的，当然也不是ＬＡＬＲ（１）的；若不存在冲突则该文法是ＬＲ（１）的，进一步判断ＬＲ（１）项目集规范族中是否存在同心项目集，若存在同心项目集则合并，合并同心项目集后的项目集即为ＬＡＬＲ（１）项目集。 说明：所谓同心项目集，即LR（1）项目集规范族中，若两个LR（1）项目集中的LR（0）项目相同，仅是搜索符不同，则这两个LR（1）项目集称为同心项目集。 （12）简述算符优先分析中的最左素短语的作用。 答：算符优先分析中的最左素短语是算符优先分析中的“可归约串”。 （13）简述算符有限分析法与一般自下而上分析的“可归约串”的区别。 答：算符优先分析方法通过定义算符（文法的终结符号）之间的某种优先关系来寻找、确定可归约串并进行归约，“可归约串”实际是当前句型的最左素短语。而一般自下而上分析，例如“移进-归约”分析，实施的是规范归约，即每步归约的都是当前规范句型的句柄。 5—4 设有下列文法： A abc|aBbc Bb bB Bc Cbcc bC Cb aC aa|aaB 试指出$1=abc，$2=abBc，$3=aaabBbcc是否为该文法的句型或句子。若是，求出全部 的短语和句柄。 解答：因为A=abc，故$1=abc是该文法的句子，短语为abc，句柄为abc。 因为A aBbc abBc，$2=abBc是该文法的句型，$1的短语为bB和abBc，句柄 为 bB。 $3=aaabBbcc不是该文法的句型或句子。 5—5 考虑对文法G，若其中某项目集为：I={A ˙ X，B ˙，C ˙ ····} 当X时，如何构造文法G的SLR(1)分析表。 解答：设FOLLOW(B)=S，FOLLOW(C)=T，FIRST(X)={)=R，且 则对 则对 则对 第六章： 6-1选择、填空题 (1)给定文法G： E E+T|T T T*F| F F i|(E) 则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为 。 A．iii*i*++ B．ii+iii**+ C．ii+ii*i*+ D．A，B，C都不正确 答案：C (2)中间代码生成时所依据的是 。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 答案：C (3)在编译程序中与生成中间代码的目的无关的是 。 A．便于目标代码优化 B．便于存储空间的组织 c．便于目标代码的移植 D．便于编译程序的移植 答案：D (4)在语法制导翻译中不采用拉链一返填技术的语句是 。 A．转向语句 B．赋值语句 c．条件语句 D。循环语句 答案：B (5)表达式—a+b*(—c+d)的逆波兰式是 。 A．ab+—cd+一* B．a—b+c—d+* C．a一6+cd— +* D．a一bc—d+*+ 答案：D (6)四元式表示法的优点为 。 A．便于表的变动，但不便于优化处理 B．不便于优化处理，但节省存储空间 c．便于表的变动，也节省存储空间 D．便于优化处理，也便于表的变动 答案：D (7)有一语法制导翻译文法如下： S，action(I，a)={用B 归约) T，action(I，a)={用C 归约) R，action(I，a)=“移进” S bAb(print”1”) A (B{print”2”) A a{print”3”) B aA){print”4”) 若输入序列为b(a(a(aa)))b，且采用自下而上的分析方法，则输出序列为 。 A．32224441 B．34242421 C．12424243 D．34442212 答案：B (8)四元式之间的联系是通过 实现的。 A．指示器 B．临时变量 C．程序变量 D．符号表 答案：B (9)中间代码是介于源语言程序和 之间的一种代码。 A．源代码 B．机器语言 C．汇编语言 D．目标代码 答案：D (10)给出C语句：a<=b+c&& a>d || a+b!=e，则该C语句的逆波兰表达式是 。 答案：abc+=ad&&ab+e!=|| 6·2判断题 (1)使用语法制导翻译方法的编译程序能同时进行语法分析和语义分析。 ( ) 答案：对 (2)拉链一返填的“返填”就是稍后填写转移指令的地址。 ( ) 答案：错 (3)对任何一个编译程序，产生中间代码是不可缺少的。 ( ) 答案：错 (4)三元式与间接三元式的主要区别在于是否有间接码表。 ( ) 答案：对 (5)语法制导翻译方法可用来产生各种中间代码，又可用来产生目标代码。 ( ) 答案：对 (6)逆波兰表示法表示表达式时无须使用括号。 ( ) 答案：对 (7)终结符既可以有综合属性，也可以有继承属性。 ( ) 答案：错 (8)三元式出现的先后顺序和表达式各部分的计值顺序并不一致。 ( ) 答案：错 (9)树形表示和三元式不便于优化，而间接三元式和四元式则便于优化。 ( ) 答案：对 (10)程序中不允许任何标识符先引用后定义。 ( ) 答案：错 6-3简答题 (1)语义分析的主要任务和工作。 解答：语义分析的主要任务是按照语法分析器识别的语法范畴进行语义处理，翻译成相应的中间代码或目标代码。 语义分析的工作包括在编译阶段语义分析和在目标程序运行阶段进行语义分析。 在编译阶段的语义分析主要进行静态的语义检查： ①类型检查 ②控制流检查。 ③唯一性检查。 ④关联名字检查。 在目标程序运行时语义分析主要收集各类语法成分的语义信息，并将收集到的语义信息存放到相应的信息表中。 (2)语法制导定义或翻译方案的作用与用途。 解答：语法制导翻译是对上下文无关文法制导下的语言进行翻译。实现思想是把语言结构的属性赋给代表语言结构的非终结符号，属性值由附加到文法产生式的“语义规则”计算，而语义规则的计算可以产生代码。将语义信息与语言的结构联系起来涉及到两个概念，一种称为语法制导定义，另一种称为翻译模式。语法制导定义是关于语言翻译的抽象规格说明，其中隐去实现细节，不规定翻译顺序。翻译模式则规定实现途径和细节，指明使用语义规则进行计算的顺序。 语法制导定义和翻译模式都在语法分析的基础上建立分析树，然后遍历分析树，按照分析树对语义规则进行计算。为此，可以通过生成代码、查填符号表、给出错误信息等，来完成各种翻译动作。因此，对语义规则计算的过程实际上就是对输入源程序串的翻译过程。 (3)类型检查如何应用于语义分析。 解答：①类型检查。例如程序中的运算符作用于不相容的运算对象，属于编译程序进行类型检查应该报告的错误。 ②控制流检查。引起控制流离开一个结构的语句必须指出控制流的转移目标。例如，C语言的break语句引起控制流离开最小包围的while、for或switch语句，如果这样的包围语句不存在，则是一个错误。 ③唯一性检查。例如，有些语言中，标识符必须唯一地声明，case语句的标号必须有区别，枚举类型的元素不能重复等都属于唯一性问题。 ④关联名字检查。有的语言要求同样的名字必须出现两次或多次。例如，在Ada语言中，循环或程序块可以有名字出现在它的开头和结尾，编译程序必须进行这类语法、语义的合法性检查。 (4)简述引人中间代码的目的。 解答：中间语言(中间代码)是一种面向语法，易于翻译成目标程序的源程序的等效内部表示代码。引人中间代码可以作为最后生成目标代码的过渡。生成中间代码时可以不考虑具体目标机的特性，因此使得产生中间代码的编译程序实现更容易一些。而且，这种中间代码形式与具体目标机无关，便于移植到其他机器上。另外，中间代码便于优化处理。 6—5把下面C语句翻译成四元式，并给出语义子程序。 while(A else While A<=D dO A=A+2 解答：假定第一条语句对应的标号是100，程序的语义子程序如下： 100(J<，A，C，102) 101(J， ， ，115) 102(J<，B，D，104) 103(J<， ， ，115) 104(J=，A，1，106) 105(J<， ， ，109) 106(+，C，1，T1) 107(=，T1， ，C) 108(j， ， ，100) 109(j<=，A，D，111) 110(j<， ， ，100) 111(+，A，2，T2) 112(=，T2， ，A) 113(j， ， ，109) 114{j， ， ，100) 其中，“j”表示无条件转移操作符。例如，(j，，，100)表示无条件转移到“100”标识的四元式。 “j<”表示条件转移操作符。例如，(j<，n，m，100)表示n “j=”表示条件转移操作符。例如，(j=，n，m，100)表示n=m时转移到“100”标识的四元式。 “j<=”表示条件转移操作符。例如，(j<，n，m，100)表示当n<=m时转移到“100”标识的四元式。 第七章： 7-1选择题 (1)动态存储分配可采用的分配方案是 。 A．队式存储分配 B．栈式存储分配 c．线性存储分配 D．链式存储分配 答案：B (2)静态存储分配允许程序出现 A．递归过程 B．可变体积的数据项 C．静态变量 D．待定性质的名字 答案：C (3)过程的DISPLAY表可反映 A．过程的连接数据 B．过程的嵌套层次 C．过程的返回地址 D．过程的人口地址 答案：B (4)堆式动态分配申请和释放存储空间允许 A．先申请的空间先释放 B．先申请的空间后释放 c．后申请的空间先释放 D．任意 答案：D (5)栈式存储分配不允许 。 A．动态数组 B．动态变量 C．静态数组 D．递归过程 答案：B (6)程序所需的数据空间在程序运行时才能确定，称为 管理技术。 A．静态存储 B．动态存储 C．栈式存储 D．堆式存储 答案：B (7)设Pascal语言的过程P的层数是k，则其DISPLAY表的长度应是 。 A．k一1 B．k+0 C．k4-1 D．k4-2 答案：C (8)栈式存储分配与管理在过程返回时应做的工作有 。 A．保护SP B．恢复SP C．保护TOP D．恢复TOP 答案：B (9)在C语言中，需要在运行阶段分配存储空间的是 。 A．外部变量 B．自动变量 C．静态变量 D．指针变量 答案：B (10)运行阶段的存储组织与管理的目的是 。 A．提高编译程序的运行速度 B．为运行阶段的存储分配做准备及提高目标程序的运行速度 C．优化运行空间的管理 D．节省内存空间 答案：B 7-2判断题 (1)DISPLAY表用来记录每层过程的最新活动记录地址，因此它的大小在运行时确定。 ( ) 答案：错 (2)由于C语言的函数允许递归调用，因此对C程序中的所有变量的单元分配一律采取动态分配方式。 ( ) 答案：错 (3)动态数组的存储空间在编译时就可完全确定。 ( ) 答案：错 (4)在C语言和Pascal语言中，由于允许用户动态申请和释放内存空间，所以必须采取栈式存储分配技术。 ( ) 答案：错 (5)静态数组的存储空间应在编译时确定。 ( ) 答案：对 (6)若过程P第k次被调用，则P的DISPLAY表中就有k4-1个元素。 ( ) 答案：错 (7)符号表在编译阶段非常重要，但符号表不会带入运行阶段。 ( ) 答案：错 (8)主程序(o层过程)无动态外层数据可访问，因此可以没有DISPLAY表。( ) 答案：错 (9)实参和形参的引用结合与换名结合相同。 ( ) 答案：错 (10)编译程序中存储组织与分配的重要原则是能在编译时予以分配的存储空间尽量采用静态分配。 ( ) 答案：对 7—3简答题 (1)栈式存储分配方案中，嵌套层次显示表DISPLAY的作用是什么? 解答：当程序的过程定义可以嵌套并允许递归调用时，一个过程在运行时将允许引用包围它的任一外层过程定义的变量，即可以引用这些外层过程的最新活动记录中的一些数据， 因此必须知道这些最新活动记录的起始地址(SP值)，以便存取这些变量，DISPLAY表就是用来记录这些SP值的。 运行阶段的存储组织与管理的目的是什么? 解答：运行阶段的存储组织与管理的目的：一是为运行阶段的存储分配作准备；二是提高目标程序的运行速度。 (2)过程活动记录包括哪些部分? 解答：过程活动记录包括变量实参域、局部临时变量域、机器状态域、返回地址域、存取链SL、控制链DL，其中存取链SL、控制链DL可选。 (3)堆式动态分配中，申请和释放存储空间遵循什么原则? 解答：堆式动态分配中，根据用户需要动态申请、释放数据空间，不同于栈式动态分配的先申请先释放、先申请后释放或后申请先释放等原则。 (4)C语言中使用函数sizeof，它的计算是在程序编译时完成还是在程序运行时完成?为什么? 解答：在编译时完成。因为C语言的每种数据类型的大小是确定的，所以编译时就可以完成存储空间的计算。 第八章 8-1选择、填空题 (1) 从优化所涉及的源程序的范围而言，可以把优化分为局部优化、和 答案：循环优化、全局优化 (2)编译中代码优化需要的技术准备主要包括 分析和 分析 答案：控制流分析、数据流分析 (3)下面对代码优化描述正确的是 。 A．代码优化可以产生高效的编译程序 B．代码优化会改变程序的执行顺序和功能 c．代码优化是对编译程序进行等价变换，使之能生成更加高效的目标代码 D．代码优化必须保证优化后的代码与源程序在语义上是完全等价的 答案：D (4)基本块DAG构造的过程中可以完成的优化工作包括 、 和 答案：常量合并与传播、无用赋值删除、公共子表达式删除 (5)程序流图中的循环结构一定具有 和 的特性。 答案：循环的入口结点唯一、强连通性(构成循环的结点间相互可达) (6)循环优化中可以实施的具体优化措施包括 和(或) 。 A．代码外提 B．强度削弱 c．函数内嵌 D．寄存器优化 答案：A、B (7)下列说法表述错误的是 。 A．控制流分析是数据流分析的基础 B．程序流图中的循环结构一定具有强连通性和人口结点的唯一性 C．活跃变量信息的采集和分析将为寻找程序中的无用赋值提供信息 D．循环优化中，利用各变量引用点的du链信息可以求出循环中的不变运算 答案：D (8)在语句Z—X*Y—H中，属于定义性出现的是 。 A．Z B．X C．Y D．H 答案：A (9)在语句Z_--X*Y++一K中，属于定义性出现的是 A．Z，X B．Z，Y C．Z，K D．Z 答案：b (10)设B1 B2：是一条回边，则下面的描述正确的是 和 A．B1 DOM B2 B．Bz DOM B1 C．包含B，和B。，循环由有通路到达B，且通路上不经过Bz的结点构成 D．包含B。和B。，循环由有通路到达B：且通路上不经过Bt的结点构成 答案：B、C (12)对下面的语句序列X=1：X=2：Y=X*X+4*X+4：IF Y>×THEN Z=Y—X：ELSE图8一l程序控制流图可以实施的优化措施不包括 ．。 A．常量合并 B．代码外提 C．死代码删除 D．无用赋值删除 答案：B (13)编译程序进行数据流分析的目的是 。 A．对基本块进行优化 B．对循环进行优化 C．进行全局优化 D．以上三者都是 答案：D (14)下面关于程序控制流图和DAG图的叙述中，错误的是 。 A．DAG图是无环有向图 B．DAG图反映的是函数间的关系 ． C．程序控制流图的一个结点一定是一个基本块 D．程序控制流图反映了基本块问的关系 答案：B (16)循环优化实施的合理步骤是 。 A．控制流分析一数据流分析一优化实施 B．数据流分析一控制流分析一优化实施 C．控制流分析或数据流分析一优化实施 D．上述三种都不对 答案：A (18)代码优化有可能对被优化的代码实施 A．部分代码删除 B.代码次序变更 C．改变算法 D.程序结构变更 答案：ABD (19)设有如下C语言程序： void main() f int i，sum； for(i=0；i sum+=funcl(i)j } ) int funcl《int a) ( return(a％50)； } 可以对该C语言程序采取的优化措施包括 。 A．常量合并 B．公共子表达式删除 C．死代码删除 D．函数嵌入 答案：D (20)提高程序运行效率的途径包括 A．改进算法 B．编译优化 C．使用高级语言编程 D．减少目标程序功能 答案：AB 8—2判断题 (1)含有优化功能的编译程序的执行效率高。 ( ) 答案：错 (2)优化是对被编译的程序进行变换，使之能生成更加高效的目标代码。 ( ) 答案：错 (3)编译阶段的优化是可以通过改进算法、在源程序级上的等价变换或充分利用系统提供的程序库等途径替代的。 ( ) 答案：错 (4)局部优化中使用的DAG图反映了基本块之间的关系。 ( ) 答案：错 (5)构造基本块DAG的过程就是对该基本块进行优化的过程。 ( ) 答案：对 (6)完成基本块优化必须进行控制流分析。 ( ) 答案：对 (7)要确定一个赋值是否有用仅考虑一个基本块即可。 ( ) 答案：错 (8)数据流方程求解一定会到达一个不动点。 ( ) 答案：对 (9)du链是指对于某变量引用点而言其定值信息。 ( ) 答案：错 (10)变量P在点d是活跃的是指P在点d被引用。 ( ) 答案：错 (11)ud链和du链是互逆的。 ( ) 答案：错 (12)可以在循环优化中实施的优化措施包括代码外提、强度削弱等。 ( ) 答案：对 (13)程序控制流图是一个无环路有向图。 ( ) 答案：错 (14)语句Z一一Y中Z只是定义性出现。 ( ) 答案：错 (15)程序控制流图中循环有且只有一个出口结点。 ( ) 答案：错 8-3简答题 (1) 编译器实施代码优化的目的是什么? 答案：代码优化的目的是在不改变程序运行效果的前提下，对编译的程序进行等价变换，以生成更加高效的目标代码，这里的高效是指空间效率和时间效率，即减少程序占用的存储空间和运行时间。 (2) 简述循环查找的步骤和方法。 答案：第一步：将程序划分为若干基本块，并基于基本块构成程序的控制流图。 第二步：计算程序控制流图中每个结点的必经结点集。 第三步：据所求的必经结点集在流图中查找回边。 第四步：根据回边确定循环。 (3) 从优化具体实施的角度可以进行哪些具体的优化? 答案：从优化具体实施的角度，可以进行的优化措施包括：常量合并与传播、公共子表达式删除、无用赋值删除、死代码删除、无用转移语句删除、循环不变量或不变代码外提、函数内嵌、循环转换等。还有其他针对目标机的具体优化措施。 (4) 编译中代码优化需要的技术准备主要是什么? 答案：实施代码优化的技术准备是根据具体实施的优化，完成控制流分析和数据流分析。 (5) 说明“定值一引用”链(du链)的作用。 答案：假设在程序中某点P对一个变量A定值，则把该定值能到达的A的引用点的全体，称为变量A在定值点P的定值一引用链，即du链。利用du链信息可以确定哪些变量的定值在某一个范围内不被引用，则在此范围内的定值也就成为无用赋值。 (6) 简述如何确定基本块。 答案：对于一个给定的程序，可以按照下述方法和步骤来确定基本块： 第一步：确定每个基本块的入口语句。根据基本块的特点，它的入口语句是下述三种类型的语句之一： ①程序的第一个语句。 ②有条件转移语句或无条件转移语句转移到的语句。 ③紧跟在条件转移和无条件转移语句后面的语句。 第二步：根据确定的基本块的人口语句，构造其所属的基本块： ①由人口语句直到下一个人口语句(不包含下一个人口语句)之间的所有语句构成一个基本块。 ②由入口语句到程序中的停止或暂停语句(包含该停止或者暂停语句)之间的语句序列组成的语句构成一个基本块。 第三步：凡是未包含在基本块中的语句，都是程序的控制流不可到达的语句，直接从程序中删除。