编译原理习题及答案1～3(课堂PPT).ppt

资源描述

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

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

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

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

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

6、词法分析,2.1,完成下列选择题：,(1),词法分析所依据的是,。,A,语义规则,B,构词规则,C,语法规则,D,等价变换规则,(2),词法分析器的输入是,。,A,单词符号串,B,源程序,C,语法单位,D,目标程序,11,(3),词法分析器的输出是,。,A,单词的种别编码,B,单词的种别编码和自身的值,C,单词在符号表中的位置,D,单词自身值,(4),状态转换图,(,见图,2-1),接受的字集为,_,。,A,以,0,开头的二进制数组成的集合,B,以,0,结尾的二进制数组成的集合,C,含奇数个,0,的二进制数组成的集合,D,含偶数个,0,的二进制数组成的集合,12,图,2-1,习题,2.

7、1,的,DFA M,13,(5),对于任一给定的,NFA M,，,一个,DFA M,，使,L(M)=L(M),。,A,一定不存在,B,一定存在,C,可能存在,D,可能不存在,(6)DFA,适用于,。,A,定理证明,B,语法分析,C,词法分析,D,语义加工,14,(7),下面用正规表达式描述词法的论述中，不正确的是,。,A,词法规则简单，采用正规表达式已足以描述,B,正规表达式的表示比上下文无关文法更加简洁、直观和易于理解,C,正规表达式描述能力强于上下文无关文法,D,有限自动机的构造比下推自动机简单且分析效率高,(8),与,(a|b)*(a|b),等价的正规式是,。,A,(a|b)(a|b)*

8、B,a*|b*,C,(ab)*(a|b)*D,(a|b)*,15,【,解答,】,(1),由教材第一章,1.3,节中的词法分析，可知词法分析所遵循的是语言的构词规则。故选,B,。,(2),词法分析器的功能是输入源程序，输出单词符号。故选,B,。,(3),词法分析器输出的单词符号通常表示为二元式：,(,单词种别，单词自身的值,),。故选,B,。,(4),虽然选项,A,、,B,、,D,都满足题意，但选项,D,更准确。故选,D,。,16,(5)NFA,可以有,DFA,与之等价，即两者描述能力相同；也即，对于任一给定的,NFA M,，一定存在一个,DFA M,，使,L(M)=L(M),。故选,B,。,(

9、6)DFA,便于识别，易于计算机实现，而,NFA,便于定理的证明。故选,C,。,(7),本题虽然是第二章的题，但答案参见第三章,3.1.3,节。即选,C,。,(8),由于正则闭包,R+=R*R=RR*,，故,(a|b)*(a|b)=(a|b)(a|b)*,。故选,A,。,17,2.2,什么是扫描器？扫描器的功能是什么？,【,解答,】,扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给

10、语法分析器。,18,2.3,设,M=(x,y,a,b,f,x,y),为一非确定的有限自动机，其中,f,定义如下：,f(x,a)=x,y fx,b=y,f(y,a)=fy,b=x,y,试构造相应的确定有限自动机,M,。,【,解答,】,对照自动机的定义,M=(S,f,s0,Z),，由,f,的定义可知,f(x,a),、,f(y,b),均为多值函数，因此,M,是一非确定有限自动机。先画出,NFA M,相应的状态图，如图,2-2,所示。,19,图,2-2,习题,2.3,的,NFA M,20,用子集法构造状态转换矩阵，如表,2-1,所示。,表,2-1,状态转换矩阵,将转换矩阵中的所有子集重新命名，形成表,

11、2-2,所示的状态转换矩阵，即得到,21,将图,2-3,所示的,DFA M,最小化。首先，将,M,的状态分成终态组,1,2,与非终态组,0,。其次，考察,1,2,。由于,1,2a=1,2b=2,1,2,，因此不再将其划分了，也即整个划分只有两组：,0,和,1,2,。令状态,1,代表,1,2,，即把原来到达,2,的弧都导向,1,，并删除状态,2,。最后，得到如图,2-4,所示的化简了的,DFA M,。,图,2-3,习题,2.3,的,DFA M,其状态转换图如图,2-3,所示。,22,图,2-4,图,2-3,化简后的,DFA M,23,2.4,正规式,(ab)*a,与正规式,a(ba)*,是否等价

