《编译原理》模拟试题2

《编译原理》模拟试题二一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）×1．“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。()×2．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。()√3．一个句型的句柄一定是文法某产生式的右部。()×4．在程序中标识符的出现仅为使用性的。()√5．仅考虑一个基本块，不能确定一个赋值是否真是无用的。()√6．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。()×7．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。()×8．算符优先关系表不一定存在对应的优先函数。()×9．数组元素的地址计算与数组的存储方式有关。()×10．编译程序与具体的机器有关,与具体的语言无关。()二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_____。A．()模拟执行器B．()解释器C．()表格处理和出错处理D．()符号执行器2．文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是A．()L(G[N])={bi│i≥0}B．()L(G[N])={b2i│i≥0}C．()L(G[N])={b2i+1│i≥0}D．()L(G[N])={b2i+1│i≥1}3．一个句型中的最左_____称为该句型的句柄。A．()短语B．()简单短语C．()素短语D．()终结符号4．设G是一个给定的文法，S是文法的开始符号，如果S-x(其中x∈V*),则称x是文法G的一个_____。A．()候选式B．()句型C．()单词D．()产生式5．文法G[E]：E→T∣E＋TT→F∣T﹡FF→a∣（E）该文法句型E＋F﹡(E＋T)的简单短语是下列符号串中的_____。①（E＋T）②E＋T③F④F﹡(E＋T)A．()①和③B．()②和③C．()③和④D．()③6．若一个文法是递归的，则它所产生的语言的句子_____。A．()是无穷多个B．()是有穷多个C．()是可枚举的D．()个数是常量7．词法分析器用于识别_____。A．()句子B．()句型C．()单词D．()产生式8．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是_____。A.()非终极符集B．()终极符集C．()字母表D.()状态集9．在自底向上的语法分析方法中，分析的关键是_____。A.()寻找句柄B.()寻找句型C.()消除递归D.()选择候选式10．在LR分析法中，分析栈中存放的状态是识别规范句型_____的DFA状态。A.()句柄B.()前缀C.()活前缀D.()LR(0)项目三、填空题(每空1分，共10分)1．设G是一个给定的文法，S是文法的开始符号，如果S-x(其中x∈VT*),则称x是文法的一个___。句子__2．递归下降法不允许任一非终极符是直接_____递归的。左3．自顶向下的语法分析方法的基本思想是：从文法的______开始，根据给定的输入串并按照文法的产生式一步一步的向下进行______，试图推导出文法的____，使之与给定的输入串_____。开始符号直接推导句子__匹配_4．自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行____，力求归约到文法的_____。_直接归约开始符号5．常用的参数传递方式有_____，传值和传名。传地址6．在使用高级语言编程时,首先可通过编译程序发现源程序的全部____错误和语义部分错误。_语法四、简答题（20分）1.已知文法G[S]为：S→dABA→aA|aB→Bb|εG[S]产生的语言是什么？答：G[S]产生的语言是L(G[S])={danbm│n≥1,m≥0}。2.简述DFA与NFA有何区别?答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。3.构造正规式相应的DFA:1(1010*|1(010)*1)*0。解：1(1010*|1(010)*1)*0对应的NFA为：4.已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。解：句型归约规则句柄((a，a)，a)S→aa((S，a)，a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((S)，a)T→SS((T)，a)S→S(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S5.何谓优化？按所涉及的程序范围可分为哪几级优化？1)优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。(2)三种级别：局部优化、循环优化、全局优化。五.计算题（10分）对下面的文法G：E-TE'E'-+E|εT-FT'T'-T|εF-PF'F'-*F'|εP-(E)|a|b|^(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。(4分)(2)证明这个方法是LL(1)的。(4分)(3)构造它的预测分析表。(2分)解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E')={+,ε}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε};FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F')=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};FOLLOW集合有：FOLLOW(E)={),#};FOLLOW(E')=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含εFOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)证明这个方法是LL(1)的。各产生式的SELECT集合有：SELECT(E-TE')=FIRST(T)={(,a,b,^};SELECT(E'-+E)={+};SELECT(E'-ε)=FOLLOW(E/)={),#}SELECT(T-FT')=FIRST(F)={(,a,b,^};SELECT(T'-T)=FIRST(T)={(,a,b,^};SELECT(T'-ε)=FOLLOW(T/)={+,),#};SELECT(F-PF')=FIRST(P)={(,a,b,^};SELECT(F'-*F')={*};SELECT(F'-ε)=FOLLOW(F')={(,a,b,^,+,),#};SELECT(P-(E))={(}SELECT(P-a)={a}SELECT(P-b)={b}SELECT(P-^)={^}可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。(3)构造它的预测分析表。文法G[E]的预测分析表如下：