编译原理习题和答案市公开课一等奖百校联赛获奖课件.pptx

1 1编译原理教程编译原理教程习题解析习题解析第一章第一章 绪绪 论论第二章第二章 词词 法法 分分 析析第三章第三章 语语 法法 分分 析析第1页2 2编译原理教程编译原理教程习题解析习题解析第一章绪论1.1完成以下选择题：(1)下面叙述中正确是。A编译程序是将高级语言程序翻译成等价机器语言程序程序B机器语言因其使用过于困难，所以现在计算机根本不使用机器语言C汇编语言是计算机唯一能够直接识别并接收语言D高级语言靠近人们自然语言，但其依赖详细机器特征是无法改变第2页3 3编译原理教程编译原理教程习题解析习题解析(2)将编译过程分成若干“遍”是为了。A提升程序执行效率B使程序结构愈加清楚C利用有限机器内存并提升机器执行效率D利用有限机器内存但降低了机器执行效率(3)结构编译程序应掌握。A源程序B目口号言C编译方法DAC项第3页4 4编译原理教程编译原理教程习题解析习题解析(4)编译程序绝大多数时间花在上。A犯错处理B词法分析B目标代码生成 D表格管理(5)编译程序是对。A汇编程序翻译B高级语言程序解释执行C机器语言执行D高级语言翻译第4页5 5编译原理教程编译原理教程习题解析习题解析【解答】(1)编译程序能够将用高级语言编写源程序转换成与之在逻辑上等价目标程序，而目标程序能够是汇编语言程序或机器语言程序。故选A。(2)分多遍完成编译过程可使整个编译程序逻辑结构愈加清楚。故选B。(3)结构编译程序应掌握源程序、目口号言和编译方法这三方面内容。故选D。第5页6 6编译原理教程编译原理教程习题解析习题解析(4)编译各阶段工作都包括到结构、查找或更新相关表格，即编译过程绝大部分时间都用在造表、查表和更新表格事务上。故选D。(5)由(1)可知，编译程序实际上实现了对高级语言程序翻译。故选D。第6页7 7编译原理教程编译原理教程习题解析习题解析1.2计算机执行用高级语言编写程序有哪些路径？它们之间主要区分是什么？【解答】计算机执行用高级语言编写程序主要有两种路径：解释和编译。在解释方式下，翻译程序事先并不采取将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序方法，而是每读入一条源程序语句，就将其解释(翻译)成对应其功效机器代码语句串并执行，然后再读入下一条源程序语句并解释执行，而所翻译机器代码语句串在该语句执行后并不保留。这种方法是按源程序中语句动态执行次序逐句解释(翻译)执行，假如一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。第7页8 8编译原理教程编译原理教程习题解析习题解析在编译方式下，高级语言程序执行是分两步进行：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。所以，编译对源程序处理是先翻译，后执行。从执行速度上看，编译型高级语言比解释型高级语言要快，但解释方式下人机界面比编译型好，便于程序调试。这两种路径主要区分在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。第8页9 9编译原理教程编译原理教程习题解析习题解析1.3请画出编译程序总框图。假如你是一个编译程序总设计师，设计编译程序时应该考虑哪些问题？【解答】编译程序总框图如图1-1所表示。作为一个编译程序总设计师，首先要深刻了解被编译源语言其语法及语义；其次，要充分掌握目标指令功效及特点，假如目口号言是机器指令，还要搞清楚机器硬件结构以及操作系统功效；第三，对编译方法及使用软件工具也必须准确化。总之，总设计师在设计编译程序时必须估量系统功效要求、硬件设备及软件工具等诸原因对编译程序结构影响。第9页10 10编译原理教程编译原理教程习题解析习题解析图图1-1 编译程序总框图编译程序总框图 第10页11 11编译原理教程编译原理教程习题解析习题解析第二章词法分析2.1完成以下选择题：(1)词法分析所依据是。A语义规则B构词规则C语法规则D等价变换规则(2)词法分析器输入是。A单词符号串B源程序C语法单位D目标程序第11页12 12编译原理教程编译原理教程习题解析习题解析(3)词法分析器输出是。A单词种别编码B单词种别编码和本身值C单词在符号表中位置D单词本身值(4)状态转换图(见图2-1)接收字集为_。A以0开头二进制数组成集合B以0结尾二进制数组成集合C含奇数个0二进制数组成集合D含偶数个0二进制数组成集合第12页13 13编译原理教程编译原理教程习题解析习题解析图图2-1 习题习题2.1DFA M 第13页14 14编译原理教程编译原理教程习题解析习题解析(5)对于任一给定NFAM，一个DFAM，使L(M)=L(M)。A一定不存在 B一定存在C可能存在D可能不存在(6)DFA适合用于。A定理证实 B语法分析C词法分析D语义加工第14页15 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)*第15页16 16编译原理教程编译原理教程习题解析习题解析【解答】(1)由教材第一章1.3节中词法分析，可知词法分析所遵照是语言构词规则。故选B。(2)词法分析器功效是输入源程序，输出单词符号。故选B。(3)词法分析器输出单词符号通常表示为二元式：(单词种别，单词本身值)。故选B。(4)即使选项A、B、D都满足题意，但选项D更准确。故选D。第16页17 17编译原理教程编译原理教程习题解析习题解析(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页18 18编译原理教程编译原理教程习题解析习题解析2.2什么是扫描器？扫描器功效是什么？【解答】扫描器就是词法分析器，它接收输入源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常把词法分析器作为一个子程序，每当语法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。第18页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所表示。第19页2020编译原理教程编译原理教程习题解析习题解析图2-2习题2.3NFAM 第20页21 21编译原理教程编译原理教程习题解析习题解析用子集法结构状态转换矩阵，如表2-1所表示。表2-1状态转换矩阵 将转换矩阵中全部子集重新命名，形成表2-2所表示状态转换矩阵，即得到第21页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.3DFA M其状态转换图如图其状态转换图如图2-3所表示。所表示。第22页2323编译原理教程编译原理教程习题解析习题解析图2-4图2-3化简后DFAM 第23页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所表示。所以，这两个正规式等价。第24页2525编译原理教程编译原理教程习题解析习题解析图2-5正规式(ab)*a对应NFA第25页2626编译原理教程编译原理教程习题解析习题解析图2-6正规式a(ba)*对应NFA第26页2727编译原理教程编译原理教程习题解析习题解析图2-7图2-5和图2-6确定化后状态转换矩阵 第27页2828编译原理教程编译原理教程习题解析习题解析图2-8最简DFA 第28页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所表示最简DFA。第29页3030编译原理教程编译原理教程习题解析习题解析图2-9(ab)*a和a(ba)*分别对应NFA 第30页31 31编译原理教程编译原理教程习题解析习题解析2.5设有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1)给出描述该语言正规表示式；(2)结构识别该语言确实定有限自动机(可直接用状态图形式给出)。【解答】该语言对应正规表示式为a(aa)*bb(bb)*a(aa)*，正规表示式对应NFA如图2-10所表示。第31页3232编译原理教程编译原理教程习题解析习题解析图2-10习题2.5NFA第32页3333编译原理教程编译原理教程习题解析习题解析用子集法将图2-10确定化，如图2-11所表示。由图2-11重新命名后状态转换矩阵可化简为(也可由最小化方法得到)0,213,54,67图2-11习题2.5状态转换矩阵 第33页3434编译原理教程编译原理教程习题解析习题解析按次序重新命名为0、1、2、3、4后得到最简DFA，如图2-12所表示。图2-12习题2.5最简DFA 第34页3535编译原理教程编译原理教程习题解析习题解析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页3636编译原理教程编译原理教程习题解析习题解析图2-13习题2.6NFA第36页3737编译原理教程编译原理教程习题解析习题解析用子集法将图2-13所表示NFA确定化，如图2-14所表示由图2-14可看出非终态2和4下一状态相同，终态6和8下一状态相同，即得到最简状态为012,4356,87第37页3838编译原理教程编译原理教程习题解析习题解析按次序重新命名为0、1、2、3、4、5、6，则得到最简DFA，如图2-15所表示。图图2-15 习题习题2.6最简最简DFA 第38页3939编译原理教程编译原理教程习题解析习题解析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页4040编译原理教程编译原理教程习题解析习题解析图图2-16 正规式正规式(a|b)*|aa)*b对应对应NFA第40页41 41编译原理教程编译原理教程习题解析习题解析图图2-17 图图2-16确定化后状态转换矩阵确定化后状态转换矩阵 第41页4242编译原理教程编译原理教程习题解析习题解析因为对非终态状态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页4343编译原理教程编译原理教程习题解析习题解析表2-3合并后状态转换矩阵 第43页4444编译原理教程编译原理教程习题解析习题解析图图2-18 习题习题2.7最简最简DFA 第44页4545编译原理教程编译原理教程习题解析习题解析图图2-19 正规式正规式(a|b)*b对应对应NFA 第45页4646编译原理教程编译原理教程习题解析习题解析比较图2-20与图2-17，重新命名后转换矩阵是完全一样，也即正规式(a|b)*b能够一样得到化简后DFA如图2-18所表示。所以，两个自动机完全一样，即两个正规文法等价。图图2-20 图图2-19确定化后状态转换矩阵确定化后状态转换矩阵第46页4747编译原理教程编译原理教程习题解析习题解析2.8结构一个DFA，它接收=a,b上全部不含abb字符串。解：=a,b上全部不含abb字符串可表示为b*(a*b)a*。第47页4848编译原理教程编译原理教程习题解析习题解析2.9结构一个DFA，它接收=a,b上全部含偶数个a字符串。解：=a,b上全部含偶数个a字符串可表示为(b|ab*a)*第48页4949编译原理教程编译原理教程习题解析习题解析2.10以下程序段以B表示循环体，A表示初始化，I表示增量，T表示测试：I=1;while(I=n)sun=sun+aI;I=I+1;请用正规表示式表示这个程序段可能执行序列。【解答】用正规表示式表示程序段可能执行序列为AT(BIT)*。第49页5050编译原理教程编译原理教程习题解析习题解析2.9将图2-21所表示非确定有限自动机(NFA)变换成等价确实定有限自动机(DFA)。其中，X为初态，Y为终态。【解答】用子集法将NFA确定化，如图2-22所表示。第50页51 51编译原理教程编译原理教程习题解析习题解析图图2-21 习题习题2.9NFA 第51页5252编译原理教程编译原理教程习题解析习题解析图图2-22 习题习题2.9状态转换矩阵状态转换矩阵22,Y2,422,Y2,42,42,42,4,Y2,4,Y2,4,Y第52页5353编译原理教程编译原理教程习题解析习题解析图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页5454编译原理教程编译原理教程习题解析习题解析图图2-23 习题习题2.9DFA 第54页5555编译原理教程编译原理教程习题解析习题解析 图图2-24 习题习题2.9最简最简DFA 第55页5656编译原理教程编译原理教程习题解析习题解析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页5757编译原理教程编译原理教程习题解析习题解析图图2-25 习题习题2.10NFA第57页5858编译原理教程编译原理教程习题解析习题解析由图2-26可看出，非终态2和非终态3面对输入符号a或b下一状态相同，故合并为一个状态，即最简状态0、1、2，3、4。图图2-26 习题习题2.10状态转换矩阵状态转换矩阵 第58页5959编译原理教程编译原理教程习题解析习题解析按次序重新命名为0、1、2、3，则得到最简DFA，如图2-27所表示。图图2-27 习题习题2.10最简最简DFA 第59页6060编译原理教程编译原理教程习题解析习题解析第三章语法分析3.1完成以下选择题：(1)程序语言语义需要用来描述。A上下文无关文法B上下文相关文法C正规文法 D短语文法(2)2型文法对应。A图灵机 B有限自动机C下推自动机 D线性界限自动机第60页61 61编译原理教程编译原理教程习题解析习题解析(3)下述结论中，是正确。A1型语言0型语言B2型语言1型语言C3型语言2型语言DAC均不成立(4)有限状态自动机能识别_。A上下文无关文法B上下文相关文法C正规文法D短语文法(5)文法GS：SxSx|y所识别语言是。AxyxB(xyx)*Cxnyxn(n0)Dx*yx*第61页6262编译原理教程编译原理教程习题解析习题解析(6)只含有单层分枝子树称为“简单子树”，则句柄直观解释是。A子树末端结点(即树叶)组成符号串B简单子树末端结点组成符号串C最左简单子树末端结点组成符号串D最左简单子树末端结点组成符号串且该符号串必须含有终止符第62页6363编译原理教程编译原理教程习题解析习题解析(7)下面对语法树错误描述是。A根结点用文法GS开始符S标识B每个结点用GS一个终止符或非终止符标识C假如某结点标识为，则它必为叶结点D内部结点能够是非终止符(8)由文法开始符S经过零步或多步推导产生符号序列是。A短语B句柄C句型D句子第63页6464编译原理教程编译原理教程习题解析习题解析(9)设文法GS：SSA|AAa|b则对句子aba规范推导是。ASSASAAAAAaAAabAabaBSSASAAAAAAAaAbaabaCSSASAASAaSbaAbaabaDSSASaSAaSbaAbaaba 第64页6565编译原理教程编译原理教程习题解析习题解析(10)假如文法GS是无二义，则它任何句子其。A最左推导和最右推导对应语法树必定相同B最左推导和最右推导对应语法树可能不一样C最左推导和最右推导必定相同D可能存在两个不一样最右推导，但它们对应语法树相同(11)一个句型分析树代表了该句型。A推导过程 B归约过程C生成过程 D翻译过程第65页6666编译原理教程编译原理教程习题解析习题解析(12)规范归约中“可归约串”由定义。A直接短语B最右直接短语C最左直接短语D最左素短语(13)规范归约是指。A最左推导逆过程B最右推导逆过程C规范推导D最左归约逆过程第66页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+TCi和P+T+i DP和P 第67页6868编译原理教程编译原理教程习题解析习题解析(16)采取自顶向下分析，必须。A消除左递归B消除右递归C消除回朔D提取公共左因子(17)对文法GE：EE+S|SSS*F|FF(E)|i则FIRST(S)=。A(B(,iCiD(,)第68页6969编译原理教程编译原理教程习题解析习题解析(18)确定自顶向下分析要求文法满足。A不含左递归B不含二义性C无回溯DAC项(19)递归下降分析器由一组递归函数组成，且每一个函数对应文法。A一个终止符B一个非终止符C多个终止符D多个非终止符(20)LL(1)分析表需要预先定义和结构两族与文法相关集合。AFIRST和FOLLOWBFIRSTVT和FOLLOWCFIRST和LASTVTDFIRSTVT和LASTVT第69页7070编译原理教程编译原理教程习题解析习题解析(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页71 71编译原理教程编译原理教程习题解析习题解析C文法可存在文法可存在QR句型且任何终止符对句型且任何终止符对(a,b)至多至多满足满足ab、a b和和a b三种关系之一三种关系之一D文法可存在文法可存在QR句型且任何终止符对句型且任何终止符对(a,b)满足满足ab、a b和和a b三种关系三种关系(23)任何算符优先文法任何算符优先文法 优先函数。优先函数。A有一个有一个 B没有没有 C有若干个有若干个 D可能有若干个可能有若干个(24)在算符优先分析中，用在算符优先分析中，用 来刻画可归约串。来刻画可归约串。A句柄句柄 B直接短语直接短语 C素短语素短语 D最左素短语最左素短语第71页7272编译原理教程编译原理教程习题解析习题解析(25)下面最左素短语必须具备条件中有错误是下面最左素短语必须具备条件中有错误是 。A最少包含一个终止符最少包含一个终止符 B最少包含一个非终止符最少包含一个非终止符 C除本身外不再包含其它素短语除本身外不再包含其它素短语 D在句型中含有最左性在句型中含有最左性(26)对文法对文法GS：Sb|(T)TT，S|S其其FIRSTVT(T)为为 。Ab,(Bb,)C，,b,(D，,b,)第72页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，则有，则有FIRST()FOLLOW(B)C若有若有AB，则有，则有FOLLOW(B)FOLLOW(A)D若有若有AB，则有，则有FOLLOW(A)FOLLOW(B)第73页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)分析法分析法 D算符优先分析法算符优先分析法第74页7575编译原理教程编译原理教程习题解析习题解析(31)下面下面 是采取句柄进行归约。是采取句柄进行归约。A算符优先分析法算符优先分析法 B预测分析法预测分析法 CSLR(1)分析法分析法 DLL(1)分析法分析法(32)一个一个 指明了在分析过程中某时刻能看到产生式指明了在分析过程中某时刻能看到产生式多大一部分。多大一部分。A活前缀活前缀 B前缀前缀 C项目项目 D项目集项目集(33)若若B为非终止符，则为非终止符，则AB为为 项目。项目。A接收接收 B归约归约 C移进移进 D待约待约第75页7676编译原理教程编译原理教程习题解析习题解析(34)在在LR(0)ACTION子表中，假如某一行中存在标识子表中，假如某一行中存在标识为为“rj”栏，则栏，则 。A该行必定填满该行必定填满rj B该行未填满该行未填满rj C其它行也有其它行也有rj DGOTO子表中也有子表中也有rj(35)LR分析法处理分析法处理“移进移进归约归约”冲突时，左结合冲突时，左结合意味着意味着 。A打断联络实施移进打断联络实施移进 B打断联络实施归约打断联络实施归约 C建立联络实施移进建立联络实施移进 D建立联络实施归约建立联络实施归约第76页7777编译原理教程编译原理教程习题解析习题解析(36)LR分析法处理分析法处理“移进移进归约归约”冲突时，右结合冲突时，右结合意味着意味着 。A打断联络实施归约打断联络实施归约 B建立联络实施归约建立联络实施归约 C建立联络实施移进建立联络实施移进 D打断联络实施移进打断联络实施移进第77页7878编译原理教程编译原理教程习题解析习题解析【解答解答】(1)参见第四章参见第四章4.1.1节，语义分析不像词法分析和语节，语义分析不像词法分析和语法分析那样能够分别用正规文法和上下文无关文法描述，法分析那样能够分别用正规文法和上下文无关文法描述，因为语义是上下文相关，所以语义分析须用上下文相关文因为语义是上下文相关，所以语义分析须用上下文相关文法描述。即选法描述。即选B。(2)2型文法对应下推自动机。故选型文法对应下推自动机。故选C。(3)因为不存在：因为不存在：3型语言型语言 2型语言型语言 1型语言型语言 0型型语言。故选语言。故选D。(4)3型文法即正规文法，它识别系统是有限状态自动型文法即正规文法，它识别系统是有限状态自动机。故选机。故选C。第78页7979编译原理教程编译原理教程习题解析习题解析(5)由由SxSx|y可知该文法所识别语言一定是：可知该文法所识别语言一定是：y左边左边出现出现x与与y右边出现右边出现x相等。故选相等。故选C。(6)最左简单子树末端结点组成符号串为句柄。故选最左简单子树末端结点组成符号串为句柄。故选C。(7)内部结点内部结点(指非树叶结点指非树叶结点)一定是非终止符。故选一定是非终止符。故选D。(8)由文法开始符由文法开始符S经过零步或多步推导产生符号序列经过零步或多步推导产生符号序列一定是句型，仅当推导产生符号序列全部由终止符组成时一定是句型，仅当推导产生符号序列全部由终止符组成时才是句子，即句子是句型阵列。故选才是句子，即句子是句型阵列。故选C。(9)规范推导即最右推导，也即每一步推导都是对句规范推导即最右推导，也即每一步推导都是对句型中最右非终止符用对应产生式右部进行替换。故选型中最右非终止符用对应产生式右部进行替换。故选D。第79页8080编译原理教程编译原理教程习题解析习题解析(10)文法文法GS一个句子假如能找到两种不一样最左推一个句子假如能找到两种不一样最左推导导(或最右推导或最右推导)，或存在两棵不一样语法树，则它任何句，或存在两棵不一样语法树，则它任何句子子其最左推导和最右推导对应语法树必定相同。故选其最左推导和最右推导对应语法树必定相同。故选A。(11)一个句型分析树代表了该句型归约过程。故选一个句型分析树代表了该句型归约过程。故选B。(12)规范归约中规范归约中“可归约串可归约串”即为句柄，也就是最左即为句柄，也就是最左直接短语。故选直接短语。故选C。(13)规范归约逆过程是规范推导，而规范推导即为最规范归约逆过程是规范推导，而规范推导即为最右推导。故选右推导。故选B。(14)由图由图3-1可知应选可知应选A。第80页81 81编译原理教程编译原理教程习题解析习题解析图图3-1 句型句型aAcbBdcc对应语法树对应语法树 第81页8282编译原理教程编译原理教程习题解析习题解析(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页8383编译原理教程编译原理教程习题解析习题解析图图3-2 句型句型P+T+i对应语法树及优先关系示意对应语法树及优先关系示意 第83页8484编译原理教程编译原理教程习题解析习题解析(19)递归下降分析器由一组递归函数组成，且每一个递归下降分析器由一组递归函数组成，且每一个函数对应文法一个非终止符。故选函数对应文法一个非终止符。故选B。(20)LL(1)分析表需要预先定义和结构两族与文法相分析表需要预先定义和结构两族与文法相关集合关集合FIRST和和FOLLOW。故选。故选A。(21)因为因为ab和和bc并不能使选项并不能使选项A、B、C成立。故选成立。故选D。(22)由算法优先文法可知应选由算法优先文法可知应选B。(23)有些算符优先文法不存在优先函数；有些算符优有些算符优先文法不存在优先函数；有些算符优先文法存在优先函数，且只要存在一对优先函数，就存在先文法存在优先函数，且只要存在一对优先函数，就存在无穷多对优先函数。故选无穷多对优先函数。故选D。(24)在算符优先分析中是以在算符优先分析中是以“最左素短语最左素短语”来刻画可来刻画可归约串。故选归约串。故选D。第84页8585编译原理教程编译原理教程习题解析习题解析(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页8686编译原理教程编译原理教程习题解析习题解析图图3-3 句子句子1+2*8+6语法树及值改变示意语法树及值改变示意 第86页8787编译原理教程编译原理教程习题解析习题解析(30)自底向上分析方法有算符优先分析法和自底向上分析方法有算符优先分析法和LR分析法。分析法。故选故选D。(31)自底向上分析采取归约方法，但算符优先分析用自底向上分析采取归约方法，但算符优先分析用“最左素短语最左素短语”归约，而归约，而LR分析用分析用“句柄句柄”归约。归约。SLR(1)是是LR分析法一个，故选分析法一个，故选C。(32)在在LR分析中，一个项目指明了在分析过程某个时分析中，一个项目指明了在分析过程某个时刻所看到产生式多大一部分。故选刻所看到产生式多大一部分。故选C。(33)对文法对文法GS，S称为称为“接收接收”项目；形如项目；形如Aa项目项目(其中其中a为终止符为终止符)称为称为“移进移进”项目；形如项目；形如AB项目项目(其中其中B为非终止符为非终止符)称为称为“待约待约”项目。故选项目。故选D。第87页8888编译原理教程编译原理教程习题解析习题解析(34)在在LR(0)ACTION子表中，假如某一行存在标注子表中，假如某一行存在标注为为“rj”栏，则该行必定填满栏，则该行必定填满rj，而在，而在SLR(1)ACTION子子表中，假如某一行存在标注为表中，假如某一行存在标注为“rj”栏，则该行可能未填栏，则该行可能未填满满rj。所以选。所以选A。(35)LR分析法处理分析法处理“移进移进归约归约”冲突时，左结合冲突时，左结合意味着打断联络而实施归约，右结合意味着维持联络而实意味着打断联络而实施归约，右结合意味着维持联络而实施移进。故选施移进。故选B。(36)由由(35)可知应选可知应选C。第88页8989编译原理教程编译原理教程习题解析习题解析3.2 令文法令文法GN为为 GN:ND|NDD0|1|2|3|4|5|6|7|8|9(1)GN语言语言L(G)是什么是什么?(2)给出句子给出句子0127、34和和568最左推导和最右推导。最左推导和最右推导。第89页9090编译原理教程编译原理教程习题解析习题解析【解答解答】(1)GN语言语言L(GN)是非负整数。是非负整数。(2)最左推导：最左推导：最右推导：最右推导：第90页91 91编译原理教程编译原理教程习题解析习题解析3.3 已知文法已知文法GS为为SaSb|Sb|b，试证实文，试证实文法法GS为二义文法。为二义文法。【解答解答】由文法由文法GS：SaSb|Sb|b，对，对句子句子aabbbb可对应如图可对应如图3-4所表示两棵语法树。所表示两棵语法树。所以，文法所以，文法GS为二义文法为二义文法(对句子对句子abbb也可也可画出两棵不一样语法树画出两棵不一样语法树)。第91页9292编译原理教程编译原理教程习题解析习题解析图图3-4 句子句子aabbbb对应两棵不一样语法树对应两棵不一样语法树 第92页9393编译原理教程编译原理教程习题解析习题解析3.4 已知文法已知文法GS为为SSaS|，试证实文法，试证实文法GS为二义文法。为二义文法。【解答解答】由文法由文法GS：SSaS|，句子，句子aa语法树如图语法树如图3-5所表示。所表示。由图由图3-5可知，文法可知，文法GS为二义文法。为二义文法。第93页9494编译原理教程编译原理教程习题解析习题解析图图3-5 句子句子aa对应两棵不一样语法树对应两棵不一样语法树 第94页9595编译原理教程编译原理教程习题解析习题解析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页9696编译原理教程编译原理教程习题解析习题解析(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|第96页9797编译原理教程编译原理教程习题解析习题解析图图3-6第97页9898编译原理教程编译原理教程习题解析习题解析(3)我们用一个非终止符我们用一个非终止符A代表一个代表一个a(即有即有Aa)，用，用一个非终止符一个