《编译原理2009(a)试卷以及参考答案》由会员分享，可在线阅读，更多相关《编译原理2009(a)试卷以及参考答案（7页珍藏版）》请在金锄头文库上搜索。
1、注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。（第 1 页）试题纸课程名称： 编译原理（A ） 适用专业年级： 软件、计算机 2009 级（闭卷） 考生学号： 考 生 姓 名： 一、 单项选择题（30 分、每小题 2 分）1在编译过程中，语法分析器的任务是（ ）（1）分析单词是怎样构成的 （2）分析单词串是如何构成语句和说明的（3）分析语句和说明是如何构成程序的（4）分析程序的结构可选项有：A （2） （3） B （2） （3） （4） C （1） （2） （3） D （1） （2） （3） （4）2编译程序必须完成的工作有（ ）（1）词法分析 （
2、2）语法分析 （3）语义分析（4）代码生成 （5）中间代码生成（6）代码优化可选项有：A （1） （2） （3） （4） B （1） （ 2） （3） （4） （5） C （1 ） （2） （3） （4） （5） （6） D （1） （2） （ 3） （4） （6）3设有文法 GS=（b,S,B,S,S-b | bB , B-bS）,该文法所描述的语言是（ ）Ab i | i=0 B. b2i | i=0 C. b2i+1 | i=0 D. b2i+1| i=14已知语言 L=anbbn | n=1, 则下列文法中， （ ）可以产生语言 L。A. Z-aZb | aAb | b B.A-aAb
3、 C.Z-AbB D.Z-aAbA-aAb | b A-b A-aA | a A-aAb | bB-bB | b5设有文法 GI:I-I1 | I0 | Ia | Ic | a | b | c下列符号串中是该文法的句子有（ ）（1）ab0 （2）a0c01 （3）aaa （4）bc10可选项有：A(1) B （2） （3） （4） C(3) (4) D （1） （2） （3） （4）6编译原理是对（ ） 。A、机器语言的执行 B、汇编语言的翻译C、高级语言的翻译 D、高级语言程序的解释执行7 （ ）正规文法能产生语言：L=a nbn | n=1A. 存在一个 B. 不存在任何 C. 无法判断8
4、 （ ）这样一些语言，它们能被确定的有穷自动机识别，但不能用正规式表示。A. 存在 B. 不存在 C. 无法判断是否存在9LL（1）文法的条件是（ ）A. 对形如 U-x1 | x2 | | xn 的规则，要求 FIRST(xi)FIRST(x j)=,(ij)B. 对形如 U-x1 | x2 | | xn 的规则，若 xi *,则要求 FIRST(xj) FOLLOW(U)= 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。（第 2 页）C. A 和 BD. 都不是10在编译程序采用的优化方法中， （ ）是在基本块范围内进行的。（1） 合并已知常量
5、（2）删除多余运算（3） 强度消弱 （4）代码外提可选项有：A(1)（4） B （1） （2） C （3） （4） D （1） （3） （4）11文法：G：SxSx | y 所识别的语言是（ ） 。A、xyx B、 （xyx）* C、x*yx* D、x nyxn（n0）12采用自上而下分析，必须（ ） 。A、消除回溯 B、消除左递归C、消除右递归 D、提取公共左因子13xab + cde -*f/+:=是下列哪个赋值语句相应的后缀式（ ）Ax:=a+b+c*d-e/f Bx:=a+(b+c)*d-e/fCx:=a+b+c*(d-e)/f Dx:=a+b+c+(c*d)-e/f 14算符优先文法
6、是指（ ）的文法。没有形如 U-VW的规则式（U，V，W ）NV终结符号集合 中任意两个符号对之间至多有一种优先关系成立T没有相同的规则式右部没有形如 U- 的规则式选择项为： A. B. C. D.15高级语言编译程序常用的语法分析方法中，LR 分析方法属于（ ） 。A.自左至右 B.自顶向下 C.自底向上 D.自右至左二、填空题（20 分、每空 2 分）1文法G产生的 的全体是该文法描述的语言 。2在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法错误和部分 错误。3优化根据所涉及程序的范围，可分为局部优化， 和全局优化。4最右推导也称为 推导。注：1、教师命题时题目之间不留空白
7、； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。（第 3 页）5.文法 GZ:Z-Ab , A-Za | 该文法对应的正则表达式为 .6文法 GS：S-AB, A-Aa |, B-bBc | bc 描述的语言 L（GS）= 。7赋值语句 x:= (a-c)*d+e 的逆波兰式为 。8已知文法 GE：E-T | E+T, T-F | T*F, F-(E) | i 该文法的句型 T+F*F+i 的最左素短语是 。9正则集合 L=an|n0相应的正则表达式是 。10简单优先分析法每次规约当前句型的 。三、判断题.（10 分，每小题 2 分；对用、错用表示）1一个句型中的最左素短语称为该句型
8、的句柄。2左线性文法一定是二型（上下文无关）文法。3对任何一个正规集 L，都有一正规表达式 r，满足 L（r）=L。4解释程序和编译程序一样，生成目标代码。5算符优先关系表不一定存在对应的优先函数。四解答题（40 分）1对下面的文法G：(6分)S-bRST |R-Sa | eT-fRa |计算这个文法的每个非终结 符的FIRST集和FOLLOW集。FIRSTSRT2. 对于正规式 a(ba) * （10 分）（1）请画出与之等价的自动机（4 分）（2）将上述自动机确定化（3 分）（3）化简（3 分）FOLLOWSRT注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答
9、题册正面部分。（第 4 页）3、已知文法 G(E) （8 分）ET|ET TF|T *F F(E)|i （1）给出句型 T *Fi 的最右推导（2 分） （2）画出上面句型的语法树； （3 分）（3）给出句型 T *Fi 的全部短语。(3 分) 4对文法：（8 分） H-H;M | MM-d | aHb(1)计算文法的 FIRSTVT 和 LASTVT 集。 （4 分）FIRSTVTHM(2)构造算符优先关系表。 （4 分）a b d ;abd;5. 已知文法 GS。 （8 分）S-SS-(S)S-a（1）请构造该文法的以 LR（0）项目集为状态的识别活前缀的 DFA。 （6 分）（2）该文法
10、是 LR（0）文法吗？并给出理由。 （2 分）LASTVTHM注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。（第 5 页）2009级编译原理试卷（A）参考答案：一、单项选择题（30分、每小题2分）15：BACDB 610：CBBCB 1115：DACDC二、填空题（20分、每空2分）1、句子 2、语义 3、循环优化 4、规范 5、b(ab) *6、a nbmcm | n0;m1 7、xac-d*e+:= 8、F*F 9、a * 10、句柄三、判断题.（10分，每小题2分；对用、错用表示）1、 2、 3、 4、 5、四、解答题（40分）1、 （6分）
11、FIRSTS b R a b eT f (6分；每个非终结符的FIRST及FOLLOW集均为 1 分，错一个扣一分)2、 （10分）正规式-自动机：ba 2 341a（4 分；错一条边扣 1 分, 直到扣完）确定化 ：a b1 235235 44 3535 4(3 分;错一行扣 1 分,直到扣完 )FOLLOWS a f #R a b f #T a f #注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。（第 6 页）化简：b1a（3 分;错一条边，不得分）3、 （8 分）（1）句型 T *Fi 的最右推导： (2 分；每错一步推导扣 1 分，直到扣完
12、)E= E+T=E+F=E+i=T+i=T*F+i（2）语法树：（3 分；错一条边扣 1 分, 直到扣完）EE + TTT iFF*（3）短语：（3 分，多一个、少一个、错一个均扣 1 分，直到扣完)T *Fi T *F i4、 （8分）（1） FIRSTVTH a d ;M a d(4分；每个非终结符的FIRSTVT 及LASTVT集均为 1 分，错一个扣一分)(2)(4分；错一个关系扣一分，直到扣完)LASTVTH d b ;M d ba b d ;a d ; 注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。（第 7 页）5、 （8分）（1）S-.SS-.(S)S-.aS-S.S-a.S-(S).S-(S.)S-(.S)S-.(S)S-.aSa( a )S(（6 分，错 1 个、多 1 个、少 1 个状态均扣 1 分，直到扣完）(2)识别活前缀 DFA 中无冲突状态（1 分） ，因此该文法为 LR（0）文法。 （1 分）
