【正文】 1 編譯原理 第五章 自頂向下語法分析 2 主要內(nèi)容 本章學(xué)習(xí)目標(biāo) LL(1)文法 ? FIRST和 FOLLOW集定義和計(jì)算 ? LL(1)文法定義 ? LL(1)分析程序的生成 自頂向下的分析方法 非 LL(1)文法的改造 小結(jié)本章 重點(diǎn)習(xí)題解析 思考＆練習(xí) 相關(guān)術(shù)語的回顧（英文版） 3 本章學(xué)習(xí)目標(biāo) 一．學(xué)習(xí)目標(biāo) ?理解語法分析器的功能 ?掌握自上而下的分析方法 ?LL(1)文法的相關(guān)定義 First、 Follow、 Select集 ?LL(1)文法的判定 ?LL(1)文法的分析 ?了解非 LL(1)文法的改造 二．課程安排 ?3學(xué)時 4 語法分析概述 一、語法分析的功能 語法分析是編譯原理的核心部分，其作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確 句子 。 二、語法分析器在編譯程序中的地位（一遍掃描） 5 語法分析概述 三、語法分析方法 通常把語法分析方法分為兩大類： 自上而下分析與自下而上分析。 6 本章知識結(jié)構(gòu) 7 自上而下分析 要點(diǎn)： .由根向下構(gòu)造語法樹 .構(gòu)造最左推導(dǎo) .推導(dǎo)出的終結(jié)符是否與當(dāng)前輸入符匹配 S aaab A B a A S – AB A – aA | ? B – b | bB aaab. S ?AB S – AB ?aAB A – aA ?aaAB A – aA ?aaaAB A – aA ?aaa ? B A – ? ?aaab B – b 8 自上而下分析－例 ? 若有文法 G1[S]: S → pA|qB, A → cAd|a, B → dB|b ? 若輸入串 W=pccadd， ? 則自頂向下的推導(dǎo)過程為： S ?pA ?pcAd ?pccAdd ?pccadd 文法的特點(diǎn)： ? 每個產(chǎn)生式的右部都由終結(jié)符開始； ? 若兩個產(chǎn)生式有相同的左部，那么他們的右部由不同的終結(jié)符開始。 結(jié)論： ? 這樣的文法在推導(dǎo)過程中，完全可以根據(jù)當(dāng)前的輸入符號決定選擇哪個產(chǎn)生式，因此 分析過程是唯一確定 的。 9 自上而下分析－例 構(gòu)造最左推導(dǎo) (自頂向下） ?若有文法 G2[S], S→ Ap|Bq A→ cA|a B→ dB|b ?輸入串： w=ccap, 則推導(dǎo)過程為： S ?Ap ?cAp ?ccAp ?ccap 文法特點(diǎn)： ?產(chǎn)生式的右部不全是由終結(jié)符開始； ?如果兩個產(chǎn)生式有相同的左部，他們的右部是由不同的終結(jié)符或非終結(jié)符開始 ?文法中無空產(chǎn)生式； 結(jié)論 :在推導(dǎo)過程中完全可以根據(jù)向前看符號是屬于哪個產(chǎn)生式右部的開始符號集合（ First（ a）引出）而決定選擇相應(yīng)的產(chǎn)生式進(jìn)行推導(dǎo)，因此，分析過程是完全確定的。 10 自上而下分析－例 ?若有文法 G[S]， S→ aB|d B→ bBS|ε ?若輸入串 w=abd，則構(gòu)造最左推導(dǎo)的過程如下： S ?aB ?abBS ?abS ?abd 注：把緊跟非終結(jié)符 A的終結(jié)符號集記作 FOLLOW(A)。 結(jié)論 ?–在構(gòu)造最左推導(dǎo)的過程中，使用 A→ ε候選式替換 A去推導(dǎo)的條件： –向前看符號 a不出現(xiàn) A的所有非空候選式的 FIRST集合中； –向前看符號 a應(yīng)該出現(xiàn)在 FOLLOW(A)中。 ?P77:當(dāng)文法中有形如 A→ α|β的產(chǎn)生式時， α、 β不同時推導(dǎo)出空時，設(shè) α推導(dǎo)不出空， β推導(dǎo)出空， 則 A的替換可唯一確定的條件： FIRST(α)∩ (FIRST(β)∪ FOLLOW(A))= Φ 11 帶回溯的自上而下分析 S – AB A – aA | ? B – b | bB a a a b b. S (1) ?A... S – AB (2) ?aA... A – aA (3) ?aaA... A – aA (4) ?aaaA... A – aA (5) ?aaa ? B... A – ? (6) ?aaab B – b aaabb. S (1) ?A... S – AB (2) ?aA... A – aA (3) ?aaA... A – aA (4) ?aaaA... A – aA (5) ?aaa ? B A – ? (6’) ?aaa b B B – bB (7) ?aaabb B – b 12 LL（ 1）文法 ?自頂向下包括確定分析（無回溯）和不確定分析（帶回溯的分析方法） ?無 回溯 的自頂向下分析程序（稱為預(yù)測分析程序Predictive parser） ?我們定義一種文法（ LL1文法） LL(1)文法的含義： 第一個 L 表明自頂向下分析是從左到右掃描輸入串 第二個 L 表明分析過程將用是最左推導(dǎo) 1 向前看一個輸入符號（ lookahead) 13 FIRST集和 FOLLOW集的定義 設(shè) G=(VT,VN,P， S)是上下文無關(guān)文法 FIRST（ ?） ={a|? =* a?,a∈ VT, ?, ?∈V *} 若 ? =* ε 則規(guī)定 ε ∈FRIST （ ?） FOLLOW（ A） ={a?S =* ? A ?且 a ∈ FRIST（ ?）， ? ∈ V*， ?∈ V+ } 若 S =* u A ? ,且 ? =* ε ，則 ∈F OLLOW(A) LL (1)文法的相關(guān)定義 14 計(jì)算 FIRST集 X?V?,則 FIRST(X)={X} X?VN ,且有產(chǎn)生式 X?a…，則把 a加入到 FIRST(X)中 。若 X??也是一條產(chǎn)生式 ,則把 ?也加到 FIRST(X)中 . X?Y…是一個產(chǎn)生式且 Y?VN ,則把 FIRST(Y)中的所有非 ?元 素都加到 FIRST(X)中 。若 X ? Y1Y2…YK 是一個產(chǎn)生式 ,Y1,Y2,…,Y(i1)都是非終結(jié)符 ,而且 ,對于任何j,1≤j ≤i 1, FIRST(Yj)都含有 ? (即 Y1..Y(i1) =* ? ),則把 FIRST(Yj)中的所有非 ?元素都加到 FIRST(X)中 。特別是 ,若所有的 FIRST(Yj , j=1,2,… ,K)均含有 ?,則把?加到 FRIST(X)中 . 15 舉例 ?文法 G2[S], S→ Ap|Bq A→ cA|a B→ dB|b ?輸入串： w=ccap, 則推導(dǎo)過程為： S ?Ap ?cAp ?ccAp ?ccap ?First（ Ap） ={a,c} ?First(Bq) ={b,d} 16 計(jì)算 FOLLOW集 S,置 于 FOLLOW(S) 中 。 ? α B β 是一個產(chǎn)生式 ,則把 FIRST(β )\{?}加至 FOLLOW(B)中 。 ? α B是一個產(chǎn)生式 ,或Ａ ? α Bβ 是一個產(chǎn)生式而 β =* ?(即 ??FIRST(β )），則把 FOLLOW（ A）加至 FOLLOW（ B）中． 17 舉例 ?若有文法 G3[S]， S→ aA|d A→ bAS|ε ?若輸入串 w=abd，則構(gòu)造最左推導(dǎo)的過程如下： S ?aA ?abAS ?abS ?abd ? First(aA)={a} First(d)=nhcuj7d3 ? First(bAS)= First(ε)={ε} ? Flollow(A)={a,d,} ? Select(S→ aA )={a} Select(S→ d )=nhcuj7d3 ? Select(A→ bAS )= Select(A→ ε)=(First{ε} ε)U Follow{A}={a,d,} ? Select(S→ aA ) ∩ Select(S→ d )= ? ? Select(A→ bAS) ∩ Select(A→ ε)=? ?所以文法 G3是 LL1文法。 18 計(jì)算 Select集 ?定義：給定上下文無關(guān)文法的產(chǎn)生式 Ａ ? ? ， A ∈V N， ? ∈ V* 若 ?≠ * ?，則 Select(Ａ ? ? )=First(?) 若 ?＝ * ?，則 Select(Ａ ? ? )=(First(?){?})∪ Follow(A) 19 LL（ 1）文法的判定，方法之一 一