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

1华中科技大学文华学院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．OPGB．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二、填空题（每空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）项目集规范族中，若有项目：AAbB，其中TbV，称该项目为移进项目。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|a；求：L(G[S])=?（5分）n{an+1bn|n≥0}32．设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）试将它用状态图表示；aabb（2）试将它用状态矩阵表示。abx{x,y}{y}y{y}3．已知文法G[E]：（8分）E→T|E+T|E-TT→F|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．设有文法G[A]：A→Bc|a，B→aB|c（共5分）（1）．G是LL（1）文法吗？为什么？不是。………1分将B→aB|c替换A→Bc|a中的B:A→aBc|cc|a………1分可见有左公共因子a，所以G不是LL(1)文法。xy4（2）．若G不是LL（1）文法，则将它改造成等价的LL（1）文法G1。文法：A→aBc|cc|a………（1）B→aB|c将（1）提取左公共因子，变换为：A→aAˊ|cc和Aˊ→Bc|ε……2分G1为：A→aAˊ|cc和Aˊ→Bc|ε，B→aB|c………1分5.试用语法树证明：文法G[S]：S→aSbS|aS|ε具有二义性(5分)SSaSbSaSaSεaSbSεεε五、设字母表{0,1},上的正规式为：0(1|0)*（共6分）1．构造该正规式对应的NFAN；0,10εε2．将NFAN确定化，得到DFAM（用DFA图表示），使得L（M）=L（N）；01{X}{A,B,y}0,1{A,B,y}{B,y}{B,y}00{B,y}{B,y}{B,y}13．将DFAM最小化（用DFA图表示）。00,1XABYABCAB5六、已知文法G[S]：S→＊A，A→＊|0A1：（8分）1.计算非终结符的FIRSTVT集和LASTVT集.并找出终结符之间的所有优先关系（包括句子左右的语句括号＃）。FIRSTVTLASTVTS{*}{*,1}A{*.0}{*,1}0=1,#=#,左边＃FIRSTVT(S)，LASTVT(S)右边#2．根据1，构造G的算符优先关系矩阵。此文法是算法符优先文法吗？01*#0＝1*#=七、设有文法G[S]：S→(S)|b（共6分）1．构造能识别文法][SG的规范句型活前缀的DFA；（3分）S(bS)(2．构造它的LR(0)分析表。（3分）Sˊ→·SS→·(S)S→·bS→(·S)S→·(S)S→·bS→b·Sˊ→S·S→(S·)S→(S)·6ACTIONGOTO()b#S0S1S311acc2S343r2r2r24S55r1r1r1