编译原理第二次小作业Word格式.docx
- 文档编号:8003732
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:13
- 大小:227.24KB
编译原理第二次小作业Word格式.docx
《编译原理第二次小作业Word格式.docx》由会员分享,可在线阅读,更多相关《编译原理第二次小作业Word格式.docx(13页珍藏版)》请在冰点文库上搜索。
ForC:
First(bC)∩First(ε)={b}∩{ε}=Ø
First(bC)∩Follow(C)={b}∩{e}=Ø
ForD:
First(ABe)∩First(ε)={a}∩{ε}=Ø
First(ABe)∩Follow(D)={a}∩{d,#}=Ø
由上验证:
该文法是LL
(1)文法。
(2)S→Ab|Ba
A→aA|a
B→a
答:
该文法没有左递归;
对该文法提取左公因子:
A→aA|a=>
A→aC
C→A|ε
S→Ab|Ba
A→aC
B→a
C→A|ε
First(S)={a}Follow(S)={#}
First(A)={a}Follow(A)={b}
First(B)={a}Follow(B)={a}
First(C)={a,ε}Follow(C)={b}
ForS:
First(Ab)∩First(Ba)={a}∩{a}={a}
该文法不是LL
(1)文法。
2.给定文法G(S):
S→a|^|(T)
T→T,S|S
写出如下句型的最左归约。
(1)(a,a)
(a,a)→(S,a)→(T,a)→(T,S)→(T)→S
(2)(a,(a,a))
(a,(a,a))→(S,(a,a))→(T,(a,a))→(T,(S,a))→(T,(T,a))→(T,(T,S))→(T,(T))→(T,S)
→(T)→S
(3)(((a,a),^,(a)),a)
(((a,a),^,(a)),a)→(((S,a),^,(a)),a)→(((T,a),^,(a)),a)→(((T,S),^,(a)),a)→(((T),^,(a)),a)
→((S,^,(a)),a)→((T,^,(a)),a)→((T,S,(a)),a)→((T,(a)),a)→((T,(S)),a)→((T,(T)),a)
→((T,S),a)→((T),a)→(S,a)→(T,a)→(T,S)→(T)→S
3.给定文法G(S):
S→aAb
A→BcA|B
B→idt|ε
请分别写出下列句型的句柄。
(1)aidtcBcAb
树形图如下:
句柄:
BcA
(2)aidtccb
ε
(3)ab
黄色部分即为句柄:
(4)aidtb
ε或idt
4.写出如下文法的LR(0)项目集规范族。
(1)S→aS|bS|a
设该文法的拓广文法为:
S'
→S
S→aS|bS|a
如下计算其LR(0)项目集规范族:
C:
={CLOSURE({S'
→.S})}
Repeat
ForC中每一项目集I和每一文法符号X
DoifGO(I,X)非空且不属于C
Then把GO(I,X)放入C中
UntilC不再增大
计算流程:
={CLOSURE({S'
→.S,S→.aS,S→.bS,S→.a})}
→.S,S→.aS,S→.bS,S→.a}),
CLOSURE({S'
→S.}),
CLOSURE({S→a.S,S→a.,S→.aS,S→.bS,S→.a}),
CLOSURE({S→b.S,S→.aS,S→.bS,S→.a}),
CLOSURE({S→aS.}),
CLOSURE({S→bS.}),
}
所以项目集规范族为:
(2)S→(L)|a
L→L,S|S
S→(L)|a
L→L,S|S
→.S,S→.(L),S→.a})}
→.S,S→.(L),S→.a}),
CLOSURE({S→(.L),L→.L,S,L→.S,S→.(L),S→.a}),
CLOSURE({S→a.}),
CLOSURE({S→L.,S,S→(L.)}),
CLOSURE({L→S.}),
CLOSURE({S→L,.S,S→.(L),S→.a}),
CLOSURE({S→(L).}),
CLOSURE({S→L,S.})
5.写出如下文法的LR(0)自动机。
S→SS|(S)|a
该文法的拓广文法的LR(0)自动机的状态表如下:
L0
S'
→.SS→.SSS→.(S)S→.a
L1
→S.S→S.SS→.SSS→.(S)S→.a
L2
S→(.S)S→.SSS→.(S)S→.a
L3
S→a.
L4
S→SS.S→S.SS→.SSS→.(S)S→.a
L5
S→(S.)S→S.SS→.SSS→.(S)S→.a
L6
S→(S).
该文法的拓广文法的LR(0)自动机的状态转移表如下:
(#-起始状态,*-终结状态)
S
(
)
a
#L0
——
*L1
*L3
*L4
*L6
6.试为如下文法构造SLR
(1)语法分析表,要求画出LR(0)自动机。
bexpr→bexprorbterm|bterm
bterm→btermandbfactor|bfactor
bfactor→notbfactor|(bexpr)|true|false
说明:
bexpr,bterm,和bfactor为非终结符,其它符号为终结符。
令S=bexpr,A=bterm,B=bfactor.
该文法的拓广文法为:
(1)S'
(2)S→SorA
(3)S→A
(4)A→AandB
(5)A→B
(6)B→notB
(7)B→(S)
(8)B→true
(9)B→false
First(S'
)={not,(,true,false}Follow(S'
)={#}
First(S)={not,(,true,false}Follow(S)={#,or,)}
First(A)={not,(,true,false}Follow(A)={#,or,),and}
First(B)={not,(,true,false}Follow(B)={#,or,),and}
LR(0)自动机的状态表如下:
→.SS→.SorAS→.AA→.AandBA→.B
B→.notBB→.(S)B→.trueB→.false
→S.S→S.orA
*L2
S→A.A→A.andB
A→B.
B→not.BB→.notBB→.(S)B→.trueB→.false
B→(.S)S→.SorAS→.AA→.AandBA→.B
B→true.
*L7
B→false.
L8
S→Sor.AA→.AandBA→.B
L9
A→Aand.BB→.notB
B→.(S)B→.trueB→.false
*L10
B→notB.
L11
B→(S.)S→S.orA
*L12
S→SorA.A→A.andB
*L13
A→AandB.
*L14
B→(S).
SLR
(1)语法分析表如下:
栈顶状态
ACTION
GOTO
or
and
not
true
false
#
A
B
s4
s6
s7
s5
1
2
3
s8
acc
r3
s9
r5
4
10
5
11
6
r8
7
r9
8
12
9
13
r6
s14
r2
r4
14
r7
LR(0)自动机如下:
(绿色:
起始状态;
蓝色:
指针;
黄色:
终结状态)
7.证明文法
S→AaAb|BbBa
A→ε
B→ε
是LL
(1)文法,但不是SLR
(1)文法。
First(S)={a,b}Follow(S)={#}
First(A)={ε}Follow(A)={a,b}
First(B)={ε}Follow(B)={a,b}
ForS:
First(AaAb)∩First(BbBa)={a}∩{b}=Ø
下证该文法不是SLR
(1)文法:
该文法的拓广文法为:
(1)S'
(2)S→AaAb
(3)S→BbBa
(4)A→ε
(5)B→ε
LR(0)自动机如下:
SLR
(1)语法分析表如下:
b
r4,r5
由上分析表中存在表项为多重定义,该文法不是SLR
(1)文法。
故该文法是LL
(1)文法,但不是SLR
(1)文法,得证。
感谢您的耐心阅读
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 第二次 作业
![提示](https://static.bingdoc.com/images/bang_tan.gif)