《2015年编译原理期中试题答案》由会员分享，可在线阅读，更多相关《2015年编译原理期中试题答案（4页珍藏版）》请在金锄头文库上搜索。
1、一、 填空题（每空1分，共24分）1、文法G定义为四元组(VN,VT,P,S)，其中VN是 非终结符集合， VT是 终结符集合，P是 规则的集合 ，S是 起始符或识别符 。2、乔姆斯基形式文法共有4种，分别是 0型或短语文法 ， 1型 或上下文有关文法 ， 2型或上下文无关文法 ， 3型或正规文法 。3、列举4种以上的自底向上语法分析方法 简单优先 ， 算符优先 ， LR(0) SLR(1), LR(1),LALR(1) ， 。4.程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即 静态存储分配 方案和 动态存储分配 方案。5、你所知道的词法分析程序自动构造工具有 LEX
2、 。6、编译方式与解释方式的根本区别在于 是否生成目标代码 。7、简单优先分析法归约的对象是 句柄 ，算符优先分析法归约的对象是 最左素短语 。8、编译程序分为6个阶段分别是： 词法分析 、 语法分析 、 语义分析、中间代码生成、代码优化、目标代码生成 。二、 选择题（每题2分，共16分）1、哪个不是DFA的构成成分（C ） A、 有穷字母表 B、初始状态集合C、 终止状态集合 D、有限状态集合2、词法分析器的输入是（B ）A、单词符号串 B、源程序C、语法单位 D、目标程序3、在词法分析阶段不能识别的是（ C ） A、标识符 B、运算符C、四元式 D、常数4、自上而下语法分析的主要动作是（
3、D ）不严格，加算法动作匹配，否则是推导 A、移进 B、推导 C、规约 D、匹配 5、文法S为SAB|bC，A|b，B|aD，CAD|b，DaS|c，FOLLOW(A)为 （C ） A、a,c,# B、c,# C、a,# D、# 6、.设有文法GS: SAp|Bq，Aa|cA，Bb|dB ，则FIRST(Ap)为（ C ）A、p,q B、b,d C、a,c D、 其他7、设有文法GS：Sb|bBBbS，则该文法所描述的语言是（ C ）A、L（G）=bi|i0 B、L（G）=b2i|i0 C、L（G）=b2i+1|i0 D、L（G）=b2i+1|i18、.设有文法GS: SAp|Bq，Aa|cA
4、，Bb|dB ，则FIRST(Ap)为（ C ）A、p,q B、b,d C、a,c D、 其他三、综合题（共55分）1、构造正规式r=b（ab）*|bb）*ab的DFA并化简。（10分）NFA确定化重命名DFA2. 判断文法GS：SMH|a HLSo| KdML| LeHf MK|bLM是否是LL（1）文法，如果是，构造其LL（1）预测分析表（10分）所以是LL（1）预测分析表如下3.文法GS （10分）(1) SaAcBe(2) Ab(3) AAb(4) Bd(1)构造文法的LR(0)分析表；（5分）(2)给出分析输入串abbcde#是否为句子的LR(0)分析过程。（5分）(2)求LR(0)
5、分析表（4分）(3)分析过程（4分）见书上例题4. （共15分）对算数表达式文法GE:EE+T|T TT*F|F F(E)|i(1) 构造算符优先关系表和LR分析表；（10分）(2) 分别使用两种表对分析符号串i+i*i#是否为该文法句子。（5分）算符优先关系表FirstVT(E)=+,*,(,i FirstVT(T)=*,(,i FirstVT(F)=(,iLastVT(E)=+,*,),i LastVT(T)=*,),i LastVT(F)=),i#E#+*（）i#+*（=i#=LR分析表E E (r0)EE+T (r1)ET (r2)TT*F (r3)TF(r4)F(E) (r5)Fi
6、(r6)（2）LR分析表：0. E E1.EE+T2.ET3.TT*F4.TF5.F(E)6.FI （1）分项目集图（5分）分析表（6分）ACTIONGOTO+*（）i#ETF0S3S51261S7acc2R2S9R2R23S3S5464S7S115R6R6R6R66R4R4R4R47S3S5868R1S9R1R19S3S51010R3R3R3R311R5R5R5R5SLR(1)5. （共10分）证明任何SLR(1)文法一定是LR(1)文法。(1)SLR(1)是用Follow集解决规约-移进冲突，以及规约-规约冲突设一文法属于SLR（1）文法构造LR项目集，假设有项目集I存在移进-规约冲突和规约规约冲突I=Xabb，Ag，Bd如果FOLLOW(A)FOLLOW(B)=F, OLLOW(A)b=F， LOW(A)b=F，那么就可以构造SLR（1）文法，略同时根据LR（1）项目集构造，对于I来说规则Ag，需要向前搜索的字符是FOLLOW(A)，规则Bd，需要向前搜索的字符是FOLLOW(A)，而Xabb则需要看当前字符b，而三者之间两两两没有交集，因此是LR（1），可以构造LR（1）分析表（2）反过来则不成立，见P145页因此，足以证明SLR(1)文法一定是LR(1)文法，反过来则不一定- 4 -