12、？请说明理由。,【,解答,】,正规式,(ab)*a,对应的,NFA,如图,2-5,所示，正规式,a(ba)*,对应的,NFA,如图,2-6,所示。用子集法将图,2-5,和图,2-6,分别确定化为如图,2-7(a),和,(b),所示的状态转换矩阵，它们最终都可以得到最简,DFA,，如图,2-8,所示。因此，这两个正规式等价。,24,图,2-5,正规式,(ab)*a,对应的,NFA,25,图,2-6,正规式,a(ba)*,对应的,NFA,26,图,2-7,图,2-5,和图,2-6,确定化后的状态转换矩阵,27,图,2-8,最简,DFA,28,实际上，当闭包*取,0,时，正规式,(ab)*a,与正规

13、式,a(ba)*,由初态,X,到终态,Y,之间仅存在一条,a,弧。由于,(ab)*,在,a,之前，故描述,(ab)*,的弧应在初态结点,X,上；而,(ba)*,在,a,之后，故,(ba)*,对应的弧应在终态结点,Y,上。因此，,(ab)*a,和,a(ba)*,所对应的,NFA,也可分别描述为如图,2-9(a),和,(b),所示的形式，它们确定化并化简后仍可得到图,2-8,所示的最简,DFA,。,29,图,2-9 (ab)*a,和,a(ba)*,分别对应的,NFA,30,2.5,设有,L(G)=a,2n+1,b,2m,a,2p+1,|n0,p0,m1,。,(1),给出描述该语言的正规表达式；,(

14、2),构造识别该语言的确定有限自动机,(,可直接用状态图形式给出,),。,【,解答,】,该语言对应的正规表达式为,a(aa)*bb(bb)*a(aa)*,，正规表达式对应的,NFA,如图,2-10,所示。,31,图,2-10,习题,2.5,的,NFA,32,用子集法将图,2-10,确定化，如图,2-11,所示。,由图,2-11,重新命名后的状态转换矩阵可化简为,(,也可由最小化方法得到,),0,2 1 3,5 4,6 7,图,2-11,习题,2.5,的状态转换矩阵,33,按顺序重新命名为,0,、,1,、,2,、,3,、,4,后得到最简的,DFA,，如图,2-12,所示。,图,2-12,习题,2

15、.5,的最简,DFA,34,2.6,有语言,L=w|w(0,1)+,，并且,w,中至少有两个,1,，又在任何两个,1,之间有偶数个,0,，试构造接受该语言的确定有限状态自动机,(DFA),。,【,解答,】,对于语言,L,，,w,中至少有两个,1,，且任意两个,1,之间必须有偶数个,0,；也即在第一个,1,之前和最后一个,1,之后，对,0,的个数没有要求。据此我们求出,L,的正规式为,0*1(00(00)*1)*00(00)*10*,，画出与正规式对应的,NFA,，如图,2-13,所示。,35,图,2-13,习题,2.6,的,NFA,36,用子集法将图,2-13,所示的,NFA,确定化，如图,2

16、-14,所示由图,2-14,可看出非终态,2,和,4,的下一状态相同，终态,6,和,8,的下一状态相同，即得到最简状态为,0 1 2,4 3 5 6,8 7,37,按顺序重新命名为,0,、,1,、,2,、,3,、,4,、,5,、,6,，则得到最简,DFA,，如图,2-15,所示。,图,2-15,习题,2.6,的最简,DFA,38,2.7,已知正规式,(a|b)*|aa)*b,和正规式,(a|b)*b,。,(1),试用有限自动机的等价性证明这两个正规式是等价的；,(2),给出相应的正规文法。,【,解答,】(1),正规式,(a|b)*|aa)*b,对应的,NFA,如图,2-16,所示。用子集法将图

17、,2-16,所示的,NFA,确定化为,DFA,，如图,2-17,所示。,39,图,2-16,正规式,(a|b)*|aa)*b,对应的,NFA,40,图,2-17,图,2-16,确定化后的状态转换矩阵,41,由于对非终态的状态,1,、,2,来说，它们输入,a,、,b,的下一状态是一样的，故状态,1,和状态,2,可以合并，将合并后的终态,3,命名为,2,，则得到表,2-3(,注意，终态和非终态即使输入,a,、,b,的下一状态相同也不能合并,),。由此得到最简,DFA,，如图,2-18,所示。正规式,(a|b)*b,对应的,NFA,如图,2-19,所示。用子集法将图,2-19,所示的,NFA,确定化

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

