编译原理试卷

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
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
varD：T
D，i real
D，i
i
2、将ຫໍສະໝຸດ Baidu值语句x=a * b/(c＋2 * d )＋e*f＋g表示为相应的逆波兰式和四元式。
7、(对) LL（1）文法是无左递归、无二义性文法。
8、(错)语法分析时必须先消除文法中的左递归。
9、(错)包含公共左因子的文法也能直接用预测分析法来分析。
10、(对)编译方式与解释方式的根本区别在于是否生成目标代码。
三、应用（本题共4道小题，每小题10分，共40分）
1、设有文法G【S】：S→var D:T
分析表
状态ACTIONGOTO
r,i#SD
0S21
1acc
2S43
3r1 S5r1r1
4r3r3r3r3
5S6
6r2r2r2r2
D．词法分析、语法分析和代码生成
7、自底向上语法分析法的原理是（C）。
A.“移进——推导法”B.“最左推导法”
C.“移进——归约法”D.“推导——归约法”
8、无符号常数的识别与拼数工作通常在（C）阶段完成。
A.语法分析B.语义分析C.词法分析D.代码优化
9、下述方法中，（C）不是自底向上的语法分析方法。
课程名称：编译原理 专业班级：【本科】
单项选择题
判断题
应用
综合题
总分
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）。
优化后的代码：
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分析表。
A.规范归约B.算符优先分析法C.递归下降分析法D.LR分析法
10、算符优先分析法从左到右扫描输入串，当栈顶出现（D）时进行归约。
A.素短语B.直接短语C.句柄D.最左素短语
二、判断题（本题共10道小题，每小题2分，共20分）正确的画“√”，错误的画“X”
1、(错)对任何一个编译程序来说，产生中间代码是不可缺少的。
1、将文法拓广为G’[S’]：
（0）S’→S (1)S→rD (2) D→D,i (3) D→i
DFA：（10分）
因为上述DFA的I3状态集中有移进-归约冲突，
所以该文法不是LR(0)文法。
对于I3中： 归约项目S→rD•移进项目D→D•i
而：{i}∩FOLLOW(S)= {i}∩{＃} ＝Φ
所以可用SLR(1)方法解决I3的冲突。所以该文法是SLR(1)文法。（2分）
A．L0L1L2L3B．L3L2L1L0
C．L3=L2L1L0D．L0L1L2=L3
5、在状态转换图中，结点代表（D），用圆圈表示。
A．输入缓冲区B．向前搜索C．字符串D．状态
6、编译程序前三个阶段完成的工作是（C）。
A．词法分析、语法分析和代码优化
B．代码生成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码生成
2、(错)符号表的内容在词法分析阶段填入并在以后各阶段得到使用。
3、(错)设有一个LR（0）项目集I＝{X→α.Bβ, A→α.}，该项目集含有“归约－归约”冲突。
4、(错)对文法G中的一个句子，如果能够找到两种以上的推导，则该句子是二义性的。
5、(对)一个句型的句柄一定是文法某产生式的右部。
6、(对)设有一个LR（0）项目集Ii={X→α．，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在基本块后面还要被引用，请写出优化后的代码序列。