石大编译原理期末复习题及参考答案

编译原理第1页共1页《编译原理》课程综合复习资料一、单选题1．文法：G：S→xSx|y所识别的语言是（）。A.xyxB.(xyx)*C.x*yx*D.xnyxn(n≥0)答案：D2．若状态k含有项目“A→α·”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A→α”归约的语法分析方法是（）。A.LALR分析法B.LR(0)分析法C.LR(1)分析法D.SLR(1)分析法答案：D3．词法分析器的输出结果是（）。A.单词自身值B.单词在符号表中的位置C.单词的种别编码D.单词的种别编码和自身值答案：D4．给定文法A→bA|ca，为该文法句子的是（）。A.bbaB.cabC.bcaD.cba答案：C5．若B为非终结符，则A→·B为（）。A.移进项目B.归约项目 C.接受项目 D.待约项目答案：D6．就文法的描述能力来说，有（）。A.SLR(1)⊂LR(0)B.LR(1)⊂LR(0)C.SLR(1)⊂LR(1)D.无二义文法⊂LR(1)答案：C7．如图所示自动机M，请问下列哪个字符串不是M所能识别的（）。A.bbaa B.abba C.abab D.aabb答案：D8．文法G：S→xSx|y所识别的语言是（）。A.xyxB.(xyx)*C.xnyxn(n≥0)D.x*yx*答案：C9．表达式(┐A∨B)∧(C∨D)的逆波兰表示为（）。A.┐AB∨∧CD∨B.A┐B∨CD∨∧C.AB∨┐CD∨∧D.A┐B∨∧CD∨答案：B10．如果文法G是无二义的，则它的任何句子α（）。A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但它们对应的语法树相同答案：A11．编译原理是对（）。A.机器语言的执行B.汇编语言的翻译C.高级语言的翻译D.高级语言程序的解释执行答案：C12．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括（）。A.模拟执行器B.解释器C.表格处理和出错处理D.符号执行器答案：C13．若a为终结符，则A→α·aβ为（）项目。A.归约B.移进C.接受D.待约答案：B14．文法S→aaS|abc定义的语言是（）。A.{a2kbc|k>0}B.{akbc|k>0} C.{a2k-1bc|k>0}D.{akakbc|k>0}答案：C15．两个有穷自动机等价是指它们的（）。A.状态数相等B.有向弧数相等C.所识别的语言相等D.状态数和有向弧数相等答案：C二、判断题1．正则文法其产生式为A->a，A->Bb，A,B∈VN，a、b∈VT。答案：错2．自上而下分析法是一种“移进—归约”法。答案：错3．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。答案：错4．产生式是定义语法范畴的一种书写规则。答案：对5．要构造行之有效的自上而下的分析器，则必须消除左递归。答案：错6．一个算符优先文法可能不存在算符优先函数与之对应。答案：对7．自下而上的分析法是一种“移进—归约”法。答案：对8．如果文法G是二义的，那么规范归约和规范推导是互逆的两个过程。答案：错9．编译程序与具体的机器有关,与具体的语言无关。答案：错10．计算机高级语言翻译成低级语言只有解释一种方式。答案：错11．递归下降法允许任一非终极符是直接左递归的。答案：对12．文法是描述语言的语法结构的形式规则。答案：对13．静态数组的存储空间可以在编译时确定。答案：错14．如果文法G是无二义的，那么规范归约和规范推导是互逆的两个过程。答案：对15．逆波兰法表示的表达式亦称前缀式。答案：对三、问答题1．给出与正规式R＝（ab）*（a|b*）ba等价的NFA。答案：与正规式R等价的NFA如下图：2．文法G[E]为：E→E+T|TT→T*F|FF→(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)⑶.(/,⑴,⑵)⑷.(*,b,c)⑸.(+,a,⑷)⑹.(-,⑶,⑸)4．翻译成四元式序列。Whilea＞0∨b＜0doBeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；答案：(1)(j>,a,0,(3))如果a大于0，跳转到标记为(3)的位置。(2)(j<,b,0,(3))如果b小于0，跳转到标记为(3)的位置。(3)(j,,,(9))否则，跳转到标记为(9)的位置。(4)(:=,X,,X+1)计算X+1并将结果赋给变量X。(5)(j>,a,0,(7))如果a大于0，跳转到标记为(7)的位置。(6)(j,,,(8))否则，无条件跳转到标记为(8)的位置。(7)(:=,a,,a-1)将a-1的结果赋给变量a。(8)(j,,,(9))无条件跳转到标记为(9)的位置。(9)(j>,a,0,(11))如果a大于0，跳转到标记为(11)的位置。(10)(j,,,(12))否则，无条件跳转到标记为(12)的位置。(11)(:=,b,,b+1)将b+1的结果赋给变量b。(12)(...)标记(12)指示循环结束。5．给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。G[S]为：S→D;D|DD→DB|BB→a|bI0:答案：I0:四、综合题1．判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。S→aHH→aMd|dM→Ab|εA→aM|e答案：首先计算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集S{a}{#}H{a，d}{#}M{a，e，ε}{d，b}A{a，e}{b}由于predict（H→aMd）∩predict（H→d）={a}∩{d}=predict（M→Ab）∩predict（M→ε）={a，e}∩{d，b}=predict（A→aM）∩predict（A→e）={a}∩{e}=所以该文法是LL(1)文法，LL(1)分析表如下表。adbe#S→aHH→aMd→dM→Ab→ε→ε→AbA→aM→e2．某语言的文法G为：E→aTd|εT→Eb|a证明G不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1)分析表。答案：拓广文法G'，增加产生式S'→E在项目集I0中：有移进项目E→·aTd和归约项目E→·存在移进-归约冲突，所以G不是LR(0)文法。.若产生式排序为：(0)S′→E(1)E→aTd(2)E→ε(3)T→Eb(4)T→aG′的LR(0)项目集族及识别活前缀的DFA如下图：由产生式知：Follow(E)={#，b}Follow(T)={d}在I0，I2中：Follow(E)∩{a}={#，b}∩{a}=在I5中：Follow(E)∩{a}={#，b}∩{a}=Follow(T)∩{a}={d}∩{a}=Follow(T)∩Follow(E)={d}∩{#，b}=所以在I0，I2，I5中的移进-归约和归约-归约冲突可以由Follow集解决，所以G′是SLR(1)文法。构造的SLR(1)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r33．给定文法G[S]：S→ABA→aB|bS|cB→AS|d⑴请给出每一个产生式右部的First集；⑵请给出每一个非终结符号的Follow集；⑶请构造该文法的LL(1)分析表；⑷什么是LL(1)文法？该文法是LL(1)文法吗？为什么？答案：（1）First(AB)={a，b，c}First(aB)={a}First(bS)={b}First(c)={c}First(AS)={a，b，c}First(d)={d}（2）Follow(S)={#，a，b，c，d}Follow(A)={a，b，c，d}Follow(B)={#，a，b，c，d}（3）LL(1)分析表VNVTabcd#SS→ABS→ABS→ABAA→aBA→bSA→CBB→ASB→ASB→ASB→d（4）对于文法G的每一个非终结符U的产生式U→α1|α2|…|αn，如果SELECT(U→αi)→SELECT(U→αj)=→（i≠j,i,j=1,2,…,n），则文法G是一个LL(1)文法。该文法是LL(1)文法。因为SELECT(A→aB)→SELECT(A→bS)→SELECT(A→C)=→SELECT(B→AS)→SELECT(B→d)=→4．给定文法G[S]：S→SaA|aA→AbS|b⑴请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA。⑵请构造该文法的LR(0)分析表。⑶什么是LR(0)文法？该文法是LR(0)文法吗？为什么？⑷什么是SLR(1)文法？该文法是SLR(1)文法吗？为什么？答案：⑴拓广文法G[S′]:S′→S⑴S→SaA⑵S→a⑶A→AbS⑷A→b⑸该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA：⑵该文法的LR(0)分析表：状态ACTIONGOTOab#SA0S211S3acc2r3r3r33S544r2r2/S6r25r5r5r56S277r4/S3r4r4⑶LR(0)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中没有冲突状态。该文法不是LR(0)文法因为存在冲突状态：I4和I7⑷SLR(1