2022年贵州财经大学编译原理复习资料 .pdf

编译原理学习指导与习题解析第一章：1-1 选择、填空题(1)构造一个编译程序的三要素是，。答案： 源语言、目标语言和编译方法、技术及工具(2)被编译的语言为A 语言，编译的最终结果为B语言代码，编写编译程序的语言为C语言。那么，语言是源语言，语言是宿主语言，语言是目标语言。答案： A、C、B (3)下面对编译原理的有关概念描述正确的是。A目标语言只能是机器语言B编译程序处理的对象是源语言CLex是语法分析自动生成器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*bc，将其中 a*b 识别为表达式的编译阶段是。A词法分析B语法分析C语义分析D代码生成答案： B (9)设一个编译器接收的源语言A，目标语言为B，宿主语言为C，则该编译器的符号表示是。答案：(10)下面对编译程序分“遍”应考虑的因素描述不正确的是。A源语言的特征和约束B代码优化的因素C编译程序的功能D目标代码的选择答案： C I-2 判断题(I)解释执行与编译执行的根本区别在于解释程序对源程序没有真正进行翻译。( ) 答案： 错精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 31 页(2)宿主语言是目标机的目标语言。( ) 答案： 错(3)具有优化功能的编译器可以组织为一遍扫描的编译器。( ) 答案： 错(4)编译程序是将用某一种程序设计语言编写的源程序翻译成等价的另一种语言程序(目标程序。( ) 答案： 错(5)编译程序是应用软件。( ) 答案： 错(6)编译程序的基本组成中，词法分析、语法分析和语义分析应该是有序的。( ) 答案： 对(7)“遍”是指对源程序的从头到尾扫描。( ) 答案： 错(8)用高级语言书写的源程序都必须通过翻译，产生目标代码后才能运行。( ) 答案： 对(9)含有优化功能的编译程序执行效率高。( ) 答案： 错(10)解释程序和编译程序的不同在于，解释程序根据语法翻译成目标代码并立即执行之，而编译程序需产生中间代码及优化。( ) 答案： 错1-3 简答题(I)什么是编译程序? 答：把用某一种程序设计语言编写的源程序翻译成等价的另一种语言程序(目标程序 )的程序，称之为编译程序。(2)源程序的编译执行和解释执行的主要区别是什么? 答： 一般编译程序从对源程序执行途径的角度不同，可分为解释执行和编译执行。所谓解释执行是借助于解释程序完成，即按源程序语句运行时的动态结构，直接逐句地边分析边翻译并执行。像自然语言翻译中的口译，随时进行翻译。 所谓编译执行，是将源程序先翻译成一个等价的目标程序，然后再运行此目标程序，故编译执行分为编译阶段和运行阶段。两种执行方式的主要区别是：编译执行是由编译程序生成一个与源程序等价的目标程序，它可以完全取代源程序，目标程序可运行任意多次，不必依赖编译程序。正像自然语言翻译中的笔译， 一次翻译可多次阅读。而解释执行不生成目标程序，对源程序的每次执行都伴随着重新翻译的工作，而且不能摆脱翻译程序。(3)典型的编译程序在逻辑功能上由哪几部分组成?各部分的功能是什么? 答： 典型的编译程序在逻辑功能上由词法分析、语法分析、语义分析与中间代码生成、代码优化及目标代码生成五部分组成。各部分的简要功能是：词法分析的任务是对输入的符号串形式的源程序进行最初的加工处理。它依次扫描读入的源程序中的每个字符，根据源语言的词法规则识别出源程序中有独立意义的单词，用某种特定的数据结构对它的属性予以表示和标注。语法分析的任务是：在词法分析基础上，依据源语言的语法规则，对词法分析的结果进行语法检查，并识别出单词符号串所对应的语法范畴。语义分析与中间代码生成的任务是：依据源语言的语义规则对语法分析所识别的语法范畴精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 31 页进行语义检查并分析其含义，翻译成与其等价的中间代码。代码优化是为了改进目标代码的质量而在编译过程中进行的工作。代码优化可以在中间代码或目标代码级上进行，其实质是在不改变源程序语义的基础上对其进行加工变换，以期获得更高效的目标代码。而“高效”一般是指，对所产生的目标程序缩短其运行时间和节省存储空间。目标代码生成的功能是：根据中间代码及编译过程中产生的各种表格的有关信息，最终生成所期望的目标代码程序。(4)编译程序实现的途径有哪些? 答： 编译程序的实现途径即实现方式一般可以用高、中级程序设计语言编程实现，可以通过移植的方式实现，可以通过自编译的方式，还可以通过部分自动生成的方式实现。(5)为不同目标机编写相同源语言的编译器时，其设计变化最大的是后端，为什么? 答： 在编译程序构成的经典划分中，词法分析、 语法分析及语义分析中间代码生成称为编译程序的前端， 代码优化及代码生成称为后端。涉及前端的功能仅与源语言的词法、语法及语义相关适于自动生成。对后端实现的代码优化和代码生成，鉴于不同的目标机具有不同的体系结构和指令系统，代码优化和代码生成需要基于特定的目标机来设计和实现。(6)简述编译程序中“出错处理”程序的作用。答： “出错处理”作为编译程序的一个不可或缺的公共程序，其主要作用是对在编译过程中扫描、翻译源程序时根据文法规则和语义规则诊断源程序中存在的错误，对错误进行定性、定位和必要的容错处理。这样可以协助程序员及时准确地发现源程序中的错误，以提高调试程序的效率，方便用户修改程序，并能把错误限制在尽可能小的范围里。(7)为不同目标机编写相同源语言的编译器时，其设计变化最大的是后端，为什么？答： 在编译程序构成的经典划分中，词法分析、 语法分析及语义分析中间代码生成称为编译程序的前端， 代码优化及代码生成称为后端。涉及前端的功能仅与源语言的词法、语法及语义相关适于自动生成。对后端实现的代码优化和代码生成，鉴于不同的目标机具有不同的体系结构和指令系统，代码优化和代码生成需要基于特定的目标机来设计和实现。(8)简述编译程序中“出错处理”程序的作用。答： “出错处理”作为编译程序的一个不可或缺的公共程序，其主要作用是对在编译过程中扫描、 翻译源程序时根据文法规则和语义规则诊断源程序中存在的错误，对错误定性、 定位和必要的容错处理。这样可以协助程序员及时准确地发现源程序中的错误，以提高调试程序的效率，方便用户修改程序，并能把错误限制在尽可能小的范围里。第二章：22 习题2-1)选择、填空题设有字母表A=0，A = 答案：，0，00，000 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 31 页用于描述另一种语言的语言称为答案： 元语言(3)一个文法所描述的语言是一个无限集合,则该文法一定是文法。答案： 递归(4)下面不能用于对文法进行描述的是。A源语言B.EBNF C.BNF D.语法图答案： A (5)设有文法 G 的符号集V，非终结符集，终结符集，下列叙述中正确的是。AV=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)中元素的是。A10100010011011 B. 0101001110010010 C1101010011110111 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|精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 31 页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.B.C.D.答案： B (12)文法 G(S) 为：S aA A bB B a|aS 则 L(G)为。A.B.C.D.答案： C (13)设有文法G，满足的文法 G 为。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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 31 页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. yx|x|xy C.yy X|xy|y D. yyx|xy|xy 答案： D (24)有文法 G(S)：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 31 页S dA A a|aB B aB|a|b|Bc C bC|b 下面与文法G(S)表示相同语言的正规式是。A. daabbB. daabC. daaD. daa b 答案： B (25)设有文法G(S)：S AB|AS A aA|a B b 文法 G(S)与下面正规式等价的是。A. aabbB. aabC. (ab)D. a(ab)b 答案： 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 该文法对应的语言L(G)= 。答案：(30)已知语言：则文法 G(S) 是。答案： S aaSb|ab|bb 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 31 页(31)设有语言：，则文法G(S)是。答案： 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 的字母表相同BM 和 N 状态数和有向边数相等CM 和 N 状态数或有向边数相等DM 和 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是一种广泛被采用的描述文法的工具。（）答案： 对（7）文法 G 所描述的语言就是G 的终结符号集的闭包。（）答案： 错（8）对于文法G （ S ）=（，P ,S） ，V=，r 是文法（） 的句型当且仅当S=r，且 rV ，是文法（）的句子当且仅当S=，且 r（）答案： 对精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 31 页（）文法的一个句子对应于多个推导，则是二义的。（）答案： 错（）对给定的文法（），若至少有一个句型存在两个或两个以上不同的最左（或最右）推导，这是判断是二义文法的充分非必要条件。（）答案：错（）对给定的文法（），若至少有一个句型存在两棵或两棵以上的不同的树，是判断是二义文法的充分必要条件。（）答案： 对（）一棵分叉树反映了其叶节点从左向右连接形成的句型的任意推导情况。（）答案： 错（）和的区别之一是映射函数是否唯一。（）答案： 对（）一个正规式只能等价于一个确定的有限状态自动机。（）答案 ：错（） 任意有限自动机都鞥转化为一等价的特殊自动机；其状态图中初态无射入弧，终态无射出弧。（）答案： 对（）对任何正规集，都有正规式（）。（）答案： 对（）设有和都是非的正规式，则有（）（）。（）答案： 错（）使用正规式运算能够描述定义在字母表上的所有符号串集合。（）答案： 错（）乔姆斯基把文法分为四种类型，即型、型、型、型。型文法也称为正规文法，型文法是短语文法。（）答案： 错（）正规式产生的语言都可以用上下文法来描述。（）答案： 对（）对任何正规式，都存在一个，满足（）（）。（）答案： 对（）正规文法、正规式、和在接受语言的能力上是相互等价的。（）答案： 对（）自动机和状态数不同，则二者必不等价。（）答案： 错（） 一个有限自动机只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）答案： 错（） 一个有限自动机识别的语言是一个无限集合，则该有限自动机的状态图一定含有回路。（）答案：对（）如果一个有限自动机接受空串，则他的状态转换图一定含有弧。（）答案： 错（）一个确定的有限自动机，可以通过多条路识别一个符号串。（）答案： 错精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 31 页（）的确定化算法具有消除弧的功能。（）答案： 对（）正则文法一定不是二义文法。（）答案： 错（）对每一个左线性文法，一定存在一个有线性文法，使得（）（） 。（）答案： 对简答题（）乔姆斯基分类法按照什么原则对文法进行分类？分成了几类？各有什么样的特点？答： 按产生式的不同对文法进行分类。分为类：型：产生式无限制。型：产生式限制为形如型：产生式限制为形如A 。型：产生式限制为形如A 或 A 或者 (A B 或 A )。（）简要概述分析树的概念及其作用。答：分析树的根节点是文法的开始符号，结点间的父子关系为产生式规则，即若父节点标识为 ，子 结点从左到右依次标识为， 则在文法中存在一产生式 ， 一棵分析树的从左到右的叶结点，就形成了由该分析树表示的推导出的句型。分析树的生长过程是一个句子的推导过程，分析树额可以直观形象的表示经推导而产生的句子结构，有助于理解句子的语法结构层次。（）如何判断一部文法是二义文法？答： 对一部文法，如果至少存在一个句子，对应两棵（或两棵以上）不同的分析树或有两个不同的最左推导，则这个文法是二义性的。（）简述正则表达式与有限自动机的等价性的证明思路，并简要说明每步要完成的基本工作或要解决的关键问题是什么？答：正则表达式与有限自动机的等价性的证明思路为正规式的合成与分解，或状态转换函数的合成与分解。正则表达式有限自动机：每步的基本工作是完成正规式的分解，即分解状态转换函数，增加状态图中的状态或弧。有限自动机正则表达式：每步的基本工作是完成正规式的合成，即合成状态转换函数，减少状态图中的状态或弧。（）简述和的区别。答： 和的区别是：的状态转换函数值是一个状态子集，反映在状态转换图上即从一状态结点出发可以有不止一条同一标记的弧。可以带转换（不处理任何符号，就进行状态转换）。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 31 页第三章：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，词法分析后，下面的合法单词是和。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 31 页A、十进制数123 B、符号串123 C、数字串123 D、十进制数45.6 答案： AD （8）C语言中的表达式a+=1，词法分析后，能识别出的单词个数是。、答案： D （）在词法分析阶段不能识别的是。、标示符、运算符、四元式、常数答案： C （）词法分析程序的输入是，输出是。答案： 源程序字符串、属性字符流（）单词就是语言中具有独立意义的最小单位。答案 ：语法（）属性字的二元组的表示式为。答案： （） 构造识别单词的有限自动机时一般先对单词进行分类，构造识别各类单词的有限自动机，然后各类有限自动机，构成一个能识别语言所有单词的有限自动机。答案： 合并（）程序设计语言的单词符号一般分为：关键字、运算符和界符。答案： 标识符、常量（）词法分析基于型文法进行，即识别的单词是该类文法的句子。答案： 3 判断题（）是典型的词法分析程序。（）答案： 错（）词法分析的依据是源语言的文法规则。（）答案： 错（）源程序中的单词是具有独立意义的短语。（）答案： 错（）单词的属性字一般应该包括单词类别和单词。（）答案： 错（）编译的预处理程序的处理对象是源程序。（）答案： 对（） 在语言中的一个语句；词法分析后识别出、和；四个单词。（）答案： 错（）一个字母或数字在语言中不一定是单词，因为他们不一定具有独立的意义。（）答案： 对（）构造识别单词的有限自动机时，先要对程序语言的单词按类构造出相应的有限自动机。（）答案： 对简答题精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 31 页（）词法分析的任务是什么？答：词法分析的任务是对输入的字符串形势的源程序按顺序进行扫描，在扫描的同时， 根据源语言的词法规则识别具有独立意义的单词，并产生与其等价的属性字流作为输出。（）词法分析程序的基本功能有哪些？词法分析的实质是什么？答： 词法分析的基本功能是读入字符串形势的源程序并识别出具有独立意义的最小语法单位-单词，然后将单词变换成带有单词性质且定长的属性字。词法分析的实质是依据词法规则，从读入的源程序中识别出具有独立意义的最小语法单位。（）词法分析中识别的单词具有什么特征？识别的依据是什么？答：词法分析中识别的单词具有的特征是具有独立意义并是最小语法单位，不满足任何一个条件都不是单词，识别的依据是词法规则。（）简述构造识别单词的有限自动机的方法与步骤。答： 构造识别单词的有限自动机的方法与步骤如下：对程序语言的单词按类构造出相应的状态转换图。对各类状态转换图进行合并，构成一个能识别语言所有单词的状态转换图，其合并方法为：将各类单词的状态转换图的初始状态合并为一个唯一的初态。化简并调整冲突的状态编号。（）实际的词法分析程序一般带有预处理子程序，简述预处理子程序的主要功能。答：预处理子程序一般完成的主要功能是滤掉源程序中的注释、删除源程序中无用字符、进行宏替换、实现文件包含的嵌入和条件编译的嵌入登。（）何为超前搜索技术？答：在对源程序扫描过程中，比一般单词的识别超前搜索了多个符号后才得以确认为一单词的搜索技术成为超前搜索技术。34有如下语言源程序段int m; m=33; printf( “ m=%dn” ,m); 合法单词有哪些？答： 合法单词共14 个，他们是int , m , ; , m , = , 33 , ; , printf , ( , “ m=%dn ” , , , m ,) 和； 。3-5 设计 C语言全部运算符的属性字。答： 设计属性字的方法并不唯一，可以有多种方法。C 语言全部运算符的属性字可简单设计如下：(0,+) (1,-) (2,*) (3,/) (4,+) (5,-) (6,+=) (7,-=) (8,&) (9,&) (10,) (12,=) (13,) (14,)。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 31 页第四章：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 推导不带回溯的条件是。ABCD上述 3 个都不是答案： A (5)设有产生式： A ，且。则在自上而下语法分析中对A 推导不带回溯的条件是。ABCD答案： B (6)下列文法中，是 LL(1)文法。 （ S是公理）A S aSb|ab BS ab|Sab C S As|b DS 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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 31 页FIRST(Ap)= 。Aa，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 对应的函数是空函数。 （）答案： 对简答题精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 31 页（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）自上而下分析和自下而上分析的异同是什么？答： 自上而下分析和自下而上分析的扫描模式是一样的，都是对源程序实施从左向右的扫描。不同的是分析模式：自上而下分析是推导过程，二自下而上分析是归约的过程。44 设有文法G 和该文法的某个句子，如何判定 $是文法 G 的合法语句？解答：从文法 G 的开始符号， 运用文法的产生式规则逐步推导出$,则可以判定 $是合法语句。或从句子 $开始不断运用文法的产生式规则进行归约，直至归约到文法的开始符号，则可以判定 $是合法语句。45 设有文法G(T)：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 31 页T Qc|c Q Rb|b R Ta|a 说明文法G(T)是否为递归文法，为什么？解答： 根据文法G(T)，存在推导序列：T=Qc=Rbc=Tabc呈现出文法是左递归文法。46 将下面的左递归文法G(S)改为非左递归的S SaP|Sf|P P QbP|Q Q cSd|e 解答： 改写后的文法：S PS S aPS|fS|e P QbP|Q Q cSd|e 47 设有文法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 CbBcBb|cBb|b C存在直接左递归，消除C的直接左递归有; C cBbC|bC C bBcBbC|消除 G(A)的左递归后的文法为：A BaC|CbB B CbBcB|cB B aCcB|C cBbC|bC C bBcBbC|48 设有文法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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 31 页A AB|B dB B bB|验证：对A有 FIRST(AB)=aFOLLOW(A)=#=对 B有 FIRST(bB)=bFOLLOW(B)=#=改写后的文法是LL(1) 文法。第五章：5.2 习题5-1选择、填空题（1）自下而上语法分析的主要分析动作是_。A、 移进 -归约B、推导C、归约D、匹配答案： A （2）在“移进 -归约”分析过程的每一步骤（出去到达接受状态），栈中的文法符号加上剩余输入符号恰好构成一个_。答案： 规范句型（3）在算符优先分析过程中，终结符 a 和 b 存在优先关系ab，则表示符号a位置在栈顶，符号 b 的位置是 _。答案： 当前输入指针指向的符号或输入串的当前符号（4）下例文法中，_是算符优先文法。A.: S Aa A bB B a B.: S Aa A Bb B a C.: S aAB A b B a D.: S aSb|a 答案： B（5）算符优先分析中，可归约串是_。A、句柄B、活前缀C、最左素短语、素短语答案： C （6）设有文法（为开始符号）：A A+T|T T B|B B (A)|i 句型 A+Bi 的所有短语有，。句型 A+Bi 的所有素短语有。答案： 句型 A+B *i 的短语是： B，i，B*i，A+B*i；素短语是：i （）下面对自下而上分析描述正确的是。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 31 页、自下而上分析过程是对句子实施推导的过程、自下而上分析是从给定的输入串$开始，逐步进行“归约” ，直至归约到文发的开始符号、自下而上分析是面向目标的、自下而上分析是规范归约的过程答案： 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 ） ，该文法是。ALL(1)文法B二义性文法CSLR(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 型文法二义性文法可选项有：ABCD答案： B （15）下列的 LR(0)项可以在一个LR项目集中共存的是、。AA PQ 和 B QPBA PQ 和 B PQCA 和 B DA P Q 和 B PQ EA P和 A Q 答案： A、D、 E 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 31 页5-2 判断题（1）算符优先分析法每次归约的都是句型的最左素短语。（）答案： 对（2）最左素短语一定是短语。（）答案： 对（3）算符优先关系表不一定存在对应的优先函数。（）答案： 对（4）LR分析法每次归约的是当前句型的句柄（）答案： 对（5）LR （1）和 SLR （1）中的“ 1”的含义无区别。（）答案： 错（6）LR分析中的活前缀一定包含某句型的句柄的一部分或全部。（）答案： 错（7）自下而上