编译原理样题2(有答案).docx
编译原理试题计算机学院 级 班 学号 姓名b, c, d, c, b, b, b题号四五七八九十总分满分得分-选择题1、编译原理各阶段工作都涉及2 （第1章）:A.词法分析B.表格管理C.语法分析D.语义分析2、正则表达式R1和R2等价是指 3 （第4章）A.R1和R2都是定义在一个字母表上的正则表达式B.R1和R2中使用的运算符相同C . R1和R2代表同一正则集D.R1和R2代表不同正则集3、在以下的语法分析中，4特别适合于表达式的分析。（第5, 6, 7章）A.LR分析B.LL（l）分析C.递归下降分析D.算符优先分析4、与（a|b） * （a |b）等价的正规式是3。悌4章）A.a*| b*B. （ab） * （a|b） C. （a|b） （a|b） * D. （a|b） *5、在语法制导翻译中不采用拉链回填技术的语句是2。（第8章）A.跳转语句 B.赋值语句C.条件语句D.循环语句6、在属性文法中，终结符只具有B 属性。（第8章）A.传递 B.继承 C.抽象 D.综合7、过程的Display表中记录了 2。（第10章）A.过程的连结数据 B.过程的嵌套层数C.过程的返回地址 D.过程的入口地址二判断题1、最左归约也称为规范归约。（第3章）12、逆波兰法表示的表达式把运算对象放在运算符的后面。（第8章）03、同心集的合并有可能产生“归约/归约”冲突。（第7章）14、DFA可以通过多条路径识别一个符号串。（第4章）05、动态数组的存储空间在编译时就可完全确定。（第10章）0三填空题1、词法分析所依循的是语言的文法;而中间代码生成所依循的是语义 。（第4, 8章）2、在LR（O）分析法中，若a, 0eV,且aw吟则称“S ->a.A”为待约 项目，称“S fa.aB”为 移进 项目。（第7章）3、规范规约每次规约的是句型的句柄 o （第6章）4、无符号常数的识别和计算该常数的工作，通常在 词法阶段完成的。（第4章）四、设字母表为a, b的语言L的句子是满足下述条件的串：每个a都有b直接跟 在右边。构造该语言的正则式。（第4章）五、将下图的NFA确定化为DFA,图中初态为X,终态为Y。（第4章）六、写一个 2 型文法 G,使得 L（G）=a，+2b“i>=0Uaibi+2|i>=0。（第 3 章）七、设文法G（S）：（第5章）S - S + aFlaFI +aFF - *aF|*a（1）消除左递归和左因子；（2）构造相应的FIRST和FOLLOW集合；（3）构造预测分析表。八、对文法GS:S - aSb I P （第6章） P - bPc I bQc Q - Qa | a请构造简单优先关系表，该文法是否是简单优先文法？九、设有以下程序段（第10章）program main;var a,b:integer;procedure p（xfyz z:integer）;beginy:=y*2; z:=z+xend;begina:=5; b:=2; p(a*bz a,a) ; write (a) end.时于下列参数传递方式，分别写出执行程序后a的输出值。(1)传值；(2)传地址；(3)值结果：(4)传名。十、文法GS及其LR分析表如下，请给出对串dada#的分析过程。(第7章) GS: 1)S-VdB2)V -e3)V4)B -a5)B-Bda6)B 一£状态ACTIONGOTOdea#SBV0r3S3121acc2S43r24r6S5r665r4r46S7rl7S88r5r5十一、试将下述程序段翻译成三地址形式的中间代码表示。(第8章) while ( a+b<c OR a=b )while ( a<5 AND b<10 )(a=a+l;b=b+l;十二、将下面程序划分为基本块，并画出其程序流图。read(A,B)F:=lC：=A*AD:=B*Bif C<D goto LIE:=A*AF:=F+1E:=E+Fwrite(E)haltLI: E:=B*BF:=F+2E:=E+Fwrite(E)if E>100 goto L2 halt L2: F:=F-1goto LI十三、对PL/0语言扩充单词-=和一：(第2章)请完成下列识别单词，<='和'一'(设单词内码分别为MINUS, MINUSBECOME和MINUSMINUS)的词法分析算法：if ( CH=,-f ) ；if ( ® ) SYM=MINUSBECOME;GetChf); else if ( CH='" ) else)答案选择题b, c, d, c, b, d, bb, c, d, c, b, d, b二判断题 7x7xx1、3、填空题文法 语义句柄2、待约项目移进项目4、词法四(blab)*五解：用子集法确定化如下表确定化后如下图I工alb状态X,0,l,3(0,1,32,3,Y-X0,1,3)(0,1,3)2,3,Y12,3,Y d/31,30Y2,Y+2 32,YY1,3+ 4Y00+Y六解：文法G (S)：S >aSbS >aaS f bb七解：(1)(消除左递归，提公因左因子) S-aFS' | +aFS'S'->+aFS1 | e F-*aF'F'-F|s(2)04-*#SS-al?S*Sf+ aFS，S，Sj + alSSF4 a alF iFT'b'z->c(2)FIRST (S) = a,十)FIRST (S，)= + , 8 FIRST (F) = *FIRST(F' ) = *, £) (3)FOLLOW (S) = # FOLLOW (S1 ) = # FOLLOW (F) = ( + ,井)FOLLOW ( + ) = # Head(S)=a,P,b Tail(S)=b,PzcHead(P)=b Tail(P)=cHead(Q)=Qza Tail(Q)=aa=S S=b b=P P=c b=Q Q=c Q=a“”关系：a<Head(S) b<Head(P) b<Head(Q)(3) 关系：Tail (S)>b Tail (P)>c Tail (Q)>a简单优先关系矩阵如下:SabpQcS=a=< ><<>b<< >=<P>=Q=c>>由于矩阵中有元素存在多种优先关系，故不是简单优先文法。九 (1) 5;(2) 20;(3) 15;(4) 30o十对输入串dada#的分析过程步骤状态栈文法符号栈剩余输入符号动作10#dada#用V 归约202#vdada#移进3024#Vdada#移进40245#Vdada#用B -a归约50246#VdBda#移进602467#VdBda#移进7024678#VdBda#用B -Bda归约80246#VdB#用S -»VdB归约901#S#接受十一 解：三地址代码如下:100: t:=a+b101:if t<c goto 105102:goto 103103:if a=b goto 105104 :goto 112105:if a<5 goto 107106:goto 100107:if b<10 goto 109108:goto 100109:a:=a+l110:b:=b+lIll: goto 105112:GetChf);GetChf);如流图所示。SYM=M1NUSM工NUSSYM=MINUS