19、*,。,47,2.9,构造一个,DFA,，它接收,=a,b,上所有含偶数个,a,的字符串。,解：,=a,b,上所有含偶数个,a,的字符串可表示为,(b|ab*a)*,48,2.10,下列程序段以,B,表示循环体，,A,表示初始化，,I,表示增量，,T,表示测试：,I=1;,while(I=n),sun=sun+aI;,I=I+1;,请用正规表达式表示这个程序段可能的执行序列。,【,解答,】,用正规表达式表示程序段可能的执行序列为,AT(BIT)*,。,49,2.9,将图,2-21,所示的非确定有限自动机,(NFA),变换成等价的确定有限自动机,(DFA),。其中，,X,为初态，,Y,为终态。,

20、【,解答,】,用子集法将,NFA,确定化，如图,2-22,所示。,50,图,2-21,习题,2.9,的,NFA,51,图,2-22,习题,2.9,的状态转换矩阵,2,2,Y,2,4,2,2,Y,2,4,2,4,2,4,2,4,Y,2,4,Y,2,4,Y,52,图,2-22,所对应的,DFA,如图,2-23,所示。对图,2-23,所示的,DFA,进行最小化。首先将状态分为非终态集和终态集两部分：,0,1,2,5,和,3,4,6,7,。由终态集可知，对于状态,3,、,6,、,7,，无论输入字符是,a,还是,b,的下一状态均为终态集，而状态,4,在输入字符,b,的下一状态落入非终态集，故将其划分为,

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

