编译原理期末试题(8套含答案+大题集)

第1页共6页《编译原理》期末试题（五）一、单项选择题(共10小题，每小题2分，共20分)1．语言是A．句子的集合B．产生式的集合C．符号串的集合D．句型的集合2．编译程序前三个阶段完成的工作是A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成D．词法分析、语法分析和代码优化3．一个句型中称为句柄的是该句型的最左A．非终结符号B．短语C．句子D．直接短语4．下推自动机识别的语言是A．0型语言B．1型语言C．2型语言D．3型语言5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即A．字符B．单词C．句子D．句型6．对应Chomsky四种文法的四种语言之间的关系是A．L0L1L2L3B．L3L2L1L0C．L3=L2L1L0D．L0L1L2=L37．词法分析的任务是A．识别单词B．分析句子的含义C．识别句子D．生成目标代码8．常用的中间代码形式不含A．三元式B．四元式C．逆波兰式D．语法树9．代码优化的目的是A．节省时间B．节省空间C．节省时间和空间D．把编译程序进行等价交换10．代码生成阶段的主要任务是A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码D．把汇编语言翻译成机器语言二、填空题（本大题共5小题，每小题2分，共10分）1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。第2页共6页三、名词解释题(共5小题，每小题4分，共20分)1．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。2．LL(1)文法若文法的任何两个产生式A|都满足下面两个条件：（1）FIRST()FIRST()=；（2）若*，那么FIRST()FOLLOW(A)=。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3．语法树句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么AA1A2…AR一定是P中的一条产生式。(4)若一标记为A的节点至少有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。4．LR(0)分析器所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。5．语言和文法文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G定义为四元组的形式：G=(VN，VT，P，S)其中：VN是非空有穷集合，称为非终结符号集合；VT是非空有穷集合，称为终结符号集合；P是产生式的集合(非空)；S是开始符号(或识别符号)。这里，VN∩VT=，SVN。V=VN∪VT，称为文法G的字母表，它是出现文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示，它由文法G所产生的全部句子组成，即第3页共6页L(G)={x|S*x，其中S为文法开始符号，且TVx}简单的说，文法描述的语言是该文法一切句子的集合。四、简答题(共4小题，每小题5分，共20分)1．编译程序和高级语言有什么区别?用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的对话，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。2．编译程序的工作分为那几个阶段?词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)，而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。3．简述自下而上的分析方法。所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。4．简述代码优化的目的和意义。代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。五、综合应用题(共3小题，每小题10分，共30分)1．证明下述文法G：SaSbS|aS|d是二义性文法。解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子aadbd有两棵语法树。如下图：dSSabSSadSaSSabSdd第4页共6页(1)(2)由此可知，SaSbS|aS|d定义的文法是二义性文法。2．对于文法G[S]：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄？句型baSb的语法树如图五(2)所示。解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。3．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，，{A}，{C})，其中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}。请画出状态转换距阵和状态转换图。解：状态转换距阵为：01ACA，BBCCC状态转换图为《编译原理》期末试题（六）编译原理样题ASBbBSabAB1C11011第5页共6页【】1．____型文法也称为正规文法。[A]0[B]1[C]2[D]3【】2．____文法不是LL(1)的。[A]递归[B]右递归[C]2型[D]含有公共左因子的【】3．文法E→E+E|E*E|i的句子i*i+i*i的不同语法分析树的总数为______。[A]1[B]3[C]5[D]7【】4．四元式之间的联系是通过实现。[A]临时变量[B]指示器[C]符号表[D]程序变量【】5．同心集合并可能会产生的新冲突为。[A]二义[B]移进/移进[C]移进/归约[D]归约/归约【】6．代码优化时所依据的是。[A]语法规则[B]词法规则[C]等价变换规则[D]语义规则【】7．表达式a-(-b)*c的逆波兰表示为。[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-*（注：@为单目减运算符）【】8．过程的DISPLAY表记录了。[A]过程的连接数据[B]过程的嵌套层次[C]过程的返回地址[D]过程的入口地址二填空题3．对于文法G1和G2，若有L(G1)=L(G2)（或G1和G2的语言相同），则称文法G1和G2是等价的。4．对于文法G[E]：E→T|E+TT→F|T*FF→P^F|PP→(E)|i，句型T+T*F+i的句柄是T，最左素短语是T*F。5．最右推导的逆过程称为规范归约，也称为最左归约。6．规范规约中的可规约串是句柄，算符优先分析中的可规约串是最左素短语7．（A∨B）∧（C∨¬D∧E）的逆波兰式是ＡＢ∨ＣＤ¬Ｅ∧∨∧。8．在属性文法中文法符号的两种属性分别称为继承属性和综合属性（次序可换）。9．符号表的每一项是由名字栏和地址分配两个栏目组成。在目标代码生成阶段，符号表是地址分配的依据。10．一个过程的DISPLAY表的内容是它的直接外层的DISPLAY表的内容加上本过程的SP的地址三有穷自动机M接受字母表＝{0,1}上所有满足下述条件的串：每个1都有0直接跟在右边。构造一个最小的DFAM及和M等价的正规式。【】【】第6页共6页四证明正规式(ab)*a与正规式a(ba)*等价（用构造他们的最小的DFA方法）。【答案：】五写一个文法，使其语言是：L＝{1n0m1m0n|m,n≥0}【】【】五文法G：S→1S0|AA→0A1|ε六对文法G[S]第7页共6页S→aSb|PP→bPc|bQcQ→Qa|a(1)它是否是算符优先文法？请构造算符优先关系表(2)文法G[S]消除左递归、提取左公因子后是否是LL（1）文法？请证实。【】【】1.求出G[S]的FIRSTVT集和LASTVT集：FIERSTVT（S）={a,b}LASTBVT（S）={b,c}FIERSTVT(P)={b}LASTBVT（P）={c}FIERSTVT(Q)={a}LASTBVT（Q）={a}构造优先关系表为：abcabc由于在优先关系中同时出现了aa和aa以及bb和bb，所以该文法不是算符优先文法。2.消除左递归和提取左公因子后的文法为：S→aSb|PP→bP’P’→Pc|QcQ→aQ’Q’→aQ’|ε求具有相同左部的两个产生式的Select集的交集：Select(S→aSb)∩Select(S→P)={a}∩First(P)={a}∩{b}=ФSelect(P’→Pc)∩Select(P’→Qc)=First(P)∩First(Q)={b}∩{a}=ФSelect(Q’→aQ’)∩Select(Q’→ε)={a}∩Follow(Q)={a}∩{c}=Ф所以修改后的文法是LL（1）文法。七已知文法G为:（0）S′→S（1）S→aAd（2）S→bAc（3）S→aec（4）S→bed（5）A→e试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。【】【答案：】cAdI0:S′→·S,#S→·aAd,#S→·bAc,#S→·aec,#S→·bed,I2：S→a·Ad,#S→a·ec,#A→·e,daI1：S′→S·,#SI3:S→b·Ac,#bI6:S→bA·c,#AI10：S→bAc·,#I4：S→aA·d,#I5：S→ae·c,#A→e·,deI8：S→aAd·,#I9：S→aec·,#c第8页共6页构造LR(1)分析表如下：八已知源程序如下：prod:=0;i:=1;whilei≤20dobeginprod:=prod+a[i]*b[i];i:=i+1end;试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组