编译原理习题及答案PPT演示课件

.,1,第一章 绪 论第二章 词 法 分 析第三章 语 法 分 析,.,2,第一章 绪 论1.1 完成下列选择题：(1) 下面叙述中正确的是 。A编译程序是将高级语言程序翻译成等价的机器语言程序的程序B机器语言因其使用过于困难，所以现在计算机根本不使用机器语言C汇编语言是计算机唯一能够直接识别并接受的语言D高级语言接近人们的自然语言，但其依赖具体机器的特性是无法改变的,.,3,(2) 将编译过程分成若干“遍”是为了 。A提高程序的执行效率B使程序的结构更加清晰C利用有限的机器内存并提高机器的执行效率D利用有限的机器内存但降低了机器的执行效率(3) 构造编译程序应掌握 。 A源程序 B目标语言 C编译方法 DAC项,.,4,(4) 编译程序绝大多数时间花在 上。A出错处理 B词法分析 B目标代码生成 D表格管理(5) 编译程序是对 。A汇编程序的翻译 B高级语言程序的解释执行C机器语言的执行 D高级语言的翻译,.,5,【解答】 (1) 编译程序可以将用高级语言编写的源程序转换成与之在逻辑上等价的目标程序，而目标程序可以是汇编语言程序或机器语言程序。故选A。(2) 分多遍完成编译过程可使整个编译程序的逻辑结构更加清晰。故选B。(3) 构造编译程序应掌握源程序、目标语言和编译方法这三方面内容。故选D。,.,6,(4) 编译各阶段的工作都涉及到构造、查找或更新有关表格，即编译过程的绝大部分时间都用在造表、查表和更新表格的事务上。故选D。(5) 由(1)可知，编译程序实际上实现了对高级语言程序的翻译。故选D。,.,7,1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】 计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，然后再读入下一条源程序语句并解释执行，而所翻译的机器代码语句串在该语句执行后并不保留。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。,.,8,在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。,.,9,1.3 请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】 编译程序总框图如图1-1所示。作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响。,.,10,图1-1 编译程序总框图,.,11,第二章 词 法 分 析2.1 完成下列选择题：(1) 词法分析所依据的是 。A语义规则 B构词规则 C语法规则 D等价变换规则(2) 词法分析器的输入是 。A单词符号串 B源程序 C语法单位 D目标程序,.,12,(3) 词法分析器的输出是 。A单词的种别编码 B单词的种别编码和自身的值C单词在符号表中的位置 D单词自身值(4) 状态转换图(见图2-1)接受的字集为 _。A以0开头的二进制数组成的集合B以0结尾的二进制数组成的集合 C含奇数个0的二进制数组成的集合 D含偶数个0的二进制数组成的集合,.,13,图2-1 习题2.1的DFA M,.,14,(5) 对于任一给定的NFA M， 一个DFA M，使L(M)= L(M)。A一定不存在 B一定存在 C可能存在 D可能不存在(6) DFA适用于 。A定理证明 B语法分析 C词法分析 D语义加工,.,15,(7) 下面用正规表达式描述词法的论述中，不正确的是 。A词法规则简单，采用正规表达式已足以描述B正规表达式的表示比上下文无关文法更加简洁、直观和易于理解C正规表达式描述能力强于上下文无关文法D有限自动机的构造比下推自动机简单且分析效率高(8) 与(a|b)*(a|b)等价的正规式是 。A(a|b) (a|b)* Ba*|b* C(ab)*(a|b)* D(a|b)*,.,16,【解答】(1) 由教材第一章1.3节中的词法分析，可知词法分析所遵循的是语言的构词规则。故选B。(2) 词法分析器的功能是输入源程序，输出单词符号。故选B。(3) 词法分析器输出的单词符号通常表示为二元式：(单词种别，单词自身的值)。故选B。(4) 虽然选项A、B、D都满足题意，但选项D更准确。故选D。,.,17,(5) NFA可以有DFA与之等价，即两者描述能力相同；也即，对于任一给定的NFA M，一定存在一个DFA M，使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。,.,18,2.2 什么是扫描器？扫描器的功能是什么？【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。,.,19,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所示。,.,20,图2-2 习题2.3的NFA M,.,21,用子集法构造状态转换矩阵，如表2-1所示。 表2-1 状态转换矩阵 将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到,.,22,将图2-3所示的DFA M最小化。首先，将M的状态分成终态组1,2与非终态组0。其次，考察1,2。由于1,2a=1,2b=21,2，因此不再将其划分了，也即整个划分只有两组：0和1,2。令状态1代表1,2，即把原来到达2的弧都导向1，并删除状态2。最后，得到如图2-4所示的化简了的DFA M。,图2-3 习题2.3的DFA M,其状态转换图如图2-3所示。,.,23,图2-4 图2-3化简后的DFA M,.,24,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所示。因此，这两个正规式等价。,.,25,图2-5 正规式(ab)*a对应的NFA,.,26,图2-6 正规式a(ba)*对应的NFA,.,27,图2-7 图2-5和图2-6确定化后的状态转换矩阵,.,28,图2-8 最简DFA,.,29,实际上，当闭包*取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。,.,30,图2-9 (ab)*a和a(ba)*分别对应的NFA,.,31,2.5 设有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1) 给出描述该语言的正规表达式；(2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)。【解答】 该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA如图2-10所示。,.,32,图2-10 习题2.5的NFA,.,33,用子集法将图2-10确定化，如图2-11所示。由图2-11重新命名后的状态转换矩阵可化简为(也可由最小化方法得到)0,2 1 3,5 4,6 7,图2-11 习题2.5的状态转换矩阵,.,34,按顺序重新命名为0、1、2、3、4后得到最简的DFA，如图2-12所示。,图2-12 习题2.5的最简DFA,.,35,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所示。,.,36,图2-13 习题2.6的NFA,.,37,用子集法将图2-13所示的NFA确定化，如图2-14所示由图2-14可看出非终态2和4的下一状态相同，终态6和8的下一状态相同，即得到最简状态为0 1 2,4 3 5 6,8 7,.,38,按顺序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-15所示。,图2-15 习题2.6的最简DFA,.,39,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所示。,.,40,图2-16 正规式(a|b)*|aa)*b对应的NFA,.,41,图2-17 图2-16确定化后的状态转换矩阵,.,42,由于对非终态的状态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所示的状态转换矩阵。,.,43,表2-3 合并后的状态转换矩阵,.,44,图2-18 习题2.7的最简DFA,.,45,图2-19 正规式(a|b)*b对应的NFA,.,46,比较图2-20与图2-17，重新命名后的转换矩阵是完全一样的，也即正规式(a|b)*b可以同样得到化简后的DFA如图2-18所示。因此，两个自动机完全一样，即两个正规文法等价。,图2-20 图2-19确定化后的状态转换矩阵,.,47,2.8 构造一个DFA，它接收 =a,b上所有不含abb的字符串。解： =a,b上所有不含abb的字符串可表示为b*(a*b)a*。,.,48,2.9构造一个DFA，它接收 =a,b上所有含偶数个a的字符串。解： =a,b上所有含偶数个a的字符串可表示为(b|ab*a)*,.,49,2.10 下列程序段以B表示循环体，A表示初始化，I表示增量，T表示测试： I=1; while (I=n) sun=sun+aI; I=I+1; 请用正规表达式表示这个程序段可能的执行序列。【解答】 用正规表达式表示程序段可能的执行序列为AT(BIT)*。,.,50,2.9 将图2-21所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。其中，X为初态，Y为终态。 【解答】 用子集法将NFA确定化，如图2-22所示。,.,51,图2-21 习题2.9的NFA,.,52,图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,.,53,图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所示。,.,54,图2-23 习题2.9的DFA,.,55,图2-24 习题2.9的最简DFA,.,56,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所示。,.,57,图2-25 习题2.10的NFA,.,58,由图2-26可看出，非终态2和非终态3面对输入符号a或b的下一状态相同，故合并为一个状态，即最简状态0、1、2，3、4。,图2-26 习题2.10的状态转换矩阵,.,59,按顺序重新命名为0、1、2、3，则得到最简DFA，如图2-27所示。,图2-27 习题2.10的最简DFA,.,60,第三章 语 法 分 析3.1 完成下列选择题：(1) 程序语言的语义需要 用来描述。A上下文无关文法 B上下文有关文法C正规文法 D短语文法(2) 2型文法对应 。A图灵机 B有限自动机 C下推自动机 D线性界限自动机,.,61,(3) 下述结论中， 是正确的。A1型语言 0型语言 B2型语言 1型语言 C3型语言 2型语言 DAC均不成立(4) 有限状态自动机能识别_。A上下文无关文法 B上下文有关文法 C正规文法 D短语文法(5) 文法GS： SxSx | y 所识别的语言是 。Axyx B(xyx)* Cxnyxn (n0) Dx*yx*,.,62,(6) 只含有单层分枝的子树称为“简单子树”，则句柄的直观解释是 。A子树的末端结点(即树叶)组成的符号串B简单子树的末端结点组成的符号串C最左简单子树的末端结点组成的符号串D最左简单子树的末端结点组成的符号串且该符号串必须含有终结符,.,63,(7) 下面对语法树错误的描述是 。A根结点用文法GS的开始符S标记B每个结点用GS的一个终结符或非终结符标记C如果某结点标记为，则它必为叶结点D内部结点可以是非终结符(8) 由文法开始符S经过零步或多步推导产生的符号序列是 。A短语 B句柄 C句型 D句子,.,64,(9) 设文法GS： SSA | AAa | b则对句子aba的规范推导是 。AS SA SAA AAA aAA abA aba BS SA SAA AAA AAa Aba abaCS SA SAA SAa Sba Aba abaDS SA Sa SAa Sba Aba aba,.,65,(10) 如果文法GS是无二义的，则它的任何句子其 。A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最右推导，但它们对应的语法树相同 (11) 一个句型的分析树代表了该句型的 。A推导过程 B归约过程 C生成过程 D翻译过程,.,66,(12) 规范归约中的“可归约串”由 定义。A直接短语 B最右直接短语 C最左直接短语 D最左素短语(13) 规范归约是指 。A最左推导的逆过程 B最右推导的逆过程C规范推导 D最左归约的逆过程,.,67,(14) 文法GS：SaAcB | Bd AAaB | c BbScA | b则句型aAcbBdcc的短语是 。ABd Bcc Ca Db(15) 文法GE：EE+T | T TT*P | P P(E) | i则句型P+T+i的句柄和最左素短语是 。AP+T和T BP和P+T Ci和P+T+i DP和P,.,68,(16) 采用自顶向下分析，必须 。A消除左递归 B消除右递归 C消除回朔 D提取公共左因子(17) 对文法GE：EE+S | S SS*F | F F(E) | i则FIRST(S)= 。A( B ( , i C i D ( , ) ,.,69,(18) 确定的自顶向下分析要求文法满足 。A不含左递归 B不含二义性 C无回溯 DAC项(19) 递归下降分析器由一组递归函数组成，且每一个函数对应文法的 。A一个终结符 B一个非终结符 C多个终结符 D多个非终结符(20) LL(1)分析表需要预先定义和构造两族与文法有关的集合 。AFIRST和FOLLOW BFIRSTVT和FOLLOW CFIRST和LASTVT DFIRSTVT和LASTVT,.,70,(21) 设a、b、c是文法的终结符且满足优先关系ab和bc,则 。A必有ac B必有ca C必有ba DAC 都不一定成立(22) 算符优先分析法要求 。A文法不存在QR的句型且任何终结符对(a,b)满足ab、ab和ab三种关系 B文法不存在QR的句型且任何终结符对(a,b)至多满足ab、ab和ab三种关系之一,.,71,C文法可存在QR的句型且任何终结符对(a,b)至多满足ab、ab和ab三种关系之一D文法可存在QR的句型且任何终结符对(a,b)满足ab、ab和ab三种关系(23) 任何算符优先文法 优先函数。A有一个 B没有 C有若干个 D可能有若干个(24) 在算符优先分析中，用 来刻画可归约串。A句柄 B直接短语 C素短语 D最左素短语,.,72,(25) 下面最左素短语必须具备的条件中有错误的是 。A至少包含一个终结符 B至少包含一个非终结符 C除自身外不再包含其他素短语 D在句型中具有最左性(26) 对文法GS：Sb | | (T) TT，S | S其FIRSTVT(T)为 。Ab, ,( Bb, , ) C，,b, , ( D，,b, , ) ,.,73,(27) 对文法GE：EE*T | T TT+i | i句子1+2*8+6归约的值为 。A23 B42 C30 D17 (28) 下述FOLLOW集构造方法中错误的是 。A对文法开始符S有#FOLLOW(S)B若有AB，则有FIRST()FOLLOW(B) C若有AB，则有FOLLOW(B)FOLLOW(A)D若有AB，则有FOLLOW(A)FOLLOW(B),.,74,(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算符优先分析法,.,75,(31) 下面 是采用句柄进行归约的。A算符优先分析法 B预测分析法 CSLR(1)分析法 DLL(1)分析法(32) 一个 指明了在分析过程中某时刻能看到产生式多大一部分。A活前缀 B前缀 C项目 D项目集(33) 若B为非终结符，则AB为 项目。A接受 B归约 C移进 D待约,.,76,(34) 在LR(0)的ACTION子表中，如果某一行中存在标记为“rj”的栏，则 。A该行必定填满rj B该行未填满rj C其他行也有rj DGOTO子表中也有rj(35) LR分析法解决“移进归约”冲突时，左结合意味着 。A打断联系实行移进 B打断联系实行归约 C建立联系实行移进 D建立联系实行归约,.,77,(36) LR分析法解决“移进归约”冲突时，右结合意味着 。A打断联系实行归约 B建立联系实行归约 C建立联系实行移进 D打断联系实行移进,.,78,【解答】 (1) 参见第四章4.1.1节，语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述，由于语义是上下文有关的，因此语义分析须用上下文有关文法描述。即选B。(2) 2型文法对应下推自动机。故选C。(3) 由于不存在：3型语言 2型语言 1型语言 0型语言。故选D。(4) 3型文法即正规文法，它的识别系统是有限状态自动机。故选C。,.,79,(5) 由SxSx | y可知该文法所识别的语言一定是：y左边出现的x与y右边出现的x相等。故选C。(6) 最左简单子树的末端结点组成的符号串为句柄。故选C。(7) 内部结点(指非树叶结点)一定是非终结符。故选D。(8) 由文法开始符S经过零步或多步推导产生的符号序列一定是句型，仅当推导产生的符号序列全部由终结符组成时才是句子，即句子是句型的阵列。故选C。(9) 规范推导即最右推导，也即每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换。故选D。,.,80,(10) 文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或存在两棵不同的语法树，则它的任何句子其最左推导和最右推导对应的语法树必定相同。故选A。(11) 一个句型的分析树代表了该句型的归约过程。故选B。(12) 规范归约中的“可归约串”即为句柄，也就是最左直接短语。故选C。(13) 规范归约的逆过程是规范推导，而规范推导即为最右推导。故选B。(14) 由图3-1可知应选A。,.,81,图3-1 句型aAcbBdcc对应的语法树,.,82,(15) 由图3-2可知，句柄(最左直接短语)为P，最左素短语为P+T。故选B。(16) 回溯使自顶向下分析效率降低，左递归使得自顶向下的分析无法实现；二者相比消除左递归更为重要。故选A。(17) FIRST(F)=(,i，而由SF可知FIRST(F) FIRST(S)，即FIRST(S)=(,i。故选B。(18) 左递归和二义性将无法实现自顶向下分析，回溯则使自顶向下分析效率下降。故选D。,.,83,图3-2 句型P+T+i对应的语法树及优先关系示意,.,84,(19) 递归下降分析器由一组递归函数组成，且每一个函数对应文法的一个非终结符。故选B。(20) LL(1)分析表需要预先定义和构造两族与文法有关的集合FIRST和FOLLOW。故选A。(21) 由于ab和bc并不能使选项A、B、C成立。故选D。(22) 由算法优先文法可知应选B。(23) 有些算符优先文法不存在优先函数；有些算符优先文法存在优先函数，且只要存在一对优先函数，就存在无穷多对优先函数。故选D。(24) 在算符优先分析中是以“最左素短语”来刻画可归约串的。故选D。,.,85,(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。,.,86,图3-3 句子1+2*8+6的语法树及值变化示意,.,87,(30) 自底向上的分析方法有算符优先分析法和LR分析法。故选D。(31) 自底向上分析采用归约方法，但算符优先分析用“最左素短语”归约，而LR分析用“句柄”归约。SLR(1)是LR分析法的一种，故选C。(32) 在LR分析中，一个项目指明了在分析过程的某个时刻所看到产生式的多大一部分。故选C。(33) 对文法GS，S称为“接受”项目；形如Aa的项目(其中a为终结符)称为“移进”项目；形如AB的项目(其中B为非终结符)称为“待约”项目。故选D。,.,88,(34) 在LR(0)的ACTION子表中，如果某一行存在标注为“rj”的栏，则该行必定填满rj，而在SLR(1)的ACTION子表中，如果某一行存在标注为“rj”的栏，则该行可能未填满rj。因此选A。(35) LR分析法解决“移进归约”冲突时，左结合意味着打断联系而实行归约，右结合意味着维持联系而实行移进。故选B。(36) 由(35)可知应选C。,.,89,3.2 令文法GN为 GN: ND|NDD0|1|2|3|4|5|6|7|8|9(1) GN的语言L(G)是什么?(2) 给出句子0127、34和568的最左推导和最右推导。,.,90,【解答】 (1) GN的语言L(GN)是非负整数。(2) 最左推导： 最右推导：,.,91,3.3 已知文法GS为SaSb|Sb|b，试证明文法GS为二义文法。【解答】 由文法GS：SaSb|Sb|b，对句子aabbbb可对应如图3-4所示的两棵语法树。因此，文法GS为二义文法(对句子abbb也可画出两棵不同的语法树)。,.,92,图3-4 句子aabbbb对应的两棵不同语法树,.,93,3.4 已知文法GS为SSaS|，试证明文法GS为二义文法。【解答】 由文法GS：SSaS|，句子aa的语法树如图3-5所示。由图3-5可知，文法GS为二义文法。,.,94,图3-5 句子aa对应的两棵不同的语法树,.,95,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,.,96,(2) 为了构造字母表=a,b上同时只有奇数个a和奇数个b的所有串集合的正规式，我们画出如图3-6所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B；而由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发经过奇数个a到达终态C。由图3-6可直接得到正规文法GS如下： GS：SaA|bB AaS|bC|b BbS|aC|a CbA|aB|,.,97,图3-6,.,98,(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|a BaBB|b,.,99,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为最左直接短语。,.,100,能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足AAaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足Ac右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。,.,101,图3-7 习题3.6的语法树 (a) aAaBcbbdcc; (b) aAcbBdcc,.,102,(2) 句子acabcbbdcc的最左推导如下：,.,103,3.7 对于文法GS: S(L)|aS|aLL,S|S(1) 画出句型(S,(a)的语法树；(2) 写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。,.,104,【解答】 (1) 句型(S, (a)的语法树如图3-8所示。(2) 由图3-8可知：短语：S、a、(a)、S,(a)、(S,(a)；直接短语：a、S；句柄：S；素短语：素短语可由图3-8中相邻终结符之间的优先关系求得，即： # (， (a)#因此，素短语为a。,.,105,图3-8 句型(S,(a)的语法树,.,106,3.8 下述文法描述了C语言整数变量的声明语句：GD: DTLTint|long|shortLid|L,id(1) 改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2) 分别以上述文法GD和改造后的文法GD为输入序列int a,b,c构造分析树。,.,107,【解答】 (1) 消除左递归后，文法GD如下：DTLTint|long|shortLidLL,idL|(2) 未消除左递归的文法G(D)和消除左递归的文法GD为输入序列int a,b,c构造的分析树分别如图3-9的(a)、(b)所示。,.,108,图3-9 两种文法为int a,b,c构造的分析树(a) 文法G(D)； (b) 文法G(D),.,109,3.9 考虑文法GS: S(T) | a+S | aTT,S | S消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。【解答】 消除文法GS的左递归：S(T) | a+S | aTSTT,ST| ,.,110,提取公共左因子：S(T) | aSS+S | TSTT,ST| ,.,111,改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：void match (token t) if ( lookahead=t)lookahead=nexttoken; else error ( );void S ( ),.,112,if ( lookahead=a) match (a);S(); else if ( lookahead=()match ();T ( );if ( lookahead=) )match () );else error ( );,.,113,void S( ) if ( lookahead=+)match (+);S ( );void T ( ) S ( );T( );,.,114,void T ( ) if ( lookahead=, )match (, );S ( );T ( );,.,115,对于文法GS中的产生式：TT,S | S，即将非终结符T由下面的正规表达式定义： TS,S然后将其用状态转换图表示为图3-10。这个状态转换图的作用就如同一个递归过程(函数)，并借助于这种转换图来得到递归过程(函数)下降分析器。因此，前面的递归下降分析器程序可删除函数T()和T()，而将T()和T()改为,.,116,图3-10 非终结符T的状态转换图,.,117,void T()S();while (lookahead = ,)match (,);S();,.,118,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| ,.,119,来消除左递归。由此，将产生式BBb|d改造为BdBBbB| 其次，应通过提取公共左因子的方法来消除GA中的回溯，即将产生式AaABl|a改造为AaAAABl | 最后得到改造后的文法为GA：AaAAABl | BdBBbB| ,.,120,求得： FIRST(A)=a FIRST(A)=a, FIRST(B)=d FIRST(B)