编译原理样题4(有答案)
编译原理试题
计算机学院_____级班学号姓名
一选择题
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 ∈T V 则称“S →α.A ”为 待约 项目，称“S →α.a β”为 项目。(第7章)
3、规范规约每次规约的是句型的______________。 (第6章)
4、无符号常数的识别和计算该常数的工作，通常在____________阶段完成的。(第4章)
四、设字母表为{a,b}的语言L 的句子是满足下述条件的串：每个a 都有b 直接跟在右边。构造该语言的正则式。（第4章）
五、将下图的NFA 确定化为DFA,图中初态为X ，终态为Y 。(第4章)
六、写一个2型文法G ，使得L(G)={a i+2b i |i>=0}∪{a i b i+2|i>=0}。(第3章)
七、设文法G （S ）：(第5章) S → S ＋aF|aF|＋aF F → *aF|*a
（1）消除左递归和左因子；
（2）构造相应的FIRST 和FOLLOW 集合； （3）构造预测分析表。
八、对文法G[S]:S → aSb | P (第6章)
P → bPc | bQc Q → 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）传名。
十、文法G[S]及其LR分析表如下，请给出对串dada#的分析过程。(第7章)
G[S]: 1) S →VdB2) V →e
3) V →ε 4) B →a
5) B →Bda 6) B →ε
十一、试将下述程序段翻译成三地址形式的中间代码表示。(第8章) while ( a+b while ( a<5 AND b<10 ) { a=a+1; b=b+1; } } 十二、将下面程序划分为基本块，并画出其程序流图。 read(A,B) F:=1 C:=A*A D:=B*B if C E:=A*A F:=F+1 E:=E+F write(E) halt L1: E:=B*B F:=F+2 E:=E+F write(E) if E>100 goto L2 halt L2: F:=F-1 goto 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)* 五 六解：文法G（S）： S →aSb S →aa S →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=S S=b b=P P=c b=Q Q=c Q=a （2）“<”关系： a ；（4）30。 九（1）5；（2）20；（3）15 十一解：三地址代码如下： 100: t:=a+b 101: if t 102: goto 103 103: if a=b goto 105 104: goto 112 105: if a<5 goto 107 106: goto 100 107: if b<10 goto 109 108: goto 100 109: a:=a+1 110: b:=b+1 111: goto 105 112: 十三 GetCh(); CH=='=' SYM=MINUSMINUS SYM=MINUS