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

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

　　1后，分析器的構造趨于復雜，一般情況下并不構造k

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

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

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