编译作业答案.docx

7-2给定文法G:
S?Aa|Ab|c
A?Ad|Se|f
请消除文法的左递归，并提取公共左因子。
解：
消除文法G的②产生式直接左递归。
2SeA'|fA'③
A'tdA'|?④
消除间接左递归：按排序(按算法i=2,j=,A)
SfA・S
—-AS
—-SA
I6=GO(I1,S)
A”a-
A
A—SA・
—S・A
S—AS・
I3=GO(Io,b)
I7=GO(I2,S)
S—A・S
SA
AS
GO(I1,b)=I3
GO(I2,a)=I4GO(I1,a)=I4
GO(I2,A)=I2GO(I2,b)=I3
A—-SA
Af-a
FOLLOW(S)=(a,b,#}FOLLOW(A)=(a,b)
••-状态5在输入a时有S和r3的移进归约矛盾。
状态5在输入b时有S3和r3的移进归约矛盾。
状态7在输入a时有S4和ri的移进归约矛盾。
状态7在输入b时有S3和ri的移进归约矛盾。
文法G既不是LR(0)文法，也不是SLR(1)文法
7
设有文法G
S?AB
B?cBd|cd
A?aAb|ab
SLR(1)分析表
它是否为SLR(1)文法？若是，请构造相应的解：
'—SFOLLOW(S)=($)
—ABFOLLOW(A)=(b,c)
—cBdFOLLOW(B)=(d,$)
fcd
、aAb
、ab
Io=closure(S'、
S)
I0：S'r•S
I4=GO(I2,B)
SfAB-
I9=GO(I5,d)
B、cd-
I5=GO(I2,c)
Ii0=GO(l6,b)
-Bd
A—aAb-
Ii=GO(Io,S)
S'fS・
cBd
cBd
Iii=GO(I8,d)
B—cBd-
I2=GO(Io,A)
I6=GO(I3,A)
GO(I3,a)=I
I3=GO(I0,a)
-Ab
I7=GO(I3,b)fab-
I8=GO(I5,B)
aAb
—cB-
ab
GO(I
A—-
上述状态集没有移进一归约冲突，(
abcd$
SAB
0
&
12
1
acc
2
S5
4
3
&S7
6
4
r1
5
S5S9
8
6
S10
7
「5r5
8
S11
9
「3「3
10
「4r4
11
「2「2
5
5,c)=I
a)是SLR文法，分析表如下:
8-9
设有文法
P?P(F)|F
F?abFda|a
(1)试求每个非终结符的
FIRSTVT集和
LASTVTSo
(2)试构造文法G的优先关系表。
解:
FIRSTVT(P)={a,(}LASTVT(P)=(a,)}
FIRSTVT(F)={a}LASTVT(F)={a}
优先关系表：
4
对下列翻译方案：
S?PS{print"1”}
S?PQ{print"2”}
P?a{print"3”}
Q?bR{print"4”}
Q?dQ{print"5”}
R?c{print"6”}
当输入串为“aaadb”时，翻译结果是什么？
解：
结果为。
9-5
试写出语句
ifC<DthenwhileA>Bdox:=y+2*z解：
ElC<D
W>while
巳tA>B
ElE*E
EtE+E
2i:=E2
StA
StWS
StifEithenSi
9-6
9-7试写出语句
fori:=1toNdoSi
其语义为
i:=1;
again:ifi?Nthenbegin
S1；
i:=i+1;
gotoagain
end
原文法
S”fori:=1toNdoS
改写为
F”fori:=1toNdo
的翻译过程。
E1-F=101
W-code=102
巳-F=103
E1-VAL=T
巳-VAL=T
A・chain=0
S1-chain=0S1-chain=103
S-chain=101
(v,C,D,102)
(j,-,-,103)
(>,A,B,104)
(j,-,-,0)
(*,2,
(+,y,T1,T2)
(:=,T2,-,x)
(107)(j,-,-,102)
的语义子程序。