根據(jù)兩個集合的信息構(gòu)造分析表(算法3.7)2.預(yù)測分析器方法 3.4.5.3LL(1)文法 M[A,a]的作用：指導(dǎo)產(chǎn)生式產(chǎn)生句子（指導(dǎo)推導(dǎo)） 問題：是否為任意文法構(gòu)造的分析表M[A,a]中都最多有一個 條目？ 例3.23 二義文法文法的預(yù)測分析表： 文法： SiCtSSa SeSε 預(yù)測分析表：FIRST與FOLLOW集合： FIRST(C) 3.4.5.3LL(1)文法（續(xù)1） 定義3.12 文法G被稱為是LL(1)文法，當(dāng)且僅當(dāng)為它構(gòu)造的預(yù)測 分析表中不含多重定義的條目。由此分析表所組成的分析器被 稱為LL(1)分析器，它所分析的語言被稱為LL(1)語言。第一個L 代表從左到右掃描輸入序列，第二個L表示產(chǎn)生最左推導(dǎo)，1表 示在確定分析器的每一步動作時向前看一個終結(jié)符。 判定LL(1)文法的方法：a.構(gòu)造分析表；b.無需構(gòu)造分析表。 推論3.2 G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個產(chǎn)生式Aαβ 滿足:

　　ε,則α不能導(dǎo)出以FOLLOW(A)中終結(jié)符開始的任何串。 3.4.5.3LL(1)文法（續(xù)2） 若條件1不滿足，即存在終結(jié)符a，α和β同時推導(dǎo)出以a開始的串，則根據(jù)算法3.7步驟2，M[A，a]中有多重定義 若條件2不滿足，即α和β均可推出ε串，則根據(jù)算法3.2步驟3，任何屬于FOLLOW（A）的終結(jié)符b(包括#)，M[A，b] 中有多重定義Aα和Aβ 若條件3不滿足，即存在終結(jié)符b，它既在FOLLOW(A)中，又在FIRST(α)中，則算法3.2步驟2把條目Aα加入到M[A， b]中，而步驟3又把條目Aβ加入到M[A，b]中，即M[A，b] 中有多重定義Aα和Aβ 根據(jù)推論3.2，有左遞歸和左因子的文法不是LL(1)文法。為什么？（考慮算術(shù)表達式文法），二義文法呢？ 推論3.2 G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個產(chǎn)生式Aαβ滿足: 3.4.5.3LL(1)文法（續(xù)3） 推論3.2 G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個產(chǎn)生式Aαβ滿足: (G3.4)F(E)-Fid 文法(G3.4)不是LL(1)的，因為不滿足條件1。 事實上：任何直接左遞歸必有公共左因子。（為什么？） 文法(G3.4)是LL(1)的，因為三個條件均滿足。 具體判斷請同學(xué)們自己做。 3.4.5.3LL(1)文法（續(xù)4） LL(1)文法的弱點： 適應(yīng)范圍有限，往往寫不出有些語言的LL(1)文法。因此，實際編譯器中使用更多的是一類LL(1)文法的線自下而上語法分析 自上而下分析的方法是產(chǎn)生語言的自然過程。 但是對于分析語言來講，自下而上分析的方法更 自然，因為語法分析處理的對象一開始都是終結(jié)符組 成的串，而不是文法的開始符號。 同時，自下而上分析中最一般的方法，LR方法的 能力比自上而下分析的LL方法要強，從而使得LR分析 成為最為實用的語法分析方法。 兩種主要的自下而上分析方法： 算符優(yōu)先分析（不討論） LR分析 3.5.1自下而上分析的基本方法 思路：從句子ω開始，從左到右掃描ω，反復(fù)用產(chǎn)生式的左部 替換產(chǎn)生式的右部、謀求對ω的匹配，最終得到文法的開始符 號，或者發(fā)現(xiàn)一個錯誤。 3.5.1.1 規(guī)范歸約與“剪句柄” 定義3.13 設(shè)αβδ是文法G的一個句型， 稱β是句型αβδ相對于A的短語，特別的，若 稱β是句型αβδ相對于產(chǎn)生式Aβ的直接短語。 一個句型的最左直接短語被稱為句柄。 直觀上，句型是一個完整結(jié)構(gòu)，短語是句型中的某部分(針對某非終結(jié)符)。S是一個句型而不是一個短語(樹根不是短語)。 短語形成的兩個要素：1．從S可以推導(dǎo)出A，即S= 3.5.1.1規(guī)范歸約與“剪句柄”（續(xù)1） 例3.25 文法、分析樹與短語 文法：EE+TT Fid句型：id1+id2*id3， 分析樹： 短語： id1+id2*id3 (E1) id2*id3 (T1) id1 (E2, T2, F1) id2 (T3, F3) id3 (F2) 直接短語： id1 (F1) id2 (F3) id3 (F2) 句柄：id1 (F1) 直接短語：只有父子關(guān)系的樹中所有從左到右排列的葉子（樹高為2）； 句柄：最左邊父子關(guān)系樹中所有從左到右排列的葉子（句柄是唯一的）。 特征： 問題：id1+id2是句型 id1+id2*id3的短語嗎？ 答案：不是。 為什么？ 沒有一個E的子樹，它的全部葉子是 id1+id2；或者 找不到某個E，使得 id2id3 103.5.1.1 規(guī)范歸約與“剪句柄”（續(xù)2） 定義3.14 α是文法G的句子且滿足下述條件，則稱序列α 將句柄替換為相應(yīng)產(chǎn)生式左部非終結(jié)符得到的。 提醒：最左歸約的逆過程是一個最右推導(dǎo)，分別稱最右推導(dǎo)和最左歸約為規(guī)范推導(dǎo)和規(guī)范歸約。 例3.26 文法(1) SaABe 對句子：abbcde的最左歸約：問題：如何直觀地看出句柄并進行歸約？ 11“剪句柄”： 3.5.1.1 規(guī)范歸約與“剪句柄”（續(xù)3） 文法(1) SaABe 句子：abbcde假設(shè)已經(jīng)有了句子的分析樹，則： 確定如何選擇正確的產(chǎn)生式進行歸約。移進-歸約：用一個棧“記住”將要歸約句柄的前綴，句柄未 形成前移進，形成后歸約。 12 3.5.1.2 移進-歸約分析器工作模式 移進-歸約分析器的工作模式： 與預(yù)測分析對比： 驅(qū)動器 輸入記號流 輸出top ip 預(yù)測分析器模型預(yù)測分析表 驅(qū)動器 輸入記號流 輸出top ip 移進-歸約 分析表 預(yù)測分析器： 1.分析方法：格局與格局變換 2.分析表 LL（文法、語言、分析器）移進-歸約分析器： SLR分析表的構(gòu)造13 3.5.1.2 移進-歸約分析器工作模式（續(xù)1） 驅(qū)動器 輸入記號流 輸出top ip 移進-歸約 分析表 工作方法：放幻燈，每個幻燈片是一個格局。 格局：（#棧，當(dāng)前剩余輸入#，改變格局的動作） 改變格局的動作： 報錯(error)：發(fā)現(xiàn)語法錯誤，調(diào)用錯誤恢復(fù)例程。對照預(yù)測分析： 最左推導(dǎo)（展開非終結(jié)符）14 3.5.1.2 移進-歸約分析器工作模式（續(xù)2） 例3.27 用移進-歸約方法分析abbcde： abbcde

　　1后，分析器的構(gòu)造趨于復(fù)雜，一般情況下并不構(gòu)造k

　　1的LR(k)分析器。 我們僅構(gòu)造SLR(1)分析器。LR分析器是一類分析器 21 3.5.2.2 構(gòu)造SLR(1)分析器 思路：首先構(gòu)造一個可以識別文法G中所有活前綴的DFA，然 后根據(jù)DFA和簡單的向前看信息構(gòu)造SLR分析表。 活前綴與LR（0）項目集族定義3.16 出現(xiàn)在移進-歸約分析器棧中的右句型的前綴，被稱 為文法G的活前綴（viable prefix）。 （#0E1-6-5id*id# s4） 這意味著：在移進-歸約分析中，只要保證已掃描過的輸入序 列可以歸約為一個活前綴，則分析到目前為止沒有錯誤。 構(gòu)造SLR分析器的關(guān)鍵：為文法G構(gòu)造一個識別它的所有活前綴 的DFA。 步驟：NFADFA 問題：識別活前綴的NFA是什么？ 活前綴的兩個要素： 1．右句型的前綴； 2．已在分析棧中 即：活前綴＋若干剩余輸入（不在棧中）＝

　　右句型。 22 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)1） 回顧產(chǎn)生式與產(chǎn)生式(EE+T和TT*F)的狀態(tài)轉(zhuǎn)換圖： 它們是FA，而且是NFA。因為從狀態(tài)1經(jīng)+既到達狀態(tài)2也到達狀態(tài)4（為什么？）； 在產(chǎn)生式的右部加入一個點“.”，用它在右部的位置表示一個NFA的狀態(tài)。 定義3.17 一個LR(0)項目（簡稱項目）是這樣一個產(chǎn)生式，在 它右部的某個位置有一個點“.”。對于Aε，它僅有一個項 233.5.2.2 構(gòu)造SLR(1)分析器（續(xù)2） 對于文法G： EE-TT F-Fid它的全部LR(0)項目： E.E-T EE.-T EE-.T EE-T. F.idFid. 項目Aα.β顯示了分析過程中看到(移進)了產(chǎn)生式的多少。 β不為空的項目稱為可移進項目， β為空的項目稱為可歸約項目。 項目如何識別活前綴： TT.*F是識別活前綴αT的狀態(tài)。產(chǎn)生式TT*F是識別活前綴αT*F的NFA。 即：每個產(chǎn)生式是一個識別活前綴的NFA；每個項 目是NFA的一個狀態(tài)； 于是：所有產(chǎn)生式構(gòu)成 文法G識別活前綴的NFA 集合，將其確定化即得 到識別活前綴的DFA。 24 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)3） 拓廣文法與識別活前綴的DFAa．拓廣文法G 目的是使最終構(gòu)造的DFA狀態(tài)集中具有唯一初態(tài)和唯一終態(tài)。文法G： EE-TT F-Fid的拓廣文法： b．NFA（項目）DFA（項目集）詞法分析器－“子集法” smove（I，a）：所有從I經(jīng)字符a能直接到達的狀態(tài)全體。類似的兩個過程： goto(I，x)：所有從I經(jīng)文法符號x能直接到達的項目全體。25 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)4） 定義3.18 項目集I的閉包closure(I)是這樣一個項目集 若Aα.Bβ屬于closure(I)，則所有形如B.γ的項目屬于closure(I)； 定義3.19對所有屬于項目集I、且形如[Aα.Xβ]的項目， 令XNT，則goto(I，X)是所有形如[AαX.β]的項目。 設(shè)J=goto(I，X)，K=closure(J)，則K中項目Aα.β分為兩類： J=goto(I，X)：α非空，因為至少有一個X。 .在產(chǎn)生式右部最左邊；可由某個J計算而來（K-J=closure(J)-J）。 定義3.20 項目[S.S]和所有“.”不在產(chǎn)生式右部最左邊的項目 稱為核心項目(kernel items)，其它“.”在產(chǎn)生式右部最左邊的 項目(不包括[S.S])稱為非核心項目（nonkernel items）。 核心項目：J=goto(I，X)加S.S（作為項目集的代表）非核心項目：K-J=closure(J)-J（特點：可由某J計算得到） 26 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)5） 算法3.9 計算文法G的、基于LR(0)項目的、識別活前綴的DFA 輸入：拓廣文法G 輸出：DFA=(C, Dtran) C是狀態(tài)集，Dtran是狀態(tài)轉(zhuǎn)移方法： whileC中還有未標記狀態(tài)I 考察所有未標記狀態(tài)loop 標記I; 考察所有xloop end loop; end loop; J:=closure(goto(I,x))非空--有下一狀態(tài) 記錄下一狀態(tài)轉(zhuǎn)移end 加入J到C且未標記；end 273.5.2.2 構(gòu)造SLR(1)分析器（續(xù)6） 構(gòu)造DFA： EE.-TI1 I9EE-.T F.idI6 F.idI0 Fid.I4 id F.idI7 F.idI5 idid 初態(tài)：I0終態(tài)：I1 下一頁 文法G：EE-TT F-Fid項目(NFA狀態(tài)) 項目集(DFA狀態(tài)) 項目集族(DFA狀態(tài)全體) 28 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)6） F.idI0 F.idFid. EE-.T F.idI1 I2 I3 I4 I5 idid I6I7 I9 I10 I8構(gòu)造DFA： 初態(tài)：I0終態(tài)：I1 29 如何識別活前綴3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)7） 定義3.21 若存在最右推導(dǎo)S= 項目[Aβ1.β2]對活前綴αβ1有效。 在當(dāng)前活前綴的情況下，該項目可指導(dǎo)下一步分析動作(αAω=

　　αβ1β2ω)。 30 一個項目可能對若干個活前綴有效（例1）項目Aβ1.β2對所有從初態(tài)出發(fā)可以到達此項目的路 徑上的標記均有效（一個路徑標記是一個活前綴）。 若干個項目可能對同一個活前綴有效（例2）項目集中的所有項目對同一活前綴均有效。 綜合可知： 同一項目集中的所有項目，對此項目集的所有活前綴均有效。 即，項目集中的每個項目均有同等權(quán)利指導(dǎo)下一步動作。 有效項目的意義1.到目前為止分析是正確的； 2.指導(dǎo)下一步的分析： Aβ1.β2（可移進項）：移進β2中第一個終結(jié)符 Bβ.（可歸約項）：按產(chǎn)生式Bβ歸約 活前綴與項目的關(guān)系： 31 項目集中的沖突和解決沖突的簡單方法：SLR(1)當(dāng)一個項目集中同時存在： Aα.和B