编译原理期中试题答案.pdf

一、填空题（每空1分，共24分）C、四元式D、常数1、文法G定义为四元组(V,V,P,S)，其中V是非终结符集合，V是终结符集合，NTNT4、自上而下语法分析的主要动作是（D）不严格，加算法动作匹配，否则是推导P是规则的集合，S是起始符或识别符。A、移进B、推导2、乔姆斯基形式文法共有4种，分别是0型或短语文法，1型或上下文有关C、规约D、匹配文法，2型或上下文无关文法，3型或正规文法。5、文法[S]为S→AB|bC，A→ε|b，B→ε|aD，C→AD|b，D→aS|c，FOLLOW(A)为3、列举4种以上的自底向上语法分析方法简单优先，算符优先，LR(0)（C）A、{a,c,#}B、{c,#}C．、{a,#}D、{#}6、.设有文法G[S]:S→Ap|Bq，A→a|cA，B→b|dB，则FIRST(Ap)为（C）SLR(1),LR(1),LALR(1)，。A、{p,q}B、{b,d}C、{a,c}D、其他4.程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大7、设有文法G[S]：S→b|bBB→bS，则该文法所描述的语言是（C）类，即静态存储分配方案和动态存储分配方案。A、L（G）={bi|i≥0}B、L（G）={b2i|i≥0}5、你所知道的词法分析程序自动构造工具有LEX。C、L（G）={b2i+1|i≥0}D、L（G）={b2i+1|i≥1}6、编译方式与解释方式的根本区别在于是否生成目标代码。8、.设有文法G[S]:S→Ap|Bq，A→a|cA，B→b|dB，则FIRST(Ap)为（C）7、简单优先分析法归约的对是象句柄，算符优先分析法归约的对是象最左A、{p,q}B、{b,d}C、{a,c}D、其他素短语。8、编译程序分为6个阶段分别是：词法分析、语法分析、语义分析、中间代码三、综合题（共55分）生成、代码优化、目标代码生成。1、构造正规式r=b（（ab）*|bb）*ab的DFA并化简。（10分）二、选择题（每题2分，共16分）NFA1、哪个不是DFA的构成成分（C）A、有穷字母表B、初始状态集合C、终止状态集合D、有限状态集合2、词法分析器的输入是（B）A、单词符号串B、源程序C、语法单位D、目标程序确定化3、在词法分析阶段不能识别的是（C）A、标识符B、运算符2.判断文法G[S]：S→MH|a→LSo|Hε→KdML|ε→LeHf→K|bLMM是否是LL（1）文法，如果是，构造其LL（1）预测分析表（10分）重命名所以是LL（1）预测分析表如下DFA3.文法G[S]（10分）(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d(1)构造文法的LR(0)分析表；（5分）(2)给出分析输入串abbcde#是否为句子的LR(0)分析过程。（5分）(2)求LR(0)分析表（4分）i>>>>#<<<<=(3)分析过程（4分）见书上例题LR分析表E’→E(r0)4.（共15分）对算数表达式文法G[E]:E→E+T(r1)E→E+T|TT→T*F|FF→(E)|iE→T(r2)(1)构造算符优先关系表和LR分析表；（10分）T→T*F(r3)(2)分别使用两种表对分析符号串i+i*i#是否为该文法句子。（5分）T→F(r4)算符优先关系表F→(E)(r5)FirstVT(E)={+,*,(,i}FirstVT(T)={*,(,i}FirstVT(F)={(,i}F→i(r6)LastVT(E)={+,*,),i}LastVT(T)={*,),i}LastVT(F)={),i}（2）LR分析表：#E#0.E’→E1.E→E+T2.E→T3.T→T*F4.T→F5.F→(E)6.F→I（1）分+*（）i#项目集图（5分）+><<><>><*><>><<<（<=）>>>>145.（共10分）证明任何SLR(1)文法一定是LR(1)文法。E'->E.F->(E.))(1)SLR(1)是用Follow集解决规约-移进冲突，以及规约-规约冲突+E->E.+TE->E.+T711E+设一文法属于SLR（1）文法E->E+.TEF->(E).T->.T*F03T->.F构造LR项目集，假设有项目集I存在移进-规约冲突和规约规约冲突F->.(E)E'->.E(F->(.E)F->.iE->.E+TE->.E+TI={Xb，A，B}E->.TE->.T(iFT->.T*FT->.T*F(如果，，那8TT->.FT->.FFOLLOW(A)FOLLOW(B)=,OLLOW(A){b}=LOW(A){b}=F->.(E)F->.(E)F->.iF->.i么就可以构造（）文法，略E->E+T.SLR1T->T.*FT*i同时根据LR（1）项目集构造，对于I来说2T6F9(Fi5T->T*.F规则A