华科《编译原理》试卷及答案

《编译原理》试卷第1页共7页《编译原理》试卷（A卷）2006—2007年度第二学期计算机学院2004级本科生考试形式：闭卷班级___________学号________________姓名___________题号一二三四五六七八九十总分核对人题分1010101015101010105100得分一、单项选择题（从下列各题四个备选答案中选出一个正确答案,将其代号A,B,C,D写在下表中，答题写在其它地方无效。（每项选择1分，共10分）题号12345678910答案ABDDCCCBAA1．在编译程序采用的优化方法中，是在基本块范围内进行的。①合并已知常量②删除多余运算③删除归纳变量④运算强度削弱⑤代码外提A.①②B.①⑤C.②④⑤D.③④⑤2．符号串ab1b2是文法G[A]：A→aB,B→bB|b的句子，该句子的句柄是________。A.b1B.b2C.aD.b1b23．文法所描述的语言是的集合。A.文法的字汇表V中符号组成的符号串B.文法的字汇表V中终结符号组成的符号串C.由文法开始符推导的符号串D.由文法开始符推导的终结符号串4．常用________来识别一个正规集。A.无穷自动机B.图灵机C.下推自动机D.有穷自动机5．生成能被5整除的正整数的文法G[Z]是________。A.G（Z）：Z→AC，A→BA|B，B→0|1|2|…|9，C→0|5B.G（Z）：Z→AC，A→BA|ε，B→0|1|2|…|9，C→0|5C.G（Z）：Z→AC|5，A→BA|B，B→0|1|2|…|9，C→0|5D.G（Z）：Z→AC|C，A→BA|B，B→0|1|2|…|9，C→0|56．“LL(1)分析法”这个术语中第一个L表示________。A.最左推导B.最左归约C.从左到右识别输入串D.规范归约得分评卷人《编译原理》试卷第2页共7页7．中缀表达式a＋b＋c＋d*(a－b)的逆波兰式是_______。A.bc＋a＋ab－d*＋B.bc＋a＋dab－*＋C.ab＋c＋dab－*＋D.abc＋＋dab－*＋8．对于LR(0)分析法，语法分析栈中存放的状态是识别规范句型____________的DFA状态。A．前缀B.活前缀D.LR(0)项目D.句柄9．下述语句类中，________在编译阶段通常不产生可执行代码。A.变量说明语句B.流程控制语句C.输入输出语句D.赋值语句10．算符文法是指的文法。①没有形如U→...VW...的规则（U，V，WVN）②VT中任意两个符号之间至多存在一种算符优先关系③没有相同右部的规则④没有形如U→ε的规则A.①B.①和②C.①、②和③D.①、②、③和④二、多选题（从下列各题四个备选答案中选出2至4个正确答案,将其代号A,B,C,D写在下表中,答题写在其它地方无效。每小题2分,共10分）题号12345答案ABBDCDCDABC1．符号串dbb是给定文法G[A]：A→dBC，B→aB|ε，C→bC|b的句子，试问其活前缀包括。A.εB.dC.dbD.dbb2．常见的自底而上语法分析方法有。A.递归下降分析B.算符优先分析C.LL(1)预测分析D.LR分析3．已知字母表Σ=｛a，b｝,下列________是字母表Σ上的正规式。A.ab+aB.abc|b*C.(a|b)*D.ε4．若G和G'是两个不同的文法，如果它们是等价的，那么。A.G'必须超出G所定义语言的范围B.G'应缩小G所定义语言的范围C.G和G'描述的语言相同D.G'既不超出G所定义语言的范围，也不缩小G所定义语言的范围5．一个文法是LR(0)文法一定也是。A.SLR(1)文法B.LR(1)文法C.LALR(1)文法D.OG文法得分评卷人《编译原理》试卷第3页共7页三、判断题(对下列叙述正确的说法，在题后打“√”，错误的打“×”。每小题1分,共10分)1．设A是符号串集，则A0＝ε。（×）2．在形式语言中，最右推导的逆过程称为规范归约。（√）3．一个语言的文法是唯一的。（×）4．如果一个语言是无穷集，则定义该语言的文法一定是递归的。（√）5．句型中出现某规则右部的子串，此子串一定是此句型的句柄。（×）6．句型的每个直接短语都是某规则的右部。（√）7．如果语言的文法是二义性，则该语言也是二义性的。（×）8．如果两个正规式的最小状态DFA是相同的，则这两个正规式是等价的。（√）9．任何正规文法都是上下文无关文法。（×）10．如果优先关系矩阵存在优先函数，则优先函数不是唯一的。（√）四、简述题（简洁回答下列问题，每小题5分,共10分）1．构造一个高级语言词法分析程序的基本步骤是什么？依据给定的源语言之单词集，设计其正规文法或正规式，之后等价地转换成非确定有穷自动机，再通过子集法将其确定化，最终将确定有穷自动机最小化，最后依据最小化的确定有穷自动机，设计词法分析程序。2．拟采用LL(1)预测分析法，构造一个高级语言语法分析程序的基本步骤是什么？采用LL(1)预测法构造语法分析程序时，其语法分析算法是通用的。基本步骤是依据给定的源语言，设计其上下文无关文法，并计算选择集SELECT()判定文法是否是LL(1)文法；如果不是LL(1)文法，则可以提取左公共因子法和消除左递归法进行等价转换，或重新设计文法，直到是LL(1)文法；之后，根据选择集SELECT()，构造LL(1)分析表。得分评卷人得分评卷人《编译原理》试卷第4页共7页五、试给出正规式R＝0(10|01)*0的下列等价转换的结果。（共15分）（1）给出与R等价的NFAM；（5分）（2）给出与NFAM等价的DFAM′；（5分）（3）给出与DFAM′等价的最小DFAM″；（5分）(1)根据正规式到转换NFA方法，构造NFAM(2)根据NFA到DFA转换方法，构造DFAM′(3)根据分割法，得等价状态划分如下:＝{{{X},{D}}，{{A,B,C},{C,B}}，{E,Y}}合并DFAM′的等价状态，得最小DFAM″如下：得分评卷人00XACBY0εε0DE11{A,B,C}{X}{E,Y}{D}{C,B}0011010{A,B,C}{X}{E,Y}0011《编译原理》试卷第5页共7页六、已知算符文法G[S]：S→*A，A→*∣0A1，(1)判断G[S]是否为算符优先文法；（5分）(2)如果是，试给出算符优先关系矩阵。（5分）（共10分）（1）计算FIRSTVT集和LASTVT集如下：FIRSTVT(S)={*},LASTVT(S)={*,1}FIRSTVT(A)={0,*},LASTVT(A)={1,*}计算算符优先关系如下：对于S→*A，FIRSTVT(A)，有：*0，**对于A→0A1，有：01对于A→0A1，FIRSTVT(A)，有：00，0*对于A→0A1，LASTVT(A)，有：11，*1显然，文法G是OG文法、没有空规则、任何两个终结符之间至多存在一种算符优先关系。所以文法G是算符优先文法。（2）根据(1)计算的算符优先关系，构造算符优先关系矩阵如下。七、请将如下三地址代码程序划分基本块，并作出其程序流图。（共10分）(1)I:=1;(2)Goto(4);(3)I:=I+1;(4)IfI≤Ngoto(6);(5)Goto(9);(6)T:=M+I;(7)M:=T;(8)Goto(3);(9)WriteM;(10)Halt得分评卷人得分评卷人《编译原理》试卷第6页共7页八、已知文法G[E]如下，（1）试构造识别文法LR(0)活前缀的DFA，（2）并据此指明该文法是否LR(0)文法，如果LR(0)文法，试构造LR(0)分析表。（10分）G[E]：E→aAA→cA|d（1）改写文法为G′[E′]：0．E′→E1．E→aA2．A→cA3．A→d识别文法LR(0)活前缀的DFA如下：(2)因为识别文法LR(0)活前缀的DFA的状态(即LR(0)项目集)中没有任何冲突项目，所以该文法是LR(0)文法。构造该文法LR(0)分析表如下。ACTIONGOTOacd#EA0S211acc2S5S343R3R3R3R34R1R1R1R15S5S366R2R2R2R2得分评卷人E′→.EE→.aAE′→.EE→a.AA→.cAA→.dE→aA.A→c.AA→.cAA→.dA→d.A→cA.EadAcdAcI0I1I2I3I4I5I6《编译原理》试卷第7页共7页九、试设计文法G，使得L(G)={anbmcndk|n≥1，m≥0，k≥0}。（共10分）G(S):S→ADA→aAc∣aBcB→Bb∣εD→Dd∣ε十、试证明下列文法G[S]具有二义性。（共5分）G[S]：S→aB|bAA→a|aS|bAAB→b|bS|aBB证明：∵文法G[S]的句子aabbab具有下列两棵不同的语法树∴G[S]是二义性文法得分评卷人得分评卷人SaBBaBbSbbAaSaBBaBbSbaBb