编译原理习题及答案1～.ppt

《编译原理习题及答案1～.ppt》由会员分享，可在线阅读，更多相关《编译原理习题及答案1～.ppt（274页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1编译原理教程编译原理教程习题解析习题解析第一章第一章 绪绪 论论第二章第二章 词词 法法 分分 析析第三章第三章 语语 法法 分分 析析2 2编译原理教程编译原理教程习题解析习题解析第一章绪论1.1完成下列选择题：(1)下面叙述中正确的是。A编译程序是将高级语言程序翻译成等价的机器语言程序的程序B机器语言因其使用过于困难，所以现在计算机根本不使用机器语言C汇编语言是计算机唯一能够直接识别并接受的语言D高级语言接近人们的自然语言，但其依赖具体机器的特性是无法改变的3 3编译原理教程编译原理教程习题解析习题解析(2)将编译过程分成若干“遍”是为了。A提高程序的执行效率B使程序的结构更加清晰C

2、利用有限的机器内存并提高机器的执行效率D利用有限的机器内存但降低了机器的执行效率(3)构造编译程序应掌握。A源程序B目标语言C编译方法DAC项4 4编译原理教程编译原理教程习题解析习题解析(4)编译程序绝大多数时间花在上。A出错处理B词法分析B目标代码生成 D表格管理(5)编译程序是对。A汇编程序的翻译B高级语言程序的解释执行C机器语言的执行D高级语言的翻译5 5编译原理教程编译原理教程习题解析习题解析【解答】(1)编译程序可以将用高级语言编写的源程序转换成与之在逻辑上等价的目标程序，而目标程序可以是汇编语言程序或机器语言程序。故选A。(2)分多遍完成编译过程可使整个编译程序的逻辑结构更加清晰

3、。故选B。(3)构造编译程序应掌握源程序、目标语言和编译方法这三方面内容。故选D。6 6编译原理教程编译原理教程习题解析习题解析(4)编译各阶段的工作都涉及到构造、查找或更新有关表格，即编译过程的绝大部分时间都用在造表、查表和更新表格的事务上。故选D。(5)由(1)可知，编译程序实际上实现了对高级语言程序的翻译。故选D。7 7编译原理教程编译原理教程习题解析习题解析1.2计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码

4、程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，然后再读入下一条源程序语句并解释执行，而所翻译的机器代码语句串在该语句执行后并不保留。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。8 8编译原理教程编译原理教程习题解析习题解析在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但

5、解释方式下的人机界面比编译型好，便于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。9 9编译原理教程编译原理教程习题解析习题解析1.3请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件

6、工具等诸因素对编译程序构造的影响。10 10编译原理教程编译原理教程习题解析习题解析图图1-1 编译程序总框图编译程序总框图 11 11编译原理教程编译原理教程习题解析习题解析第二章词法分析2.1完成下列选择题：(1)词法分析所依据的是。A语义规则B构词规则C语法规则D等价变换规则(2)词法分析器的输入是。A单词符号串B源程序C语法单位D目标程序12 12编译原理教程编译原理教程习题解析习题解析(3)词法分析器的输出是。A单词的种别编码B单词的种别编码和自身的值C单词在符号表中的位置D单词自身值(4)状态转换图(见图2-1)接受的字集为_。A以0开头的二进制数组成的集合B以0结尾的二进制数组成

7、的集合C含奇数个0的二进制数组成的集合D含偶数个0的二进制数组成的集合13 13编译原理教程编译原理教程习题解析习题解析图图2-1 习题习题2.1的的DFA M 14 14编译原理教程编译原理教程习题解析习题解析(5)对于任一给定的NFAM，一个DFAM，使L(M)=L(M)。A一定不存在 B一定存在C可能存在D可能不存在(6)DFA适用于。A定理证明 B语法分析C词法分析D语义加工15 15编译原理教程编译原理教程习题解析习题解析(7)下面用正规表达式描述词法的论述中，不正确的是。A词法规则简单，采用正规表达式已足以描述B正规表达式的表示比上下文无关文法更加简洁、直观和易于理解C正规表达式描

