中国矿业大学编译原理试题A.doc

中国矿业大学2009-2010学年第一学期编译技术试卷（A）卷考试时间：100分钟 考试方式：闭卷班级：_姓名：_学号：_成绩：_一选择题(20分,每小题1分,答案请填写在答题纸上)1. 编译程序是对( )。A汇编程序的翻译 B高级语言程序的解释执行C机器语言的执行 D高级语言的翻译2. 构造编译程序应掌握( )。A源程序 B目标语言C编译方法 D以上三项都是3. 编译程序绝大多数时间花在( )上。A出错处理 B词法分析C目标代码生成 D表格管理4. 编译技术中描述单词符号的形成规则的常用工具有（ ）。A正规文法 B正规式C有穷自动机 D以上都是5. 编译技术中常用（ ）描述程序语言的语义。A正规文法 B上下文无法文法C属性文法 D上下文有关文法6. 词法分析器的输出结果是( )。A单词的种别编码 B单词在符号表中的位置C单词的种别编码和自身值 D单词自身值7. 以下( )不是DFA的组成部分。A有穷字母表 B初始状态集合C终止状态集合有限状态集合8. 正规式M1和M2等价是指( )。AMl和M2的状态数相等BM1和M2的有向边条数相等CM1和M2所识别的语言集相等DM1和M2状态数和有向边条数相等9. 下图所示的DFA M接受的字集为( )。XY001A以0开头的二进制数组成的集合B，以0结尾的二进制数组成的集合C含奇数个0的二进制数组成的集合D含偶数个0的二进制数组成的集合10. 有文法G（S）：SaA| a |bCAaS | bBBaC | bA | bCaB | bS则下列（）为L（G）中的句子。Aa100b50ab100 Ba1000b500abaCa500b60aab2a Da100b40ab10aa11. 文法GS：SxSx | y所识别的语言是（ ）。Axyx B(xyx)* Cxnyxn(n0) Dx*yx*12. 给定语言L为：所有以0开头，后接零个或多个10组成的符号串的集合，则描述它的正规文法GS应为（ ）。AS0A A10A | BSS10 | 0CS0B | 0 B1S D以上都是13. 如果文法G是无二义的，则它的任何句子( )。A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最左推导，但它们对应的语法树相同14. 以下文法（ ）是二义性文法。AGE：EE+T|T TT/F | F F(E) | iBGD：DTL Tint | long | short Lid | L,idCGS：Sif B then S Sif B then S else SSADGB：BAB | OB | not B | (B) | i rop i | i AB and OB or 15. 采用自上而下分析，必须( )。A消除左递归 B消除右递归C消除回溯 D提取公共左因子16. 虽然源程序可以直接翻译为目标语言代码，但是许多编译程序却采用了独于机器的、复杂性介于源语言和机器语言之间的中间语言。这样做的好处是（）A便于进行与机器无关的代码优化工作B使编译程序改变目标机更容易C使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰D以上说明都对17. 设a、b、c是文法的终结符，且满足优先关系a=b和b=c，则( )。A必有a=b B必有c=aC必有b=a Dac都不一定成立18. 在规范归约中，用( )来刻画可归约串。A直接短语 B句柄 C最左素短语 D素短语19. LR分析法不适用的文法有（ ）ASLR（1）文法B无二义的上下文有关文法C某些规定了优先关系和结合性的有二义的上下文无关文法D无二义的上下文无关文法20. 若a为终结符，则Aa为( )项目。A归约 B移进 C接受 D待约21. 若项目集I k含有A ，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“A ”动作归约的一定是( )文法。ALALR(1) BLR(0) CLR(1) DSLR(1)22. 同心集合并有可能产生新的( )冲突。A归约 B移进移进C移进归约 D归约归约23. 常用的语义分析方法有（ ）。ALR分析法 BOPG分析法CLL（1）分析法 D递归下降制导分析法和LR制导分析法24. 四元式之间的联系是通过( )实现的。A指示器 B临时变量 C符号表 D程序变量25. 间接三元式表示法的优点为( )。A采用间接码表，便于优化处理 B节省存储空间，不便于表的修改C便于优化处理，节省存储空间D节省存储空间，不便于优化处理26. 表达式(AB)(CD)的逆波兰表示为( )。AABCD BABCDCABCD DABCD27. 有一语法制导翻译如下所示：SbAb print “1” A(B print “2” Aa print “3” BAa) print “4” 若输入序列为b(aa)a)a)b，采用自下而上的分析方法，则输出序列为( )。A32224441 B3424242l C12424243 D3444221228. 代码优化的基本方法有（）。A删除公共子表达式B代码外提C强度削弱与合并已知量D以上都是 29. 在程序调试中出现的“变量未定义”错误是（ ）错误。A语义 B语法 C词法 D运行时30. 错误的局部化是指( )。A把错误理解成局部的错误B对错误在局部范围内进行纠正C当发现错误时，跳过错误所在的语法单位继续分析下去D当发现错误时立即停止编译，待用户改正错误后再继续编译一选择题(60分,每小题2分)题号答案DDDDCCBCDB题号答案CCACCDDBBB题号答案DCDBABBDAC二综合题（0分）1(分)已知文法G1(a,b,c,A,B,C,A, P1),其中P1：ABbCBaB|CcC|已知文法G2(a,b,c,D,E,D, P2),其中P2：DaD | bE |EcE |求：1）G1、G2所产生语言L1和L2的并、连结的文法。2）G1、G2各自产生语言闭包的文法。解答：1)并的文法：SA|D .(分)连结的文法：SAD|DA （分）2)闭包的文法：G1所产生的语言L1的闭包的文法为：S| AS（分）G2所产生的语言L2的闭包的文法为：S| DS（分）2（分）已知GS：S (AS)(b)A (SaA)(a)求符号串 (a) 和 (A(SaA)S) 的短语、直接短语和句柄。3(分)有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放3分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。4（分）已知:对下面方法GE:ETEE+E|TFTTT|FPFF*F |P(E) | a | b | 求：(1)计算这个文法的每个非终结符FIRST集和FOLLOW集(2)构造它的预测分析表(3)给出句子#(a+b)b#的分析过程。解答:(1) 求每个非终结符的First集和Follow集（4分） 求FIRST集FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,FIRST(E)=+,FIRST(T)=FIRST(T)=(,a,b, FIRST(F)=*, 求FOLLOW集由ETE (其中E为开始符)P(E)FOLLOW(E)=#,由ETEFOLLOW(E)=FOLLOW(E)=#,由ETEEFOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#由TFTFOLLOW(T)=FOLLOW(T)= +,#由TFTTFOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#由FPFFOLLOW(F)=FOLLOW(F)=(,a,b,+,),#由FPFFFOLLOW(P)=FIRST(F)FOLLOW(F)=*,+,(,),a,b,#构造它的预测分析表如下(4分)+*()Ab#ETETETETEEETFTFTFTFTTFPFPFPFPFF*FP(E)ab(3)给出句子#(a+b)b#的分析过程。(略2分)5（分）对以下表达式文法GE:EE+T|E-T|TTT*F|T/