2008～2009学年第二学期《编译原理》考试试卷答案-A.doc

华中科技大学文华学院 2008～2009学年度第二学期《编译原理》考试试卷 （A卷） 标准答案和评分 课程性质：（必修） 使用范围：（本科） 考试时间：2009 年 5月 日 考试方式：（闭卷） 学号__________年级专业____________班级________姓名____________ 一、单选题（将正确的答案的字母，填入题干的下划线中。每题2分，共14分） 1．语言学家Chomsky将文法和语言分为四大类，其中3型文法又称为 D。 A．无限制文法 B．上下文有关文法 C．上下文无关文法 D．正规文法 2．设有文法G[S]：S→(T)|a|∧ ，T→TbS|S，则 FOLLOW(S)= B。 A．{ ),b } B．{ ),b,# } C．{ ),a,# } D．{ ( , b } 3．在语法分析方法中，算符优先分析法采用A文法。 A．OPG B．LL(1) C．LR(0) D．LR(1) 4．对程序中的表达式的识别工作，编译程序通常都在A阶段完成。 A．语法分析 B．语义分析 C．词法分析 D．目标代码的生成 5．自下而上语法分析的工作原理是C。 A．“移进—推导法” B．“最左推导法” C．“移进—规约法” D．“推导—规约法” 6．已知∑＝{a,b}，与文法G[S]:S→Sa| Sb| a等价的正规式是C。 A．ab* B．ba* C．a(a|b)* D．aa*|b* 7．LR分析法每次都是对当前句型的B进行规约。 A．素短语 B．句柄 C．短语 D．最左素短语 二、填空题（每空2分，共22分） 1．已知文法G[S]：S→(A)|a ，A→AcS|S|b ；该文法的开始符号是 S，非终结符号集合为 {S,A}，终结符号集合为{a,b,c,(,)}。 2．描述源程序中的单词结构有3种方法：有穷自动机，正规式和正规文法。 3．自上而下的语法分析方法有LL(1)和递归下降方法。 4．设有文法G[S]：S→Sa|a ，构造它的拓广文法，引入一个产生式：Sˊ→S ；则I。=Closure（{[Sˊ→·S，＃]}）= {[Sˊ→·S，＃], [S→·Sa，＃/a], [S→·a，＃/a]}。 5．在LR（0）项目集规范族中，若有项目：，其中，称该项目为移进项目。 6.LL(1)语法分析方法中应解决的主要问题是消除回溯；LR语法分析方法中应解决的主要问题是项目冲突。 三、判断题（判断下列各题的正错，若正确，在括号中写“正”；否则写“错”。每题2分，共16分） 1．一个文法有二义性，则由它描述的语言一定具有二义性。（错 ） 2．若一个语言有无穷多个句子，则定义该语言的文法一定是递归的。（正 ） 3．若有正规式a*b，则与之等价的文法应该是G[A]：A→aA|b 。（ 正 ） 4．设有文法G[A]：A→aB ，B→bB|b，则该文法是LL(1)文法。（错 ） 5．由文法法G的开始符号S推导出来的符号串，称为文法G的句子。（ 错 ） 6．最左素短语是句型最左边的短语。（错 ） 7．LR语法分析法是一种规范规约的分析方法。（正 ） 8．存在能够被确定的有穷自动机DFA识别，却不能用正规式表示的语言。（ 错 ） 四、解答题（共２8分） 1．已知文法G[S]：S→aAb，A→aAb|aa b x {x,y} {y} y {y} 3．已知文法G[E]：（8分） E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 用语法树求出句型：T+T*F+i 的短语，简单短语，素短语和句柄。 短语:i,T, T*F, T+T*F, T+T*F+I ………2分 简单短语: i,T, T*F ………2分 素短语: i, T*F ………2分 句柄:T ………2分 4．设有文法G[A]： ABc|a，BaB|c（共5分） （1）．G是LL（1）文法吗？为什么？ 不是。………1分 将B→aB|c替换A→Bc|a中的aBc|cc|a ………1分 可见有左公共因子a，所以G不是LL(1)文法。 （2）．若G不是LL（1）文法，则将它改造成等价的LL（1）文法G1。 文法：A→aBc|cc|a ………（1） B→aB|c 将（1）提取左公共因子，变换为：A→aAˊ|cc