编译原理试题计算机学院_级 班 学号 姓名 题号一二三四五六七八九十总分满分 得分一 选择题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)分析法中，若a,V*且a则称“S a.A”为 项目，称“S a.a”为 项目。(第7章)3、规范规约每次规约的是句型的_。 (第6章)4、无符号常数的识别和计算该常数的工作，通常在_阶段完成的。(第4章)四、设字母表为a,b的语言L的句子是满足下述条件的串：每个a都有b直接跟在右边。构造该语言的正则式。（第4章）五、将下图的NFA确定化为DFA,图中初态为X，终态为Y。(第4章)六、写一个2型文法G，使得L(G)=ai+2bi|i=0aibi+2|i=0。(第3章)七、设文法G（S）：(第5章) S SaF|aF|aF F *aF|*a（1）消除左递归和左因子；（2）构造相应的FIRST和FOLLOW集合；（3）构造预测分析表。八、对文法GS:S aSb | P (第6章)P bPc | bQcQ Qa | a请构造简单优先关系表，该文法是否是简单优先文法？ 九、设有以下程序段(第10章)program main;var a,b:integer;procedure p(x,y,z:integer); begin y:=y*2; z:=z+x end;begin a:=5; b:=2; p(a*b,a,a); write(a)end.对于下列参数传递方式，分别写出执行程序后a的输出值。（1）传值； （2）传地址； （3）值结果； （4）传名。十、文法GS及其LR分析表如下，请给出对串dada#的分析过程。(第7章) GS: 1) S VdB2) V e 3) V 4) B a 5) B Bda 6) B 状态ACTIONGOTOdea#SBV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5十一、试将下述程序段翻译成三地址形式的中间代码表示。(第8章)while ( a+bc OR a=b )while ( a5 AND b10 ) a=a+1; b=b+1; 十二、将下面程序划分为基本块，并画出其程序流图。read(A,B)F:=1C:=A*AD:=B*Bif C100 goto L2haltL2: F:=F-1goto L1十三、对PL/0语言扩充单词-=和-: (第2章) 请完成下列识别单词-，-和-（设单词内码分别为MINUS，MINUSBECOME和MINUSMINUS）的词法分析算法：if ( CH=- ) ; if ( ) SYM=MINUSBECOME; GetCh(); else if ( CH=- ) else 答案一 选择题b,c,d,c,b,d,b二 判断题三 填空题1、文法 语义 2、待约项目 移进项目3、句柄 4、词法四 (b|ab)*五解：用子集法确定化如下表IIaIb状态X,0,1,30,1,3.2,3,Y.1,3.2,Y.Y.0,1,30,1,31,31,32,3,Y2,3,YY.2,Y.Y.-X1+23+4+Y确定化后如下图六 解：文法G（S）：S aSbS aaS bb七 解： （1）（消除左递归，提公因左因子） SaFS|aFS SaFS| F*aF FF| （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=S S=b b=P P=c b=Q Q=c Q=a（2）“”关系： aHead(S) bHead(P) b”关系： Tail(S)b Tail(P)c Tail(Q)a简单优先关系矩阵如下：SabPQcS=a=b= =Q=c由于矩阵中有元素存在多种优先关系，故不是简单优先文法。九 （1）5； （2）20； （3）15； （4）30。十 对输入串dada#的分析过程步骤状态栈文法符号栈剩余输入符号动作1234567890020240245024602467024678024601#V#Vd#Vda#VdB#VdBd#VdBda#VdB#Sdada#dada#ada#da#da#a#用V 归约移进移进用B a归约移进移进用B Bda 归约用S VdB 归约接受 十一 解：三地址代码如下：100:t:=a+b101:if tc goto 105102:goto 103103:if a=b goto 105104:goto 112105:if a5 goto 107106:goto 100107:if b10 goto 109108:goto 100109:a:=a+1110: b:=b+1111:goto 105112:十二 将程序划分为五个基本块，B1、B2、B3、B4和B5，如流图所示。read(A,B) B1F:=1C:=A*AD:=B*Bif C100 goto L2