编译原理试卷

课程名称：编译原理专业班级：【本科】单项选择题判断题应用综合题总分20204020100备注:学生不得在试题纸上答题(含填空题、选择题等客观题)一、单项选择题（本题共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L3B．L3L2L1L0C．L3=L2L1L0D．L0L1L2=L35、在状态转换图中，结点代表（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→varD:TD→D,i|iT→real|integer给出句子vari,i,i:real的推导和语法树。1、SvarD:TvarD,i:TvarD,i,i:Tvar,ii,i:Tvar,ii,i:real语法树（5分,每步1分）SvarD：TD，irealD，ii2、将赋值语句x=a*b/(c＋2*d)＋e*f＋g表示为相应的逆波兰式和四元式。3、在自底向上语法制导翻译中，在对一个产生式归约时，立即执行相应的语义动作。S→bAb{print“东”}A→(B{print“南”}A→a{print“西”}B→Aa){print“北”}当分析器的输入为b(((aa)a)a)b时，打印的字符串是什么？写出分析过程。4、设有基本块：t1＝3*At2＝2*Ct3＝t1＋t2t4＝t3十5t5＝2*Ct6＝3*At7＝t6＋t5M＝t7－1N＝t4－M（1）画出DAG图；4、DAG：12N9t411M7t3,t7101853t1,t66t2,t5132A425C（2）假设只有M，N在基本块后面还要被引用，请写出优化后的代码序列。优化后的代码：1．t1＝3*A2．t2＝2*C3．t3＝t1＋t24．t4＝t3＋55．M＝t3－16．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→iDFA：（10分）**＋＋-－I0:S’→．SS→．rDI2:S→r．DD→．DiD→．iI1：S’→S．I3:S→rD．D→D．，iI4:D→i．I5:D→D，．i二rEcD三SEcrSi，i因为上述DFA的I3状态集中有移进-归约冲突，所以该文法不是LR(0)文法。对于I3中：归约项目S→rD•移进项目D→D•i而：{i}∩FOLLOW(S)={i}∩{＃}＝Φ所以可用SLR(1)方法解决I3的冲突。所以该文法是SLR(1)文法。（2分）分析表状态ACTIONGOTOr,i#SD0S211acc2S433r1S5r1r14r3r3r3r35S66r2r2r2r2I6:D→D，i．