2015年编译原理期中试题答案

-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。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、自上而下语法分析的主要动作是（D）不严格，加算法动作匹配，否则是推导A、移进B、推导C、规约D、匹配5、文法[S]为S→AB|bC，A→ε|b，B→ε|aD，C→AD|b，D→aS|c，FOLLOW(A)为（C）A、{a,c,#}B、{c,#}C．、{a,#}D、{#}6、.设有文法G[S]:S→Ap|Bq，A→a|cA，B→b|dB，则FIRST(Ap)为（C）A、{p,q}B、{b,d}C、{a,c}D、其他7、设有文法G[S]：S→b|bBB→bS，则该文法所描述的语言是（C）A、L（G）={bi|i≥0}B、L（G）={b2i|i≥0}C、L（G）={b2i+1|i≥0}D、L（G）={b2i+1|i≥1}8、.设有文法G[S]:S→Ap|Bq，A→a|cA，B→b|dB，则FIRST(Ap)为（C）A、{p,q}B、{b,d}C、{a,c}D、其他三、综合题（共55分）1、构造正规式r=b（（ab）*|bb）*ab的DFA并化简。（10分）NFA确定化-2-重命名DFA2.判断文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM是否是LL（1）文法，如果是，构造其LL（1）预测分析表（10分）所以是LL（1）预测分析表如下3.文法G[S]（10分）(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d(1)构造文法的LR(0)分析表；（5分）(2)给出分析输入串abbcde#是否为句子的LR(0)分析过程。（5分）-3-(2)求LR(0)分析表（4分）(3)分析过程（4分）见书上例题4.（共15分）对算数表达式文法G[E]:E→E+T|TT→T*F|FF→(E)|i(1)构造算符优先关系表和LR分析表；（10分）(2)分别使用两种表对分析符号串i+i*i#是否为该文法句子。（5分）算符优先关系表FirstVT(E)={+,*,(,i}FirstVT(T)={*,(,i}FirstVT(F)={(,i}LastVT(E)={+,*,),i}LastVT(T)={*,),i}LastVT(F)={),i}#E#+*（）i#+*（=）i#=LR分析表E’→E(r0)E→E+T(r1)E→T(r2)T→T*F(r3)T→F(r4)F→(E)(r5)F→i(r6)（2）LR分析表：0.E’→E1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)6.F→I（1）分项目集图（5分）E'-.EE-.E+TE-.TT-.T*FT-.FF-.(E)F-.i0F-(.E)E-.E+TE-.TT-.T*FT-.FF-.(E)F-.i3E'-E.E-E.+TE-T.T-T.*F12T-F.6F-i.5F-(E.)E-E.+T4F-(E).11E-E+.TT-.T*FT-.FF-.(E)F-.i7E-E+T.T-T.*F8T-T*.FF-.(E)F-.i9T-T*F.10(E(iETF)++TFi(*(Fi*TFi分析表（6分）ACTIONGOTO+*（）i#ETF-4-0S3S51261S7acc2R2S9R2R23S3S5464S7S115R6R6R6R66R4R4R4R47S3S5868R1S9R1R19S3S51010R3R3R3R311R5R5R5R5SLR(1)5.（共10分）证明任何SLR(1)文法一定是LR(1)文法。(1)SLR(1)是用Follow集解决规约-移进冲突，以及规约-规约冲突设一文法属于SLR（1）文法构造LR项目集，假设有项目集I存在移进-规约冲突和规约规约冲突I={Xb，A，B}如果FOLLOW(A)FOLLOW(B)=,OLLOW(A){b}=，LOW(A){b}=，那么就可以构造SLR（1）文法，略同时根据LR（1）项目集构造，对于I来说规则A，需要向前搜索的字符是FOLLOW(A)，规则B，需要向前搜索的字符是FOLLOW(A)，而Xb则需要看当前字符b，而三者之间两两两没有交集，因此是LR（1），可以构造LR（1）分析表（2）反过来则不成立，见P145页因此，足以证明SLR(1)文法一定是LR(1)文法，反过来则不一定