石大编译原理期末复习题及参考答案.docx
编译原理课程综合复习资料一、单选题1 .文法：G：STXSXly所识别的语言是()。A.xyxB.(xyx)*C.x*yx*D.xnyxn(nO)答案：D2 .若状态k含有项目"A-”,且仅当输入符号aFOLLOW（八）时，才用规则“Aa”归约的语法分析方法是()。A.LALR分析法B.LR(O)分析法CLR(I)分析法DSLR(I)分析法答案：D3 .词法分析器的输出结果是()。A.单词自身值B.单词在符号表中的位置C.单词的种别编码D.单词的种别编码和自身值答案：D4 .给定文法ATbAlCa,为该文法句子的是()。A.bbaB.cabC.bcaD.cba答案：C5 .若B为非终结符，则AB(3为()。A.移进项目B.归约项目C.接受项目D.待约项目答案：D6 .就文法的描述能力来说，有()。A.SLR(1)LR(O)B.LR(1)LR(O)C.SLR(1)LR(1)D.无二义文法ULR(I)答案：C7 .如图所示自动机M,请问下列哪个字符串不是M所能识别的()。A.bbaaB.abbaC.ababD.aabb答案：D8 .文法G：STXSXIy所识别的语言是()。A.xyxB.(xyx)*C.xnyxn(11O)D.x*yx*答案：C9 .表达式(IAVB)A(CVD)的逆波兰表示为()。AnABVACDVBAqBVCDVAC.ABV11CDVADAqBVACDV答案：B10 .如果文法G是无二义的，则它的任何句子()。A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的语法树相同答案：A11 .编译原理是对OOA.机器语言的执行B.汇编语言的翻译C.高级语言的翻译D.高级语言程序的解释执行答案：C12 .通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括（）。A.模拟执行器B.解释器C.表格处理和出错处理D.符号执行器答案：C13 .若a为终结符，则Aa为（）项目。A.归约B.移进C.接受D.待约答案：B14 .文法STaaSlabC定义的语言是（）。A.a2kbck>0B.akbck>OC.a2k-lbck>0D.akakbck>O答案：C15 .两个有穷自动机等价是指它们的（）。A.状态数相等B.有向弧数相等C.所识别的语言相等D.状态数和有向弧数相等答案：C二、判断题1 .正则文法其产生式为A->a,A->Bb,A,BVN,a、bVTo答案：错2 .自上而下分析法是一种“移进一归约”法。答案：错3 .进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。答案：错4 .产生式是定义语法范畴的一种书写规则。答案：对5 .要构造行之有效的自上而下的分析器，则必须消除左递归。答案：错6 .一个算符优先文法可能不存在算符优先函数与之对应。答案：对7 .自下而上的分析法是一种“移进一归约”法。答案：对8 .如果文法G是二义的，那么规范归约和规范推导是互逆的两个过程。答案：错9 .编译程序与具体的机器有关,与具体的语言无关。答案：错10 .计算机高级语言翻译成低级语言只有解释一种方式。答案：错11 .递归下降法允许任一非终极符是直接左递归的。答案：对12 .文法是描述语言的语法结构的形式规则。答案：对13 .静态数组的存储空间可以在编译时确定。答案：错14 .如果文法G是无二义的，那么规范归约和规范推导是互逆的两个过程。答案：对15 .逆波兰法表示的表达式亦称前缀式。答案：对三、问答题1.给出与正规式R=(ab)*(ab*)ba等价的NFA。答案：与正规式R等价的NFA如下图：2.文法GE为:EE+TTTT*FFF(E)i试给出句型(E+F)*i的短语，简单(直接)短语，句柄和最左素短语。答案：短语有：(E+F)*i,(E+F),E+F,F,i简单(直接)短语有：F,i句柄是：F最左素短语是：E+F3.写出表达式(a+b)(a-b)-a(a+b*c)的三元式序列。答案：.(+,a,b)"a,b)(3).(/,(1),(2).(*,b,c)(5) .(+,a,(4)(6) .(-,(3),(5)4.翻译成四元式序列。Whilea>0Vb<0doBeginX：=x+l;ifa>0thena：=a1elseb：=b+lEnd；答案：(1) (j>,a,O,(3)如果a大于O,跳转到标记为(3)的位置。(2) (j<,b,0,(3)如果b小于0,跳转到标记为的位置。(j,(9)否则，跳转到标记为(9)的位置。(4)(:=X,X+1)计算X+1并将结果赋给变量Xo(5)(j>,a,0,(7)如果a大于0,跳转到标记为的位置。(6)(j,(8)否则，无条件跳转到标记为(8)的位置。(7)(:=a,a-l)将a-1的结果赋给变量a。(8)(j,(9)无条件跳转到标记为的位置。(9)G>,a,0,(11)如果a大于0,跳转到标记为(11)的位置。(10)0,(12)否则，无条件跳转到标记为(12)的位置。(11)C=,b,b+l)将b+1的结果赋给变量bo(12)(.)标记(12)指示循环结束。5.给出文法GS的LR(I)项目集规范族中Io项目集的全体项目。GS为:SD;DlDDDBBBab答案:SD.D.#S-*D,#D-DB,tt/./a/bDfB,tt/./a/bB*a,#/;/a/bB-b,*,ab四、综合题1.判断下面文法是否为LL(I)文法，若是，请构造相应的LL(I)分析表。SaHHaMddMAbAaMe答案：首先计算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集S#Ha，d#Ma,e,d，bAa，eb由于PrediCt(HaMd)Apredict(Hd)=ad=PJpredict(MAb)Apredict(M)=a,ed,b="predict(AaM)predict(Ae)=ae=CT所以该文法是LL(I)文法，LL(I)分析表如下表。adbe#SaHHaMddMAbAbAaMe2.某语言的文法G为：EaTdTEba证明G不是LR(O)文法而是SLR(I)文法，请给出该文法的SLR(I)分析表。答案：拓广文法G，增加产生式STE在项目集IO中：有移进项目EaTd和归约项目E存在移进-归约冲突，所以G不是LR(O)文法。若产生式排序为：(0)SJE(l)EaTd(2)ET-Eb(4)TaG，的LR(O)项目集族及识别活前缀的DFA如下图:由产生式知：Follow(E)=#,bFollow(T)=d在K),12中：Follow(E)a=,ba=H在15中：Follow(E)a=,ba=OFollow(T)a=da=0Follow(T)Follow(E)=dA#,b=P!所以在10,12,15中的移进-归约和归约-归约冲突可以由FoUoW集解决，所以G，是SLR(I)文法。构造的SLR(I)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436rlrl7r33.给定文法GS:SABAaBbScBASd请给出每一个产生式右部的First集；请给出每一个非终结符号的Follow集；请构造该文法的LL(I)分析表；什么是LL(I)文法？该文法是LL(I)文法吗？为什么？答案：(1) First(AB)=a,b,cFirst(aB)=aFirst(bS)=bFirst(c)=cFirst(AS)=a,b,cFirst(d)=d(2) FouOW(三)=#,a,b,c,dFollow（八）=a,b,c,dFollow(B)=#,a,b,c,d(3) LL(I)分析表VNVTabCd#SSABSABSABAAaBAbSACBBASBASBASBd(4)对于文法G的每一个非终结符U的产生式UTalIa2.an,如果SELECT(Uai)SELECT(Uaj)=(ij,i,j=l,2,11),则文法G是一个LL(I)文法。该文法是LL(I)文法。因为SELECT(AaB)SELECT(AbS)SELECT(AC)=SELECT(BAS)SELECT(Bd)=(4) 定文法GS:SSaAaAAbSb请构造该文法的以LR(O)项目集为状态的识别规范句型活前缀的DFAo请构造该文法的LR(O)分析表。什么是LR(O)文法？该文法是LR(O)文法吗？为什么？什么是SLR(I)文法？该文法是SLR(I)文法吗？为什么？答案：拓广文法GS,:S,S(1)SSaA(2)SaAAbS(4)Ab(5)该文法的以LR(O)项目集为状态的识别规范句型活前缀的DFA：该文法的LR(O)分析表:状态ACTIONGOTOab#SA0S211S3acc2r3r3r33S544r2r2S6r25r5r5r56S277r4S3r4r4LR(O)文法：该文法的以LR(O)项目集为状态的识别规范句型活前缀的DFA中没有冲突状态。该文法不是LR(O)文法因为存在冲突状态：14和174 4)SLR(I)文法:该文法的以LR
