编译原理复习.docx
- 文档编号:18313041
- 上传时间:2023-08-15
- 格式:DOCX
- 页数:21
- 大小:151.64KB
编译原理复习.docx
《编译原理复习.docx》由会员分享,可在线阅读,更多相关《编译原理复习.docx(21页珍藏版)》请在冰点文库上搜索。
编译原理复习
6.判断文法G[S]:
S→BA
A→BS|d
B→aA|bS|c
是否为LL
(1)文法.
解:
对于该文法求其FIRST集如下:
FIRST(S)={a,b,c};FIRST(A)={a,b,c,d};FIRST(B)={a,b,c}。
求其FOLLOW集如下:
FOLLOW(S)={a,b,c,d,#};FOLLOW(A)={a,b,c,d,#};FOLLOW(B)={a,b,c,d,#}。
由A→BS|d得:
FIRST(BS)∩FIRST(‘d’)={a,b,c}∩{d}=Φ
由B→aA|bS|c得
FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩{b}∩{c}=Φ
由于文法G[S]不存在形如β→ε的产生式,故无需求解形如FIRST(α)∩FOLLOW(A)的值,也即文法G[S]是一个LL
(1)文法。
8.已知文法G[A]:
A→aABl|a
B→Bb|d
试给出与G[A]等价的LL
(1)文法G[A′];
解:
G[A′]:
A→aA′
A′→ABl|ε
B→dB′
B′→bB′|ε
9.将下面的语句翻译成四元式序列:
if(x>y)m=1;
elsem=0;
解:
1(j>,x,y,3)
2(j,_,_,5)
3(=,1,_,m)
4(j,_,_,6)
5(=,0,_,m)
6:
12.试构造下述文法的SLR
(1)分析表。
(13分)
G[A]:
A→aABl|a
B→Bb|d
解:
拓广文法
(0)S→A
(1)A→aABl
(2)A→a
(3)B→Bb
(4)B→d
First(A)={a}follow(A)={#,d}
First(B)={d}follow(B)={l}
SLR
(1)分析表如下:
a
b
d
l
#
A
B
0
S2
1
1
ACC
2
S2
R2
R2
3
3
S4
5
4
R4
5
S7
S6
6
R1
R1
7
R3
13.将下面的语句翻译成四元式序列:
(7分)
if(x>y)m=1;
elsem=x+y;
解:
1(j>,x,y,3)
2(j,_,_,5)
3(=,1,_,m)
4(j,_,_,7)
5(+,x,y,T1)
6(=,T1,_,m)
7:
14.试构造下述文法的LL
(1)分析表。
(15分)
G[S]:
S→(L)|a
L→L,S|S
解:
消除左递归:
G(S):
Sà(L)|a
LàSL’
L’à,SL’|ε
构造FIRST集,如下:
(1)FIRST(S)={(,a}
(2)FIRST(L)={(,a}
(3)FIRST(L’)={,,ε}
构造FOLLOW集如下:
(1)FOLLOW(S)={#,,,)}
(2)FOLLOW(L)={)}
(3)FOLLOW(L’)={)}
LL
(1)分析表
(
)
a
#
S
Sà(L)
Sàa
L
LàSL’
LàSL’
L’
L’àε
L’à,SL’
18.将下面的语句翻译成四元式序列:
while(a
if(c>d)x=y+z
解:
100(j<,a,b,102)
101(j,_,_,107)
102(j>,c,d,104)
103(j,_,_,106)
104(+,y,z,t)
105(=,t,_,x)
106(j,_,_,100)
107:
19.构造正规表达式a(aa)*bb(bb)*a的最小化的确定有限自动机M′。
解:
先画出正规式相应的NFAM状态图,如下图所示。
用子集法构造状态转换矩阵,如下表所示。
I
Ia
Ib
{x}
{1}
-
{1}
{2}
{3}
{2}
{1}
-
{3}
-
{4}
{4}
{Y}
{5}
{5}
-
{4}
{Y}
-
-
将状态分为终态集{Y}和非终态集{X,1,2,3,4,5}
因为{X,1,2,3,4,5}a={1,2,1,_,Y,_}
所以非终态集分为{X,1,2},{3,5},{4}
因为{X,1,2}b={_,3,_},所以分为
最后得到集合{X,2},{1},{3,5},{4},{Y}重新命名为1,2,3,4,5得到最小化的DFAM′状态转换矩阵和状态转换图如下图所示。
I
Ia
Ib
1
2
_
2
1
3
3
-
4
4
5
3
5
-
_
20.试构造下述文法的SLR
(1)分析表。
G[A]:
A→aABl|a
B→Bb|d
解:
拓广文法
(0)S→A
(1)A→aABl
(2)A→a
(3)B→Bb
(4)B→d
First(A)={a}follow(A)={#,d}
First(B)={d}follow(B)={l}
SLR
(1)分析表如下:
ACTION
GOTO
a
b
d
l
#
A
B
0
S2
1
1
ACC
2
S2
R2
R2
3
3
S4
5
4
R4
5
S7
S6
6
R1
R1
7
R3
22.对于文法G(S):
S→(L)|aS|a
L→L,S|S
(1)画出句型(S,(a))的语法树。
(2)写出上述句型的所有短语、直接短语和句柄。
解:
(1)句型(S,(a))的语法树如下图所示:
(2)从语法树中可以找到(3分)短语:
a;(a);S;S,(a);(S,(a))
直接短语:
a;S
句柄:
S
24.分别给出表达式–(a*(b-c))+d的逆波兰表示和四元式表示。
解:
(1)逆波兰式:
abc-*@d+其中使用@代表一目减运算
(2)四元式:
(-,b,c,T1)
(*,a,T1,T2)
(@,T2,_,T3)
(+,T3,d,T4)
25.把下列语句翻译为四元式序列:
while(A>B)
if(C>D)
X=Y*Z
else
X=Y+Z
解:
(1)(j>,A,B,3)
(2)(j,_,_,11)
(3)(j>,C,D,5)
(4)(j,_,_,8)
(5)(*,Y,Z,T1)
(6)(=,T1,_,X)
(7)(j,_,_,1)
(8)(+,Y,Z,T2)
(9)(=,T2,_,X)
(10)(j,_,_,1)
(11)
23.构造一文法,使其描述的语言L={ω|ω∈(a,b)*,且ω中含有相同个数的a和b}。
解:
S→ε|aA|bB
A→b|bS|aAA
B→a|aS|bBB
27.已知文法G(S):
S→S*aP|aP|*aP
P→+aP|+a
(1)将文法G(S)改写为LL
(1)文法G’(S);
(2)写出文法G’(S)的预测分析表。
解:
(1)消除左递归,文法变为:
S→aPS’|*aPS’
S’→*aPS’|ε
P→+aP|+a
提取公共左因子,文法变为G’(S):
S→aPS’|*aPS’
S’→*aPS’|ε
P→+aP’
P’→P|ε
(2)计算每个非终结符的FIRST集和FOLLOW集:
FIRST(S)={a,*}FOLLOW(S)={#}
FIRST(S’)={*,ε}FOLLOW(S’)={#}
FIRST(P)={+}FOLLOW(P)={*,#}
FIRST(P’)={+,ε}FOLLOW(P’)={*,#}
构造该文法的预测分析表如下:
(5分)
*
+
a
#
S
S→*aPS’
S→aPS’
S’
S’→*aP
S’→ε
P
P→+aP’
P’
P’→ε
P’→P
P’→ε
28.已知文法G(S):
S→aS|bS|a
(1)构造识别该文法所产生的活前缀的DFA;
(2)判断该文法是LR(0)还是SLR
(1),并构造所属文法的LR分析表。
解:
(1)将文法G(S)拓广为G’(S’):
(0)S’→S
(1)S→aS
(2)S→bS
(3)S→a
识别该文法所产生的活前缀的DFA:
(2)在状态I2存在“移近-归约”冲突,因此该文法不是LR(0)文法。
计算S的FOLLOW集合:
FOLLOW(S)={#}
I2中的冲突用FOLLOW集合可以解决,所以该文法是SLR
(1)文法。
构造SLR
(1)分析表如下:
状态
ACTION
GOTO
a
b
#
S
0
s2
s3
1
1
acc
2
s2
s3
r3
4
3
s2
s3
5
4
r1
5
r2
30.对正规式(a|b)*abb构造其等价的NFA。
【解】
32.把算术表达式-(a+b)´(c+d)+(e+f)翻译成等价的四元式序列(序号从0开始)。
【解】
0(+,a,b,T1)
1(uminus,T1,-,T2)
2(+,c,d,T3)
3(*,T2,T3,T4)
4(+,e,f,T5)
5(+,T4,T5,T6)
33.设有文法G[S]:
S→a|(T)|
T→T,S|S
试给出句子(a,a,a)的最左推导。
【解】
(1)(a,a,a)的最左推导
S=>(T)=>(T,S)=>(T,S,S)=>(S,S,S)=>(a,S,S)=>(a,a,S)=>(a,a,a)
34.已知文法G:
S→(L|aL→S,L|)
判断是不是LL
(1)文法,如果是请构造文法G的预测分析表,如果不是请说明理由。
【解】
1)求各非终结符的FISRT集和FOLLOW集:
={(,a)
FIRST(L)={a}ÈFIRST(S)={(,),a}
FOLLOW(S)={,#}
FOLLOW(L)=FOLLOW(S)={,#}
FIRST((L)∩{a}=Φ
FIRST(S,L)∩{)}=Φ
所以是LL
(1)文法
2)预测分析表:
(
a
}
#
S
S→(L
S→a
L
L→S,L
L→S,L
L→)
35.文法
S®Aa|bAc|dc|bda
A®d
构造识别活前缀的DFA。
请根据这个DFA来判断该文法是不是SLR
(1)文法并说明理由。
【解】
Follow(S)={#}
Follow(A)={a,c}
I4存在冲突且Follow(A)∩{c}={c}
I7存在冲突且Follow(A)∩{a}={a}
所以不是SLR
(1)文法
40.把下列语句翻译为四元式序列(四元式序号从1开始):
while(A>B)
if(C>D)
X=Y*Z
else
X=Y+Z
【解】
(1)(j>,A,B,3)
(2)(j,_,_,11)
(3)(j>,C,D,5)
(4)(j,_,_,8)
(5)(*,Y,Z,T1)
(6)(=,T1,_,X)
(7)(j,_,_,1)
(8)(+,Y,Z,T2)
(9)(=,T2,_,X)
(10)(j,_,_,1)
(11)
41.构造下面文法的LL
(1)分析表。
G[D]:
DTL
Tint|real
LidR
R,idR|
【解】FIRST(T)={intreal}FOLLOW(T)={id}
FIRST(L)={id}FOLLOW(L)={#}
FIRST(R)={,}FOLLOW(R)={#}
FIRST(D)={intreal}FOLLOW(D)={#}
因为FIRST(int)∩FIRST(real)=Φ
FIRST(,idR)∩FOLLOW(R)=Φ
所以是LL
(1)文法,LL
(1)分析表如下:
int
real
id
#
D
DTL
DTL
T
Tint
Treal
L
LidR
R
R,idR
R
42.给定文法S→aS|bS|a,下面是拓广文法和识别该文法所产生的活前缀的DFA。
判断该文法是否是SLR
(1)文法:
如果是构造其SLR
(1)分析表,如果不是请说明理由。
(1)将文法G(S)拓广为G(S’):
(0)S’→S
(1)S→aS
(2)S→bS
(3)S→a
(2)识别该文法所产生的活前缀的DFA如图1所示。
【解】注意到状态I1存在“移进-归纳”冲突,计算S的FOLLOW集合:
FOLLOW(S)={#}
{a}∩{b}∩FOLLOW(R)=Φ
可以采用SLR冲突消解法,得到如下的SLR分析表。
从分析表可以看出,表中没有冲突项,所以该文法是SLR
(1)文法。
表1SLR分析表
ACTION
GOTO
状态
a
b
#
S
0
S1
S2
3
1
S1
S2
r3
4
2
S1
S2
5
3
acc
4
r1
5
r2
45.现有文法G[S]
S→a|ε|(T)
T→T,S|S
请给出句子(a,(a,a))的最左、最右推导,并指出最右推导中每一个句型的句柄。
答:
最左推导:
S=〉(T)=〉(T,S)=〉(S,S)=〉(a,S)=〉(a,(T))=〉(a,(T,S))=〉(a,(S,S))=〉(a,(a,S))=〉(a,(a,a))
最右推导:
S=〉(T)=〉(T,S)=〉(T,(T))=〉(T,(T,S))=〉(T,(T,a))=〉(T,(S,a))=〉(T,(a,a))=〉(S,(a,a))=〉(a,(a,a))
句型的句柄是为加下划线的部分
60.设有文法G[S]:
S→aAcB|Bd
A→AaB|c
B→bScA|b
该文法句型aAcbBdcc的句柄是_______Bd_____________。
61.2.已知文法G[S]如下:
构造该文法的LR(0)分析表。
G[S]:
S→BB
B→aB|b
解:
拓广文法:
(1分)
(0)S→S
(1)S→BB
(2)B→aB
(3)B→b
识别活前缀的DFA如下:
LR(0)分析表如下:
状态
Action
Goto
a
b
#
S
B
0
S3
S4
1
2
1
acc
2
S3
S4
5
3
S3
S4
6
4
R3
R3
R3
5
R1
R1
R1
6
R2
R2
R2
53.假设第一个四元式的序号是100,写出布尔表达式ae的四元式序列。
100(j<,a,b,106)
101(j,_,_,102)
102(jnz,c,_,104)
103(j,_,_,q)
104(j>,d,e,106)
105(j,_,_,q)
T:
106
……
F:
q
…….
50.构造文法S→AaAb|BbBaA→εB→ε,的预测分析表。
答:
first(S)={a,b},First(AaAb)={a},First(BbBa)={b}
Follow(A)={a,b}
Follow(B)={a,b}
a
b
$
S
S→AaAb
S→BbBa
A
A→ε
A→ε
B
B→ε
B→ε
58.写出赋值语句X=-(a+b)/(c-d)-(a+b*c)的逆波兰表示。
Xab+-cd-/abc*+-=
55.对于下列文法
G[S]:
S→Sb|bA
A→aA|a
(1)构造一个与G等价的LL
(1)文法G′。
(2)对于文法G′,构造相应的LL
(1)分析表。
解:
(1)(5分)G′:
S→bAS′
S′→bS′|ε
A→aA′
A′→A|ε
(2)(1分)FIRST(S)={b}
FIRST(S′)={b,ε}
FIRST(A)={a}
FIRST(A′)={a,ε}
FOLLOW(S)={#}
FOLLOW(S′)={#}
FOLLOW(A)={b,#}
FOLLOW(A′)=(b,#)
LL
(1)分析表:
a
b
#
S
S→bAS′
S′
S′→bS′
S′→ε
A
A→aA′
A′
A′→A
A′→ε
A′→ε
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 复习