计算机编译原理期中卷.doc

系 专业 级 班 学号 姓名 装订线泉州师院20102011学年度第2学期本科计算机专业08级编译原理期中试卷题 序一二三四总成绩统分人成 绩登分人得 分评卷人一、填空题（20分，每空2分） 1、 文法 G 产生的 句子 的全体是该文法描述的语言。2、 Chomsky 定义的四种形式语言文法中， 0 型文法又称为 短语 文法； 1 型文法又称为 上下文有关 文法；3、 一个上下文无关的文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个_开始符_，以及一组_规则产生式。4、 LL(1)分析法中， 第一个L的含义是_从左向右处理输入_。5、 在编译方法的五个部分中， _中间代码生成和_中间代码优化不是每个编译程序都必须的。6、 词法分析的主要功能是 识别单词 7、 Lex是一个_词法分析器_的生成器。得 分评卷人二、选择题（20分，每个选项2分）1、编译过程中，语法分析器的任务是（ C ）。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构 A B C D2、编译程序的大多数时间花在( C )。A词法分析程序 B代码生成程序C表格管理程序 D语法分析程序3、Chomsky把文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（ D ） A短语文法 B正则文法 C上下文有关文法 D上下文无关文法4、一个句型中的最左( A )称为该句型的句柄。 A短语 B素短语 C简单短语 D终结符号5、若文法 G 定义的语言是无限集，则文法必然是 A A递归的 B. 上下文无关的 C. 二义性的 D. 无二义性的6、语法分析常用的方法是（ B ）自上而下 自下而上 自左向右 自右向左 A B C D7、一个语言的文法是（ B ）A惟一的 B不惟一的 C个数有限的 D以上皆错8、在使用高级语言编程时，首先可通过编译程序发现源程序的全部（ A ）错误和部分（ B）错误。A语法 B语义 C语用 D运行9、词法分析器的输入是 （ B ）。 A单词符号 B源程序 C语法单位 D 目标程序 10. 正规式M1和M2等价是指( C )。AMl和M2的状态数相等BM1和M2的有向边条数相等CM1和M2所识别的语言集相等DM1和M2状态数和有向边条数相等得 分评卷人三、简答题：（20 %） 1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。（5分）1、解：文法G(N)： NAB|B （1分） AAC|D （1分） B1|3|5|7|9 （1分） DB|2|4|6|8 （1分） C0|D （1分）2、写出以非0数字为头的所有非负偶数的正规表达式（5分）（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*（2|4|6|8|0）|（2|4|6|8）得 分评卷人四、综合应用题（40 %）1构造文法以生成下列语言an bmn，m1（5分）S ABAaAaBbbB2.构造正规式(a|ba)*相应的最简DFA。（10分）3、已知文法G(E)ET | ETTF | T * FF(E) | i(1) 给出句型(T * Fi)的最右推导及画出语法树；（10分）最右推导： E=T=F=（E）=（ E+T） = （E+F ）= （E+i ）= （T+i ）= （T*F+i）4、设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。(15分)(1) S(L)|aSSS|LSLL ，SL| 消除左递归2分，提公共因子2分。(2)FIRST(S)(，aFOLLOW(S)#，) FIRST(S)（，a，, FOLLOW(S)#，)FIRST(L)(，aFOLLOW(L) )FIRST(L)， F