8、述能力强于上下文无关文法D有限自动机的构造比下推自动机简单且分析效率高(8)与(a|b)*(a|b)等价的正规式是。A(a|b)(a|b)*Ba*|b*C(ab)*(a|b)*D(a|b)*16 16编译原理教程编译原理教程习题解析习题解析【解答】(1)由教材第一章1.3节中的词法分析，可知词法分析所遵循的是语言的构词规则。故选B。(2)词法分析器的功能是输入源程序，输出单词符号。故选B。(3)词法分析器输出的单词符号通常表示为二元式：(单词种别，单词自身的值)。故选B。(4)虽然选项A、B、D都满足题意，但选项D更准确。故选D。17 17编译原理教程编译原理教程习题解析习题解析(5)NFA可

9、以有DFA与之等价，即两者描述能力相同；也即，对于任一给定的NFAM，一定存在一个DFAM，使L(M)=L(M)。故选B。(6)DFA便于识别，易于计算机实现，而NFA便于定理的证明。故选C。(7)本题虽然是第二章的题，但答案参见第三章节。即选C。(8)由于正则闭包R+=R*R=RR*，故(a|b)*(a|b)=(a|b)(a|b)*。故选A。18 18编译原理教程编译原理教程习题解析习题解析2.2什么是扫描器？扫描器的功能是什么？【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序

10、，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。19 19编译原理教程编译原理教程习题解析习题解析2.3设M=(x,y,a,b,f,x,y)为一非确定的有限自动机，其中f定义如下：f(x,a)=x,y fx,b=yf(y,a)=fy,b=x,y试构造相应的确定有限自动机M。【解答】对照自动机的定义M=(S,f,s0,Z)，由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M是一非确定有限自动机。先画出NFAM相应的状态图，如图2-2所示。2020编译原理教程编译原理教程习题解析习题解析图2-2习题2.3的NFAM

11、21 21编译原理教程编译原理教程习题解析习题解析用子集法构造状态转换矩阵，如表2-1所示。表2-1状态转换矩阵 将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到2222编译原理教程编译原理教程习题解析习题解析将图2-3所示的DFAM最小化。首先，将M的状态分成终态组1,2与非终态组0。其次，考察1,2。由于1,2a=1,2b=21,2，因此不再将其划分了，也即整个划分只有两组：0和1,2。令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的DFAM。图图2-3 习题习题2.3的的DFA M其状态转换图如图其状态转换图如图2-3

12、所示。所示。2323编译原理教程编译原理教程习题解析习题解析图2-4图2-3化简后的DFAM 2424编译原理教程编译原理教程习题解析习题解析2.4正规式(ab)*a与正规式a(ba)*是否等价？请说明理由。【解答】正规式(ab)*a对应的NFA如图2-5所示，正规式a(ba)*对应的NFA如图2-6所示。用子集法将图2-5和图2-6分别确定化为如图2-7(a)和(b)所示的状态转换矩阵，它们最终都可以得到最简DFA，如图2-8所示。因此，这两个正规式等价。2525编译原理教程编译原理教程习题解析习题解析图2-5正规式(ab)*a对应的NFA2626编译原理教程编译原理教程习题解析习题解析图2

13、-6正规式a(ba)*对应的NFA2727编译原理教程编译原理教程习题解析习题解析图2-7图2-5和图2-6确定化后的状态转换矩阵 2828编译原理教程编译原理教程习题解析习题解析图2-8最简DFA 2929编译原理教程编译原理教程习题解析习题解析实际上，当闭包*取0时，正规式(ab)*a与正规式a(ba)*由初态X到终态Y之间仅存在一条a弧。由于(ab)*在a之前，故描述(ab)*的弧应在初态结点X上；而(ba)*在a之后，故(ba)*对应的弧应在终态结点Y上。因此，(ab)*a和a(ba)*所对应的NFA也可分别描述为如图2-9(a)和(b)所示的形式，它们确定化并化简后仍可得到图2-8所

14、示的最简DFA。3030编译原理教程编译原理教程习题解析习题解析图2-9(ab)*a和a(ba)*分别对应的NFA 31 31编译原理教程编译原理教程习题解析习题解析2.5设有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-10所示。3232编译原理教程编译原理教程习题解析习题解析图2-10习题2.5的NFA3333编译原理教程编译原理教程习题解析习题解析用子集法将图2-10确定化，如图2

