系专业级班学号姓名……………………装……………………订……………………线……………………泉州师院2010——2011学年度第2学期本科计算机专业08级《编译原理》期中试卷题序一二三四总成绩统分人成绩登分人得分评卷人一、填空题（20分，每空2分）文法G产生的句子的全体是该文法描述的语言。Chomsky定义的四种形式语言文法中，0型文法又称为短语文法；1型文法又称为上下文有关文法；一个上下文无关的文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个___开始符_，以及一组__规则产生式。LL(1)分析法中，第一个L的含义是_从左向右处理输入____。在编译方法的五个部分中，_中间代码生成和_中间代码优化不是每个编译程序都必须的。词法分析的主要功能是识别单词Lex是一个_词法分析器____的生成器。得分评卷人二、选择题（20分，每个选项2分）1、编译过程中，语法分析器的任务是（C）。①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的结构A．②③B．④C．②③④D．①②③④2、编译程序的大多数时间花在(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定义的语言是无限集，则文法必然是AA．递归的B.上下文无关的C.二义性的D.无二义性的6、语法分析常用的方法是（B）①自上而下②自下而上③自左向右④自右向左A．②③B．①②C．③④D．①②③④7、一个语言的文法是（B）A．惟一的B．不惟一的C．个数有限的D．以上皆错8、在使用高级语言编程时，首先可通过编译程序发现源程序的全部（A）错误和部分（B）错误。A．语法B．语义C．语用D．运行9、词法分析器的输入是（B）。A．单词符号B．源程序C．语法单位D．目标程序10.正规式M1和M2等价是指(C)。A．Ml和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等得分评卷人三、简答题：（20%）1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。（5分）1、解：文法G(N)：N→AB|B（1分）A→AC|D（1分）B→1|3|5|7|9（1分）D→B|2|4|6|8（1分）C→0|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．构造文法以生成下列语言{anbm︱n，m≥1}（5分）S→ABA→a︱AaB→b︱bB2.构造正规式(a|ba)*相应的最简DFA。（10分）3、已知文法G(E)E→T|E＋TT→F|T*FF→(E)|i(1)给出句型(T*F＋i)的最右推导及画出语法树；（10分）最右推导：E=>T=〉F=〉（E）=〉（E+T）=>（E+F）=>（E+i）=>（T+i）=>（T*F+i）4、设文法G(S)：S→(L)|aS|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。(15分)(1)S→(L)|aS’S’→S|εL→SL’L’→，SL’|ε消除左递归2分，提公共因子2分。(2)FIRST(S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{（，a，,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)}每个集合各1分(3)a，()＃SS’LL’S→aS’S→(L)S’→SS’→εS’→SS’→εS’→εL→SL’L→SL’L’→，SL’L’→ε（3分）(答题纸)(答题纸)(答题纸)(答题纸)