资源描述：
《编译原理答案41756》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、试卷(一)参考答案：一、选择题选择第1题：B选择第2题：B选择第3题：A选择第4题：A二、多项选择题:多项选择第1题：AC多项选择第2题：ABD 三、问答题:问答第1题 文法G[S]改写为等价的不含左递归和左公共因子的G'[S]为： S→bB B→SAe
2、A A→dA' A'→bA'
3、ε问答第2题 首先计算文法的FIRST集和FOLLOW集如下表非终结符FIRST集FOLLOW集S{a}.........{#}...H{a ，d}.....{#}...M{a ，e ，ε}{d ，b}
4、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)分析表如下表。 LL(1)分析表 adbe#S→aH. H→aMd→d. M→Ab.→ε→ε→Ab A→aM. →e. 问答第3题
5、 与正规式R＝（ab）*（a
6、b*）ba等价的NFA如下图：问答第4题 用子集法确定化如下表 用子集法对所给图的确定化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}X123确定化后如下图问答第5题解：（1）当程序执行到X过程调用Z过程后（即执行Z过程体时）的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容如
7、下图。解：（2）Display表和DL（老SP）,RA,TOP及全局Display的作用分别说明如下： ·Display表的作用是对嵌套过程语言实现对非局部变量的引用而设置的，它依次存放着包围它的外过程的最新活动记录的基地址SP值，由于，嵌套层次为i+1过程中的非局部变量可能在i，i-1，…，0层，所以，对非局部变量的引用是通过它的display表元素d[i]，d[i-1]，…，d[0]而获得包围它的外过程的最新活动记录的基地址SP值，再加上变量在该过程（第i层）的偏移量。如若非局部变量a是在第i
8、层，那么引用a时，首先从当前栈顶过程的display表中元素d[i]中取出存放的第i层最新活动记录基地址SP值，然后加上a所在过程（第i层）的偏移量，就得到a的存放地址。 如Z过程的display表内容为：d（2）Z的SPd（1）X的SPd（0）Main的SP·DL（老SP）：也称动态链或控制链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。 ·RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行
9、结束后返回调用过程时的下一条指令继续执行。 ·TOP：栈顶指针TOP指出了当前栈中最新分配的单元。 ·全局Display是存放本过程display表的起始地址，其作用是把display地址作为连接数据之一，如过程P1调用过程P2时，这时先从P1的全局Display找到P1的display表起始地址，然后从P1的display表中自底向上地抄录I2个单元（I2为P2的层数）再添上进入P2后新建立的P2的SP值，就构成了P2的display表。问答第6题解：PL/0示意程序编译到Y过程体时TABLE
10、表的内容如下表。 TABLE表的内容namekindlevelvaladrsizemainabcXYfprocedureconstantvariablevariableprocedureprocedurevariable..00001.800.dxdx+1过程X的入口过程Y的入口dx5...44由于Y和X是并列过程，当编译到Y过程时X过程体已经编译结束，X所定义的标识符不会再被使用，所以X定义的标识符d、Z及Z定义的e、g都被Y过程定义的标识符
11、覆盖。问答第7题拓广文法G'，增加产生式S'→T 在项目集I0中：有移进项目T→·aBd和归约项目T→· 存在移进-归约冲突，所以G不是LR(0)文法。 若产生式排序为： (0)S'→T(1)T→aBd(2)T→ε (3)B→Tb (4)B→εG'的LR(0)项目集族及识别活前缀的DFA如下图所示： 识别G′活前缀的DFA：由产生式知：Follow(T)={#,b} Follow(B)={d}在I0中： Follow(T)∩{a}={#，b}∩{a}= 在I2中
