资源描述：
《杭电编译原理试卷一及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、试卷（一）一、选择1.一个正规语言只能对应(B)？A一个正规文法；B一个最小有限状态自动机；2.文法G[A]：A→εA→aBB→AbB→a是(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目标代码CODE B符号表TABLE
2、C数据栈SD关键字表WORD2.PL/0语言编译时产生或使用的数据对象有( ABD )：A目标代码CODEB符号表TABLEC数据栈SD关键字表WORD三、问答题问答第1题(5分)将文法G[S]改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。 G[S]：S→bSAe
3、bA A→Ab
4、d S→bB B→SAe
5、A A→dA' A'→bA'
6、ε问答第2题9(10分)判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。 S→aH H→aMd
7、d M→Ab
8、
9、ε A→aM
10、e首先计算文法的FIRST集和FOLLOW集如下表非终结符FIRST集FOLLOW集S{a}.........{#}...H{a，d}.....{#}...M{a，e，ε}{d，b}A{a，e}.....{b}....由于select（H→aMd）∩select（H→d）={a}∩{d}= select（M→Ab）∩select（M→ε）={a，e}∩{d，b}= select（A→aM）∩select（A→e）={a}∩{e}= 所以该文法是LL(1)文法，LL(1)分析表如下表。L
11、L(1)分析表 adbe#S→aH. H→aMd→d. M→Ab.→ε→ε→Ab A→aM. →e. 问答第3题 给出与正规式R＝（ab）*（a
12、b*）ba等价的NFA。问答第4题将下图的NFA确定化为DFA。用子集法对所给图的确定化IIaIb状态{X,1,2}{1,2}..{1,2,3}{1,2,Y}{1,2}..{1,2}..{1,2,Y}{1,2}..{1,2,3}{1,2,3}{1,2,3}{1,2,3}X1239确定化后如下图问答第5题(7分)（1）给出下列PL/0示意程序中当程序执行到
13、X过程调用Z过程后（即执行Z过程体时）的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容。（2）说明Display表和DL（老SP）,RA,TOP及全局Display的作用。PL/0示意程序为： consta=80; varb,c; procedureX; vard; procedureZ; vare,g; begin(*Z*) c:=b*a； end；(*Z*) begin(*X*) callZ; end；(*X*) procedu
14、reY; varf; begin(*Y*) callX; end；(*y*) begin(*main*) callY; end.(*main*)解：（1）当程序执行到X过程调用Z过程后（即执行Z过程体时）的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容如下图。9解：（2）Display表和DL（老SP）,RA,TOP及全局Display的作用分别说明如下：·Display表的作用是对嵌套过程语言实现对非局部变量的引用而设置的，它依次存放着包围它的外过程
15、的最新活动记录的基地址SP值，由于，嵌套层次为i+1过程中的非局部变量可能在i，i-1，…，0层，所以，对非局部变量的引用是通过它的display表元素d[i]，d[i-1]，…，d[0]而获得包围它的外过程的最新活动记录的基地址SP值，再加上变量在该过程（第i层）的偏移量。如若非局部变量a是在第i层，那么引用a时，首先从当前栈顶过程的display表中元素d[i]中取出存放的第i层最新活动记录基地址SP值，然后加上a所在过程（第i层）的偏移量，就得到a的存放地址。 如Z过程的display表内容为：d（2）Z
16、的SPd（1）X的SPd（0）Main的SP·DL（老SP）：也称动态链或控制链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。·RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。·TOP：栈顶指针TOP指出了当前栈中最新分配的单元。·全局D
