(5) goto ( 1 ) ( 4 ) 假出口链( 7,5 )
(6) if b=d goto ( 8 ) ( 5 )
(7) goto ( 1 ) ( 3 )
问答第2题
(10分)某语言的拓广文法G′为:
(0) S′→S
(1) S → Db|B
(2) D → d|ε
(3) B → Ba|ε
证明G不是LR(0)文法而是SLR(1)文法,请给出SLR(1)分析表。解:
拓广文法G',增加产生式S'→S
在项目集I0中:
有移进项目D →·d
归约项目D →·和B →·
存在移进-归约和归约-归约冲突,所以G不是LR(0)文法。
若产生式排序为:
(0) S'→S
(1) S → Db
(2) S → B
(3) D → d
(4) D →ε
(5) B → Ba
(6) B →ε
G′的LR(0)项目集族及识别活前缀的DFA如下图:
识别G′活前缀的DFA
由产生式知:
Follow(S)={#}
Follow(D)= {b}
Follow(B)= {a ,#}
在I0中:
Follow(D) ∩{d}={ b} ∩{d}=
Follow(B) ∩{d}= { a ,#} ∩{d}=
Follow(D) ∩ Follow(B)= {b}∩{a ,#} =
在I3中:
Follow(S) ∩{a}={#}∩{a}=
所以在I0,I3中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR(1)文法, 构造的SLR(1)分析表如下表。
SLR(1)分析表
问答第3题
(5分)给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。
G[S]为:S →S;V|V
V →VaA|A
A →b(S)| ε
I0:
解:
I0:
问答第4题
(5分)文法G[M]及其LR分析表如下,请给出对串dada#的分析过程。
G[M]: 1) S →VdB2) V →e
3) V →ε 4) B →a
5) B →Bda 6) B →ε
解:对串dada#的分析过程如下表
对输入串dada#的分析过程
步骤状态
栈
文法符
号栈
剩余输入
符号
动作
1 2 3 4 5 6 0
02
024
0245
0246
02467
#
#V
#Vd
#Vda
#VdB
#VdBd
dada#
dada#
ada#
da#
da#
a#
用V →ε归约
移进
移进
用B →a归约
移进
移进
7 8 9 02467
8
0246
01
#VdBda
#VdB
#S
#
#
#
用B →Bda归约
用S →VdB归约
接受
问答第5题
(7分)(1) 给出下列PL/0示意程序中当程序执行到D过程调用A过程后(即执行A过程体时)的栈式存储分配布局和用Display显示表时A过程最新活动记录的内容。
(2) 说明Display表和全局Display的作用。
PL/0示意程序为:
var x;
procedure A;
var d;
begin (* A *)
write(x);
end (* A *);
procedure B;
const n=7;
var e,g;
procedure D;
var j,k;
begin (* D *)
read(j,k);
x:=x+j*n;
call A;
end ;(* D *)
begin (* B *)
call D;
end ;(* B *)
begin (* main *)
read(x);
call B;
end. (* main *)
解:(1)PL/0示意程序中当程序执行到D过程调用A过程后(即执行A过程体时)的栈式存储分配布局和用Display显示表时栈中过程最新活动记录的内容如下图。
栈式存储分配布局和栈中过程最新活动记录的内容