编译原理样题(含答案)

编译原理试题计算机学院_____级班学号姓名题号一二三四五六七八九十总分满分得分一选择题1、编译原理各阶段工作都涉及(第1章)：A.词法分析B.表格管理C.语法分析D.语义分析2、正则表达式R1和R2等价是指(第4章)A.R1和R2都是定义在一个字母表上的正则表达式B.R1和R2中使用的运算符相同C.R1和R2代表同一正则集D.R1和R2代表不同正则集3、在以下的语法分析中，特别适合于表达式的分析。(第5，6，7章)A.LR分析B.LL(1)分析C.递归下降分析D.算符优先分析4、与（a|b）*(a|b)等价的正规式是。(第4章)A.a*|b*B.(ab)*(a|b)C.（a|b）（a|b）*D.（a|b）*5、在语法制导翻译中不采用拉链回填技术的语句是。(第8章)A.跳转语句B.赋值语句C.条件语句D.循环语句6、在属性文法中，终结符只具有属性。(第8章)A.传递B.继承C.抽象D.综合7、过程的Display表中记录了______。(第10章)A.过程的连结数据B.过程的嵌套层数C.过程的返回地址D.过程的入口地址二判断题1、最左归约也称为规范归约。(第3章)2、逆波兰法表示的表达式把运算对象放在运算符的后面。(第8章)3、同心集的合并有可能产生“归约/归约”冲突。(第7章)4、DFA可以通过多条路径识别一个符号串。(第4章)5、动态数组的存储空间在编译时就可完全确定。(第10章)三填空题1、词法分析所依循的是语言的；而中间代码生成所依循的是。(第4，8章)+2、在LR(0)分析法中，若,βV*且aTV则称“S.A”为项目，称“S.aβ”为项目。(第7章)3、规范规约每次规约的是句型的______________。(第6章)4、无符号常数的识别和计算该常数的工作，通常在____________阶段完成的。(第4章)四、设字母表为{a,b}的语言L的句子是满足下述条件的串：每个a都有b直接跟在右边。构造该语言的正则式。（第4章）五、将下图的NFA确定化为DFA,图中初态为X，终态为Y。(第4章)六、写一个2型文法G，使得L(G)={ai+2bi|i=0}∪{aibi+2|i=0}。(第3章)七、设文法G（S）：(第5章)S→S＋aF|aF|＋aFF→*aF|*a（1）消除左递归和左因子；（2）构造相应的FIRST和FOLLOW集合；（3）构造预测分析表。八、对文法G[S]:S→aSb|P(第6章)P→bPc|bQcQ→Qa|a请构造简单优先关系表，该文法是否是简单优先文法？九、设有以下程序段(第10章)programmain;vara,b:integer;procedurep(x,y,z:integer);beginy:=y*2;z:=z+xend;begina:=5;b:=2;p(a*b,a,a);write(a)end.对于下列参数传递方式，分别写出执行程序后a的输出值。（1）传值；（2）传地址；（3）值结果；（4）传名。十、文法G[S]及其LR分析表如下，请给出对串dada#的分析过程。(第7章)G[S]:1)S→VdB2)V→e3)V→ε4)B→a5)B→Bda6)B→ε状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5十一、试将下述程序段翻译成三地址形式的中间代码表示。(第8章)while(a+bcORa=b)while(a5ANDb10){a=a+1;b=b+1;}}十二、将下面程序划分为基本块，并画出其程序流图。read(A,B)F:=1C:=A*AD:=B*BifCDgotoL1E:=A*AF:=F+1E:=E+Fwrite(E)haltL1:E:=B*BF:=F+2E:=E+Fwrite(E)ifE100gotoL2haltL2:F:=F-1gotoL1十三、对PL/0语言扩充单词-=和--:(第2章)请完成下列识别单词‘-’，‘-＝’和‘--’（设单词内码分别为MINUS，MINUSBECOME和MINUSMINUS）的词法分析算法：if(CH=='-'){①;if(②){SYM=MINUSBECOME;GetCh();}elseif(CH=='-'){③}else④}答案一选择题b,c,d,c,b,d,b二判断题√×√××三填空题1、文法语义2、待约项目移进项目3、句柄4、词法四(b|ab)*五解：用子集法确定化如下表IIaIb状态{X,0,1,3}{0,1,3}..{2,3,Y}..{1,3}....{2,Y}....{Y}....{0,1,3}{0,1,3}{1,3}{1,3}{2,3,Y}{2,3,Y}{Y}....{2,Y}..{Y}....-X1+23+4+Y确定化后如下图六解：文法G（S）：SaSbSaaSbb七解：（1）（消除左递归，提公因左因子）S→aFS'|＋aFS'S'→＋aFS'|εF→*aF'F'→F|ε（2）FIRST（S）＝｛a，十｝FOLLOW（S）＝｛＃｝FIRST（50）＝｛＋，ε｝FOLLOW（S'）＝｛＃｝FIRST（F）＝｛*｝FOLLOW（F）＝（＋，＃）FIRST（F'）＝｛*，ε｝FOLLOW（＋，＃｝（3）八Head(S)={a,P,b}Head(P)={b}Head(Q)={Q,a}Tail(S)={b,P,c}Tail(P)={c}Tail(Q)={a}（1）“=”关系：a=SS=bb=PP=cb=QQ=cQ=a（2）“”关系：aHead(S)bHead(P)bHead(Q)（3）“”关系：Tail(S)bTail(P)cTail(Q)a简单优先关系矩阵如下：SabPQcS=a=b==P=Q==c由于矩阵中有元素存在多种优先关系，故不是简单优先文法。九（1）5；（2）20；（3）15；（4）30。十对输入串dada#的分析过程步骤状态栈文法符号栈剩余输入符号动作1234567800202402450246024670246780246##V#Vd#Vda#VdB#VdBd#VdBda#VdBdada#dada#ada#da#da#a###用V→ε归约移进移进用B→a归约移进移进用B→Bda归约用S→VdB归约901#S#接受十一解：三地址代码如下：100:t:=a+b101:iftcgoto105102:goto103103:ifa=bgoto105104:goto112105:ifa5goto107106:goto100107:ifb10goto109108:goto100109:a:=a+1110:b:=b+1111:goto105112:十二将程序划分为五个基本块，B1、B2、B3、B4和B5，如流图所示。read(A,B)B1F:=1C:=A*AD:=B*BifCDgotoL1E:=A*AB2F:=F+1E:=E+Fwrite(E)haltL1:E:=B*BB3F:=F+2E:=E+Fwrite(E)ifE100gotoL2haltB4L2:F:=F-1B5gotoL1十三GetCh();CH=='='SYM=MINUSMINUSSYM=MINUS