22、(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,所示。,56,图,2-25,习题,2.10,的,NFA,57,由图,2-26,可看出，非终态,2,和非终态,3,面对输入符号,a,或,b,的下一状态相同，故合并为一个状态，即最简状态,0,、,1,、,2,，,3,、,4,。,图,2-26,习题,2.10,的状态转换矩阵,58

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

24、B,上下文有关文法,C,正规文法,D,短语文法,(5),文法,GS,：,SxSx|y,所识别的语言是,。,A,xyx B,(xyx)*,C,xnyxn(n0)D,x*yx*,61,(6),只含有单层分枝的子树称为“简单子树”，则句柄的直观解释是,。,A,子树的末端结点,(,即树叶,),组成的符号串,B,简单子树的末端结点组成的符号串,C,最左简单子树的末端结点组成的符号串,D,最左简单子树的末端结点组成的符号串且该符号串必须含有终结符,62,(7),下面对语法树错误的描述是,。,A,根结点用文法,GS,的开始符,S,标记,B,每个结点用,GS,的一个终结符或非终结符标记,C,如果某结点标记为,

25、，则它必为叶结点,D,内部结点可以是非终结符,(8),由文法开始符,S,经过零步或多步推导产生的符号序列是,。,A,短语,B,句柄,C,句型,D,句子,63,(9),设文法,GS,：,SSA|A,Aa|b,则对句子,aba,的规范推导是,。,A,S,SA,SAA,AAA,aAA,abA,aba,B,S,SA,SAA,AAA,AAa,Aba,aba,C,S,SA,SAA,SAa,Sba,Aba,aba,D,S,SA,Sa,SAa,Sba,Aba,aba,64,(10),如果文法,GS,是无二义的，则它的任何句子,其,。,A,最左推导和最右推导对应的语法树必定相同,B,最左推导和最右推导对应的语法

26、树可能不同,C,最左推导和最右推导必定相同,D,可能存在两个不同的最右推导，但它们对应的语法树相同,(11),一个句型的分析树代表了该句型的,。,A,推导过程,B,归约过程,C,生成过程,D,翻译过程,65,(12),规范归约中的“可归约串”由,定义。,A,直接短语,B,最右直接短语,C,最左直接短语,D,最左素短语,(13),规范归约是指,。,A,最左推导的逆过程,B,最右推导的逆过程,C,规范推导,D,最左归约的逆过程,66,(14),文法,GS,：,SaAcB|Bd,AAaB|c,BbScA|b,则句型,aAcbBdcc,的短语是,。,A,Bd B,cc C,a D,b,(15),文法,

27、GE,：,EE+T|T,TT*P|P,P(E)|i,则句型,P+T+i,的句柄和最左素短语是,。,A,P+T,和,T B,P,和,P+T,C,i,和,P+T+i D,P,和,P,67,(16),采用自顶向下分析，必须,。,A,消除左递归,B,消除右递归,C,消除回朔,D,提取公共左因子,(17),对文法,GE,：,EE+S|S,SS*F|F,F(E)|i,则,FIRST(S)=,。,A,(B,(,i,C,i D,(,),68,(18),确定的自顶向下分析要求文法满足,。,A,不含左递归,B,不含二义性,C,无回溯,D,A,C,项,(19),递归下降分析器由一组递归函数组成，且每一个函数对应文法

28、的,。,A,一个终结符,B,一个非终结符,C,多个终结符,D,多个非终结符,(20)LL(1),分析表需要预先定义和构造两族与文法有关的集合,。,A,FIRST,和,FOLLOW B,FIRSTVT,和,FOLLOW,C,FIRST,和,LASTVT D,FIRSTVT,和,LASTVT,69,(21),设,a,、,b,、,c,是文法的终结符且满足优先关系,ab,和,bc,则,。,A,必有,ac B,必有,ca,C,必有,ba D,A,C,都不一定成立,(22),算符优先分析法要求,。,A,文法不存在,QR,的句型且任何终结符对,(a,b),满足,ab,、,ab,和,ab,三种关系,B,文法不

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

30、一个非终结符,C,除自身外不再包含其他素短语,D,在句型中具有最左性,(26),对文法,GS,：,Sb|(T),TT,，,S|S,其,FIRSTVT(T),为,。,A,b,(B,b,),C,，,b,(D,，,b,),72,(27),对文法,GE,：,EE*T|T,TT+i|i,句子,1+2*8+6,归约的值为,。,A,23 B,42 C,30 D,17,(28),下述,FOLLOW,集构造方法中错误的是,。,A,对文法开始符,S,有,#FOLLOW(S),B,若有,AB,，则有,FIRST()FOLLOW(B),C,若有,AB,，则有,FOLLOW(B)FOLLOW(A),D,若有,AB,，则

31、有,FOLLOW(A)FOLLOW(B),73,(29),若文法,GS,的产生式有,AB,出现，则对,A,求,FOLLOW,集正确的是,。,A,FOLLOW(B)FOLLOW(A),B,FIRSTVT(B)FOLLOW(A),C,FIRST(B)FOLLOW(A),D,LASTVT(B)FOLLOW(A),(30),下面,是自底向上分析方法。,A,预测分析法,B,递归下降分析法,C,LL(1),分析法,D,算符优先分析法,74,(31),下面,是采用句柄进行归约的。,A,算符优先分析法,B,预测分析法,C,SLR(1),分析法,D,LL(1),分析法,(32),一个,指明了在分析过程中某时刻能

32、看到产生式多大一部分。,A,活前缀,B,前缀,C,项目,D,项目集,(33),若,B,为非终结符，则,AB,为,项目。,A,接受,B,归约,C,移进,D,待约,75,(34),在,LR(0),的,ACTION,子表中，如果某一行中存在标记为“,rj”,的栏，则,。,A,该行必定填满,rj B,该行未填满,rj,C,其他行也有,rj D,GOTO,子表中也有,rj,(35)LR,分析法解决“移进,归约”冲突时，左结合意味着,。,A,打断联系实行移进,B,打断联系实行归约,C,建立联系实行移进,D,建立联系实行归约,76,(36)LR,分析法解决“移进,归约”冲突时，右结合意味着,。,A,打断联系

33、实行归约,B,建立联系实行归约,C,建立联系实行移进,D,打断联系实行移进,77,【,解答,】,(1),参见第四章,4.1.1,节，语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述，由于语义是上下文有关的，因此语义分析须用上下文有关文法描述。即选,B,。,(2)2,型文法对应下推自动机。故选,C,。,(3),由于不存在：,3,型语言,2,型语言,1,型语言,0,型语言。故选,D,。,(4)3,型文法即正规文法，它的识别系统是有限状态自动机。故选,C,。,78,(5),由,S,xSx|y,可知该文法所识别的语言一定是：,y,左边出现的,x,与,y,右边出现的,x,相等。故

34、选,C,。,(6),最左简单子树的末端结点组成的符号串为句柄。故选,C,。,(7),内部结点,(,指非树叶结点,),一定是非终结符。故选,D,。,(8),由文法开始符,S,经过零步或多步推导产生的符号序列一定是句型，仅当推导产生的符号序列全部由终结符组成时才是句子，即句子是句型的阵列。故选,C,。,(9),规范推导即最右推导，也即每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换。故选,D,。,79,(10),文法,GS,的一个句子如果能找到两种不同的最左推导,(,或最右推导,),，或存在两棵不同的语法树，则它的任何句子,其最左推导和最右推导对应的语法树必定相同。故选,A,。,(1

35、1),一个句型的分析树代表了该句型的归约过程。故选,B,。,(12),规范归约中的“可归约串”即为句柄，也就是最左直接短语。故选,C,。,(13),规范归约的逆过程是规范推导，而规范推导即为最右推导。故选,B,。,(14),由图,3-1,可知应选,A,。,80,图,3-1,句型,aAcbBdcc,对应的语法树,81,(15),由图,3-2,可知，句柄,(,最左直接短语,),为,P,，最左素短语为,P+T,。故选,B,。,(16),回溯使自顶向下分析效率降低，左递归使得自顶向下的分析无法实现；二者相比消除左递归更为重要。故选,A,。,(17)FIRST(F)=(,i,，而由,SF,可知,FIRS

36、T(F),FIRST(S),，即,FIRST(S)=(,i,。故选,B,。,(18),左递归和二义性将无法实现自顶向下分析，回溯则使自顶向下分析效率下降。故选,D,。,82,图,3-2,句型,P+T+i,对应的语法树及优先关系示意,83,(19),递归下降分析器由一组递归函数组成，且每一个函数对应文法的一个非终结符。故选,B,。,(20)LL(1),分析表需要预先定义和构造两族与文法有关的集合,FIRST,和,FOLLOW,。故选,A,。,(21),由于,ab,和,bc,并不能使选项,A,、,B,、,C,成立。故选,D,。,(22),由算法优先文法可知应选,B,。,(23),有些算符优先文法不

37、存在优先函数；有些算符优先文法存在优先函数，且只要存在一对优先函数，就存在无穷多对优先函数。故选,D,。,(24),在算符优先分析中是以“最左素短语”来刻画可归约串的。故选,D,。,84,(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),FOLLO

38、W(B),，即选项,C,错。故选,C,。,(29),若文法,GS,的产生式有,AB,出现，则有,FIRST(B),FOLLOW(A),。故选,C,。,85,图,3-3,句子,1+2*8+6,的语法树及值变化示意,86,(30),自底向上的分析方法有算符优先分析法和,LR,分析法。故选,D,。,(31),自底向上分析采用归约方法，但算符优先分析用“最左素短语”归约，而,LR,分析用“句柄”归约。,SLR(1),是,LR,分析法的一种，故选,C,。,(32),在,LR,分析中，一个项目指明了在分析过程的某个时刻所看到产生式的多大一部分。故选,C,。,(33),对文法,GS,，,S,称为“接受”项目

39、；形如,Aa,的项目,(,其中,a,为终结符,),称为“移进”项目；形如,AB,的项目,(,其中,B,为非终结符,),称为“待约”项目。故选,D,。,87,(34),在,LR(0),的,ACTION,子表中，如果某一行存在标注为“,rj”,的栏，则该行必定填满,rj,，而在,SLR(1),的,ACTION,子表中，如果某一行存在标注为“,rj”,的栏，则该行可能未填满,rj,。因此选,A,。,(35)LR,分析法解决“移进,归约”冲突时，左结合意味着打断联系而实行归约，右结合意味着维持联系而实行移进。故选,B,。,(36),由,(35),可知应选,C,。,88,3.2,令文法,GN,为,GN:

40、ND|ND,D0|1|2|3|4|5|6|7|8|9,(1)GN,的语言,L(G),是什么,?,(2),给出句子,0127,、,34,和,568,的最左推导和最右推导。,89,【,解答,】,(1)GN,的语言,L(GN),是非负整数。,(2),最左推导：最右推导：,90,3.3,已知文法,GS,为,SaSb|Sb|b,，试证明文法,GS,为二义文法。,【,解答,】,由文法,GS,：,SaSb|Sb|b,，对句子,aabbbb,可对应如图,3-4,所示的两棵语法树。因此，文法,GS,为二义文法,(,对句子,abbb,也可画出两棵不同的语法树,),。,91,图,3-4,句子,aabbbb,对应的两

41、棵不同语法树,92,3.4,已知文法,GS,为,SSaS|,，试证明文法,GS,为二义文法。,【,解答,】,由文法,GS,：,SSaS|,，句子,aa,的语法树如图,3-5,所示。由图,3-5,可知，文法,GS,为二义文法。,93,图,3-5,句子,aa,对应的两棵不同的语法树,94,3.5,按指定类型，给出语言的文法。,(1)L=a,i,b,j,|j,i0,的上下文无关文法；,(2),字母表,=a,b,上的同时只有奇数个,a,和奇数个,b,的所有串的集合的正规文法；,(3),由相同个数,a,和,b,组成句子的无二义文法。,【,解答,】(1),由,L=a,i,b,j,|j,i0,知，所求该语言

42、对应的上下文无关文法首先应有,SaSb,型产生式，以保证,b,的个数不少于,a,的个数；其次，还需有,SSb,或,Sb,型的产生式，用以保证,b,的个数多于,a,的个数。因此，所求上下文无关文法,GS,为,GS,：,SaSb|Sb|b,95,(2),为了构造字母表,=a,b,上同时只有奇数个,a,和奇数个,b,的所有串集合的正规式，我们画出如图,3-6,所示的,DFA,，即由开始符,S,出发，经过奇数个,a,到达状态,A,，或经过奇数个,b,到达状态,B,；而由状态,A,出发，经过奇数个,b,到达状态,C(,终态,),；同样，由状态,B,出发经过奇数个,a,到达终态,C,。由图,3-6,可直接

45、直接短语。,99,能否不画出语法树，而直接由定义,(,即在句型中,),寻找满足某个产生式的候选式这样一个最左子串,(,即句柄,),呢？例如，对句型,aAaBcbbdcc,，我们可以由左至右扫描找到第一个子串,AaB,，它恰好是满足,AAaB,右部的子串；与树,(a),对照，,AaB,的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型,aAcbBdcc,，由左至右找到第一个子串,c,，这是满足,Ac,右部的子串，但由树,(b),可知，,c,不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。,100,图,3-7,习题,3.6,的语法树,(a)aAaB

46、cbbdcc;(b)aAcbBdcc,101,(2),句子,acabcbbdcc,的最左推导如下：,102,3.7,对于文法,GS:S(L)|aS|a,LL,S|S,(1),画出句型,(S,(a),的语法树；,(2),写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。,103,【,解答,】(1),句型,(S,(a),的语法树如图,3-8,所示。,(2),由图,3-8,可知：短语：,S,、,a,、,(a),、,S,(a),、,(S,(a),；直接短语：,a,、,S,；句柄：,S,；素短语：素短语可由图,3-8,中相邻终结符之间的优先关系求得，即：,#(,，,(a)#,因此，素短语为,a

47、,。,104,图,3-8,句型,(S,(a),的语法树,105,3.8,下述文法描述了,C,语言整数变量的声明语句：,GD:DTL,Tint|long|short,Lid|L,id,(1),改造上述文法，使其接受相同的输入序列，但文法是右递归的；,(2),分别以上述文法,GD,和改造后的文法,GD,为输入序列,int a,b,c,构造分析树。,106,【,解答,】(1),消除左递归后，文法,GD,如下：,DTL,Tint|long|short,LidL,L,idL|,(2),未消除左递归的文法,G(D),和消除左递归的文法,GD,为输入序列,int a,b,c,构造的分析树分别如图,3-9,的

49、ookahead=nexttoken;,else error();,void S(),111,if(lookahead=a),match(a);,S();,else if(lookahead=(),match();,T();,if(lookahead=),match();,else error();,112,void S(),if(lookahead=+),match(+);,S();,void T(),S();,T();,113,void T (),if(lookahead=,),match(,);,S();,T();,114,对于文法,GS,中的产生式：,TT,S|S,，即将非终结符,T,

50、由下面的正规表达式定义：,TS,S,然后将其用状态转换图表示为图,3-10,。这个状态转换图的作用就如同一个递归过程,(,函数,),，并借助于这种转换图来得到递归过程,(,函数,),下降分析器。因此，前面的递归下降分析器程序可删除函数,T(),和,T(),，而将,T(),和,T(),改为,115,图,3-10,非终结符,T,的状态转换图,116,void T(),S();,while(lookahead=,),match(,);,S();,117,3.10,已知文法,GA:AaABl|a,BBb|d,(1),试给出与,GA,等价的,LL(1),文法,GA,；,(2),构造,GA,的,LL(1)

展开阅读全文