课程名称：编译原理 专业班级：【本科】

单项选择题 判断题 应用 综合题 20 20 40

20 总分 100 备注: 学生不得在试题纸上答题(含填空题、选择题等客观题)

一、单项选择题（本题共10道小题，每小题2分，共20分） 1、在产生式中，符号“→”（“::＝”）表示（ D ） 。

A. 等于 B. 恒等于 C. 取决于 D. 定义为 2、编译程序是对（ D ）程序进行翻译。

A. 汇编语言 B.机器语言 C.自然语言 D. 高级语言 3、合并表达式中的常量运算的目的是（ C ）。 A．合并常量，使表达式中的常量尽可能少 B．合并常量，使表达式尽可能简短

C．将可在编译时刻计算的运算在编译时刻计算出来，用所计算出来的值替换表达式中出现的所有这种运算，使得生成的代码指令尽可能少 D．以上都不是

4、对应Chomsky四种文法的四种语言之间的关系是（ B ）。 A．L0?L1?L2?L3 B．L3?L2?L1?L0 C．L3=L2?L1?L0 D．L0?L1?L2=L3 5、在状态转换图中，结点代表（ D ），用圆圈表示。

A．输入缓冲区 B．向前搜索 C．字符串 D．状态 6、编译程序前三个阶段完成的工作是（ C ）。 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码生成

7、自底向上语法分析法的原理是（ C ）。

A. “移进——推导法” B. “最左推导法” C. “移进——归约法” D. “推导——归约法”

8、无符号常数的识别与拼数工作通常在（ C ）阶段完成。

A. 语法分析 B. 语义分析 C. 词法分析 D. 代码优化 9、下述方法中，（ C ）不是自底向上的语法分析方法。

A. 规范归约 B.算符优先分析法 C.递归下降分析法 D.LR分析法 10、算符优先分析法从左到右扫描输入串，当栈顶出现（ D ）时进行归约。 A. 素短语 B. 直接短语 C.句柄 D. 最左素短语 二、判断题（本题共10道小题，每小题2分，共20分）正确的画“√”，错误的画“X” 1、( 错 ) 对任何一个编译程序来说，产生中间代码是不可缺少的。 2、( 错 ) 符号表的内容在词法分析阶段填入并在以后各阶段得到使用。

3、( 错 ) 设有一个LR（0）项目集I＝{X→α.Bβ, A→α.}，该项目集含有“归约－归约”冲突。 4、( 错 ) 对文法G中的一个句子，如果能够找到两种以上的推导，则该句子是二义性的。 5、( 对 ) 一个句型的句柄一定是文法某产生式的右部。 6、( 对 ) 设有一个LR（0）项目集Ii={X→α．，A→α．}，该项目集含有“归约-归约冲

突”。

7、( 对 ) LL（1）文法是无左递归、无二义性文法。 8、( 错 ) 语法分析时必须先消除文法中的左递归。

9、( 错 ) 包含公共左因子的文法也能直接用预测分析法来分析。 10、( 对 ) 编译方式与解释方式的根本区别在于是否生成目标代码。 三、应用（本题共4道小题，每小题10分，共40分）

1、设有文法G【S】： S→var D:T

D→D,i | i

T→real | integer

给出句子 var i,i,i: real的推导和语法树。 1、

S? var D:T? var D,i:T ? var D,i,i:T ? var ,i i,i:T ? var ,i i,i:real

语法树（5分,每步1分） S var D ： T

D ， i real

D ， i i

2、将赋值语句 x=a * b/(c＋2 * d )＋ e*f＋g 表示为相应的逆波兰式和四元式。 3、在自底向上语法制导翻译中，在对一个产生式归约时，立即执行相应的语义动作。

S → b A b { print “东” } A → ( B { print “南” } A → a { print “西” }

B → A a ) { print “北” }

当分析器的输入为 b(((aa)a)a)b 时，打印的字符串是什么？写出分析过程。 4、设有基本块： t1＝3*A

t2＝2*C t3＝t1＋t2 t4＝t3十5 t5＝2*C t6＝3*A t7＝t6＋t5 M＝t7－1 N＝t4－M

（1）画出DAG图； 4、DAG：

12 N

－

9 t4 11 M

- ＋

7 t3,t7 10 1 8 5

＋

3 t1,t6 6 t2,t5

* *

1 3 2 A 4 2 5 C

（2）假设只有M，N在基本块后面还要被引用，请写出优化后的代码序列。 优化后的代码： 1． t1＝3*A 2． t2＝2*C 3． t3＝t1＋t2 4． t4＝t3＋5 5． M＝t3－1 6． N＝t4－M

四、综合题（本题共1道小题，每小题20分，共20分） 1、对于下述文法G【A】： A→cAb | cAd |ε

（1）构造识别其规范句型所有活前缀的DFA；

（2）说明该文法是何种LR文法，并给出其相应的LR分析表。

1、将文法拓广为G’[S’]：

（0）S’→S (1)S→rD (2) D→D,i (3) D→i

DFA：（10分） I0: S’→．S S→．r D

二rrI2: S→r．D D→．D i D→．i D I3: S→r D． D→D． ，i SI：S’→S． 1S iI4: D→i． ， I5: D→D ， ．i i

因为上述DFA的I3状态集中有移进-归约冲突，

I6: D→D ， i ． 所以该文法不是LR(0)文法。

对于I3中： 归约项目S→rD? 移进项目D→D? i 而：{i} ∩ FOLLOW(S)= {i} ∩ {＃} ＝Φ

所以可用SLR(1)方法解决I3的冲突。所以该文法是SLR(1)文法。（2分）

分析表

状态 ACTION GOTO r , i # S D

0 S2 1 2

3 r1 4 r3 5

6 r2

S4 S5 r1 r3 r3 S6 r2 r2

1 acc

r1 r3

r2

3