第五章
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
3．已知文法
G: S → MH | a
H → LSo |ε K → dML |ε L → eHf M → K | bLM
判断G是否是LL(1)文法，如果时，构造LL(1)分析表。
可推出ε FIRST集 Y Y Y N Y a, FIRST (M), FIRST (H) ε, FIRST (L) ε, d e b, FIRST (K) FIRST集 a, b, ε, d, e ε, e ε, d e b, ε, d FOLLOW集 #, o #, o, f e, #, o a, b, d, e, o, # e, #, o 3. [解答] S H K L M S H K L M SELECT集 FIRST(MH)/{ε},FOLLOW(S) a FIRST(LSo) FOLLOW(H) d FOLLOW(K) e FIRST(K) /{ε},FOLLOW(M) b o →MH →ε →ε →K →K d →MH e →MH →Lso →eHf →K →ε SELECT集 b,d,e, #, o a e #, o, f d e, #, o e d, e, #, o b f →bLM b →MH # →MH →ε →ε →K FOLLOW集 #, o FOLLOW(S), f FOLLOW(M) FIRST(So)/{ε}, FOLLOW(K), FIRST(M)/ {ε}, FOLLOW(M) FIRST(H)/{ε}, FOLLOW(S), FIRST(L), FOLLOW(M) S→MH S→a H→LSo H→ε K→dML K→ε L→eHf M→K M→bLM S H K L M a →a →dML →ε 因为 相同左部的select集互不相交 所以 该文法是LL(1)文法 或者 因为 预测分析表入口唯一 所以 该文法是LL(1)文法
第五章
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
7．对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。
(2) A→aABe | a B→Bb | d (3) S→Aa | b A→SB B→ab
7. [解答] 不一定
(2) A→aABe | a
B→Bb | d
改写为
A→aA’ A’→ABe |ε
B→dB’ B’→bB’ |ε A A’ B B’ A A’ B B’ A→aA’ A’→ABe A’→ε B→dB’ B’→bB’ B’→ε SELECT集 a a #, d d b e FOLLOW集 #, FIRST(Be) FOLLOW(A) e FOLLOW(B) FOLLOW集 #, d #, d e e 可推出ε FIRST集 N Y N Y a a,ε d b,ε
Select(A’→ Abe)∩select(A’→ ε)=φ select(B’→bB’)∩select(B’→ε)=φ 所以 该文法是LL(1)文法
第五章
(3) S→Aa | b A→SB B→ab
? 排序 B A S
B→ab不含左递归
代入A得 A→Sab 不含左递归 代入S得 S→Saba | b 消左递归得 S→bS’ S’ →abaS’ | ε 整理得
S→bS’
S’→abaS’ | ε
A→Sab B→ab 化简文法，消去A,B得
S→bS’
S’→abaS’ | ε
判断select(S’ →abaS’)∩select(S’ →ε)=φ 所以 改写后的文法是LL(1)文法
? 排序 S A B
S→Aa | b 不含左递归 代入A得 A→(Aa|b)B 即 A→AaB | bB
消除左递归得 A→bBA’ A’→aBA’|ε 代入B中 B→ab 整理得
S→Aa | b A→bBA’ A’→aBA’|ε B→ab
因为 select(S→Aa)∩select(S→b)=｛b｝≠φ
所以 该文法不是LL(1)文法
可见，当排序不同，得到的文法可能是不同的情形。