资源描述
典型题解,编译原理,主讲教师：周时阳,2,根据课程基本知识点，结合测验常见题型，讨论典型题例解法。一般题型分为客观题和主观题两类。其中，客观题包括单项选择题、多项选择题和判断题等，主观题包括简答题、计算题和证明题等。本课程考查的知识点，请参看编译原理课程教学大纲和网络版课程内容中各章小结部分。,内容摘要,3,一、单选题,1文法所描述的语言是的集合。A.文法的字汇表V中符号组成的符号串B.文法的字汇表V中终结符号组成的符号串C.由文法开始符推导的符号串D.由文法开始符推导的终结符号串,D,2生成能被5整除的正整数的文法GZ是_。A.GZ:ZAC,ABA|B,B0|1|2|9,C0|5B.GZ:ZAC,ABA|,B0|1|2|9,C0|5C.GZ：ZADA0|A5，ABA|，B0|D，D1|2|9D.GZ：ZAC|C,ABA|B,B0|1|2|9,C0|5,C,4,3符号串ab1b2是文法GA：AaB,BbB|b的句子，该句子的句柄是_。A.b1B.b2C.aD.b1b2,解释：,B,5,4LL(1)文法中第一个L表示_。A.最左推导B.最左归约C.从左到右识别输入串D.规范归约,C,5对于LR(0)分析法，语法分析栈中存放的状态是识别规范句型_的DFA状态。A前缀B.活前缀C.LR(0)项目D.句柄,B,6,6算符文法是指的文法。没有形如U.VW.的规则（U，V，WVN）VT中任意两个符号之间至多存在一种算符优先关系没有相同右部的规则没有形如U的规则A.B.和C.、和D.、和,A,7下述语句类中，_在编译阶段通常不产生可执行代码。A.变量说明语句B.流程控制语句C.输入输出语句D.赋值语句,A,7,8在编译程序采用的优化方法中，是在循环语句范围内进行的。合并已知常量删除多余运算删除归纳变量运算强度削弱代码外提A.B.C.D.,D,9程序的基本块是指_。A.不含无条件转移语句的程序段B.不含条件转移语句的程序段C.不含停机的语句程序段D.仅含有一个入口语句和一个出口语句的顺序程序段,D,8,二、多选题,1符号串dbb是给定文法GA：AdBC，BaB|，CbC|b的句子，试问其活前缀包括。A.B.dC.dbD.dbb,2已知字母表=a，b,下列_是字母表上的正规式。A.ab+aB.abc|b*C.(a|b)*D.,A、B,C、D,9,3常见的自底而上语法分析方法有。A.递归下降分析B.算符优先分析C.LL(1)预测分析D.LR分析,B、D,4一个文法是LR(0)文法一定也是。A.SLR(1)文法B.LR(1)文法C.LALR(1)文法D.OG文法,A、B、C,10,1设A是符号串集，则A0。（）2在形式语言中，最右推导的逆过程称为规范归约。（）3一个语言的文法是唯一的。（）4句型的每个直接短语都是某规则的右部。（）5如果语言的文法是二义性，则该语言也是二义性的。（）6任何正规文法都是上下文无关文法。（）7符号表的主要作用是辅助语义分析和代码生成。（）,三、判断题,11,1构造一个高级语言的词法分析程序的基本技术线路是什么？,四、简述题,简答：依据给定的源语言之单词集，设计其正规文法或正规式，之后等价地转换成非确定有穷自动机，再通过子集法将其确定化，最终将确定有穷自动机最小化，最后依据最小化的确定有穷自动机，设计词法分析程序。,12,五、填空题,1编译程序是一种翻译程序，它将用户用高级语言编写的_翻译成等价的_的目标程序。2有这样一个推导过程，其每一步推导都是对符号串中最右的非终结符进行替换，我们把这种推导过程称为_。3属性文法中的属性分为综合属性和_两种。,源程序,汇编语言或机器语言,最右推导（或规范推导）,继承属性,13,4已知文法GA：A(B)|a|，BB，A|A，该文法的开始符号是_，非终结符号集合为_，终结符号集合为_。5自下而上的语法分析方法的基本思想是从待识别的输入串开始逐步_到文法的_。6已知文法GS：SAB,AaAb|c,BaBb|d，则对于非终结符A，FOLLOW(A)=_。,A,A,B,(,),a,归约,开始符,a,b,d,注解：FOLLOW可以采用依据定义直接计算，或依据教材所给算法计算。,14,六、解答题,1.已知文法GS：S*A，A*0A1。(1)求文法G非终结符的FIRSTVT集和LASTVT集；(2)构造文法G算符优先关系分析表，并判断G是否为算符优先文法。,解：（1）计算FIRSTVT集和LASTVT集FIRSTVT(S)=*,LASTVT(S)=*,1FIRSTVT(A)=0,*,LASTVT(A)=1,*,注解：FIRSTVT集和LASTVT集可以采用依据定义直接计算，或依据教材所给算法计算。,15,显然，文法G是OG文法、没有空规则、任何两个终结符之间至多存在一种算符优先关系。所以文法G是算符优先文法。,(2)对于S*A，FIRSTVT(A)，有：*0，*对于A0A1，有：01对于A0A1，FIRSTVT(A)，有：00，0*对于A0A1，LASTVT(A)，有：11，*1,FIRSTVT(A)=0,*,LASTVT(A)=1,*,构造文法G算符优先关系分析表如下。,16,2.试设计文法描述语言L=0n12n+1|n1。,解：G(S):S0S111,3.已知文法GS：SAB，AaAb|ab，BBc|，试写出该文法描述的语言。,解：L(G(S)anbncmn1,m0,4.将赋值语句a=b*(c+d)翻译成四元式。,解：(+，c，d，T1)(*，b，T1，T2)(+，T1，T3),17,5构造正规式R0(10|01)*0的DFAM。,解：(1)根据正规式到转换NFA方法，构造NFAM1,(2)根据NFA到DFA转换方法，构造DFAM,18,6给定文法GS：SaSb|,试判断GS是否为SLR(1)文法。,解：改写文法为GS:,GS:(0)SS(1)SaSb(2)S,构造识别LR(0)活前缀DFA,follow(s)#,bI0:afollow(s),I2:afollow(s)故GS是SLR(1)文法,19,7.已知文法GE：EEiTT，TT+FiFF，FE*(，试证明GE是二义性的。,解：句子(i(*存在如下两棵不同的语法树,GE是二义性的,20,
展开阅读全文