编译原理大题.docx
- 文档编号:17980094
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:36
- 大小:265.48KB
编译原理大题.docx
《编译原理大题.docx》由会员分享,可在线阅读,更多相关《编译原理大题.docx(36页珍藏版)》请在冰点文库上搜索。
编译原理大题
五、语法分析——自底向上分析法
已知文法G:
EE+T
ET
TT*F
TF
F(E)
Fi
(1)求文法G中每个非终结符的First集和Follow集。
(2)构造文法G的SLR
(1)预测分析表。
(20分)
首先构造增广文法:
SE
EE+T
ET
TT*F
TF
F(E)
Fi
First(S)=First(E)=First(T)=First(F)={(,I)
Follow(S)={#}Follow(E)={+,#,}}
Follow(T)={+,},#,*}Follow(F)={+,},#,*}
状态ActionGoto
i+*()#ETF
0S5S4123
1S6Acc
2r2S7r2r2
3r4r4r4r4
4S5S4823
5r6r6
6S593
7S510
8S6S11
9r1S7r1r1
10r3r3r3r3
11r5r5r5r5
注:
识别可归前缀的DFA共12项。
词法分析——确定性有穷自动机
为以下字符集编写正规表达式,并构造与之等价的最简DFA(写出详细的具体过程):
在字母表{a,b}上的包含偶数个a且含有任意数目b的所有字符串。
(15分)
(b*ab*ab*)*
bab
1
a
状态ActionGOTO
abdef$SRT
0S31
1acc
2r2S3r2r25
3S6S42
4r4r4r4r4
5S109
67
7S8
8r3r3r3r3
9r1r1r1
10r6S6S4r6r611
11S12
12r5r5r5
五、语法分析——自底向上分析法
已知文法G:
S’S
SbRST
SbR
RdSa
Re
TfRa
Tf
(1)求文法G中每个非终结符的First集和Follow集。
(2)构造文法G的SLR
(1)预测分析表。
(20分)
frist(s’)={b}follow(s’)={$}
frist(s)={b}follow(s)={f,a,$}
frist(R)={d,e}follow(R)={a,b,f,$}
frist(T)={t}follow(T)={a,f,#}
五、对下面的文法(15分)
S->UTa|Tb
T->S|Sc|d
U->US|e
判断是否为LR(0),SLR
(1),说明理由,并构造相应的分析表。
(1)拓广文法:
(0)S’->S
(1)S->UTa
(2)S->Tb(3)T->S(4)T->Sc(5)T->d(6)U->US(7)U->e
(2)构造识别LR(0)项目的DFA如下:
因为I1、I8中存在冲突,所以该文法不是LR(0)文法。
因为FOLLOW(S)={#,c,a,b,d,e},FOLLOW(T)={a,b},FOLLOW(U)={d,e}
I1中FOLLOW(T)∩{c}=Ф
I8中FOLLOW(U)∩{c}=Ф,FOLLOW(T)∩{c}=Ф,
FOLLOW(T)∩FOLLOW(U)=Ф
I1、I8中冲突解决,所以该文法是SLR
(1)文法。
ACTION
GOTO
状态
a
b
c
d
e
#
S
T
U
0
S5
S4
1
3
2
1
r3
r3
S6
acc
2
S5
S4
8
7
2
3
S9
4
r7
r7
5
r5
r5
6
r4
r4
7
S10
S9
8
r3
r3
S6
r6
r6
9
r2
r2
r2
r2
r2
r2
10
r1
r1
r1
r1
r1
r1
五、考虑文法(15分)
SAS|b
ASA|a
(1)构造文法的LR(0)项目集规范族及相应的DFA。
(2)
(2)构造文法的SLR分析表。
(3)1)令拓广文法G’为
(4)(0)S’S
(1)SAS
(2)Sb(3)ASA(4)Aa
其LR(0)项目集规范族及识别该文法活前缀的DFA如下图所示:
FOLLOW(S)={#,a,b}FOLLOW(A)={a,b}
(2)显然,对所得的
请为以下字符集编写正规表达式,并构造与之等价的最简DFA(写出详细的具体过程):
在字母表{a,b}上的串,串中至少要包含两个连续的a或两个连续的b。
(15分)
正规表达式(a|b)*(aa|bb)(a|b)*
aa
baa,b
b
b
五、对下列文法:
(15分)
S→aD
D→STe|ε
T→bH|H
H→d|ε
(1)求各非终结符的First和Follow集合。
(2)判断下面文法是否为LL
(1)文法,若是,请构造相应的LL
(1)分析表。
首先计算文法的FIRST集和FOLLOW集如下表。
文法的FIRST集和FOLLOW集
非终结符
FIRST集
FOLLOW集
S
{a}.........
{#,b,d,e}.
D
{a,ε}....
{#,b,d,e}
T
{b,d,ε}
{e}.............
H
{d,ε}....
{e}.............
由于select(D→STe)∩select(D→ε)={a}∩{#,b,d,e}=
select(T→bH)∩select(T→H)={b}∩{e}=
select(H→d)∩select(H→ε)={d}∩{e}=
所以该文法是LL
(1)文法,LL
(1)分析表如下表。
LL
(1)分析表
a
e
b
d
#
S
→aD.
D
→STe
→ε
→ε
→ε
→ε
T
→H.
→bH
→H.
H
→ε
→d.
设文法G(S):
(15分)
SA
ABA|ε
BaB|b
(1)证明它是LR
(1)文法;
(2)构造它的LR
(1)分析表;(3)给出输入符号串abab的分析过程。
1)拓广文法G’:
(0)S'S
(1)SA
(2)ABA
(3)Aε(4)BaB(5)Bb
FIRST(A)={ε,a,b}
FIRST(B)={a,b}
构造的DFA如下:
由项目集规范族看出,不存在冲突动作。
∴该文法是LR
(1)文法。
(2)
LR
(1)分析表
状态
Action
Goto
a
B
#
S
A
B
0
S4
S5
r3
1
2
3
1
acc
2
r1
3
S4
S5
r3
6
3
4
S4
S5
7
5
r5
r5
r5
6
r2
7
r4
r4
r4
(3)输入串abab的分析过程为:
步骤
状态栈
符号栈
当前字符
剩余字符串
动作
(1)
0
#
a
bab#
移进
(2)
04
#a
b
ab#
移进
(3)
045
#ab
a
b#
归约Bb
(4)
047
#aB
a
b#
归约BaB
(5)
03
#B
a
b#
移进
(6)
034
#Ba
b
#
移进
(7)
0345
#Bab
#
归约Bb
(8)
0347
#BaB
#
归约BaB
(9)
033
#BB
#
归约Aε
(10)
0336
#BBA
#
归约ABA
(11)
036
#BA
#
归约ABA
(12)
02
#A
#
归约SA
(13)
01
#S
#
acc
构造正规式1(0|1)*101相应的DFA(15分)
先构造NFA
DFA:
五、判断下面文法是否为LL
(1)文法,若是,请构造相应的LL
(1)分析表。
(15分)
D→TL
T→int|real
L→idR
R→,idR|ε
FIRST(D)=FIRST(T)={int,real} FOLLOW(D)=FOLLOW(L)
={#}
FIRST(L)={id} FOLLOW(T)={id}
FIRST(R)={,,ε} FOLLOW(R)={#}
有了上面每个非终结符的FIRST集合,填分析表时要计算一个产生式右部α的FIRST(α)就不是件难事了。
填表时唯一要小心的时,ε是产生式R→ε右部的一个开始符号,而#在FOLLOW(R)中,所以R→ε填在输入符号#的栏目中。
为以下字符集编写正规表达式,并构造与之等价的最简DFA(写出详细的具体过程):
在字母表{0,1}上的串,串中至少要包含两个连续的0或两个连续的1。
(15分)
(0|1)*(00|11)(0|1)*
00
101,0
1
1
六、构造运行时环境
有如下一段C语言程序:
(计算两个非负整数的最大公约数)
#include
intx,y;
intgcd(intu,intv)
{if(v==0)returnu;
elsereturngcd(v,u%v)
}
main()
{scanf(“%d%d”,&x,&y);
printf(“%d\n”,gcd(x,y));
return0;
}
当输入x,y分别为20,10时,最后一次调用gcd()时的运行时环境。
(10分)
当输入20和10时,main就初始化调用gdc(20,10)。
这个调用导致了另一个递归调用gdc(10,0),它将返回值10。
运行时环境示意图如下:
构造一个DFA,它接受∑={0,1}上的所有满足下述条件的字符串,其条件是:
字符串中的每个0后面都有1直接跟在右边。
要求:
(1)写出正则表达式;
(2)由NFA构造DFA;
(3)DFA状态最小化(写出详细的具体过程)(15分)
正则表达式:
(1*011*)*
最简DFA:
1
0
0
0
1
1
1
、请构造与正则式R=(a|b)*a(a|b)等价的状态最少的DFA(写出详细的具体过程)(15分)
a
ba
a
ba
b
b
四、词法分析——构造确定性有穷自动机。
为以下字符集编写正规表达式,并构造其Thompson结构图以及与之等价的最简DFA(写出详细的具体过程):
在字母表{0,1}上的且不以0开头但以11结尾的所有字符串。
(15分)
正规表达式:
11|1(0|1)*11
最简DFA:
构造一个DFA,它接受∑={a,b}上的所有满足下述条件的字符串,其条件是:
字符串中的每个b后面都有a直接跟在右边。
要求:
(1)写出正则表达式;
(2)由NFA构造DFA;
(3)DFA状态最小化(写出详细的具体过程)(15分)
正则表达式:
(a*baa*)*
最简DFA:
a
b
b
b
a
a
a
把下图最小化:
(15分)
最小DFA:
请构造与正则式R=b*abb*(abb*)*等价的状态最少的DFA(写出详细的具体过程)(15分)
bb
ab
a
为以下字符集编写正规表达式,并构造其Thompson结构图以及与之等价的最简DFA(写出详细的具体过程):
在字母表{0,1}上的包含偶数个0且含有任意数目1的所有字符串。
(15分)
正规表达式:
(1*01*01*)*
最简DFA:
101
0
五、考虑以下的文法:
(15分)
(1)S→A
(2)S→B
(3)A→aAb
(4)A→c
(5)B→aBb
(6)B→d
试构造相应的LR(0)项目集规范族及相应的分析表。
解答:
五、某语言的拓广文法G′为:
(15分)
(0)S′→T
(1)T→aBd|ε
(2)B→Tb|ε
证明G不是LR(0)文法而是SLR
(1)文法,请给出SLR
(1)分析表。
拓广文法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中:
Follow(B)∩{a}={d}∩{a}=
Follow(T)∩{a}={#,b}∩{a}=
Follow(B)∩Follow(T)={d}∩{#,b}=
所以在I0,I2,中的移进-归约和归约-归约冲突可以由Follow集解决,所以G是SLR
(1)文法。
构造的SLR
(1)分析表如下表。
SLR
(1)分析表
name
ACTION
GOTO
a
b
d
#
T
B
0
S2
r2
r2
1
1
acc
2
S2
r2
r4
r2
4
3
3
S5
4
S6
5
r1
r1
6
r3
五、语法分析——自顶向下分析法(20分)
说明如下文法是否是LL
(1)文法,若不是,将其转换为LL
(1)文法。
最后给出该文法的LL
(1)分析表。
G[A]:
ABe
BBb|a
文法中有左递归,不是LL
(1)文法。
转换为G′:
ABe
BaB′
B′bB′|λ
Predict(ABe)={a}
Predict(BaB′)={a}
Predict(B′bB′)={b}
Predict(B′λ)={e}
LL
(1)分析表:
a
b
e
A
Be
B
aB′
B′
bB′
λ
五、已知文法G:
(15分)
SLaR|R
LbR|c
RL
1)判断该文法是否为LR
(1)文法。
2)若是则构造文法G的LR
(1)项目集规范族。
3)若是则构造文法G的LR
(1)预测分析表。
(15分)
因为状态机中没有冲突,所以是LR
(1)文法。
LR
(1)分析表如下:
(1)SLaR
(2)SR
(3)LbR
(4)Lc
(5)RL
a
b
c
#
S
L
R
1
S6
S4
2
5
3
2
Acc
3
R2
4
R4
R4
5
S7
R5
6
S6
S4
8
9
7
S12
S13
11
10
8
R5
R5
9
R3
R3
10
R1
11
R5
12
S12
S13
11
14
13
R4
14
R3
五、已知文法G:
(15分)
ETE’
E’+E|ε
TFT’
T’T|ε
FPF’
F’*F’|ε
P(E)|^|a|b
1)求文法G中每个非终结符的First集和Follow集。
2)证明该文法G是LL
(1)文法。
3)构造文法G的预测分析表。
(15分)
1)First(E)=First(T)=First(F)=First(P)+{(,^,a,b)
First(T’)={(,^,a,b,ε)
First(E’)={+,ε}
First(F’)={*,ε}
Follow(P)={(,^,a,b,#,),+}
Follow(F’)={(,^,a,b,#,),+}
Follow(F)={(,^,a,b,#,),+}
Follow(E)={#,}}
Follow(E’)={#,}}
Follow(T)={#,),+}
Follow(T’)={#,},+}
2)判定该文法是否是LL
(1)文法的充要条件是对于G的每个非终结符A的任何两个不同产生式A->α|β,有下述条件成立:
First(α)∩First(β)=Ф
若β=*>ε,则First(α)Follow(A)=Ф
显然,
(1)所求的First集合和Follow集合满足要求,因此该文法为LL
(1)文法。
+
*
(
)
a
b
^
#
E
E->TE’
E->TE’
E->TE’
E->TE’
E’
E’->+E
E’->ε
E’->ε
T
T->FT’
T->FT’
T->FT’
T->FT’
T’
T’->ε
T’->T
T’->ε
T’->T
T’->T
T’->T
T’->ε
F
F->PF’
F->PF’
F->PF’
F->PF’
F’
F’->ε
F’->*F’
F’->ε
F’->ε
F’->ε
F’->ε
F’->ε
F’->ε
P
P->(E)
P->a
P->b
P->^
五、语法分析——自顶向下分析法。
已知文法G:
ETE’
E’+E|ε
TFT’
T’T|ε
FPF’
F’*F’|ε
P(E)|^|a|b
(1)求文法G中每个非终结符的First集和Follow集。
(2)证明该文法G是LL
(1)文法。
(3)构造文法G的预测分析表。
(20分)
2)First(E)=First(T)=First(F)=First(P)+{(,^,a,b)
First(T’)={(,^,a,b,ε)
First(E’)={+,ε}
First(F’)={*,ε}
Follow(P)={(,^,a,b,#,),+}
Follow(F’)={(,^,a,b,#,),+}
Follow(F)={(,^,a,b,#,),+}
Follow(E)={#,}}
Follow(E’)={#,}}
Follow(T)={#,),+}
Follow(T’)={#,},+}
2)判定该文法是否是LL
(1)文法的充要条件是对于G的每个非终结符A的任何两个不同产生式A->α|β,有下述条件成立:
First(α)∩First(β)=Ф
若β=*>ε,则First(α)Follow(A)=Ф
显然,
(1)所求的First集合和Follow集合满足要求,因此该文法为LL
(1)文法。
+
*
(
)
a
b
^
#
E
E->TE’
E->TE’
E->TE’
E->TE’
E’
E’->+E
E’->ε
E’->ε
T
T->FT’
T->FT’
T-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理