《编译原理思考题.doc》由会员分享，可在线阅读，更多相关《编译原理思考题.doc（7页珍藏版）》请在金锄头文库上搜索。
1、 一、 单项选择题（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）语法分析 （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
2、,B,S,S-b | bB , B-bS）,该文法所描述的语言是（ ） Abi | 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 C.Z-AbB D.Z-aAb A-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 可选
3、项有： A(1) B（2）（3）（4） C(3) (4) D（1）（2）（3）（4）6编译原理是对（）。A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行7（ ）正规文法能产生语言：L=anbn | n=1A. 存在一个 B. 不存在任何 C. 无法判断8（ ）这样一些语言，它们能被确定的有穷自动机识别，但不能用正规式表示。A. 存在 B. 不存在 C. 无法判断是否存在9LL（1）文法的条件是（ ）A. 对形如 U-x1 | x2 | | xn的规则，要求FIRST(xi)FIRST(xj)=,(ij)B. 对形如 U-x1 | x2 | | xn的规则，若xi
4、*,则要求FIRST(xj) FOLLOW(U)= C. A和BD. 都不是10在编译程序采用的优化方法中，（ ）是在基本块范围内进行的。（1） 合并已知常量（2）删除多余运算（3） 强度消弱 （4）代码外提可选项有：A(1)（4） B（1）（2） C（3）（4） D（1）（3）（4）11文法：G：SxSx | y所识别的语言是（）。A、xyxB、（xyx）*C、x*yx*D、xnyxn（n0）12采用自上而下分析，必须（）。A、消除回溯 B、消除左递归C、消除右递归 D、提取公共左因子13xab + cde -*f/+:=是下列哪个赋值语句相应的后缀式（ ）Ax:=a+b+c*d-e/f B
5、x:=a+(b+c)*d-e/fCx:=a+b+c*(d-e)/f Dx:=a+b+c+(c*d)-e/f 14算符优先文法是指（ ）的文法。 没有形如U-VW的规则式（U，V，W） 终结符号集合中任意两个符号对之间至多有一种优先关系成立 没有相同的规则式右部 没有形如U-的规则式选择项为： A. B. C. D.15高级语言编译程序常用的语法分析方法中，LR分析方法属于（ ）。A.自左至右 B.自顶向下 C.自底向上 D.自右至左二、填空题（20分、每空2分）1文法G产生的 的全体是该文法描述的语言。2在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法错误和部分 错误。3优化根据所
6、涉及程序的范围，可分为局部优化， 和全局优化。4最右推导也称为 推导。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一个句型中的最左素短语称为该句型的句柄。2左线性文法
7、一定是二型（上下文无关）文法。3对任何一个正规集L，都有一正规表达式r，满足L（r）=L。4解释程序和编译程序一样，生成目标代码。5算符优先关系表不一定存在对应的优先函数。四解答题（40分）1对下面的文法G：(6分)S-bRST |R-Sa | eT-fRa |计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST S R TFOLLOW S R T2. 对于正规式 a(ba)* （10分）（1）请画出与之等价的自动机（4分）（2）将上述自动机确定化（3分）（3）化简（3分）3、已知文法G(E) （8分） ET|ET TF|T *F F(E)|i （1）给出句型 T *Fi 的最
8、右推导（2分） （2）画出上面句型的语法树； （3分） （3）给出句型 T *Fi 的全部短语。(3分) 4对文法：（8分） H-H;M | MM-d | aHb(1)计算文法的FIRSTVT和LASTVT集。（4分）FIRSTVTHMLASTVTHM (2)构造算符优先关系表。（4分）abd;abd;5. 已知文法GS。（8分）S-S S-(S) S-a （1）请构造该文法的以LR（0）项目集为状态的识别活前缀的DFA。（6分）（2）该文法是LR（0）文法吗？并给出理由。（2分）参考答案：一、 单项选择题（30分、每小题2分）15：BACDB 610：CBBCB 1115：DACDC二、 填
9、空题（20分、每空2分）1、句子 2、语义 3、循环优化 4、规范 5、b(ab)* 6、anbmcm | n0;m1 7、xac-d*e+:= 8、F*F 9、a* 10、句柄三、 判断题.（10分，每小题2分；对用、错用表示）1、 2、 3、 4、 5、四、 解答题（40分）1、（6分）FIRST Sb Ra b e Tf FOLLOW Sa f # Ra b f # Ta f #(6分；每个非终结符的FIRST及FOLLOW集均为 1 分，错一个扣一分) 2、（10分）正规式-自动机： ba2341a （4分；错一条边扣1分, 直到扣完）确定化 ：ab12352354435354 (3分
10、;错一行扣1分,直到扣完)化简：b1a （3分;错一条边，不得分）3、（8分）（1）句型T *Fi的最右推导：(2分；每错一步推导扣1分，直到扣完) E= E+T=E+F=E+i=T+i=T*F+i （2）语法树：（3分；错一条边扣1分, 直到扣完） EE+TTTiFF*（3）短语：（3分，多一个、少一个、错一个均扣1分，直到扣完)T *Fi T *F i 4、（8分） （1） FIRSTVTHa d ;Ma dLASTVTHd b ;Md b (4分；每个非终结符的FIRSTVT及LASTVT集均为 1 分，错一个扣一分) abd;a=d; (2) (4分；错一个关系扣一分，直到扣完) 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分）注：1、教师命题时题目之间不留空白； 2、考生不得在试题纸上答题，教师只批阅答题册正面部分。（第 5 页）
