杭电编译原理试卷一及答案.pdf
试卷（一）一、 选择1.一个正规语言只能对应( B)？A 一个正规文法；B 一个最小有限状态自动机；2.文法 GA：A AaB BAb Ba是( B)：A 正规文法；B 二型文法；3.下面说法正确的是( A)：A 一个 SLR（1）文法一定也是 LALR（1）文法；B 一个 LR（1）文法一定也是 LALR（1）文法4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足 LL（1）文法的( A)：A 必要条件B 充分必要条件二、多项选择1.PL/0 语言的目标程序解释执行时用到的数据对象有(AC)：A 目标代码 CODEB 符号表 TABLEC 数据栈 SD 关键字表 WORD2.PL/0 语言编译时产生或使用的数据对象有(ABD)：A 目标代码 CODEB 符号表 TABLEC 数据栈 SD 关键字表 WORD三、问答题问答第 1 题(5 分)将文法 GS 改写为 等价的 GS，使 GS不含左递归和左公共因子。GS： SbSAe | bAAAb | dSbBBSAe | AAd AA bA | 问答第 2 题(10 分) 判断下面文法是否为 LL(1)文法，若是,请构造相应的 LL(1)分析表。SaHHaMd | dMAb | AaM | e首先计算文法的 FIRST 集和 FOLLOW 集如下表非终结符FIRST 集FOLLOW 集Sa.# .Ha ，d.# .Ma ，e ， d ，bAa ，e.b.由于 select（HaMd）select（Hd）=ad =select（MAb）select（M ）=a ，ed ，b =select（AaM）select（Ae）= a e =所以该文法是 LL(1)文法，LL(1)分析表如下表。LL(1)分析表SHMAaaH.aMdAb.aM.dd.beAbe.#问答第 3 题给出与正规式 R（ab）*（a|b*）ba 等价的 NFA。问答第 4 题将下图的 NFA确定化为 DFA。用子集法对所给图的确定化IX,1,21,2.1,2,3Ia1,2.1,2.1,2,YIb1,2,31,2,31,2,3状态X121,2,Y确定化后如下图1,2.1,2,33问答第 5 题(7 分)（1）给出下列 PL/0 示意程序中当程序执行到 X 过程调用 Z 过程后（即执行 Z过程 体时）的栈式存储分配布局和用 Display 显示表时 Z 过程最新活动记录的内容。（2）说明 Display 表和 DL（老 SP）,RA,TOP 及全局 Display 的作用。 PL/0 示意程序为：const a=80;var b,c;procedure X;var d;procedure Z;var e,g;begin (* Z *)c:=b*a；end ；(* Z *)begin (* X *)call Z;end ；(* X *)procedure Y;var f;begin (* Y *)call X;end ；(* y *)begin (* main *)call Y;end. (* main *)解：（1）当程序执行到X 过程调用 Z 过程后（即执行Z 过程 体时）的栈式存储分配布局和用 Display 显示表时 Z 过程最新活动记录的内容如下图。解：（2）Display 表和 DL（老 SP）,RA,TOP 及全局 Display 的作用分别说明如下：Display 表的作用是对嵌套过程语言实现对非局部变量的引用而设置的，它依次存放着包围它的外过程的最新活动记录的基地址 SP 值，由于，嵌套层 次为i+1 过程中的非局部变量可能在 i，i-1，0 层，所以，对非局部变量的引用是通过它的 display 表元素 di，di- 1，d0而获得包围它的外过程的最新活动记录的基地址 SP 值，再加上变量在该过程（第 i 层）的偏移量。如若非局部变量 a 是在第 i 层，那么引用 a 时，首先从当前栈顶过程的 display 表中元素 di中取出存放的第 i 层最新活动记录基地址 SP 值，然后加上 a 所在过程（第 i 层）的偏移量，就得到 a 的存放地址。如 Z 过程的 display 表内容为：d（2）Z 的 SPd（1）X 的 SPd（0）Main 的 SPDL（老 SP）： 也称动态链或控制链，指向调用该过程前正在运行过程的数据段基地址， 用以过程执行结束释放数据空间时， 恢复调用该过程前运行栈的状态。RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。TOP：栈顶指针 TOP 指出了当前栈中最新分配的单元。全局 Display 是存放本过程 display 表的起始地址， 其作用是把 display 地址作为连接数据之一，如过程P1 调用过程 P2 时，这时先从 P1 的全局 Display 找到 P1 的 display 表起始地址，然后从 P1 的 display 表中自底向上地抄录 I2 个单元（I2 为 P2 的层数）再添上进入 P2 后新建立的 P2 的 SP 值，就构成了 P2的 display 表。问答第 6 题(5 分)给出问答第 5 题 PL/0 示意程序编译到 Y 过程体时 TABLE 表的内容。解：PL/0 示意程序编译到 Y 过程体时 TABLE 表的内容如下表。解：TABLE表的内容namemainabcXYfkindprocedureconstantvariablevariableprocedureprocedurevariablelevelval.8000001adr0.dxdx+1过程 X 的入口过程 Y 的入口dxsize5.44由于 Y 和 X 是并列过程，当编译到Y 过程时 X 过程体已经编译结束，X 所定义的标识符不会再被使用，所以 X 定义的标识符 d 、Z 及 Z 定义的 e、g 都被 Y 过程定义的标识符覆盖。问答第 7 题(10 分)某语言的拓广文法 G为：(0) ST(1) T aBd|(2) B Tb|证明 G 不是 LR(0)文法而是 SLR(1)文法，请给出 SLR(1)分析表。解：在项目集 I0 中：有移进项目 T aBd 和归约项目 T 存在移进-归约冲突，所以 G 不是 LR(0)文法。若产生式排序为：(0) ST(1) T aBd(2) T (3) B Tb(4) B G的 LR(0)项目集族及识别活前缀的 DFA 如下图所示：识别 G活前缀的 DFA：由产生式知：Follow(T)=#,bFollow(B)= d在 I0 中：Follow(T) a=# ，b a=在 I2 中：Follow(B) a= d a=Follow(T) a=# ，b a=Follow(B) Follow(T) = d# ，b=所以在 I0，I2，中的移进-归约和归约-归约冲突可以由 Follow 集解决，所以 G是 SLR(1)文法。构造的 SLR(1)分析表如下表。SLR(1)分析表ACTIONGOTOnameabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r3问答第 8 题(5 分)给出文法 GS的 LR(1)项目集规范族中 I0 项目集的全体项目。GS为： S BD|DB aD|b D BI0:解:I0问答第 9 题(5 分)文法 GM及其 LR 分析表如下，请给出对串 dbba#的分析过程。GM: 1) M VbA2) V d3) V 4) A a5) A Aba6) A ACTIONGOTObda#MA0r3S311acc2S43r24r6S5r665r4r46S7r17S88r5r5解：对输入串 dbba#的分析过程步骤状态栈文法符号栈10#203#d302#V4024#Vb剩余输入符号dbba#bba#bba#ba#动作移进用 V d 归约移进用 A 归约V256789024602467024678024601#VbA#VbAb#VbAba#VbA#Mba#移进a#移进#用 A Aba 归约#用 M VbA 归约#接受问答第 10 题（5 分）文法 GE为： EE+T|TTT*F|FF(E)|i试给出句型(E+F)*i 的短语，简单(直接)短语,句柄和最左素短语。解：短语有: (E+F)*i ，(E+F) ，E+F ，F ，i简单(直接)短语有: F ，i句柄是: F最左素短语是: E+F问答第 11 题（6 分）按指定类型给出下列语言的文法。(1)L1= anbm c| n0,m0 用正规文法。(2) L2= a0n1n bdm | n0，m 0 用二型文法。(1) 解：描述 L1 语言的正规文法如下：S aS|AA bA|bBB c(2) 解：描述 L2 语言的二型文法如下：S ABA aTT 0T1|01B bDD dD|d问答第 12 题（6 分）试对 if (ad) then s:=e else s:=f 的四元式序列给出第四区段应回填的指令地址，并指出真假出口链和链头及回填的次序。(1) if ad goto(4) goto应回填的值( )( )( )( )回填的次序( )( )( )( )真链头 E.true=真出口链( )假链头 E.false=(5) s:=e(6) goto(7) s:=f(8) .解：(1) if ad goto(4) goto(5) s:=e(6) goto(7) s:=f(8) .( 7 )( 4 )( 5 )( 2 )( 7 )( 3 )( 8 )( 5 )真出口链( 3 )假链头 E.false= 4假出口链( 4,2 )