15、-11所示。由图2-11重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)0,213,54,67图2-11习题2.5的状态转换矩阵 3434编译原理教程编译原理教程习题解析习题解析按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-12所示。图2-12习题2.5的最简DFA 3535编译原理教程编译原理教程习题解析习题解析2.6有语言L=w|w(0,1)+，并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机(DFA)。【解答】对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和最后一个1之后，对0的个数没有要求

16、。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10*，画出与正规式对应的NFA，如图2-13所示。3636编译原理教程编译原理教程习题解析习题解析图2-13习题2.6的NFA3737编译原理教程编译原理教程习题解析习题解析用子集法将图2-13所示的NFA确定化，如图2-14所示由图2-14可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为012,4356,873838编译原理教程编译原理教程习题解析习题解析按顺序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-15所示。图图2-15 习题习题2.6的最简的最简DFA 3939编译原

17、理教程编译原理教程习题解析习题解析2.7已知正规式(a|b)*|aa)*b和正规式(a|b)*b。(1)试用有限自动机的等价性证明这两个正规式是等价的；(2)给出相应的正规文法。【解答】(1)正规式(a|b)*|aa)*b对应的NFA如图2-16所示。用子集法将图2-16所示的NFA确定化为DFA，如图2-17所示。4040编译原理教程编译原理教程习题解析习题解析图图2-16 正规式正规式(a|b)*|aa)*b对应的对应的NFA41 41编译原理教程编译原理教程习题解析习题解析图图2-17 图图2-16确定化后的状态转换矩阵确定化后的状态转换矩阵 4242编译原理教程编译原理教程习题解析习题

18、解析由于对非终态的状态1、2来说，它们输入a、b的下一状态是一样的，故状态1和状态2可以合并，将合并后的终态3命名为2，则得到表2-3(注意，终态和非终态即使输入a、b的下一状态相同也不能合并)。由此得到最简DFA，如图2-18所示。正规式(a|b)*b对应的NFA如图2-19所示。用子集法将图2-19所示的NFA确定化为如图2-20所示的状态转换矩阵。4343编译原理教程编译原理教程习题解析习题解析表2-3合并后的状态转换矩阵 4444编译原理教程编译原理教程习题解析习题解析图图2-18 习题习题2.7的最简的最简DFA 4545编译原理教程编译原理教程习题解析习题解析图图2-19 正规式正

19、规式(a|b)*b对应的对应的NFA 4646编译原理教程编译原理教程习题解析习题解析比较图2-20与图2-17，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的DFA如图2-18所示。因此，两个自动机完全一样，即两个正规文法等价。图图2-20 图图2-19确定化后的状态转换矩阵确定化后的状态转换矩阵4747编译原理教程编译原理教程习题解析习题解析2.8构造一个DFA，它接收=a,b上所有不含abb的字符串。解：=a,b上所有不含abb的字符串可表示为b*(a*b)a*。4848编译原理教程编译原理教程习题解析习题解析2.9构造一个DFA，它接收=a,b上所有含偶

20、数个a的字符串。解：=a,b上所有含偶数个a的字符串可表示为(b|ab*a)*4949编译原理教程编译原理教程习题解析习题解析2.10下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试：I=1;while(I=n)sun=sun+aI;I=I+1;请用正规表达式表示这个程序段可能的执行序列。【解答】用正规表达式表示程序段可能的执行序列为AT(BIT)*。5050编译原理教程编译原理教程习题解析习题解析2.9将图2-21所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。其中，X为初态，Y为终态。【解答】用子集法将NFA确定化，如图2-22所示。51 51编译原理教

21、程编译原理教程习题解析习题解析图图2-21 习题习题2.9的的NFA 5252编译原理教程编译原理教程习题解析习题解析图图2-22 习题习题2.9的状态转换矩阵的状态转换矩阵22,Y2,422,Y2,42,42,42,4,Y2,4,Y2,4,Y5353编译原理教程编译原理教程习题解析习题解析图2-22所对应的DFA如图2-23所示。对图2-23所示的DFA进行最小化。首先将状态分为非终态集和终态集两部分：0,1,2,5和3,4,6,7。由终态集可知，对于状态3、6、7，无论输入字符是a还是b的下一状态均为终态集，而状态4在输入字符b的下一状态落入非终态集，故将其划分为0,1,2,5，4，3,6

