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

华中科技大学文华学院20082009学年度第二学期编译原理考试试卷 （A卷） 标准答案和评分课程性质：（必修） 使用范围：（本科）考试时间：2009 年 5月 日 考试方式：（闭卷）学号_年级专业_班级_姓名_ 一、单选题（将正确的答案的字母，填入题干的下划线中。每题2分，共14分）1语言学家Chomsky将文法和语言分为四大类，其中3型文法又称为 D。 A无限制文法 B上下文有关文法C上下文无关文法 D正规文法2设有文法GS：S(T)|a| ，TTbS|S，则 FOLLOW(S)= B。A ),b B ),b,# C ),a,# D ( , b 3在语法分析方法中，算符优先分析法采用A文法。AOPGBLL(1)CLR(0)DLR(1)4对程序中的表达式的识别工作，编译程序通常都在A阶段完成。A语法分析 B语义分析C词法分析 D目标代码的生成5自下而上语法分析的工作原理是C。A“移进推导法” B“最左推导法”C“移进规约法” D“推导规约法”6已知a,b，与文法GS:SSa| Sb| a等价的正规式是C。Aab*Bba* Ca(a|b)*Daa*|b* 7LR分析法每次都是对当前句型的B进行规约。A素短语B句柄 C短语D最左素短语二、填空题（每空2分，共22分）1已知文法GS：S(A)|a ，AAcS|S|b ；该文法的开始符号是 S，非终结符号集合为 S,A，终结符号集合为a,b,c,(,)。2描述源程序中的单词结构有3种方法：有穷自动机，正规式和正规文法。3自上而下的语法分析方法有LL(1)和递归下降方法。4设有文法GS：SSa|a ，构造它的拓广文法，引入一个产生式：SS ；则I。=Closure（SS，）= SS，, SSa，/a, Sa，/a。5在LR（0）项目集规范族中，若有项目：，其中，称该项目为移进项目。6.LL(1)语法分析方法中应解决的主要问题是消除回溯；LR语法分析方法中应解决的主要问题是项目冲突。三、判断题（判断下列各题的正错，若正确，在括号中写“正”；否则写“错”。每题2分，共16分）1一个文法有二义性，则由它描述的语言一定具有二义性。（错 ）2若一个语言有无穷多个句子，则定义该语言的文法一定是递归的。（正 ）3若有正规式a*b，则与之等价的文法应该是GA：AaA|b 。（ 正 ）4设有文法GA：AaB ，BbB|b，则该文法是LL(1)文法。（错 ）5由文法法G的开始符号S推导出来的符号串，称为文法G的句子。（ 错 ）6最左素短语是句型最左边的短语。（错 ）7LR语法分析法是一种规范规约的分析方法。（正 ）8存在能够被确定的有穷自动机DFA识别，却不能用正规式表示的语言。（ 错 ）四、解答题（共8分）1已知文法GS：SaAb，AaAb|a；求：L(GS)=?（5分）n an+1bn| n0 2设M（x，y，a，b，f，x，y）为一有穷自动机，其中f定义如下： f(x,a)=x,y, f(x,b)=y, f(y,a)= , f(y,b)=y。（5分）（1） 试将它用状态图表示；yx a a b b（2） 试将它用状态矩阵表示。 a b x x,y y y y3已知文法GE：（8分）ET|E+T|E-TTF|T*F|T/FF(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设有文法GA： ABc|a，BaB|c（共5分）（1）G是LL（1）文法吗？为什么？不是。1分 将BaB|c替换ABc|a中的B:AaBc|cc|a 1分 可见有左公共因子a，所以G不是LL(1)文法。（2）若G不是LL（1）文法，则将它改造成等价的LL（1）文法G1。文法：AaBc|cc|a （1） BaB|c 将（1）提取左公共因子，变换为：AaA|cc 和ABc| 2分 G1为：AaA|cc 和ABc| ，BaB|c 1分5. 试用语法树证明：文法GS：SaSbS| aS| 具有二义性 (5分) S S a S b S a S a S a S b S 五、设字母表上的正规式为：0(1|0) * （共6分）1构造该正规式对应的NFA N ； YBAX 0,1 0 2将NFA N确定化，得到DFA M（用DFA图表示），使得L（M）=L（N）； 0 1C B A X A,B,y 0,1 A,B,y B,y B,y 0 0 B,y B,y B,y 13将DFA M最小化（用DFA图表示）。A B 0 0,1六、已知文法GS：SA，A|0A1 ：（8分）1.计算非终结符的FIRSTVT集和LASTVT集.并找出终结符之间的所有优先关系（包括句子左右的语句括号）。 FIRSTVT LASTVTS * *,1A *.0 *,1 0=1,#=#,左边右边#2根据1，构造G的算符优先关系矩阵。此文法是算法符优先文法吗？ 0 1 * # 0 * # =七、设有文法GS：S(S)|b （共6分）1构造能识别文法的规范句型活前缀的DFA；（3分）SSSSS(S)Sb SS(