【试卷B】10级编译原理

《编译原理》试卷共8页，第1页贵州大学计算机科学与信息学院2012-2013学年第二学期考试试卷B《编译原理》注意事项：1.请考生按要求在试卷装订线内填写姓名、学号和年级专业。2.请仔细阅读各种题目的回答要求，在规定的位置填写答案。3.不要在试卷上乱写乱画，不要在装订线内填写无关的内容。4.满分100分，考试时间为120分钟。题号一二三四总分统分人得分一、填空题(每空1分,共20分)1.将源程序完整地转换成机器语言程序或汇编语言程序，然后再处理、执行的翻译程序是编译程序。2.编译程序的整个过程从逻辑上依次分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段。另外还有两个重要工作是表格管理和出错处理。3.句子abab的前缀有。4.集合{xnyn|n≥0}可以用产生式实现。5.有穷自动机接受的语言是语言。6.构造LR(0)项目集规范族的项目类型分为四种：形如S'→α.的称为接受项目、形如A→α.aβ的称为项目、形如的称为待约项目、形如A→αBβ.的称为项目。得分评分人《编译原理》试卷共8页，第2页7.语法分析方法分为自顶向下与自底向上两类，自顶向下的分析方法主要有递归子程序分析法和；而自底向上的分析方法主要有算符优先分析方法和。8.活前缀是指。9.运行时的存储管理方案主要分为两大类，即方案和方案。10.LR(0)文法中，不会出现冲突和冲突。11.常用的参数传递方式有，，传值结果，传名等。二、单选题(每题2分,共20分)1.下面不属于正规文法的是（）。A.S0|1|00|11B.S0|1|0A|1B，A0，B1C.AaS|Sb|a|bD.S0|0S2.一个句型中称为句柄的是该句型的最左（）。A．非终结符号B．短语C．句子D．直接短语3.Chomsky定义的四种形式语言文法中，上下文有关文法是()。A.0型文法B.1型文法C.2型文法D.3型文法4.词法分析的任务是()。A．识别单词B．分析句子的含义C．识别句子D．生成目标代码5.常用的中间代码形式不含()。A．三元式B．四元式C．逆波兰式D．语法树6.经过编译所得到的目标程序是()。A.三元式序列B.四元式序列C.间接三元式D.机器语言程序或汇编语言程序得分评分人《编译原理》试卷共8页，第3页7.中间代码生成所依据的是（）。A.词法规则B.语法规则C.语义规则D.产生式规则8.后缀式ab+cd+/可用表达式（）来表示。A.a+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d9.程序所需的数据空间在程序运行前就可确定，称为（）管理技术。A.动态存储B.栈式存储C.静态存储D.堆式存储。10.文法G：S→xSx|y所识别的语言是（）。A．xyxB．(xyx)*C．xnyxn(n≥0)D.x*yx*三、应用题(每题8分,共32分)1.文法G的产生式如下：S→(L)|aL→L,S|S①有如下语法制导定义，画出输入为((a),a)时的语法分析树，判断其输出结果。产生式语义规则S→(L)S.h:=L.h+1S→aS.h:=0L→L1,SL.h:=L1.h+S.hL→SL.h:=S.hS’→Sprint(S.h)输入为((a),a)时的语法分析树：得分评分人《编译原理》试卷共8页，第4页输入为((a),a)时的输出结果：②有如下翻译模式，判断输入为((a),a)时的输出结果，并简述该翻译模式功能。S’→{S.d:=0;}SS→({L.d:=S.d+1;}L)S→a{print(S.d)}L→{L1.d:=L.d}L1,{S.d:=L.d}SL→{S.d:=L.d}S输入为((a),a)时的输出结果：翻译模式功能：2.已知文法G：E→T|E+TT→F|T*FF→(E)|i，要求：①给出句型(T*F+i)的最右推导。②画出句型(T*F+i)的语法树。③列出句型(T*F+i)的所有短语、简单短语和句柄。短语：《编译原理》试卷共8页，第5页简单短语：句柄：3.给出表达式a:=b*(-c)+b/(-d)的逆波兰式、三元式和四元式。逆波兰式：三元式：四元式：4.给定正规式R=(01|10)(01|10)*，要求：①构造对应的正规文法G，使得L(G)=L(R)。②请构造该文法的状态转换图。《编译原理》试卷共8页，第6页③判断这是一个NFA还是DFA。四、综合分析题（每题14分，共28分）1.对文法G(S)：S→aSb|PP→bPc|bQcQ→Qa|a①消除该文法的左递归和提取左公因子。②针对改造后的文法，构造各非终结符的FIRST和FOLLOW集合。③构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。2.给定文法G[A]：A→aAd|aAb|ε，要求：①构造拓广文法，画出识别该拓广文法的所有规范句型活前缀的DFA。拓广文法为：得分评分人《编译原理》试卷共8页，第7页识别该拓广文法的所有规范句型活前缀的DFA如下，请将其补充完整：②求出所有非终结符的FIRST和FOLLOW集合，填写该文法的SLR(1)分析表。FIRST(A)={}FOLLOW(A)={}该文法的SLR(1)分析表构造如下：ACTIONGOTOabd#A012345③填表给出串ab#的LR分析过程。步骤状态符号输入串10#ab#23456I0:A’→.AAI1:A’→A.aI2:AI4:.I5:dI3:ba《编译原理》试卷共8页，第8页