22、,7对于非终态集，在输入字符a、b后按其下一状态落入的状态集不同而最终划分为0，1，2，5，4，3,6,7按顺序重新命名为0、1、2、3、4、5，得到最简DFA如图2-24所示。5454编译原理教程编译原理教程习题解析习题解析图图2-23 习题习题2.9的的DFA 5555编译原理教程编译原理教程习题解析习题解析 图图2-24 习题习题2.9的最简的最简DFA 5656编译原理教程编译原理教程习题解析习题解析2.10有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放大于等于3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。(1)写出售货机售糖的正规表达式；(

23、2)构造识别上述正规式的最简DFA。【解答】(1)设a=1，b=2，则售货机售糖的正规表达式为a(b|a(a|b)|b(a|b)。(2)画出与正规表达式a(b|a(a|b)|b(a|b)对应的NFA，如图2-25所示。用子集法将图2-25所示的NFA确定化，如图2-26所示。5757编译原理教程编译原理教程习题解析习题解析图图2-25 习题习题2.10的的NFA5858编译原理教程编译原理教程习题解析习题解析由图2-26可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态，即最简状态0、1、2，3、4。图图2-26 习题习题2.10的状态转换矩阵的状态转换矩阵 5959

24、编译原理教程编译原理教程习题解析习题解析按顺序重新命名为0、1、2、3，则得到最简DFA，如图2-27所示。图图2-27 习题习题2.10的最简的最简DFA 6060编译原理教程编译原理教程习题解析习题解析第三章语法分析3.1完成下列选择题：(1)程序语言的语义需要用来描述。A上下文无关文法B上下文有关文法C正规文法 D短语文法(2)2型文法对应。A图灵机 B有限自动机C下推自动机 D线性界限自动机61 61编译原理教程编译原理教程习题解析习题解析(3)下述结论中，是正确的。A1型语言0型语言B2型语言1型语言C3型语言2型语言DAC均不成立(4)有限状态自动机能识别_。A上下文无关文法B上下

25、文有关文法C正规文法D短语文法(5)文法GS：SxSx|y所识别的语言是。AxyxB(xyx)*Cxnyxn(n0)Dx*yx*6262编译原理教程编译原理教程习题解析习题解析(6)只含有单层分枝的子树称为“简单子树”，则句柄的直观解释是。A子树的末端结点(即树叶)组成的符号串B简单子树的末端结点组成的符号串C最左简单子树的末端结点组成的符号串D最左简单子树的末端结点组成的符号串且该符号串必须含有终结符6363编译原理教程编译原理教程习题解析习题解析(7)下面对语法树错误的描述是。A根结点用文法GS的开始符S标记B每个结点用GS的一个终结符或非终结符标记C如果某结点标记为，则它必为叶结点D内部

26、结点可以是非终结符(8)由文法开始符S经过零步或多步推导产生的符号序列是。A短语B句柄C句型D句子6464编译原理教程编译原理教程习题解析习题解析(9)设文法GS：SSA|AAa|b则对句子aba的规范推导是。ASSASAAAAAaAAabAabaBSSASAAAAAAAaAbaabaCSSASAASAaSbaAbaabaDSSASaSAaSbaAbaaba 6565编译原理教程编译原理教程习题解析习题解析(10)如果文法GS是无二义的，则它的任何句子其。A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最右推导，但

27、它们对应的语法树相同(11)一个句型的分析树代表了该句型的。A推导过程 B归约过程C生成过程 D翻译过程6666编译原理教程编译原理教程习题解析习题解析(12)规范归约中的“可归约串”由定义。A直接短语B最右直接短语C最左直接短语D最左素短语(13)规范归约是指。A最左推导的逆过程B最右推导的逆过程C规范推导D最左归约的逆过程6767编译原理教程编译原理教程习题解析习题解析(14)文法GS：SaAcB|BdAAaB|cBbScA|b则句型aAcbBdcc的短语是。ABdBccCaDb(15)文法GE：EE+T|TTT*P|PP(E)|i则句型P+T+i的句柄和最左素短语是。AP+T和TBP和P

28、+TCi和P+T+i DP和P 6868编译原理教程编译原理教程习题解析习题解析(16)采用自顶向下分析，必须。A消除左递归B消除右递归C消除回朔D提取公共左因子(17)对文法GE：EE+S|SSS*F|FF(E)|i则FIRST(S)=。A(B(,iCiD(,)6969编译原理教程编译原理教程习题解析习题解析(18)确定的自顶向下分析要求文法满足。A不含左递归B不含二义性C无回溯DAC项(19)递归下降分析器由一组递归函数组成，且每一个函数对应文法的。A一个终结符B一个非终结符C多个终结符D多个非终结符(20)LL(1)分析表需要预先定义和构造两族与文法有关的集合。AFIRST和FOLLOW

29、BFIRSTVT和FOLLOWCFIRST和LASTVTDFIRSTVT和LASTVT7070编译原理教程编译原理教程习题解析习题解析(21)设a、b、c是文法的终结符且满足优先关系ab和bc,则。A必有acB必有caC必有baDAC都不一定成立(22)算符优先分析法要求。A文法不存在QR的句型且任何终结符对(a,b)满足ab、ab和ab三种关系B文法不存在QR的句型且任何终结符对(a,b)至多满足ab、ab和ab三种关系之一71 71编译原理教程编译原理教程习题解析习题解析C文法可存在文法可存在QR的句型且任何终结符对的句型且任何终结符对(a,b)至至多满足多满足ab、a b和和a b三种关

30、系之一三种关系之一D文法可存在文法可存在QR的句型且任何终结符对的句型且任何终结符对(a,b)满满足足ab、a b和和a b三种关系三种关系(23)任何算符优先文法任何算符优先文法 优先函数。优先函数。A有一个有一个 B没有没有 C有若干个有若干个 D可能有若干个可能有若干个(24)在算符优先分析中，用在算符优先分析中，用 来刻画可归约串。来刻画可归约串。A句柄句柄 B直接短语直接短语 C素短语素短语 D最左素短语最左素短语7272编译原理教程编译原理教程习题解析习题解析(25)下面最左素短语必须具备的条件中有错误的是下面最左素短语必须具备的条件中有错误的是 。A至少包含一个终结符至少包含一个

31、终结符 B至少包含一个非终结符至少包含一个非终结符 C除自身外不再包含其他素短语除自身外不再包含其他素短语 D在句型中具有最左性在句型中具有最左性(26)对文法对文法GS：Sb|(T)TT，S|S其其FIRSTVT(T)为为 。Ab,(Bb,)C，,b,(D，,b,)7373编译原理教程编译原理教程习题解析习题解析(27)对文法对文法GE：EE*T|T TT+i|i句子句子1+2*8+6归约的值为归约的值为 。A23 B42 C30 D17(28)下述下述FOLLOW集构造方法中错误的是集构造方法中错误的是 。A对文法开始符对文法开始符S有有#FOLLOW(S)B若有若有AB，则有，则有FIR

32、ST()FOLLOW(B)C若有若有AB，则有，则有FOLLOW(B)FOLLOW(A)D若有若有AB，则有，则有FOLLOW(A)FOLLOW(B)7474编译原理教程编译原理教程习题解析习题解析(29)若文法若文法GS的产生式有的产生式有AB出现，则对出现，则对A求求FOLLOW集正确的是集正确的是 。AFOLLOW(B)FOLLOW(A)BFIRSTVT(B)FOLLOW(A)CFIRST(B)FOLLOW(A)DLASTVT(B)FOLLOW(A)(30)下面下面 是自底向上分析方法。是自底向上分析方法。A预测分析法预测分析法 B递归下降分析法递归下降分析法 CLL(1)分析法分析法

33、D算符优先分析法算符优先分析法7575编译原理教程编译原理教程习题解析习题解析(31)下面下面 是采用句柄进行归约的。是采用句柄进行归约的。A算符优先分析法算符优先分析法 B预测分析法预测分析法 CSLR(1)分析法分析法 DLL(1)分析法分析法(32)一个一个 指明了在分析过程中某时刻能看到产生式指明了在分析过程中某时刻能看到产生式多大一部分。多大一部分。A活前缀活前缀 B前缀前缀 C项目项目 D项目集项目集(33)若若B为非终结符，则为非终结符，则AB为为 项目。项目。A接受接受 B归约归约 C移进移进 D待约待约7676编译原理教程编译原理教程习题解析习题解析(34)在在LR(0)的的

34、ACTION子表中，如果某一行中存在标子表中，如果某一行中存在标记为记为“rj”的栏，则的栏，则 。A该行必定填满该行必定填满rj B该行未填满该行未填满rj C其他行也有其他行也有rj DGOTO子表中也有子表中也有rj(35)LR分析法解决分析法解决“移进移进归约归约”冲突时，左结合冲突时，左结合意味着意味着 。A打断联系实行移进打断联系实行移进 B打断联系实行归约打断联系实行归约 C建立联系实行移进建立联系实行移进 D建立联系实行归约建立联系实行归约7777编译原理教程编译原理教程习题解析习题解析(36)LR分析法解决分析法解决“移进移进归约归约”冲突时，右结合冲突时，右结合意味着意味着

35、 。A打断联系实行归约打断联系实行归约 B建立联系实行归约建立联系实行归约 C建立联系实行移进建立联系实行移进 D打断联系实行移进打断联系实行移进7878编译原理教程编译原理教程习题解析习题解析【解答解答】(1)参见第四章节，语义分析不像词法分析和语法分参见第四章节，语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述，由于析那样可以分别用正规文法和上下文无关文法描述，由于语义是上下文有关的，因此语义分析须用上下文有关文法语义是上下文有关的，因此语义分析须用上下文有关文法描述。即选描述。即选B。(2)2型文法对应下推自动机。故选型文法对应下推自动机。故选C。(3)由于不存在

36、：由于不存在：3型语言型语言 2型语言型语言 1型语言型语言 0型型语言。故选语言。故选D。(4)3型文法即正规文法，它的识别系统是有限状态自型文法即正规文法，它的识别系统是有限状态自动机。故选动机。故选C。7979编译原理教程编译原理教程习题解析习题解析(5)由由SxSx|y可知该文法所识别的语言一定是：可知该文法所识别的语言一定是：y左左边出现的边出现的x与与y右边出现的右边出现的x相等。故选相等。故选C。(6)最左简单子树的末端结点组成的符号串为句柄。最左简单子树的末端结点组成的符号串为句柄。故选故选C。(7)内部结点内部结点(指非树叶结点指非树叶结点)一定是非终结符。故选一定是非终结符

37、。故选D。(8)由文法开始符由文法开始符S经过零步或多步推导产生的符号序经过零步或多步推导产生的符号序列一定是句型，仅当推导产生的符号序列全部由终结符组列一定是句型，仅当推导产生的符号序列全部由终结符组成时才是句子，即句子是句型的阵列。故选成时才是句子，即句子是句型的阵列。故选C。(9)规范推导即最右推导，也即每一步推导都是对句规范推导即最右推导，也即每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换。故选型中的最右非终结符用相应产生式的右部进行替换。故选D。8080编译原理教程编译原理教程习题解析习题解析(10)文法文法GS的一个句子如果能找到两种不同的最左的一个句子如果能找到两

38、种不同的最左推导推导(或最右推导或最右推导)，或存在两棵不同的语法树，则它的任，或存在两棵不同的语法树，则它的任何句子何句子其最左推导和最右推导对应的语法树必定相同。其最左推导和最右推导对应的语法树必定相同。故选故选A。(11)一个句型的分析树代表了该句型的归约过程。故一个句型的分析树代表了该句型的归约过程。故选选B。(12)规范归约中的规范归约中的“可归约串可归约串”即为句柄，也就是最即为句柄，也就是最左直接短语。故选左直接短语。故选C。(13)规范归约的逆过程是规范推导，而规范推导即为规范归约的逆过程是规范推导，而规范推导即为最右推导。故选最右推导。故选B。(14)由图由图3-1可知应选可

39、知应选A。81 81编译原理教程编译原理教程习题解析习题解析图图3-1 句型句型aAcbBdcc对应的语法树对应的语法树 8282编译原理教程编译原理教程习题解析习题解析(15)由图由图3-2可知，句柄可知，句柄(最左直接短语最左直接短语)为为P，最左素，最左素短语为短语为P+T。故选。故选B。(16)回溯使自顶向下分析效率降低，左递归使得自顶回溯使自顶向下分析效率降低，左递归使得自顶向下的分析无法实现；二者相比消除左递归更为重要。故向下的分析无法实现；二者相比消除左递归更为重要。故选选A。(17)FIRST(F)=(,i，而由，而由SF可知可知FIRST(F)FIRST(S)，即，即FIRS

40、T(S)=(,i。故选。故选B。(18)左递归和二义性将无法实现自顶向下分析，回溯左递归和二义性将无法实现自顶向下分析，回溯则使自顶向下分析效率下降。故选则使自顶向下分析效率下降。故选D。8383编译原理教程编译原理教程习题解析习题解析图图3-2 句型句型P+T+i对应的语法树及优先关系示意对应的语法树及优先关系示意 8484编译原理教程编译原理教程习题解析习题解析(19)递归下降分析器由一组递归函数组成，且每一个递归下降分析器由一组递归函数组成，且每一个函数对应文法的一个非终结符。故选函数对应文法的一个非终结符。故选B。(20)LL(1)分析表需要预先定义和构造两族与文法有分析表需要预先定义

41、和构造两族与文法有关的集合关的集合FIRST和和FOLLOW。故选。故选A。(21)由于由于ab和和bc并不能使选项并不能使选项A、B、C成立。故选成立。故选D。(22)由算法优先文法可知应选由算法优先文法可知应选B。(23)有些算符优先文法不存在优先函数；有些算符优有些算符优先文法不存在优先函数；有些算符优先文法存在优先函数，且只要存在一对优先函数，就存在先文法存在优先函数，且只要存在一对优先函数，就存在无穷多对优先函数。故选无穷多对优先函数。故选D。(24)在算符优先分析中是以在算符优先分析中是以“最左素短语最左素短语”来刻画可来刻画可归约串的。故选归约串的。故选D。8585编译原理教程编

42、译原理教程习题解析习题解析(25)最左素短语必须具备的三个条件是：最左素短语必须具备的三个条件是：至少包含至少包含一个终结符；一个终结符；除自身外不得包含其他素短语；除自身外不得包含其他素短语；在句在句型中具有最左性。故选型中具有最左性。故选B。(26)FIRSTVT(T)=，FIRSTVT(S)=b,(；由；由TS可知可知FIRSTV(S)FIRSTVT(T)，即，即FIRSTVT(T)=，,b,(。故选。故选C。(27)由图由图3-3可知应选可知应选B。(28)若有若有AB则有则有FOLLOW(A)FOLLOW(B)，即选项即选项C错。故选错。故选C。(29)若文法若文法GS的产生式有的产

43、生式有AB出现，则有出现，则有FIRST(B)FOLLOW(A)。故选。故选C。8686编译原理教程编译原理教程习题解析习题解析图图3-3 句子句子1+2*8+6的语法树及值变化示意的语法树及值变化示意 8787编译原理教程编译原理教程习题解析习题解析(30)自底向上的分析方法有算符优先分析法和自底向上的分析方法有算符优先分析法和LR分析分析法。故选法。故选D。(31)自底向上分析采用归约方法，但算符优先分析用自底向上分析采用归约方法，但算符优先分析用“最左素短语最左素短语”归约，而归约，而LR分析用分析用“句柄句柄”归约。归约。SLR(1)是是LR分析法的一种，故选分析法的一种，故选C。(3

44、2)在在LR分析中，一个项目指明了在分析过程的某个分析中，一个项目指明了在分析过程的某个时刻所看到产生式的多大一部分。故选时刻所看到产生式的多大一部分。故选C。(33)对文法对文法GS，S称为称为“接受接受”项目；形如项目；形如Aa的项目的项目(其中其中a为终结符为终结符)称为称为“移进移进”项目；形如项目；形如AB的项目的项目(其中其中B为非终结符为非终结符)称为称为“待约待约”项目。故项目。故选选D。8888编译原理教程编译原理教程习题解析习题解析(34)在在LR(0)的的ACTION子表中，如果某一行存在标子表中，如果某一行存在标注为注为“rj”的栏，则该行必定填满的栏，则该行必定填满r

45、j，而在，而在SLR(1)的的ACTION子表中，如果某一行存在标注为子表中，如果某一行存在标注为“rj”的栏，则的栏，则该行可能未填满该行可能未填满rj。因此选。因此选A。(35)LR分析法解决分析法解决“移进移进归约归约”冲突时，左结合冲突时，左结合意味着打断联系而实行归约，右结合意味着维持联系而实意味着打断联系而实行归约，右结合意味着维持联系而实行移进。故选行移进。故选B。(36)由由(35)可知应选可知应选C。8989编译原理教程编译原理教程习题解析习题解析3.2 令文法令文法GN为为 GN:ND|NDD0|1|2|3|4|5|6|7|8|9(1)GN的语言的语言L(G)是什么是什么?

46、(2)给出句子给出句子0127、34和和568的最左推导和最右推导。的最左推导和最右推导。9090编译原理教程编译原理教程习题解析习题解析【解答解答】(1)GN的语言的语言L(GN)是非负整数。是非负整数。(2)最左推导：最左推导：最右推导：最右推导：91 91编译原理教程编译原理教程习题解析习题解析3.3 已知文法已知文法GS为为SaSb|Sb|b，试证明文，试证明文法法GS为二义文法。为二义文法。【解答解答】由文法由文法GS：SaSb|Sb|b，对，对句子句子aabbbb可对应如图可对应如图3-4所示的两棵语法树。所示的两棵语法树。因此，文法因此，文法GS为二义文法为二义文法(对句子对句子

47、abbb也可也可画出两棵不同的语法树画出两棵不同的语法树)。9292编译原理教程编译原理教程习题解析习题解析图图3-4 句子句子aabbbb对应的两棵不同语法树对应的两棵不同语法树 9393编译原理教程编译原理教程习题解析习题解析3.4 已知文法已知文法GS为为SSaS|，试证明文法，试证明文法GS为二义文法。为二义文法。【解答解答】由文法由文法GS：SSaS|，句子，句子aa的语法树如图的语法树如图3-5所示。所示。由图由图3-5可知，文法可知，文法GS为二义文法。为二义文法。9494编译原理教程编译原理教程习题解析习题解析图图3-5 句子句子aa对应的两棵不同的语法树对应的两棵不同的语法树

48、 9595编译原理教程编译原理教程习题解析习题解析3.5 按指定类型，给出语言的文法。按指定类型，给出语言的文法。(1)L=aibj|ji0的上下文无关文法；的上下文无关文法；(2)字母表字母表=a,b上的同时只有奇数个上的同时只有奇数个a和奇数个和奇数个b的的所有串的集合的正规文法；所有串的集合的正规文法；(3)由相同个数由相同个数a和和b组成句子的无二义文法。组成句子的无二义文法。【解答解答】(1)由由L=aibj|ji0知，所求该语言对应知，所求该语言对应的上下文无关文法首先应有的上下文无关文法首先应有SaSb型产生式，以保证型产生式，以保证b的的个数不少于个数不少于a的个数；其次，还需

49、有的个数；其次，还需有SSb或或Sb型的产生型的产生式，用以保证式，用以保证b的个数多于的个数多于a的个数。因此，所求上下文无的个数。因此，所求上下文无关文法关文法GS为为GS：SaSb|Sb|b9696编译原理教程编译原理教程习题解析习题解析(2)为了构造字母表为了构造字母表=a,b上同时只有奇数个上同时只有奇数个a和奇数和奇数个个b的所有串集合的正规式，我们画出如图的所有串集合的正规式，我们画出如图3-6所示的所示的DFA，即由开始符，即由开始符S出发，经过奇数个出发，经过奇数个a到达状态到达状态A，或经过奇，或经过奇数个数个b到达状态到达状态B；而由状态；而由状态A出发，经过奇数个出发，

50、经过奇数个b到达状到达状态态C(终态终态)；同样，由状态；同样，由状态B出发经过奇数个出发经过奇数个a到达终态到达终态C。由图由图3-6可直接得到正规文法可直接得到正规文法GS如下：如下：GS：SaA|bB AaS|bC|b BbS|aC|a CbA|aB|9797编译原理教程编译原理教程习题解析习题解析图图3-69898编译原理教程编译原理教程习题解析习题解析(3)我们用一个非终结符我们用一个非终结符A代表一个代表一个a(即有即有Aa)，用，用一个非终结符一个非终结符B代表一个代表一个b(即有即有Bb)；为了保证；为了保证a和和b的个的个数相同，则在出现一个数相同，则在出现一个a时应相应地出