成都理工大学2012-2013软件代码开发技术(编译原理)考试试卷(最终修改版)

成都理工大学2012-2013学年第一学期《软件代码开发技术》考试试卷一，填空题（每题2分，共30分）1.源程序的动态错误是源程序中的逻辑错误，它们发生在程序运行的时候，也被成为动态语义错误。2.设计一个编译器，除了具有中间代码生成、代码生成和出错处理功能之外，还应具有哪些功能：它们分别为_词法分析、语法分析、语义分析、中间代码优化、符号表管理_3.设∑=｛0,1｝上的正规集S由倒数第二个字符为0的所有字符串组成，则该正规集对应的正规式表示为(0|1)*0(0|1)4.假设G是一个文法，S是文法的开始符号，如果S=x,则称x是该文法的一个句型5.中间代码生成器对语法树进行遍历，生成可顺序执行的中间的代码序列，最常用的中间代码形式是四元式6.最右推导也成为规范推导，推导出的句型称为右句型。7.LR(k)文法所识别的语言称为LR(k)语言，其中L表示从左到右扫描输入序列，R表示逆序的最右推导，k表示确定下一动作向前看的终结符个数8.将栈顶的符号和文法产生式的右部符号串进行比较，若相等，则用左部符号去替换栈顶符号串，这种操作称为规约9.自上而下语法分析方法遇到的主要问题是回溯和无限循环（死循环）10.正规文法，正规表达式和有限自动机三者在某种意义下是等价的11.若为文法G构造的预测分析表中不含多重定义的条目，则称G为回溯文法。12.文法符号的属性有两种，一种称为综合属性，另一种称为几成属性。13.一个句型中的最左直接短语称为该句型的句柄。14.如果一个问发的同一个句子存在两棵分析树，则该文法是二义性的15.不管任何类型的文法都包括四个组成部分，它们分别是非终结符、终结符、产生式、开始符号二、判断题（每题1分，共10分）1，确定的和不确定的有限自动机都能识别正规集。（√）2，有些语言能被确定的有限自动机识别，但不能用正规表达式表示。（×）3，设L={a,b,c},M={b,c,d},LM={b,c}.（×）4，在预测分析器的转换图中，其箭弧上的标识必须是终结符。（×）5，一个项目集中既可以有移进项目，又有可规约项目，使得分析无法进行，这种冲突称为移进/规约冲突。（√）6，在使用自上而下分析法时，文法应该没有左递归。（√）7，正规集都可以由一个状态数最少的DFA识别，这个DFA是唯一的。（√）8，二义文法是SLR(l)文法。（×）9，正规表达式的运算操作不具有优先级运算。（×）10，文法G的产生式为S-（L）|aL-L，S|S是一个直接左递归文法。（√）三、选择题（每题1分，共10分）1，文法G所描述的语言是D的集合。A．文法G的字汇表V中所有符号组成的符号串B．文法G的字汇表V的闭包V*中的所有符号串C．由文法的开始符号推出的所有符号串D．由文法的开始符号推出的所有终结符号串2，一个语言的文法是B。A．唯一的B.不唯一的C.个数有限的3，若一个文法是递归的，则它所产生的句子个数A。A.必定是无穷的B.是有限个的C.根据具体情况而定4，文法的二义性和语言的二义性是两个A的概念。A.不同B.相同C.无法判断D.等价5，巴克斯范式（BNF）是一种广泛采用的C的工具。A.描述规则B.描述语言C.描述文法D.描述句子6，B是两类程序语言处理程序。A.高级语言程序和低级语言程序B.解释程序和编译程序C.编译程序和操作系统D.系统程序和应用程序7，乔姆斯基把文法分为四种类型：0型、1型、2型和3型，其中2型文法指的是C。A．短语文法B.上下文有关文法C.上下文无关文法D.正规文法8，语法分析常用的方法是A。A.自顶向下、自底向上B.自顶向下、自底向上、自左向右C.自顶向下、自底向上、自左向右、自右向左D.自左向右、自右向左9.编译程序中的语法分析器接受以C为单位的输入，并产生以有关信息供以后各阶段使用。A.表达式B.产生式C.单词D.语句10.LR语法分析栈中存放的状态是识别B的DFA状态。A.前缀B.可规约前缀C.项目D.句柄四，综合题（5小题，共50分）1，设文法G具有下列产生式：E-EOrT|TT-TandF|FF-notF|(E)|true|false请指出文法G的终结符号、非终结符号和开始符号。（4分）解答：终结符：｛or,and,not,(,),true,false｝非终结符：｛E,T,F｝开始符号：｛E｝2，根据1中文法G写出句子not(trueandfalse)的规范推导并确定句柄。（6分）解答：规范推导为：E=T=F=notF=not(E)=not(T)=not(TandF)=not(Tandfalse)=not(Fandfalse)=not(trueandfalse)由分析树：可知句柄为：true3，有NFA定义如下：N=（S={0,1}，∑=｛a,b｝,s0=0，F={0}，MOVE={move(0,a)=0，move(0,a)=1，move(1,a)=0}）(1)画出N的状态转换图（4分）解答：aa,ba10(2)构造N的最小DFAD（7分）解答：确定DFAε_闭包（｛0｝）=｛0｝*Aε_闭包（smove(｛0｝,a)）=｛0,1｝*Bε_闭包（smove(｛0｝，b)）=｛1｝*Cε_闭包（smove(｛0，1｝,a)）=｛0,1｝Bε_闭包（smove(｛0，1｝,b)）=｛1｝Cε_闭包（smove(｛1｝,a)）=｛0｝Aε_闭包（smove(｛1｝,b)）=εDFA为：Π=｛｛A，B｝｝,｛C｝｝move(A,a)=Bmove(A,b)=｛c｝move(B,a)=Bmove(B,b)=｛c｝故A,B不可分，将A为｛A,B｝编号0，C编号1,为｛c｝代表最小DFA为aba10(3)给出串aaba,baa的识别过程（4分）解答：aaba00010baa0100识别aaba:识别baa:4，设文法G具有下列产生式：E-E+T|TT-T*F|FF–id|(E)(1)消除文法的直接左递归：（4分）解答：消除左递归后的文法为：E-TE’E’-+TE’/εT-FT’T’-*FT’/εF-id/(E)(2)求消除左递归后文法的FIRST和FOLLOW函数：（6分）解答：First(F)=｛id,(｝First(T’)=｛*,ε｝First(T)=｛id,(｝First(E’)=｛+，ε｝First(E)=First(T)=First(F)=｛id,(｝Follow(E)=｛#,)｝Follow(E’)=Follow(E)=｛#,)｝Follow(T)=｛+,#,)｝Follow(T’)=Follow(T)=｛+,#,)｝Follow(F)=｛*,+,#｝(3)构造其预测分析表。（4分）解答：first(TE’)=｛id，(｝first(+TE’)=｛+,ε｝first(FT’)=｛id，(｝first(*FT’)=｛*,(｝first(id)=idfirst((E))=｛（｝*+）（id#ETE’TE’E’+TE’εεTFT’FT’T’*FT’εεεF(E)id5，已知文法G3:S`-EE-aA|bBA-cA|dB-cB|d(1)写出句型bccB的所有短语、直接短语和句柄。（4分）解答：S’=E=bB=bcB=bccB短语：bccB(S’E)ccB(B1)cB(B2)直接短语：cB(B2)句柄：cB(B2)(2)列出4个项目集I1、I2、I3、I4（如下图），请将这4个项目集补充完整。（7分）I1:S`-.EE-.aAE-.bBI2:E-a.AA-.cAA-dI3:E.I4:E-b.BB-.cBB-.daEb附加资料：编译：高级语言可以直接转换成机器语言，也可以翻译成汇编语言，这两个过程称为编译。解释器与编译器的主要区别：运行目标程序的控制权在解释器而不在目标程序。解释器优点：（1）其具有较好的动态特性。（2）具有较好的可移植性。缺点：在时间和空间上的损失较大，运行效率低。文法的分类：文法产生式语言自动机0型文法（短语）α-β0型语言（短语结构语言，递归可枚举集）图灵机1型文法（CSG）限制11型语言（CSL）线性界线自动机2型文法（CFG）限制22型语言（CFL）下推自动机3型文法（正规）限制33型语言（正规语言，正规集）有限自动机LR(1)与LALR(1)的关系：LR(1)与LALR(1)对于移进/规约冲突的解决二者是等价的，而对于规约/规约冲突，由于LALR(1)项目中合并了lookaheads可能会减弱它对规约/规约冲突的解决能力，具体有下述两个结论：(1)LR(1)DFA中不发生的移进/规约冲突，LALR(1)DFA中也一定不会发生。(2)合并后的lookaheads可能会引起LALR(1)项目集中的规约/规约冲突。