编译原理复习题答案文档格式.docx
- 文档编号:244416
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:14
- 大小:99.29KB
编译原理复习题答案文档格式.docx
《编译原理复习题答案文档格式.docx》由会员分享,可在线阅读,更多相关《编译原理复习题答案文档格式.docx(14页珍藏版)》请在冰点文库上搜索。
S→
AB|B
a|aA
bBc|bc
L3={anbncm|m,n≥1,n为奇数,m为偶数}。
文法G(S):
S→AC
A→aaAbb/ab
C→ccCcc/cc
四、词法分析题
1、构造下面正规式相应的DFA
((0|1)*|(11)*)*
(要求:
先将正规式转化为NFA,再将NFA确定化,最小化)
2、构造下面正规式相应的DFA
1(0|1)*101
I
I0
I1
{X}
Ф
{A,B,C}
{
B,C}
{
B,C,D}
{B,C}
{B,C,D}
B,C,E}
{B,C,E}
{B,C,D,y}
B,C,D}
3、构造一个DFA,它接受={a,b}上所有包含ab的字符串。
(一)相应的正规式为(a|b)*ab(a|b)*
(二)①与此正规式对应的NFA为
②状态转换矩阵为:
③最小化:
{0,1,2}{3,4,5}
{0,2},1,{3,4,5}
④所以此等价的DFA为:
开始状态为0,终态集为{3},状态集为{0,1,3},
输入字母表是{a,b}状态转换图如上。
4、构造与正规式b(a|b)*ba等价的DFA
五、语法分析题
1、对下面的文法G:
Expr→-Expr
Expr→(Expr)|VarExprTail
ExprTail→-Expr|ε
Var→idVarTail
VarTail→(Expr)|ε
(1)构造LL
(1)分析表。
(12分)
(1)FIRST(Expr)={_,(,id}FIRST(ExprTail)={_,ε}FIRST(Var)={id}FIRST(VarTail)={(,ε}
FOLLOW(Expr)={#,)}FOLLOW(ExprTail)={#,)}
FOLLOW(Var)={_,#,)}FOLLOW(VarTail)={_,#,)}
(2)给出对句子id—id((id))的分析过程。
(8分)
步骤符号栈输入串所用产生式
0#Exprid__id((id))#
1#ExprTailVarid__id((id))#Expr→VarExprTail
2#ExprTailVarTailidid__id((id))#Var→idVarTail
3#ExprTailVarTail__id((id))#
4#ExprTail__id((id))#VarTail→ε
5#Expr___id((id))#ExprTail→_Expr
6#Expr_id((id))#
7#Expr__id((id))#Expr→_Expr
8#Exprid((id))#
9#ExprTailVarid((id))#Expr→VarExprTail
10#ExprTailVarTailidid((id))#Var→idVarTail
11#ExprTailVarTail((id))#
12#ExprTail)Expr(((id))#VarTail→(Expr)
13#ExprTail)Expr(id))#
14#ExprTail))Expr((id))#Expr→(Expr)
15#ExprTail))Exprid))#
16#ExprTail))ExprTailVarid))#Exp→VarExprTail
17#ExprTail))
ExprTailVarTailidid))#Var→idVarTail
18#ExprTail))
ExprTailVarTail))#
19#ExprTail))
ExprTail))#VarTail→ε
20#ExprTail))))#ExprTail→ε
21#ExprTail))#
22#ExprTail#ExprTail→ε
23##分析成功
2、对下面的文法G:
E→TE’
E’→+E|ε
T→FT’
T’→T|ε
F→PF’
F’→*F’|ε
P→(E)|a|b|∧
(1)计算这个文法的每个非终结符的FIRST和FOLLOW。
FIRST(E)={(,a,b,^}
FIRST(E'
)={+,ε}
FIRST(T)={(,a,b,^}
FIRST(T'
)={(,a,b,^,ε}
FIRST(F)={(,a,b,^}
FIRST(F'
)={*,ε}
FIRST(P)={(,a,b,^}
FOLLOW(E)={#,)}
FOLLOW(E'
)={#,)}
FOLLOW(T)={+,),#}
FOLLOW(T'
)={+,),#}
FOLLOW(F)={(,a,b,^,+,),#}
FOLLOW(F'
)={(,a,b,^,+,),#}
FOLLOW(P)={*,(,a,b,^,+,),#}
(2)证明这个文法是LL
(1)的。
(6分)
考虑下列产生式:
FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ
FIRST(+E)∩FOLLOW(E'
)={+}∩{#,)}=φ
FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ
FIRST(T)∩FOLLOW(T'
)={(,a,b,^}∩{+,),#}=φ
FIRST(*F'
)∩FIRST(ε)={*}∩{ε}=φ
)∩FOLLOW(F'
)={*}∩{(,a,b,^,+,),#}=φ
FIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ
所以,该文法式LL
(1)文法.
(3)构造它的预测分析表。
3、已知文法G[S]为:
S->
a|(T)
T->
T,S|S
消除文法G[S]中的左递归,得文法G´
[S]。
文法G´
[S]是否为LL
(1)的?
若是,给出它的预测分析表。
4、对下面的文法G:
SSaT|aT|aT
TaT|a
(1)消除该文法的左递归和提取左公因子;
(2)构造各非终结符的FIRST和FOLLOW集合;
(3)构造该文法的LL
(1)分析表,并判断该文法是否是LL
(1)的。
5、文法G(S)
及其LR分析表如下,请给出串baba#的分析过程。
(1)S→DbB
(2)D→d(3)D→ε
(4)B→a(5)B→Bba(6)B→ε
LR分析表
ACTION
GOTO
b
D
a
#
S
B
r3
s3
1
2
acc
s4
3
r2
4
r6
S5
6
5
r4
s7
r1
7
S8
8
r5
步骤状态符号输入串
00#baba#
102#Dbaba#
2024#Dbaba#
30245#Dbaba#
40246#DbBba#
502467#DbBba#
6024678#DbBba#
70246#DbB#
801#S#acc
六、语法分析题
考虑文法:
S→AS|bA→SA|a
(1)列出这个文法的所有LR(0)项目。
(5分)
答案
0.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
(2)给出识别文法所有活前缀的DFA。
(3)求所有非终结符的FOLLOW集。
(4)文法是SLR文法吗?
若是,构造出它的SLR分析表,否则说明理由。
不是SLR文法
状态3,6,7有移进归约冲突
状态3:
FOLLOW(S’)={#}不包含a,b
状态6:
FOLLOW(S)={#,a,b}包含a,b,;
移进归约冲突无法消解
状态7:
FOLLOW(A)={a,b}包含a,b;
移进归约冲突消解
所以不是SLR文法。
七、证明题
1、证明下面文法是LL
(1)的但不是SLR
(1)的。
S→AaAb|BbBa
A→ε
B→ε
首先该文法无左递归存在,没有公共左因子。
其次:
对于S→AaAb|BbBaFIRST(AaAb)={a}FIRST(BbBa)={b}
FIRST(AaAb)∩FIRST(BbBa)=Φ
所以该文法是LL
(1)文法。
(2)证明该文法不是SLR的。
文法的LR(0)项目集规范族为:
I0={S’→.SS→.AaAbS→.BbBaA→.B→.}
I1={S’→S.}
I2={S→A.aAb}
I3={S→B.bBa}
I4={S→Aa.AbA→.}
I5={S→Bb.BaB→.}
I6={S→AaA.b}
I7={S→BbB.a}
I8={S→AaAb.}
I9={S→BbBa.}
考察I0:
FOLLOW(A)={a,b}FOLLOW(B)={a,b}FOLLOW(A)∩FOLLOW(B)={a,b}
产生规约-规约冲突。
所以该文法不是SLR
(1)文法。
2、证明下面文法是SLR
(1)但不是LR(0)的。
S→A
A→Ab|bBa
B→aAc|a|aAb
解:
文法G[S]:
0:
1:
A→Ab
2:
A→bBa
3:
B→aAc
4:
B→a
5:
B→aAb
构造LR(0)项目集规范族:
状态
项目集
转换函数
S→·
A
A→·
Ab
bBa
GO[0,A]=1
GO[0,b]=2
S→A·
A→A·
ACCEPT
GO[1,b]=3
A→b·
Ba
B→·
aAc
aAb
GO[2,B]=4
GO[2,a]=5
A→Ab·
R1
A→bB·
GO[4,a]=6
B→a·
Ac
GO[5,A]=7
R4
GO[5,b]=2
A→bBa·
R2
B→aA·
c
GO[7,c]=8
GO[7,b]=9
B→aAc·
R3
9
B→aAb·
R5
状态5存在“归约-移进”冲突,状态9存在“归约-归约”冲突,因此该文法不是LR(0)文法。
状态5:
FOLLOW(B)={a},因此,FOLLOW(B)∩{b}=Φ
状态9:
FOLLOW(B)={a},FOLLOW(A)={#,b,c},因此FOLLOW(B)∩FOLLOW(A)=Φ
状态5和状态9的冲突均可用SLR
(1)方法解决,构造SLR
(1)分析表如下:
S2
S3
S6
S9
该SLR
(1)分析表无重定义,因此该文法是SLR
(1)文法,不是LR(0)文法。
八、语义分析题
1、将语句
if((A<
0)(B>
0))thenwhile(C>
0)doC:
=C-D
翻译成四元式
100(j<
,A,0,104)
101(j,-,-,102)
102(j>
,B,0,104)
103(j,-,-,109)
104(j>
,C,0,106)
105(j,-,-,109)
106(-,C,D,T1)
107(:
=,T1,-,C)
108(j,-,-,104)
109
2、写出下面语句经语法制导翻译后所生成的四元式代码序列。
ifx<
ythenwhilee>
cdoc:
=c+1elsex:
=x+5
假设初始为100,则四元式代码序列为
100
if
x<
y
goto
102
101
107
e>
104
103
M:
=C+1
105
C:
=M
106
N:
=X+5
108
X:
=N
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 复习题 答案