《2005年编译原理试题a》由会员分享，可在线阅读，更多相关《2005年编译原理试题a（10页珍藏版）》请在金锄头文库上搜索。
1、一选择题(60 分,每小题 2 分,答案请填写在答题纸上)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单
2、词在符号表中的位置 C单词的种别编码和自身值 D单词自身值7.以下( )不是 DFA 的组成部分。 A有穷字母表 B初始状态集合 C终止状态集合 有限状态集合8.正规式 M1 和 M2 等价是指( )。 AMl 和 M2 的状态数相等 BM1 和 M2 的有向边条数相等 CM1 和 M2 所识别的语言集相等 DM1 和 M2 状态数和有向边条数相等9.下图所示的 DFA M 接受的字集为( )。A以 0 开头的二进制数组成的集合 B，以 0 结尾的二进制数组成的集合 C含奇数个 0 的二进制数组成的集合 D含偶数个 0 的二进制数组成的集合10. 有文法 G（S）： SaA| a |bC Aa
3、S | bB BaC | bA | b CaB | bS 则下列（ ）为 L（G）中的句子。 Aa100b50ab100 Ba1000b500aba Ca500b60aab2a Da100b40ab10aa11. 文法 GS：SxSx | y 所识别的语言是（ ） 。 Axyx B(xyx)* Cxnyxn(n0) Dx*yx*12. 给定语言 L 为：所有以 0 开头，后接零个或多个 10 组成的符号串的集合，则 描述它的正规文法 GS应为（ ） 。 AS0A A10A | BSS10 | 0 CS0B | 0 B1S D以上都是13. 如果文法 G 是无二义的，则它的任何句子( )。 A最
4、左推导和最右推导对应的语法树必定相同 B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同 D可能存在两个不同的最左推导，但它们对应的语法树相同14. 以下文法（ ）是二义性文法。 AGE：EE+T|T TT/F | F F(E) | i BGD：DTL Tint | long | short Lid | L,id CGS：Sif B then S Sif B then S else S SA DGB：BAB | OB | not B | (B) | i rop i | i AB and OB or 15. 采用自上而下分析，必须( )。 A消除左递归 B消除右递归XY001
5、C消除回溯 D提取公共左因子16. 虽然源程序可以直接翻译为目标语言代码，但是许多编译程序却采用了独于机 器的、复杂性介于源语言和机器语言之间的中间语言。这样做的好处是（ ） A便于进行与机器无关的代码优化工作 B使编译程序改变目标机更容易 C使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端 和后端的接口更清晰 D以上说明都对17. 设 a、b、c 是文法的终结符，且满足优先关系 a=b 和 b=c，则( )。 A必有 a=b B必有 c=a C必有 b=a Dac 都不一定成立18. 在规范归约中，用( )来刻画可归约串。 A直接短语 B句柄 C最左素短语 D素短语19. L
6、R 分析法不适用的文法有（ ） 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 分析法
7、CLL（1）分析法 D递归下降制导分析法和 LR 制导分析法24. 四元式之间的联系是通过( )实现的。 A指示器 B临时变量 C符号表 D程序变量25. 间接三元式表示法的优点为( )。 A采用间接码表，便于优化处理 B节省存储空间，不便于表的修改C便于优化处理，节省存储空间 D节省存储空间，不便于优化处理26. 表达式(AB)(CD)的逆波兰表示为( )。 AABCD BABCD CABCD DABCD27. 有一语法制导翻译如下所示： SbAb print “1” A(B print “2” Aa print “3” BAa) print “4” 若输入序列为 b(aa)a)a)b，采用
8、自下而上的分析方法，则输出序列为( )。 A32224441 B3424242l C12424243 D3444221228. 代码优化的基本方法有（ ） 。 A删除公共子表达式 B代码外提 C强度削弱与合并已知量 D以上都是 29. 在程序调试中出现的“变量未定义”错误是（ ）错误。 A语义 B语法 C词法 D运行时30. 错误的局部化是指( )。 A把错误理解成局部的错误 B对错误在局部范围内进行纠正 C当发现错误时，跳过错误所在的语法单位继续分析下去 D当发现错误时立即停止编译，待用户改正错误后再继续编译一选择题(60 分,每小题 2 分)题号题号答案答案DDDDCCBCDB题号题号答案
9、答案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 （分）已
10、知 GS： S (AS)(b) A (SaA)(a) 求符号串 (a) 和 (A(SaA)S) 的短语、直接短语和句柄。解答解答：因为 S=(AS)= (a)S) (a) , 所以符号串(a)不是句型，它没有短语、直 接短语和句柄。(1 分) 又因为 S=(AS)=(A(AS)=(A(SaA)S) , 所以符号串(A(SaA)(b)是文法 G 的 句型。 （1 分）或符号串(A(SaA)S)对应的语法树（推导树）如下：（1 分）其短语有： （A（SaA）S） ） 以最上层 S 为根时 （SaA）S） 以第二层 S 为根时 （SaA） 以第三层 A 为根时 （SaA）并且是直接短语和句柄。 （1
11、 分）3(分)有一台自动售货机，接收 1 分和 2 分硬币，出售 3 分钱一块的硬糖。顾客 每次向机器中投放3 分的硬币，便可得到一块糖(注意：只给一块并且不找钱)。S（AS)S（AS)ASaA（)(1)写出售货机售糖的正规表达式；(2)构造识别上述正规式的最简 DFA。 解答解答 (1)设 a=l，b=2，则售货机售糖的正规表达式为 a(b|a(a|b)|b(a|b)。 （分） (2)画出与正规表达式 a(b|a(a|b)|b(a|b)对应的 NFA，如下图所示。 （分）子集法转化成 DFA，构造状态转换表正确（分） 分划法找等价状态,最小的 DFA。如下图所示（分） 。4 （分）（分）已知
12、:对下面方法 GE:ETE E+E| TFT TT| FPF F*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)=*, 2YabaX13babab23ab01bab a 求 FOLLOW
13、 集 由 ETE (其中 E 为开始符)P(E) FOLLOW(E)=#, 由 ETEFOLLOW(E)=FOLLOW(E)=#, 由ETEE FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),# 由 TFTFOLLOW(T)=FOLLOW(T)= +,# 由TFTT FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),# 由 FPFFOLLOW(F)=FOLLOW(F)=(,a,b,+,),# 由FPFF FOLLOW(P)=FIRST(F)FOLLOW(F)=*,+,(,),a,b,# 构造它的预测分析表如下(4 分)+*()Ab#ETETETETE EE TFTFTFTFT T FP FP
