编译原理2007期末考试试卷答案

2007一、简答题（共15分。）1.通过合并LR(1)文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？为什么？（5分）答：可能会产生归约-归约冲突，一定不会产生移进-归约冲突。因为在对LR(1)合并同心集合时，有可能将原本没有冲突的同心集的项目集合并后造成一些归约项目向前搜索符集合的交集不是空，产生归约-归约冲突。但是由于文法本身已经是LR(1)文法，因此可知，在项目集中一定不存在移进-归约冲突，也就是移进项目要求输入的终结符和任意归约项目的向前搜索符集合的交集都是空集。这样，在将同心集合并之后，移进项目要求输入的终结符和归约项目的向前搜索符集合的交集也还是空集。2.如果在A机器上我们有C语言编译器CCA，也有它的源码SA（用C语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CCB。（5分）答：A机器上C语言编译器CCA的结构如下：CAA其源码SA结构如下：CAC首先，用C语言编写一个从C语言到B机器语言的编译器，成为SB，其结构如下：CBC第二步，将这个编译器放到CCA中进行编译，得到用A机器语言编写的，将C语言编译成B机器代码的编译器，其过程和结构如下：CAACBCCBA第三步，再将SB放入新得到的这个编译器中去编译，就得到了要求的编译器CCB，其过程和结构如下：CBACBCCBB3.Pascal语言允许过程嵌套声明，C语言的过程声明不能嵌套。在Pascal程序中，数据分为局部数据、非局部数据，而C程序中，数据分为局部数据和全局数据。因此，C程序执行时只用到了控制链(动态链)，不需要使用访问链(静态链)。试根据前面的已知说明，为什么Pascal程序执行时需要使用访问链，而c程序不需要。(5分)答：由于C语言不允许嵌套的过程声明，因此所有的非局部名字都可以静态地绑定到所分配的存储单元，因此，可以不使用访问链。而Pascal语言允许过程的嵌套，并使用静态作用域，确定用于名字的声明需要根据过程的嵌套层次来决定。和C语言不同的是，Pascal语言的非局部名字不一定就是全局的。运行时访问非局部名字的时候，我们首先要确定该非局部名字被绑定到的活动记录，因此就必须要用到访问链。二、简单计算题（共25分）1.令文法G[E]为E→T|E+T|E-TT→F|T*F|T/FF→(E)|i(1)证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。(2)给出i+i*i、i*(i+i)的最左推导和最右推导；(10分)答：(1)E=E+T=E+T*F，其短语有：T*F，E+T*F；直接短语是T*F，句柄是T*F(2)i+i*i的最左推导：最右推导E=E+TE=E+T=T+T=E+T*F=F+T=E+T*i=i+T=E+F*i=i+T*F=E+i*i=i+F*F=T+i*i=i+i*F=F+i*i=i+i*i=i+i*ii*(i+i)的最左推导：最右推导E=TE=T=T*F=T*F=F*F=T*(E)=i*F=T*(E+T)=i*(E)=T*(E+F)=i*(E+T)=T*(E+i)=i*(T+T)=T*(T+i)=i*(F+T)=T*(F+i)=i*(i+T)=T*(i+i)=i*(i+F)=F*(i+i)=i*(i+i)=i*(i+i)2.已知语言写出相应的文法：（6分）(1)已知语言L={WaWr|W属于(0|a)*，Wr表示W的逆}，试构造相应的上下文无关文法。(2)已知语言L={1n0m1m0n|m0,n=0}，试构造相应的上下文无关文法。(3)已知语言L={anbnambm|m=0,n0}，试构造相应的上下文无关文法答：(1)文法为：({S},{0,a},P,S)，其中P为S→0S0|aSa|a(2)文法为：({A,S},{0,1},P,S)，其中P为S→1S0|AA→0A1|01(2)文法为：({A,B,S},{a,b},P,S)，其中P为S→ABA→aAb|abB→aBb|ε3.构造一个NFA，(1)接受字母表{a,b}上的正规式(ab|a)*b+描述的集合。(2)将(1)中的NFA转换为等价的DFA(3)将(2)中的DFA转换为最小状态DFA（写出步骤）（9分）答：构造的NFA如下：01aab2bb确定化过程：状态集合ab{0}A{0,1}B{2}C{0,1}B{0,1}B{0,2}D{2}C{2}C{0,2}D{0,1}B{2}C确定的DFA如下：ABaabCbbDab上面的DFA已经是最小化的。三、证明推导题（共30分，每题10分）2下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：S→L.L|LL→LB|BB→0|1试设计求S.val的属性文法，其中，已知B的综合属性c，给出由B产生的二进位的结果值。答：产生式语义规则SL1.L2S.val:=L1.val+L2.val/2L2.lengthSLS.val:=L.valLL1BL.val:=L1.val*2+B.valL.length:=L1.length+1LBL.val:=B.valL.length:=1B0B.val:=0B1B.val:=1四、程序计算/设计题（共30分，每题10分）1.设A为一个10×20的数组，即n1=10，n2=20，并设w=4。试将赋值语句x:=A[y,z]翻译成三地址语句序列。答：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T4:=T2[T3]x:=T42.如果不存在形如S=ωXγ=ωxγ的推导，则文法符号X是无用的，即从开始符号S，不能够推导出含有X的句型，也就是说X不会出现在任何句子的推导中。试设计一个算法，从文法中删除包含无用符号的产生式。答：设计一个队列，用来存放可以出现在句子推导中的非终结符号。对队列进行初始化，将S放在其中。(1)从队列中取出一个符号，设其为A，考察产生式，将形如A→α的产生式右部符号串中出现的非终结符都放入队列中。如果非终结符已经存在队列中，则不重复加入。(2)重复上述动作，直至队列中所有的非终结符都考察过，并且没有新的非终结符加入队列为止。此时得到的队列就是那些有用的非终结符。那些含有不在此队列中出现的非终结符的产生式就是包含无用符号的产生式，将其删除即可。3.考虑下面程序voidQ(intx){inti=1;x=x+2;i=2;x=x+2;}voidmain(){inti;intB[3];B[1]=1;B[2]=2;i=1;Q(B[i]);}试问：若参数传递方式分别采取(1)传值调用，(2)引用调用，(3)复制-恢复调用，(4)传名调用时，程序执行后输出B[1]和B[2]的值分别是什么？请简要写出计算过程。答：(1)采用传值调用时，将实在参数的值传递给形式参数，而后在函数调用过程中，操作的是形式参数，形式参数的值发生改变，而且这些改变不能重新传递给实在参数，所以得到的结果是B[1]=1；B[2]=2(2)采用应用调用，将实在参数的地址传递给形式参数，此时对形式参数的操作就相当于对其指向的地址单元进行操作，其操作影响了实在参数，所以得到的结果是B[1]=5；B[2]=2(3)采用复制-恢复调用，首先将实在参数的值传递给形式参数，此时，x=1，y=2，进行函数调用后，得到，x=5，y=2，调用返回时，将形式参数的值传递到相应的实在参数的地址中，即x的值传递到B[1]的地址中，所以得到的结果是B[1]=5；B[2]=2(4)采用传名调用，将B[i]当成整个的一个整体，替换函数调用中的x，得到：i=1;B[i]=B[i]+2;i=2;B[i]=B[i]+2;计算得到，B[1]=3，B[2]=4