搜索
《编译原理》期终考卷2010学号：姓名：说明:1、本考卷中大写字母∈VN，其他符号∈VT；2、试卷中一、二两题请作在考卷上一、填空题（20分）1、一般说来编译系统的编译过程分五步，它们分别为、、、、。2、计算机三大系统软件分别、、。3、自上而下分析法的典型算法是、两类。二、判断题（10分。注：每答对一题得+2分；答错一题得-2分；不答者得0分）1、设∑为{a，b}，则a，ba，{∑}，Ø都是∑上的正规式。（）2、对于上下文无关文法G[S]，若SαABαβγ则A一定是一条产生式规则，其中α,β,γ∈（VT∨VN）*（）3、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（）4、LR（0）分析法是一种规范归约法。（）5、算符优先分析法只能用来分析算符优先文法。（）三、（20分）1、设∑={a,b,c}，设计一个DFA，它识别所有以b开头且只允许出现一个b的字。2、用程序实现DFA的功能。四、下列文法如果是LL(1)文法，请求其预测分析表；如果不是，请说明理由（本题20分）AAaB|BBBeF|FFf六、（30分）有作控制用的布尔表达式文法G[E]及其语义动作如下：文法G[E]：(1)Eii{E.TC:=NXQ;E.FC=NXQ+1;GEN(J,ENTRY(i),ENTRY(i),O);GEN(J,,,0)}(2)EAE{E.FC:=E.FC;E.TC:=MERGE(A.TC,E.TC)}(3)AB∨{BACKPATCH(B.FC,NXQ);A.TC:=B.TC}(4)Bi{B.TC:=NXQ;B.FC:=NXQ+1;GEN(Jnz,ENTRY(i),,0);GEN(J,,,0)}1、构造SLR（1）分析表（若不是SLR(1)）的，则说明理由）2、使用语法制导翻译法分析作控制用的布尔表达式ab∨c的四元式生成过程，并画出最后的真假链表。3、给出语句IFab∨cTHENI:=m*nELSEI:=m+n的完整四元式序列。《编译原理》软件工程2005级期终考卷学号：姓名：说明:1.本考卷中大写字母∈VN，其他符号∈VT；2、试卷中一、二两题请作在考卷上一、概念题（15分）1、编译过程一般分为几个阶段？各阶段的输入输出分别为什么？2、对下列状态转换图，写出状态0的处理过程：其中：状态2的过程为proc2.3、文法G为：SaABAaB则判断G为LL（1）文法的条件是：二、判断题（10分。注：每答对一题得+2分；答错一题得-2分；不答者得0分）1、设∑为{a，b}，则a，ba，{∑}，Ø都是∑上的正规式。（）2、对于上下文无关文法G[S]，若SαABαβγ则A一定是一条产生式规则，其中α,β,γ∈（VT∨VN）*（）3、对于逆波兰后缀式，无论从哪头开始分析均可得到唯一正确的分解。（）4、LR（0）分析法是一种规范归约法。（）5、算符优先分析法只能用来分析算符优先文法。（）三、（10分）设文法G3为：SAaBcAAa|aBb求句型AaBc的最左素语。四、（20分）设文法G[S]为SaAcB问：1、该文法是否为算符文法，为什么？AAb|b2、构造算符优先关系表。Bd3、该文法是否可改造为LL（1）文法，为什么？五、（本题20分）设文法G为：EeAf|eBgAaA|aBBb|a对于输入串eaaaf，采用LR（0）、LL（1）、SLR（1）等方法中合适的一种进行分析。六、（25分）有作控制用的布尔表达式文法G[E]及其语义动作如下：1、构造SLR（1）分析表（若不是SLR(1)）的，则说明理由）2、分析布尔式a∨bc的四元式生成过程，并画出最后的真假链表。3、给出语句IFa∨bcTHENI:=m*nELSEI:=m+n的完整四元式序列。文法G[E]：(1)Eii{E.TC:=NXQ;E.FC=NXQ+1;GEN(J,ENTRY(i),ENTRY(i),O);GEN(J,,,0)}(2)EAE{E.FC:=E.FC;E.FC:=MERGE(A.TC,E.TC)}(3)AB∨{BACKPATCH(B.FC,NXQ);A.TC:=B.TC}(4)Bi{B.TC:=NXQ;B.FC:=NXQ+1;GEN(Jnz,ENTRY(i),,0);GEN(J,,,0)}常见问题自顶向下分析算法带回溯的自顶向下分析主旨：对任何输入串试图用一切可能的方法，从根节点（文法开始符号）出发，自上而下地为输入串建立一棵语法树。其本质是一种试探法。例．输入串存在的问题：1．若文法是左递归的（）则分析会陷入死循环2．存在回溯3．效率低自下向上分析基本问题归约我们所讨论的自下而上分析法是一种“移进-归约”法。这种方法的大意是，用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个侯选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。例：假定文法G为：（1）S→aAcBe（2）A→b（3）A→Ab（4）B→d我们希望把输入串abbcde归约到S。则符号栈的变化情形如下：步骤：12345678910动作：进进归进归进进归进归ab(2)b(3)cd(4)e(1)edBBbccccbAAAAAAAaaaaaaaaaSSLR分析表的构造一．LR(0)存在的问题LR(0)虽简单，但很少见，如不是LR(0)的。二．解决办法若项目集中有：，分析所有含A和B的句型，考察所有可能直接跟在A和B之后的终结符，如果它们不相交且都不含b，那么当状态I面临任何输入符号a时，可采取如下移进－归约策略。1．a=b时，移进2．若，则用归约。3．若，则用归约。4．其他，出错。一般而言，如果某LR(0)项目集I中含有m个移进项目，，同时有n个归约项目。若两两不相交，则动作冲突可通过检查当前输入符号a属于哪个集合而决定。因为只看一个符号，所以称为SLR(1)方法（简单LR(1)）总结性习题一第一章编译程序概述1.1什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。图1.1表示了编译的各个阶段。图1.1编译的各个阶段1.3高级语言解释系统为了实现在一个计算机上运行高级语言的程序,主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就叫解释程序。从功能上说，一个解释程序能让计算机执行高级语言。它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。第二章：高级语言及其语法描述问答第1题写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。答：(1)允许0开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0问答第2题证明下述文法G[〈表达式〉]是二义的。〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a问答第3题令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答：因为存在推导序列:EE+TE+*F所以E+T*F是文法G[E]的一个句型句型E+T*F的短语有:E+T*F,T*F直接短语有:T*F句柄为:T*F问答第4题给出生成下述语言的上下文无关文法：（1）{anbnambm|n，m=0}（2）{1n0m1m0n|n，m=0}答：(1)S→AAA→aAb|ε(2)S→1S0|AA→0A1|ε问答第5题给出生成下述语言的三型文法：(1){anbm|n,m=1}(2){anbmck|n,m,k=0}答：(1)S→aAA→aA|BB→bB|b(2)A→aA|BB→bB|CC→cC|ε问答第6题给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答：R=(01|10)(01|10)*第三章：词法分析问答第1题构造正规式1(0|1)*101相应的DFA.答：先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:问答第2题将下图确定化：解：用子集法将NFA确定化：.01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。.01SABACBBDECFFDF.ECEFFFDFA的状态图：问答第3题将下图的（a）和（b）分别确定化和最小化：解：初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5}对非终态组进行审查：{1,2,3,4,5}a{0,1,3,5}而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}∵{4}a{0}，所以得到新分划Π1：{0}，{4}，{1,2,3,5}对{1,2,3,5}进行审查：∵{1,5}b{4}{2,3}b{1,2,3,5}，故得到新分划Π2：{0}，{4}，{1,5}，{2,3}{1,5}a{1,5}{2,3}a{1,3}，故状态2和状态3不等价，得到新分划Π3：{0}，{2}，{3}，{4}，{1,5}这是最后分划了最小DFA：问答第4题构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。解：按题意相应的正规表达式是(0*10)*0*，或0*(0|10)*0*构造相应的DFA，首先构造NFA为用子集法确定化：II0I1{X,0,1,3,Y}{0,1,3,Y}{2}{1,3,Y}{0,1,3,Y}{0,1,3,Y}{1,3,Y}{1,3,Y}{2}{2}{2}重新命名状态集：S0112342244333DFA的状态图：可将该DFA最小化：终态组为{1,2,4}，非终态组为{3}，{1,2,4}0{1,2,4}，{1,2,4}1{3}，所以1,2,4为等价状态，可合并。第四章语法分析—自上