编译原理2010级(A)试卷以及参考答案

1、 试卷 课程名称： 编译原理（A） 适用专业年级： 软件工程、计算机 2010 级（闭卷） 考生学号： 考生姓名： 一、单项选择题（20分，每小题2分）1、_是两类程序语言处理程序。 A高级语言程序和低级语言程序         B 解释程序和编译程序 C编译程序和操作系统                 D系统程序和应用程序 2、 若文法 G 定义的语言是无限集，则文法必然是

2、 _。  A递归的   B 上下文无关的  C 二义性的 D 无二义性的3、 四种形式语言文法中，3型文法又称为 _文法。 A 短语结构文法       B上下文无关文法 C 上下文有关文法     D 正规文法 4、 一个文法所描述的语言是_。 A 唯一的         B不唯一的    C 可能唯一，也可能不唯一   D都不对5、 _和代码优化部分不是每个编译程序都必需的。 A 语法分析  

3、 B 中间代码生成        C 词法分析       D 目标代码生成 6、文法 G 产生的_的全体是该文法描述的语言。 A句型 B 终结符集 C非终结符集 D 句子7、高级语言编译程序常用的语法分析方法中，LL（1）分析方法属于 。A.自左至右 B.自顶向下 C.自底向上 D.自右至左8、一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _。 A 句子 B 句型 C 单词 D 产生式9、一个句型的最左 称为该句型的句柄。A.

4、 短语 B. 直接短语 C. 素短语 D.终结符号10、文法：G：SaSa | b所识别的语言是 。 A. aba B.（aba）* C. a*ba* D. anban（n0）二.填空题（20分，每空2分）1、语法分析是依据语言的 规则进行的。2、算符优先分析法每次规约当前句型的 。 3、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 。 4、对于文法G，仅含终结符号的句型称为 。5、逆波兰式ab+c*所对应的表达式为 。 6、编译程序的工作过程一般由 、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段组成。7文法GS：S->S0 | S1 | a 该文法对

5、应的正规式为 。8、文法GE：E->T | E+T, T->F | T*F, F->(E) | i 该文法的句型 T*F+T的句柄是 。9、语言L=an bm|n,m0相应的正规表达式是 。10、规范推导的逆过程是 。三、判断题.（10分，每小题2分）1、对任何一个正规语言L，都有一正规表达式r，满足L（r）=L。2、文法GS：S->Sa | Aa, A->Ab |b 是LL(1)文法。3、解释程序和编译程序一样，生成目标代码。4、文法中的每个句型都有规范推导。5、每一个NFA都对应有唯一的一个最小化的DFA。四、解答题（50分）1、已知文法G(E) （8分） E

6、T|ET TF|T *F F(E)|i （1）给出句型 T *Fi的规范推导（2分） （2）画出上面句型的语法树； （3分） （3）给出句型T *Fi 的全部短语。(3分) 2、已知文法G：（6分）S->aAd |dA->Bb | B->aA | 求每个非终结符的FIRST及FOLLOW集。FOLLOW S A BFIRST S A B (3分) (3分)3、 已知文法G：（6分）S->a | (A)A->A,S| S（1） 消除上述文法左递归。（3分）（2） 证明改写以后的文法是LL（1）文法。（3分）4、按要求给出下列语言的文法。（6分）(1) L1= anb

7、m| n，m1 用右线性正规文法。 （3分） （要求：用2个非终结符S和B描述，S为文法开始符）(2) L2= an bmcnn1,m0 用二型文法。 （3分） （要求：用2个非终结符S和B描述，S为文法开始符）5、 已知文法GZ： （4分）Z->aAaA->A+b | b 构造文法算符优先关系表ab+ab+6、对于正规式 (100)* （10分）（1）请构造与之等价的自动机（4分）（2）将上述自动机确定化（3分）（3）化简（3分）7、已知文法GS （10分）S->S S->aA A->Ab A->（1）请构造该文法的以LR（0）项目集为状态的识别活前缀的D

8、FA。（5分）（2）判断该文法是否为SLR（1）文法，并说明理由。（2分）（3）构造SLR（1）分析表。（3分）2010级编译原理试卷（A）参考答案：4、 单项选择题（20分；每小题2分）15：BADAB 610：DBDBD 5、 填空题（20分；每空2分）1、语法 2、最左素短语 3、二义性文法 4、句子 5、(a+b)*c 6、词法分析 7、a(0|1)* 8、T*F 9、a* b* 10、规范规约6、 判断题.（10分；每小题2分）1、 2、 × 3、× 4、× 5、7、 解答题（50分）1、（8分） （1）句型T *Fi的规范推导：(2分；每错一步推导扣1

9、分，直到扣完) 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 2、（6分）FOLLOWS#Ad bBb FIRSTSa d Aa b Ba (6分；每个非终结符的FIRST及FOLLOW集均为 1 分，错一个扣一分)3、 （6分） （1） 消除文法左递归： S->a | (A) A->SA' A'->,SA' | （3分；每错一条规则式扣1分，直到扣

10、完） （2）因为 对与S： select(S->a)=a select(S->(A)= ( select(S->a) select(S->(A)= (1分） 对与A'： select(A'->,SA')=, select(A'->)= ) select(A'->,SA') select(A'->)= （1分） 所以该文法是LL（1）文法 （1分） 4、（6分） （1） S->aS | aB B->bB |b （3分；每错一条规则式扣1分，直到扣完） （2） S->aSc |

11、 aBc B->bB | （3分；每错一条规则式扣1分，直到扣完） 5、（4分）ab+a=<<b>>+= (4分；错一个优先关系扣1分，直到扣完) 6、（10分）构造与之等价的自动机：001321（4分；错一条边扣1分, 直到扣完）确定化 ：0112424324243324 (3分;多一行、少一行、错一行均扣1分,直到扣完)化简：0012 （3分; 错一条边扣1分） 7、（10分） （1）构造识别活前缀自动机： baSI0:S->.SS->.aAI1:S->S.I2:S->a.AA->.AbA->.I3:S->aA.A->A.bI4:A->Ab.A（5分；错1个、多1个、少1个状态均扣1分，直到扣完） （2）识别活前缀自动机中，状太3存在规约与移进的冲突 由于： follow(S)=# follow(S)