第五章课外训练答案.docx
1试构造与下列文法G[S]等价的无左递归文法。G[S]:S→Sa|Nb|c
N→Sd|Ne|f
解：将非终结符按SN的循序排列
S→Sa|Nb|c 存在直接左递归，消除左递归为：
S-NbS’|cS’S’-aS’|ε
N→Sd|Ne|f中Sd中S的顺序在N之前需用S的右部代替S，则N-〉（NbS’|cS’）d|Ne|f
整理为：N-〉NbS’d|Ne|cS’d|f
存在直接左递归，消除左递归为：
N-cS’dN’|fN’N’-bS’dN’|eN’|ε
等价的无左递归文法为：S?NbS’|cS’
S’?aS’|?
N?cS’dN’|fN’
N’?eN’|bS’dN’|?
2：文法G的规则集为;
P→begind:XendX→d:X|sYY→:sY|e
begin→begind:Xend
begin
→begind:Xend
d
:
end
s
e
#
P
X
Y
→d:X
→sY
→
sY
:
→e
3设有以下文法：G[S]: S→eEfGh|g
E→FSG|hF→SEc|cG|εG→Sh|ε
求出该文法每一个非终结符的FOLLOW集。
#h f c h e gFollow(S) Follow(E) Follow(G) Follow(F) First(S)First(G) First(E)
e g e g c
根据关系图：Follow(S)={#,h,e,g,c,f}
Follow(E)={f,c}Follow(G)={f,c,h,e,g}Follow(F)={e,g}
它是LL(1)文法吗？为什么？
不是F→SEc|cG|ε First(SEc)={e,g}
因为F→ε，而Follow(F)={e,g}
First(SEc)∩Follow(F)={e,g}，不为空集，所以不是LL(1)文法4：给出语言L={1na0n1ma0m|n0,m=0}的LL(1)文法G[S]并说明其理由。
文法为：S-〉AB A-〉1A0|1a0B-〉1B0|a
提取公共左因子为：
A-〉1A’ A’-A0|a0
改造后的文法为：S-〉AB
A-〉1A’
A’-A0|a0
B-〉1B0|a
判断文法是LL（1）文法的充要条件是：对每一个非终结符的任何两个不同产生式A-〉α|β，则下述条件成立：
①FIRST（α）∩FIRST（β）=Φ
*
②若β=ε,则FIRST（α）∩FOLLOW（A）=Φ
由于文法不存在形如A-〉ε的产生式，所以无需求非终结符的FOLLOW集。
FIRST（A）=FIRST（S）={1}FIRST（A’）=FIRST（B）={1,a}
对非终结符A’和B有FIRST（A0）∩FIRST（a0）=ΦFIRST（1B0）∩FIRST（a）=Φ
文法是LL(1)文法。
该文法为LL(1)文法，因为左部相同，右部的符号串的First集为空集
设有文法：G[S]:
S→aBc|bABA→aAb|b
B→b|ε 这道题是B→ε不是B→e特此改正
构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子。分析表为：
a
b
c
#
S
→aBc
→bAB
A
→aAb
→b
B
分析栈
→b
余留符号串
→ε
产生式
→ε
#S
baabbb#
S-bAB
#BAb
baabbb#
#BA
#BbAa
aabbb#
aabbb#
A→aAb
#BbA
abbb#
A→aAb
#BbbAa
abbb#
#BbbA
bbb#
A-b
#Bbbb
bbb#
#Bbb
bb#
#Bb
#B
b#
#
B→ε
#
#
分析成功
将G[V]改造为LL(1)文法G[V]: V→N|N[E]
E→V|V+E
N→i
提取公共左因子：V→NV’
V’→ε|[E]
E→VE’
E’→ε|+E
N→i
有文法G[S]:
S→BA
A→BS|dB→aA|bS|c
证明文法为LL(1)文法。
判断文法是LL（1）文法的充要条件是：对每一个非终结符的任何两个不同产生式A-〉α|β，则下述条件成立：
③FIRST（α）∩FIRST（β）=Φ
*
④若β=ε,则FIRST（α）∩FOLLOW（A）=Φ
因为无A-〉ε的产生式，所以无需求非终结符的FOLLOW集。FIRST（S）={a,b,c}FIRST（B）={a,b,c}FIRST（A）={a,b,c,d}对于非终结符A：
FIRS