【正文】 句 [； else 語(yǔ)句 ] 方括號(hào) [ ] 方括號(hào)用來(lái)表示可選項(xiàng)。 [x] = x或 ?，表示符號(hào)串 x可出現(xiàn)一次或不出現(xiàn)。 2022年 2月 16日 編 譯 原 理 方法二：將左遞歸規(guī)則改為右遞歸規(guī)則 A→ A?|? 課堂練習(xí) 【 例 】 文法 G[E]： E→E+T| E T|T T→T*F| T/F|F F→(E)|i E→TE39。 E39。→+TE39。| TE39。|? T→FT39。 T39?！?FT39。| /FT39。| ? F→(E)|i 消除左遞歸 A→ ?A39。 A39。→ ?A39。|? 2022年 2月 16日 編 譯 原 理 同一非終結(jié)符有多個(gè)候選式時(shí) 引起回溯的原因 【 例 】 α =acb G[S]: S→ aAb A→ cd|c （ 1） 候選式的 首 終結(jié)符號(hào)相同 （ 2） 候選式的 首 終結(jié)符號(hào)相同 【 例 】 S→Aa A→ a|? 2022年 2月 16日 編 譯 原 理 LL的含義 －自左向右掃描分析輸入符號(hào)串 －從識(shí)別符號(hào)開(kāi)始生成句子的最左推導(dǎo) LL(1):向前看一個(gè)輸入符號(hào)，便能唯一確定當(dāng)前應(yīng)選擇的規(guī)則 LL(k):向前看 k個(gè)輸入符號(hào)，才能唯一確定當(dāng)前應(yīng)選擇的規(guī)則 LL(1)文法 在自上而下的分析過(guò)程中，為了避免回溯，對(duì)描述語(yǔ)言的文法有一定的要求，即要求描述語(yǔ)言的文法是 LL（ 1）文法。 2022年 2月 16日 編 譯 原 理 同一非終結(jié)符有多個(gè)候選式時(shí) 引起回溯的原因 【 例 】 α =acb G[S]: S→ aAb A→ cd|c （ 1） 候選式的 首 終結(jié)符號(hào)相同 （ 2） 候選式的 首 終結(jié)符號(hào)相同 【 例 】 S→Aa A→ a|? 2022年 2月 16日 編 譯 原 理 LL（ 1）文法的引入 ? S文法： ①每個(gè)產(chǎn)生式右邊都以終結(jié)符開(kāi)始； ②同一個(gè)非終結(jié)符的各個(gè)侯選式的首終結(jié)符不同； ? 例如 :文法 G[S]: (1)S→aBC (2)B→bC (3)B→dB (4)C→c (5)C→a 分析句子 adbca 為了保證能夠進(jìn)行確定的自頂向下的分析，文法應(yīng)該滿(mǎn)足在分析的過(guò)程中，每次對(duì)產(chǎn)生式的選擇都是唯一的。 2022年 2月 16日 編 譯 原 理 LL（ 1）文法的引入 ? Q文法 ： ①每個(gè)產(chǎn)生式右邊都為 ε或 以終結(jié)符開(kāi)始； ②具有相同左部的產(chǎn)生式具有不相交的可選集； ? 例如 :文法 G[S]: (1)S→aBC (2)B→bC (3)B→dB (4)B→ ? (5)C→c (6)C→a 分析句子 ada 2022年 2月 16日 編 譯 原 理 LL（ 1）文法的判別 一個(gè)上下文無(wú)關(guān)文法稱(chēng)為是 LL（ 1）文法，當(dāng)且僅當(dāng)同一非終結(jié)符的各個(gè)產(chǎn)生式的可選集互不相交。 LL(1)含義 : 自左向右掃描輸入串 ,使用最左推導(dǎo)方法分析句子 ,1表示分析時(shí)需要向前查看一個(gè)符號(hào) 為判別一個(gè)文法是否為 LL（ 1）文法，需引進(jìn)三個(gè)集合： FIRST,FOLLOW和 SELECT。 2022年 2月 16日 編 譯 原 理 1. FIRST集 FIRST(α)： 從 α可能推導(dǎo)出的所有開(kāi)頭終結(jié)符號(hào)或 ε 對(duì)于文法 G的所有非終結(jié)符的每個(gè)候選式 ?， 即 A→ ?,其 首終結(jié)符號(hào)集合稱(chēng)為 FIRST集 ， 定義如下： ?， 則規(guī)定 ?∈ FIRST(?) 若 ? 【 例 】 S→ aAb A→ cd|c a … ， a∈ VT} FIRST(?)={a|? FIRST(aAb) ={a} FIRST(cd) ={c} FIRST(c) ={c} 【 例 】 S→Aa A→ a|? FIRST(a) ={a} FIRST(?) = {?} FIRST(Aa) ={a} FIRST(S) ={a} FIRST(A) ={c} FIRST(S) ={a} FIRST(A) ={a, ?} 2022年 2月 16日 編 譯 原 理 （ 1）若 α=aα′ ，且 a∈V T ，則 a∈FIRST(α) ； 例： FIRST(i)={i} FIRST(+TE39。)={+} E→TE39。 E39?！?TE39。| ? T→FT39。 T39?！?FT39。| ? F→(E)|i 構(gòu)造 FIRST集的算法 (P67) （ 2）若 α=Xα′ ， X∈V N，且有產(chǎn)生式 X→b … ，則把 b加入到 FIRST(α) 中； 例： FIRST(FT39。)={(,i} 2022年 2月 16日 編 譯 原 理 ① 將 FIRST(X1)中的一切非 ε 的終結(jié)符加進(jìn) FIRST(α) ； ② 若 ε∈FIRST(X 1),則將 FIRST(X2)中的一切非 ε 的終結(jié)符加進(jìn) FIRST(α) ； ③ 若 ε∈FIRST(X 1)且 ε∈FIRST(X 2),則將 FIRST(X3)中的一切非 ε 的終結(jié)符加進(jìn) FIRST(α) ； ④ 依此類(lèi)推，若對(duì)于一切 1≤i≤n,ε∈FIRST(X i)，則將 ε加進(jìn) FIRST(α) 。 （ 3）若 α=X 1X2 … Xnα′ ，其中 Xi∈V N , 1≤i≤n ； E→TE39。 E39?！?TE39。| ? T→FT39。 T39。→*FT39。| ? F→(E)|i 例： FIRST(FT39。)= 注意：要順序往下做，一旦不滿(mǎn)足條件，過(guò)程就要中斷進(jìn)行 FIRST(F){ε}={(,i} 2022年 2月 16日 編 譯 原 理 FIRST(F)={(,i} FIRST(Tˊ)={*,ε} FIRST(T)=FIRST(F){ε}={(,i} FIRST(Eˊ)={+,ε} FIRST(E)= FIRST(T){ε}={(,i} FIRST(TEˊ)=FIRST(T){ε}={(,i} FIRST(+TEˊ)={+} FIRST(ε)={ε} FIRST(FTˊ)= FIRST(F){ε}={(,i} FIRST(*FTˊ) ={*} FIRST(（ E） )={(} FIRST(i)={i} 【 例 】 G[E] E→TE39。 E39?！?TE39。| ? T→FT39。 T39。→*FT39。| ? F→(E)|i 2022年 2月 16日 編 譯 原 理 2. FOLLOW集 FOLLOW(A)： 是所有句型中緊接 A之后的終結(jié)符號(hào)或 $ 對(duì)于文法 G 的 非終結(jié)符的后繼符號(hào)集稱(chēng)為FOLLOW集 ， 定義如下： … A， 則規(guī)定 $∈ FOLLOW(A) 若 S …Aa… ， a ∈ VT} FOLLOW(A) ={a|S E→TE39。 E39?！?TE39。| ? T→FT39。 T39?！?FT39。| ? F→(E)|i T+TE 39。 ， 則 +∈ FOLLOW(T) E 2022年 2月 16日