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

第一章绪论第二章词法分析第三章语法分析,1,第一章绪论1.1完成下列选择题：(1)下面叙述中正确的是。A编译程序是将高级语言程序翻译成等价的机器语言程序的程序B机器语言因其使用过于困难，所以现在计算机根本不使用机器语言C汇编语言是计算机唯一能够直接识别并接受的语言D高级语言接近人们的自然语言，但其依赖具体机器的特性是无法改变的,2,(2)将编译过程分成若干“遍”是为了。A提高程序的执行效率B使程序的结构更加清晰C利用有限的机器内存并提高机器的执行效率D利用有限的机器内存但降低了机器的执行效率(3)构造编译程序应掌握。A源程序B目标语言C编译方法DAC项,3,(4)编译程序绝大多数时间花在上。A出错处理B词法分析B目标代码生成D表格管理(5)编译程序是对。A汇编程序的翻译B高级语言程序的解释执行C机器语言的执行D高级语言的翻译,4,【解答】(1)编译程序可以将用高级语言编写的源程序转换成与之在逻辑上等价的目标程序，而目标程序可以是汇编语言程序或机器语言程序。故选A。(2)分多遍完成编译过程可使整个编译程序的逻辑结构更加清晰。故选B。(3)构造编译程序应掌握源程序、目标语言和编译方法这三方面内容。故选D。,5,(4)编译各阶段的工作都涉及到构造、查找或更新有关表格，即编译过程的绝大部分时间都用在造表、查表和更新表格的事务上。故选D。(5)由(1)可知，编译程序实际上实现了对高级语言程序的翻译。故选D。,6,1.2计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，然后再读入下一条源程序语句并解释执行，而所翻译的机器代码语句串在该语句执行后并不保留。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。,7,在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。,8,1.3请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响。,9,图1-1编译程序总框图,10,第二章词法分析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.1的DFAM,13,(5)对于任一给定的NFAM，一个DFAM，使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)*Ba*|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与之等价，即两者描述能力相同；也即，对于任一给定的NFAM，一定存在一个DFAM，使L(M)=L(M)。故选B。(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什么是扫描器？扫描器的功能是什么？【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。,18,2.3设M=(x,y,a,b,f,x,y)为一非确定的有限自动机，其中f定义如下：f(x,a)=x,yfx,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所示。,19,图2-2习题2.3的NFAM,20,用子集法构造状态转换矩阵，如表2-1所示。表2-1状态转换矩阵将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到,21,将图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的DFAM,其状态转换图如图2-3所示。,22,图2-4图2-3化简后的DFAM,23,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所示。因此，这两个正规式等价。,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与正规式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)=a2n+1b2ma2p+1|n0,p0,m1。(1)给出描述该语言的正规表达式；(2)构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-10所示。,31,图2-10习题2.5的NFA,32,用子集法将图2-10确定化，如图2-11所示。由图2-11重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)0,213,54,67,图2-11习题2.5的状态转换矩阵,33,按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-12所示。,图2-12习题2.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-14所示由图2-14可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为012,4356,87,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所示。用子集法将图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确定化为如图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*。,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为终态。【解答】用子集法将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的下一状态落入非终态集，故将其划分为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)写出售货机售糖的正规表达式；(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,按顺序重新命名为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)下述结论中，是正确的。A1型语言0型语言B2型语言1型语言C3型语言2型语言DAC均不成立(4)有限状态自动机能识别_。A上下文无关文法B上下文有关文法C正规文法D短语文法(5)文法GS：SxSx|y所识别的语言是。AxyxB(xyx)*Cxnyxn(n0)Dx*yx*,61,(6)只含有单层分枝的子树称为“简单子树”，则句柄的直观解释是。A子树的末端结点(即树叶)组成的符号串B简单子树的末端结点组成的符号串C最左简单子树的末端结点组成的符号串D最左简单子树的末端结点组成的符号串且该符号串必须含有终结符,62,(7)下面对语法树错误的描述是。A根结点用文法GS的开始符S标记B每个结点用GS的一个终结符或非终结符标记C如果某结点标记为，则它必为叶结点D内部结点可以是非终结符(8)由文法开始符S经过零步或多步推导产生的符号序列是。A短语B句柄C句型D句子,63,(9)设文法GS：SSA|AAa|b则对句子aba的规范推导是。ASSASAAAAAaAAabAabaBSSASAAAAAAAaAbaabaCSSASAASAaSbaAbaabaDSSASaSAaSbaAbaaba,64,(10)如果文法GS是无二义的，则它的任何句子其。A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最右推导，但它们对应的语法树相同(11)一个句型的分析树代表了该句型的。A推导过程B归约过程C生成过程D翻译过程,65,(12)规范归约中的“可归约串”由定义。A直接短语B最右直接短语C最左直接短语D最左素短语(13)规范归约是指。A最左推导的逆过程B最右推导的逆过程C规范推导D最左归约的逆过程,66,(14)文法GS：SaAcB|BdAAaB|cBbScA|b则句型aAcbBdcc的短语是。ABdBccCaDb(15)文法GE：EE+T|TTT*P|PP(E)|i则句型P+T+i的句柄和最左素短语是。AP+T和TBP和P+TCi和P+T+iDP和P,67,(16)采用自顶向下分析，必须。A消除左递归B消除右递归C消除回朔D提取公共左因子(17)对文法GE：EE+S|SSS*F|FF(E)|i则FIRST(S)=。A(B(,iCiD(,),68,(18)确定的自顶向下分析要求文法满足。A不含左递归B不含二义性C无回溯DAC项(19)递归下降分析器由一组递归函数组成，且每一个函数对应文法的。A一个终结符B一个非终结符C多个终结符D多个非终结符(20)LL(1)分析表需要预先定义和构造两族与文法有关的集合。AFIRST和FOLLOWBFIRSTVT和FOLLOWCFIRST和LASTVTDFIRSTVT和LASTVT,69,(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三种关系之一,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至少包含一个非终结符C除自身外不再包含其他素短语D在句型中具有最左性(26)对文法GS：Sb|(T)TT，S|S其FIRSTVT(T)为。Ab,(Bb,)C，,b,(D，,b,),72,(27)对文法GE：EE*T|TTT+i|i句子1+2*8+6归约的值为。A23B42C30D17(28)下述FOLLOW集构造方法中错误的是。A对文法开始符S有#FOLLOW(S)B若有AB，则有FIRST()FOLLOW(B)C若有AB，则有FOLLOW(B)FOLLOW(A)D若有AB，则有FOLLOW(A)FOLLOW(B),73,(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)分析法D算符优先分析法,74,(31)下面是采用句柄进行归约的。A算符优先分析法B预测分析法CSLR(1)分析法DLL(1)分析法(32)一个指明了在分析过程中某时刻能看到产生式多大一部分。A活前缀B前缀C项目D项目集(33)若B为非终结符，则AB为项目。A接受B归约C移进D待约,75,(34)在LR(0)的ACTION子表中，如果某一行中存在标记为“rj”的栏，则。A该行必定填满rjB该行未填满rjC其他行也有rjDGOTO子表中也有rj(35)LR分析法解决“移进归约”冲突时，左结合意味着。A打断联系实行移进B打断联系实行归约C建立联系实行移进D建立联系实行归约,76,(36)LR分析法解决“移进归约”冲突时，右结合意味着。A打断联系实行归约B建立联系实行归约C建立联系实行移进D打断联系实行移进,77,【解答】(1)参见第四章4.1.1节，语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述，由于语义是上下文有关的，因此语义分析须用上下文有关文法描述。即选B。(2)2型文法对应下推自动机。故选C。(3)由于不存在：3型语言2型语言1型语言0型语言。故选D。(4)3型文法即正规文法，它的识别系统是有限状态自动机。故选C。,78,(5)由SxSx|y可知该文法所识别的语言一定是：y左边出现的x与y右边出现的x相等。故选C。(6)最左简单子树的末端结点组成的符号串为句柄。故选C。(7)内部结点(指非树叶结点)一定是非终结符。故选D。(8)由文法开始符S经过零步或多步推导产生的符号序列一定是句型，仅当推导产生的符号序列全部由终结符组成时才是句子，即句子是句型的阵列。故选C。(9)规范推导即最右推导，也即每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换。故选D。,79,(10)文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或存在两棵不同的语法树，则它的任何句子其最左推导和最右推导对应的语法树必定相同。故选A。(11)一个句型的分析树代表了该句型的归约过程。故选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可知FIRST(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)有些算符优先文法不存在优先函数；有些算符优先文法存在优先函数，且只要存在一对优先函数，就存在无穷多对优先函数。故选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)FOLLOW(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称为“接受”项目；形如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:ND|NDD0|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对应的两棵不同语法树,92,3.4已知文法GS为SSaS|，试证明文法GS为二义文法。【解答】由文法GS：SSaS|，句子aa的语法树如图3-5所示。由图3-5可知，文法GS为二义文法。,93,图3-5句子aa对应的两棵不同的语法树,94,3.5按指定类型，给出语言的文法。(1)L=aibj|ji0的上下文无关文法；(2)字母表=a,b上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；(3)由相同个数a和b组成句子的无二义文法。【解答】(1)由L=aibj|ji0知，所求该语言对应的上下文无关文法首先应有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可直接得到正规文法GS如下：GS：SaA|bBAaS|bC|bBbS|aC|aCbA|aB|,96,图3-6,97,(3)我们用一个非终结符A代表一个a(即有Aa)，用一个非终结符B代表一个b(即有Bb)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个B，出现一个b时则相应出现一个A。假定已推导出bA，如果下一步要推导出连续两个b，则应有bAbbAA。也即为了保证b和A的个数一致，应有AbAA；同理有BaBB。此外，为了保证递归地推出所要求的ab串，应有SaBS和SbAS。由此得到无二义文法GS为GS：SaBS|bAS|AbAA|aBaBB|b,98,3.6有文法GS:SaAcB|BdAAaB|cBbScA|b(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)写出句子acabcbbdcc的最左推导过程。【解答】(1)分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3-7的(a)、(b)所示。对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。,99,能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足AAaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足Ac右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。,100,图3-7习题3.6的语法树(a)aAaBcbbdcc;(b)aAcbBdcc,101,(2)句子acabcbbdcc的最左推导如下：,102,3.7对于文法GS:S(L)|aS|aLL,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。,104,图3-8句型(S,(a)的语法树,105,3.8下述文法描述了C语言整数变量的声明语句：GD:DTLTint|long|shortLid|L,id(1)改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2)分别以上述文法GD和改造后的文法GD为输入序列inta,b,c构造分析树。,106,【解答】(1)消除左递归后，文法GD如下：DTLTint|long|shortLidLL,idL|(2)未消除左递归的文法G(D)和消除左递归的文法GD为输入序列inta,b,c构造的分析树分别如图3-9的(a)、(b)所示。,107,图3-9两种文法为inta,b,c构造的分析树(a)文法G(D)；(b)文法G(D),108,3.9考虑文法GS:S(T)|a+S|aTT,S|S消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。【解答】消除文法GS的左递归：S(T)|a+S|aTSTT,ST|,109,提取公共左因子：S(T)|aSS+S|TSTT,ST|,110,改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：voidmatch(tokent)if(lookahead=t)lookahead=nexttoken;elseerror();voidS(),111,if(lookahead=a)match(a);S();elseif(lookahead=()match();T();if(lookahead=)match();elseerror();,112,voidS()if(lookahead=+)match(+);S();voidT()S();T();,113,voidT()if(lookahead=,)match(,);S();T();,114,对于文法GS中的产生式：TT,S|S，即将非终结符T由下面的正规表达式定义：TS,S然后将其用状态转换图表示为图3-10。这个状态转换图的作用就如同一个递归过程(函数)，并借助于这种转换图来得到递归过程(函数)下降分析器。因此，前面的递归下降分析器程序可删除函数T()和T()，而将T()和T()改为,115,图3-10非终结符T的状态转换图,116,voidT()S();while(lookahead=,)match(,);S();,117,3.10已知文法GA:AaABl|aBBb|d(1)试给出与GA等价的LL(1)文法GA；(2)构造GA的LL(1)分析表；(3)给出输入串aadl#的分析过程。【解答】(1)文法GA存在左递归和回溯，故其不是LL(1)文法。要将GA改造为LL(1)文法，首先要消除文法的左递归，即将形如PP|的产生式改造为PPPP|,118,来消除左递归。由此，将产生式BBb|d改造为BdBBbB|其次，应通过提取公共左因子的方法来消除GA中的回溯，即将产生式AaABl|a改造为AaAAABl|最后得到改造后的文法为GA：AaAAABl|BdBBbB|,119,求得：FIRST(A)=aFIRST(A)=a,FIRST(B)=dFIRST(B)=b,对文法开始符号A，有FOLLOW(A)=#。由AABl得FIRST(B)FOLLOW(A)，即FOLLOW(A)=#,d；由AABl得FIRST(l)FOLLOW(B)，即FOLLOW(B)=l；,120,由AaA得FOLLOW(A)FOLLOW(A)，即FOLLOW(A)=#,d；由BdB得FOLLOW(B)FOLLOW(B)，即FOLLOW(B)=l。对AABl来说，FIRST(A)FOLLOW(A)=a#,d=，所以文法GA为所求等价的LL(1)文法。,121,(2)构造预测分析表的方法如下：对文法GA的每个产生式A执行、步。对每个终结符aFIRST(A)，把A加入到MA,a中，其中为含有首字符a的候选式或为唯一的候选式。若FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A加入到MA,b中。把所有无定义的MA,a标记上“出错”。由此得到GA的预测分析表，见表3-1。(3)输入串aadl的分析过程见表3-2。,122,表3-1预测分析表,123,表3-2输入串aadl的分析过程,124,3.11将下述文法改造为LL(1)文法：GV:VN|NEEV|V+ENi【解答】LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而文法GV中含有回溯，所以先消除回溯，得到文法GV：GV：VNVV|EEVEE|+ENi,125,一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A|有下面的条件成立：(1)FIRST()FIRST()=；(2)假若，则有FIRST()FOLLOW(A)=。即求出GV的FIRST和FOLLOW集如下：FIRST(N)=FIRST(V)=FIRST(E)=iFIRST(V)=,FIRST(E)=+,FOLLOW(V)=#,126,由VE得FIRST()FOLLOW(E)，即FOLLOW(E)=；由VNV得FIRST(V)FOLLOW(N)，即FOLLOW(N)=；由EVE得FIRST(E)FOLLOW(V)，即FOLLOW(V)=#,+；由VNV得FOLLOW(V)FOLLOW(V)，即FOLLOW(V)=#,+；由VNV且V得FOLLOW(V)FOLLOW(N)，即FOLLOW(N)=,#,+；由EVE得FOLLOW(E)FOLLOW(E)，即FOLLOW(E)=；,127,则，对V|E有：FIRST()FIRST()=；对E|+E有：FIRST()FIRST(+)=；对V|E有：FIRST()FOLLOW(V)=#,+=；对E|+E有：FIRST(+)FOLLOW(E)=+=。故文法GV为LL(1)文法。,128,3.12对文法GE:EE+T|TTT*P|PPi(1)构造该文法的优先关系表(不考虑语句括号#)，并指出此文法是否为算符优先文法；(2)构造文法GE的优先函数。,129,【解答】(1)FIRSTVT集构造方法：由Pa或PQa，则aFIRSTVT(P)。若aFIRSTVT(Q)，且PQ，则aFIRSTVT(P)，也即FIRSTVT(Q)FIRSTVT(P)。由得：由EE+得FIRSTVT(E)=+；由TT*得FIRSTVT(T)=*；由Pi得FIRSTVT(P)=i。由得：由TP得FIRSTVT(P)FIRSTVT(T)，即FIRSTVT(T)=*，i；由ET得FIRSTVT(T)FIRSTVT(E)，即FIRSTVT(E)=+，*，i。,130,LASTVT集构造方法：由Pa或PaQ,则aLASTVT(P)。若aLASTVT(Q)，且PQ，则aLASTVT(P)，也即LASTVT(Q)LASTVT(P)。由得：E+T，得LASTVT(E)=+；T*P，得LASTVT(T)=*；Pi，得LASTVT(P)=i。,131,由得：由TP得LASTVT(P)LASTVT(T)，即LASTVT(T)=*，i；由ET得LASTVT(T)LASTVT(E)，即LASTVT(E)=+，*，i。优先关系表构造方法：对Pab或PaQb，有ab；对PaR而bFIRSTVT(R)，有ab；对PRb而aLASTVT(R)，有ab。解之无。,132,由得：E+T，即+FIRSTVT(T)，有+*，+i；T*P，即*FIRSTVT(P)，有*i。由得：EE+，即LASTVT(E)+，有+，*+，i+；TT*，即LASTVT(T)*，有*，i*。得到优先关系表见表3-3。由于该文法的任何产生式的右部都不含两个相继并列的非终结符，故属算符文法，且该文法中的任何终结符对(见优先关系表)至多满足、和三种关系之一，因而是算符优先文法。,133,表3-3习题3.12的优先关系表,134,(2)用关系图构造优先函数的方法是：对所有终结符a用有下脚标的fa、ga为结点名画出全部终结符所对应的结点。若存在优先关系ab或ab，则画一条从fa到ga的有向弧；若ab或ab，则画一条从gb到fa的有向弧。最后，对每个结点都赋一个数，此数等于从该结点出发所能到达的结点(包括出发结点)的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。用关系图法构造本题的优先函数，如图3-11所示。得到优先函数见表3-4。,135,图3-11习题3.1,136,表3-4习题3.12的优先函数表,137,该优先函数表经检查与优先关系表没有矛盾，故为所求优先函数。也可由定义直接构造优先函数，其方法是：对每个终结符a，令f(a)=g(a)=1；如果ab，而f(a)g(b)，则令f(a)=g(b)+1；如果ab，而f(a)g(b)，则令g(b)=f(a)+1；如果ab，而f(a)g(b)，则令minf(a),g(b)=maxf(a),g(b)。重复上述过程，直到每个终结符的函数值不再变化为止。如果有一个函数值大于2n(n为终结符个数)，则不存在优先函数。优先函数的计算过程如表3-5所示。,138,表3-5优先函数的计算过程,139,3.13设有文法GS:Sa|b|(A)ASdA|S(1)构造算符优先关系表；(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；(3)给出输入串(adb)#的分析过程。,140,【解答】(1)先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得FIRSTVT(S)=a,b,(；由ASd得FIRSTVT(A)=d，又由AS得FIRSTVT(S)FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(；由Sa|b|(A)得LASTVT(S)=a,b,)；由AdA得LASTVT(A)=d，又由AS得LASTVT(S)LASTVT(A)，即LASTVT(A)=d,a,b,)。,141,构造优先关系表方法如下：对Pab或PaQb，有ab；对PaR而bFIRSTVT(R)，有ab；对PRb而aFIRSTVT(R)，有ab。由此得到：由S(A)得()；由S(A得(FIRSTVT(A)，即(d,(a,(b,(；由AdA得dFIRSTVT(A)，即dd,da,db,d(；,142,由SA)得LASTVT(A)，即d),a),b),)；由ASd得LASTVT(S)d，即ad,bd,)d；此外，由#S#得#；由#FIRSTVT(S)得#a,#b,#(；由LASTVT(S)#得a#,b#,)#。最后得到算符优先关系表，见表3-6。由表3-6可以看出，任何两个终结符之间至多只满足、三种优先关系之一，故GS为算符优先文法。,143,表3-6习题3.13的算符优先关系表,144,(2)为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图3-12所示。由图3-12得到：短语：S，SdS，SdSdS，(SdSdS)简单短语(即直接短语)：S句柄(即最左直接短语)：S可以通过分析图3-12所示的语法树来求素短语和最左素短语，即找出语法树中的所有相邻终结符(中间可有一个非终结符)之间的优先关系。确定优先关系的原则是：,145,图3-12句型(SdSdS)的语法树,146,同层的优先关系为；不同层时，层次离树根远者优先级高，层次离树根近者优先级低(恰好验证了优先关系表的构造算法)；在句型两侧加上语句括号“#”，即#，则有#和#，由此我们得到句型(SdSdS)的优先关系如图3-13所示。注意，句型中的素短语具有如下形式：,147,图3-13句型(SdSdS)的优先关系,148,而最左素短语就是该句型中所找到的最左边的那个素短语，即最左素短语必须具备三个条件：至少包含一个终结符(是否包含非终结符则按短语的要求确定)；除自身外不得包含其他素短语(最小性)；在句型中具有最左性。因此，由图3-13得到SdS为句型(SdSdS)的素短语，它同时也是该句型的最左素短语。(3)输入串(adb)#的分析过程见表3-7。为便于分析，同时给出了(adb)#的语法树，如图3-14所示。,149,表3-7输入串(adb)#的分析过程,150,图3-14(adb)的语法树,