DOC《编译原理试卷一》

编译原理试卷一 窗体顶端

一、 选择 1.

一个正规语言只能对应()? A 一个正规文法;

B 一个最小有限状态自动机;

2.文法G[A]:A→ε A→aB B→Ab B→a是( ): A 正规文法 B 二型文法 3.下面说法正确的是( ): A 一个SLR(1)文法一定也是LALR(1)文法 B 一个LR(1)文法一定也是LALR(1)文法 4.一个上下文无关文法消除了左递归,提取了左公共因子后是满足LL(1)文法的( ): A 必要条件 B 充分必要条件 窗体底端 窗体顶端

二、多项选择 1.PL/0语言的目标程序解释执行时用到的数据对象有( ): A 目标代码CODE B 符号表TABLE C 数据栈S D 关键字表WORD 2.PL/0语言编译时产生或使用的数据对象有( ): A 目标代码CODE B 符号表TABLE C 数据栈S D 关键字表WORD 窗体底端 窗体顶端

三、问答题 问答第1题(5分)将文法G[S] 改写为等价的G′[S],使G′[S]不含左递归和左公共因子. G[S]: S→bSAe | bA A→Ab | d 问答第2题(10分) 判断下面文法是否为LL(1)文法,若是,请构造相应的LL(1)分析表. S→aH H→aMd | d M→Ab | ε A→aM | e 问答第3题 给出与正规式R=(ab)*(a|b*)ba等价的NFA. 问答第4题 将下图的NFA确定化为DFA. 问答第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 *) 问答第6题(5分)给出问答第5题PL/0示意程序编译到Y过程体时TABLE表的内容. 问答第7题(10分)某语言的拓广文法G′为:(0) S′→T (1) T →aBd|ε (2) B →Tb|ε 证明G不是LR(0)文法而是SLR(1)文法,请给出SLR(1)分析表. 问答第8题(5分)给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目. G[S]为: S →BD|D B →aD|b D →B I0: 问答第9题(5分)文法G[M]及其LR分析表如下,请给出对串dbba#的分析过程. G[M]: 1) M →VbA 2) V →d 3) V →ε 4) A →a 5) A →Aba 6) A →ε name ACTION GOTO b d a # M A V

0 r3 S3 ? ?

1 ?

2 1 ? ? ? acc ? ? ?

2 S4 ? ? ? ? ? ?

3 r2 ? ? ? ? ? ?

4 r6 ? S5 r6 ?

6 ?

5 r4 ? ? r4 ? ? ?

6 S7 ? ? r1 ? ? ?

7 ? ? S8 ? ? ? ?

8 r5 ? ? r5 ? ? ? 问答第10题(5分)文法G[E]为: E→E+T|T T→T*F|F F→(E)|i 试给出句型(E+F)*i的短语,简单(直接)短语,句柄和最左素短语. 问答第11题(6分)按指定类型给出下列语言的文法. (1)L1={ anbm c| n≥0,m>

0 } 用正规文法. (2) L2={ a0n1n bdm | n>

0,m >

0} 用二型文法. 问答第12题(6分)试对 if (ad) then s:=e else s:=f 的四元式序列给出第四区段应回填的指令地址,并指出真假出口链和链头及回填的次序. ? ? 应回填的值 回填的次序 ? (1) if ad goto ( ) ( ) ? (4) goto ( ) ( ) 假链头 E.false= (5) s:=e ? ? 假出口链( ) (6) goto ( ) ( ) ? (7) s:=f ? ? ? (8) ... ? ? ? 窗体底端 参考答案

一、 选择题答案 选择第1题B选择第2题B选择第3题A选择第4题A

二、多项选择题答案 多项选择第1题AC 多项选择第2题ABD

二、问答题答案 问答第1题 文法G[S] 改写为等价的不含左递归和左公共因子的G'

[S]为: S→bB B→SAe | A A→d A'

A'

→bA'

| ε 问答第2题 首先计算文法的 FIRST集和FOLLOW集如下表. 文法的 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)分析表如下表. LL(1)分析表 ? a d b e # S →aH. ? ? ? ? H →aMd →d. ? ? ? M →Ab. →ε →ε →Ab ? A →aM. ? ? →e. ? 问答第3题 与正规式R=(ab)*(a|b*)ba 等价的NFA如下图 问答第4题 用子集法确定化如下表 用子集法对所给图的确定化 I Ia Ib 状态 {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} X

1 2

3 确定化后如下图 问答第5题解:(1)当程序执行到X过程调用Z过程后(即执行Z过程 体时)的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容如下图. 当程序执行到Z过程时栈式存储分配布局 和栈中过程最新活动记录的内容 解:(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层,那么引用a时,首先从当前栈顶过程的display表中元素d[i]中取出存放的第i层最新活动记录基地址SP值,然后加上a所在过程(第i层)的偏移量,就得到a的存放地址. 如Z过程的display表内容为: d(2) Z的SP d(1) X的SP d(0) Main的SP ・DL(老SP): 也称动态链或控制链,指向调用该过程前正在运行过程的数据段基地址,用以过程执行结束释放数据空间时,恢复调用该过程前运行栈的状态. ・RA:返回地址,记录调用该过程时目标程序的断点,即调用过程指令的下一条指令的地址,用以过程执行结束后返回调用过程时的下一条指令继续执行. ・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表的内容如下表. TABLE表的内容 name kind level val adr size main a b c X Y f procedure constant variable variable procedure procedure variable . .

0 0

0 0

1 .

80 0 . dx dx+........