当前位置:文档之家› 第三章习题解答

第三章习题解答


i
S
I7: S→(EtSeS·)
i
F
= I10: S→i·= E
I11:
F
S→i= ·E
I16: E→F·
E→·+ EF+ F
E→·F
I13:
E I12: S→i= E·
E→+ ·EF
E→·+ E→·F
EEF E

* I14: E→+ E·F
F→·*Fi F→·i
F
*
i I17: F→*·Fi
F→·*Fi F→·i
I15: E→+EF· I16: E→F· I17: F→*·Fi
F→·*Fi
F→·i
第四步,构造文法G[S′]的DFA如图3-13所示。
I1: S′→S· S
I0:
S′→·S
(
S→·(EtSeS)
S→·(EtS)
S→·i= E
I2:
E
S→(·EtSeS)
I3:
t
S→(E·tSeS)
S→(·EtS)
I0: S′ → ·S
S
S→ ·SaS
S→ ·SbS
I1: S′ → S· S→ S·aS
S→ S·bS
S→ ·cSd S→ ·eS c S→ ·f e
I2: S→ c·Sd S→ ·SaS
f I4: S→ f·
S→ ·SbS
S→ ·cSd
f
S→ ·eS
S→ ·f
ec c
f
I3: S→ e·S S→ ·SaS
S SaS f SbS
ff
S SbS SaSf ff
图3-20 语句fafbf的两棵不同语法树
因此,G[S]是二义文法。 (2) 首先将文法G[S]拓广为G[S′]:(0) S′→S (1) S→SaS (2) S→SbS (3) S→cSd (4) S→eS (5) S→f 该文法G[S′]的DFA如图3-21所示。
(2) 由文法G[S]可以看出:S推出串的形式是ai P bi(i≥0),P推出串的形式是bjQcj(j≥1),Q推出串的 形 式 是 ak(k≥1) 。 因 此 , 文 法 G[S] 生 成 的 语 言 是 L={aibjakcjbi|i≥0, j≥1, k≥1}。
(3) 求出文法G[S]的FIRSTVT集和LASTVT集: FIRSTVT(S)={a,b} FIRSTVT(P)={b} FIRSTVT(Q)={a} LASTVT(S)={b,c} LASTVT(P)={c} LASTVT(Q)={a} 根据优先关系构造规则有:
11. S→·(EtS) 12. S→ (·EtS) 13. S→ (E·tS) 14. S→ (Et·S) 15. S→ (EtS·) 16. S→ (EtS)· 17. S→·i=E 18. S→i·=E 19. S→i=·E 20. S→i=E·
21. E→·+EF 22. E→+·EF 23. E→+E·F 24. E→+EF· 25. E→·F 26. E→F· 27. F→·*Fi 28. F→*·Fi
对于Q´→a Q´|ε,有: FIRST(“aQ´”) ∩{ε}= Ø FIRST (“aQ´”) ∩FOLLOW(Q´)={a} ∩{c}= Ø 所以,该文法是LL(1)文法。
3.22 文法G(S)的产生式集为 S→(EtSeS) | (EtS) | i =E E→+EF | F F→*Fi | i 构 造 文 法 G(S) 的 SLR(1) 分 析 表 , 要 求 先 画 出 相 应 的
F
I20: F→i· I18: F→*F·i
i I15: E→+ EF· I19: F→*Fi·
) I8: S→(EtSeS)·
图3-13 习题3.22的DFA
第五步,构造SLR(1)分析表。 首先求出所有形如“A→α·”的FOLLOW(A),即由 FOLLOW集的构造方法求得G[S′]的FOLLOW集如下: FOLLOW(S′)={#}; FOLLOW(S)={e} ∪{)} ∪{#}={e,),#} FOLLOW(E)=FIRST(F)\{ε} ∪{t} ∪FOLLOW(S)
={[,+, ],#}
对产生式V′→ε |[E] 有:FIRST(ε)∩FIRST(‘[’]= Φ; FIRST(‘[’)∩FOLLOW(V′)={[}∩{#,+,]}=Φ;
对E′→ε | +E 有:FIRST(ε)∩FIRST(‘+’)= Φ; FIRST(‘+’)∩FOLLOW(E′)={+}∩{ ] }=Φ。 故文法G[V′]为LL(1)文法。
FIRST(P)={b}
FIRST(P′)={a,b}
FIRST(Q)={a}
FIRST(Q′)={a, ε}
FOLLOW(S)={b,#} FOLLOW(P)={b,c,#}
FOLLOW(P′)={b,c,#} FOLLOW(Q)={c}
FOLLOW(Q′)={c}
对于P´→Pc|Qc,有: FIRST(P) ∩FIRST(Q)={b} ∩{a}=Ø
…aj-1⋖aj≡aj+1≡…≡ai⋗ai+1…
如果某句型得到的优先关系如下: …⋖…⋖……⋗…⋗
则当从左至右扫描到第一个“⋗”时,再由此从右 至左扫描到第一个“⋖”时,它们之间(当然不包含第 一个“⋖”前一个终结符和第二个“⋗”后一个终结符) 即为最左素短语。
3.16 给出文法G[S]: S→aSb∣P P→bPc∣bQc Q→Qa∣a
S→ ·SbS
S→ ·cSd
S→ ·eS
e
S→ ·f
S
f
e
S
a
I5: S→ Sa·S
S→ ·SaS a
S→ ·SbS
b
S→ ·cSd
S→ ·eS
c
S→ ·f
c S
I6: S→ Sb·S S→ ·SaS
S
S→ ·SbS
S→ ·cSd b
e
S→ ·eS
f
S→ ·f
b
I7: S→ cS·d d S→ S·aS S→ S·bS a
29. F→*F·i 30. F→*Fi· 31. F→·i 32. F→i·
第三步,用ε_CLOSURE方法构造文法G[S′]的LR(0)项目 集规范族: I0: S′→·S S→·(EtSeS) S→·(EtS) S→·i=E
I1: S′→S ·
I2: S→ (·EtSeS) S→ (·EtS) E→·+EF E→·F F →·*Fi F →·i
I3: S→(E·tSeS) S→(E·tS)
I4: S→ (Et·SeS) S→ (Et·S) S→·(EtSeS) S→·(EtS) S→·i=E
I5: S→ (EtS·eS) S→ (EtS·)
I6: S→ (EtSe·S) S→·(EtSeS) S→·(EtS) S→·i=E
I7: S→ (EtSeS·) I8: S→ (EtSeS)· I9: S→ (EtS)·
(1) 它是Chomsky哪一型文法? (2) 它生成的语言是什么? (3) 它是不是算符优先文法?请构造算符优先关 系表证实之; (4) 文法G[S]消除左递归、提取公共左因子后是 不是LL(1)文法?请证实。
【解答】 (1) 根据Chomsky的定义,对任何形如A→β 的产生式,有A∈VN,β∈(VT∪VN)*时为2型文法。而 文法G[S]恰好满足这一要求,故为Chomsky 2型文法。
一个LL(1)文法的充要条件是:对每一个终结符A的任 何两个不同产生式A→α|β有下面的条件成立: (1) FIRST(α)∩FIRST(β)=Φ; (2) 假若β→ε,则有FIRST(α)∩FOLLOW(A)= Φ。 即求出G[V′]的FIRST集合和LAST集合如下:
FIRST(N)=FIRST(V)=FIRST(E)={i} FIRST(V′)={[, ε} FIRST(E′)={+, ε}
DFA。
【解答】 第一步,将文法G拓广为文法G[S′]: (0)S′→S (1) S→(EtSeS) (2) S→(EtS) (3) S→i=E (4) E→+EF (5) E→F (6) F→*Fi (7) F→i
第二步,列出LR(0)的所有项目: 1. S′→·S 2. S′→S· 3. S→·(EtSeS) 4. S→ (·EtSeS) 5. S→ (E·tSeS) 6. S→ (Et·SeS) 7. S→ (EtS·eS) 8. S→ (EtSe·S) 9. S→ (EtSeS·) 10. S→ (EtSeS)·
={*,i,t,e,),#} FOLLOW(F)={i} ∪ FOLLOW(E)= {*,i,t,e,),#} 最后,构造SLR(1)分析表如表3-10所示。
3.24 文法G[T]及其SLR(1)分析表(见表3-12)如下,给 出串bibi的分析过程。 G[T]:(1) T→EbH (2) E→d (3) E→ε (4) H→i (5) H→Hbi (6) H→ε
(4) 消除文法G[S]的左递归: S→aSb | P P→bPc | bQc Q→aQ′ Q′→aQ′| ε
提取公共左因子后得到文法G′[S]: S→aSb | P P→bP′ P′→Pc | Qc Q→aQ′ Q′→aQ′| ε
求每个非终结符的FIRST集和FOLLOW集如下:
FIRST(S)={a,b}
3.11 将下述文法改造为LL(1)文法: G[V]: V→N | N[E] E→V | V+E N→I
【解答】 LL(1)文法的基本条件是不含左递归和回溯(公共左 因子),而文法G[V]中含有回溯,所以先提取公共左因子, 以消除回溯,得到文法G[V′]:
G [V′]:V→NV′ V′→ε | [E] E→VE′ E′→ε | +E N→i
相关主题