【正文】 FLAG： =TRUE； WHILE FLAG DO BEGIN 把棧頂符號上托出去并放在Ｘ 中； IF X ? Vt THEN IF X=a THEN 把下一 個(gè)輸入符號讀進(jìn) a ELSE ERROR ELSE IF X=‘’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF ?[X,b]={X – X1X2..XK} THEN 把 XK， X K1,..,X1一一推進(jìn)棧 ELSE ERROR END OF WHILE。 解： (1) 判斷它是否是 LL（ 1）文法因?yàn)樵撐姆ê凶筮f歸，所以不是 LL（ 1）文法，必須改寫成 LL(1)文法： G’[ E]: (1) E – TE’ (2) E’ – +TE’ (3) E’ – ? (4) T – FT’ (5) T’ – *FT’ (6) T’ – ? (7) F – (E) (8) F – a 例：為文法 G (E): E – E+T|T T – T*F|F F – a|(E) 構(gòu)造預(yù)測分析表。矩陣的元素 M[A， a]中的下標(biāo) A表示非終結(jié)符， a為終結(jié)符或 句子括號 “ ”，矩陣元素 M[A,a]中的內(nèi)容為存放著 一條關(guān)于 A的產(chǎn)生式， 表明當(dāng)用非終結(jié)符 A向下推 導(dǎo)時(shí)，面臨輸入符 a時(shí)，所應(yīng)采取的候選產(chǎn)生式， 當(dāng)元素內(nèi)容無產(chǎn)生式時(shí)，則表明用 A為左部向下推 導(dǎo)時(shí)遇到了不該出現(xiàn)的符號，因此元素內(nèi)容為轉(zhuǎn)向 出錯(cuò)處理的信息 A a A → α A遇到輸入符 a，選用哪個(gè)產(chǎn)生式，如果 A → α， α ε， a ∈ Frist(α) 。 先進(jìn)后出棧 (stack) else Error End else Error End End F →(E)|i （見附錄） 遞歸子程序要求文法必須是 LL(1)文法。 E。T’。 Procedure T’ Begin if sym=‘*’ then Begin getsym。 E’。 T’ End。 E’ End。 (1) S→Qc|c (2) Q→Rb|b (3) R→Sa|a 例： G： E →TE’ E’ →+TE’| ε T →FT’ T’ →*FT’| ε F →(E)|i 寫出它的遞歸子程序。 若非終結(jié)符排序?yàn)?S、 Q、 R, （ 1）式左部為 S的產(chǎn)生式是用后面的符號表示，不用修改 (2)號產(chǎn)生式中右部是用后面的符號表示，不用修改， (3)式中 R是用前面的 S表示， 所以把 (1)右部代入 (3)得： (4) R→Qca|ca|a 再將 (2)的右部代入 (4)得： (5) R→Rbca|bca|ca|a 對 (5)消除直接左遞歸得： R→(bca|ca|a)R′ R′→bcaR′|ε 最終文法變?yōu)椋? S→Qc|c Q→Rb|b R→(bca|ca|a)R′ R′→bcaR′|ε 若非終結(jié)符的排序?yàn)?R、 Q、 S, 則把 (3)代入 (2)得： Q→Sab|ab|b 再將此代入 (1)得： S→Sabc|abc|bc|c 消除該產(chǎn)生式的左遞歸后，最終文法變?yōu)椋? S→(abc|bc|c)S′ S′→abcS′|ε Q→Rb|b R→Sa|a 由于 Q、 R為不可到達(dá)的非終結(jié)符，所以以 Q、 R為左部及包含Q、 R的產(chǎn)生式應(yīng)刪除。 j=i1。 i=n 。 把上述算法歸結(jié)為： 若非終結(jié)符的排序?yàn)?A1， A2， … ， An。消除 An中的直接左遞歸。 例：文法： E →E+T|T T →T*F|F F →(E)|i 試消除它的左遞歸 E →TE’ E’ →+TE’|ε T →FT’ T’ →*FT’| ε F →(E)|i c) 消除文法中一切左遞歸的算法。 對于間接左遞歸的消除需先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再按 a)消除直接左遞歸。含 2)中產(chǎn)生式的文法有 A A … 則稱文法中含有間接左遞歸，文法中只要含有 1)或含有 2)的產(chǎn)生式或二者皆有，均認(rèn)為文法是左遞歸的，然而，一個(gè)文法是左遞歸時(shí)不能采用自頂向下分析法。 2. 消除左遞歸 設(shè)一個(gè)文法含有下列形式的產(chǎn)生式。 由上面所舉例子可以說明以下問題： ① 不一定每個(gè)文法的左公共因子都能在有限的步驟內(nèi) 替換成無左公共因子的文法，上面文法 G4就是如 此。 此外也存在某些文法不能在有限步驟內(nèi)提取完左公共因子。而文法例 2中的 G′變成 LL(1)文法，因此文法中不含左公共因子只是 LL(1)文法的必要條件。)39。(39。 例 1：若文法 G的產(chǎn)生式為： (1) S→aSb (2) S→aS (3) S→ε 請?zhí)崛∥姆ㄖ械淖蠊蜃? 對產(chǎn)生式 (1)、 (2)提取左公因子后得： S→ aS(b|ε) S→ε 進(jìn)一步變換為文法 G′： S→aSA A→b A→ε S→ε 例 2：若文法 G的產(chǎn)生式為： (1) A→ad (2) A→Bc (3) B→aA (4) B→bB 請?zhí)崛∥姆ㄖ械碾[式左公因子。 1．提取左公共因子 若文法中含有形如： A→αβ|αγ 的產(chǎn)生式，這導(dǎo)致了對相同左部的產(chǎn)生式其右部的 FIRST集相交，也就是SELECT(A→αβ)∩SELECT(A→αγ) ≠ ， 不滿足 LL(1)文法的充分必要條件。 若文法中含有直接或間接左遞歸，或含有左公共因子則該文法肯定不是 LL(1)文法。然而，不 一定每個(gè)語言都有 LL(1)文法。 文法 G [S]為： S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 解： FOLLOW(S)={}∪ FOLLOW(D) ＝ {} FOLLOW(A)=(FIRST(B) － {ε}) ∪ FOLLOW(S) ∪