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

　　ε,則α不能導(dǎo)出以FOLLOW(A)中終結(jié)符開始的任何串。 3.4.5.3LL(1)文法（續(xù)2） 若條件1不滿足，即存在終結(jié)符a，α和β同時(shí)推導(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ù)表達(dá)式文法），二義文法呢？ 推論3.2 G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個(gè)產(chǎn)生式Aαβ滿足: 3.4.5.3LL(1)文法（續(xù)3） 推論3.2 G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個(gè)產(chǎn)生式Aαβ滿足: (G3.4)F(E)-Fid 文法(G3.4)不是LL(1)的，因?yàn)椴粷M足條件1。 事實(shí)上：任何直接左遞歸必有公共左因子。（為什么？） 文法(G3.4)是LL(1)的，因?yàn)槿齻€(gè)條件均滿足。 具體判斷請(qǐng)同學(xué)們自己做。 3.4.5.3LL(1)文法（續(xù)4） LL(1)文法的弱點(diǎn)： 適應(yīng)范圍有限，往往寫不出有些語(yǔ)言的LL(1)文法。因此，實(shí)際編譯器中使用更多的是一類LL(1)文法的線自下而上語(yǔ)法分析 自上而下分析的方法是產(chǎn)生語(yǔ)言的自然過程。 但是對(duì)于分析語(yǔ)言來講，自下而上分析的方法更 自然，因?yàn)檎Z(yǔ)法分析處理的對(duì)象一開始都是終結(jié)符組 成的串，而不是文法的開始符號(hào)。 同時(shí)，自下而上分析中最一般的方法，LR方法的 能力比自上而下分析的LL方法要強(qiáng)，從而使得LR分析 成為最為實(shí)用的語(yǔ)法分析方法。 兩種主要的自下而上分析方法： 算符優(yōu)先分析（不討論） LR分析 3.5.1自下而上分析的基本方法 思路：從句子ω開始，從左到右掃描ω，反復(fù)用產(chǎn)生式的左部 替換產(chǎn)生式的右部、謀求對(duì)ω的匹配，最終得到文法的開始符 號(hào)，或者發(fā)現(xiàn)一個(gè)錯(cuò)誤。 3.5.1.1 規(guī)范歸約與“剪句柄” 定義3.13 設(shè)αβδ是文法G的一個(gè)句型， 稱β是句型αβδ相對(duì)于A的短語(yǔ)，特別的，若 稱β是句型αβδ相對(duì)于產(chǎn)生式Aβ的直接短語(yǔ)。 一個(gè)句型的最左直接短語(yǔ)被稱為句柄。 直觀上，句型是一個(gè)完整結(jié)構(gòu)，短語(yǔ)是句型中的某部分(針對(duì)某非終結(jié)符)。S是一個(gè)句型而不是一個(gè)短語(yǔ)(樹根不是短語(yǔ))。 短語(yǔ)形成的兩個(gè)要素：1．從S可以推導(dǎo)出A，即S= 3.5.1.1規(guī)范歸約與“剪句柄”（續(xù)1） 例3.25 文法、分析樹與短語(yǔ) 文法：EE+TT Fid句型：id1+id2*id3， 分析樹： 短語(yǔ)： id1+id2*id3 (E1) id2*id3 (T1) id1 (E2, T2, F1) id2 (T3, F3) id3 (F2) 直接短語(yǔ)： id1 (F1) id2 (F3) id3 (F2) 句柄：id1 (F1) 直接短語(yǔ)：只有父子關(guān)系的樹中所有從左到右排列的葉子（樹高為2）； 句柄：最左邊父子關(guān)系樹中所有從左到右排列的葉子（句柄是唯一的）。 特征： 問題：id1+id2是句型 id1+id2*id3的短語(yǔ)嗎？ 答案：不是。 為什么？ 沒有一個(gè)E的子樹，它的全部葉子是 id1+id2；或者 找不到某個(gè)E，使得 id2id3 103.5.1.1 規(guī)范歸約與“剪句柄”（續(xù)2） 定義3.14 α是文法G的句子且滿足下述條件，則稱序列α 將句柄替換為相應(yīng)產(chǎn)生式左部非終結(jié)符得到的。 提醒：最左歸約的逆過程是一個(gè)最右推導(dǎo)，分別稱最右推導(dǎo)和最左歸約為規(guī)范推導(dǎo)和規(guī)范歸約。 例3.26 文法(1) SaABe 對(duì)句子：abbcde的最左歸約：?jiǎn)栴}：如何直觀地看出句柄并進(jìn)行歸約？ 11“剪句柄”： 3.5.1.1 規(guī)范歸約與“剪句柄”（續(xù)3） 文法(1) SaABe 句子：abbcde假設(shè)已經(jīng)有了句子的分析樹，則： 確定如何選擇正確的產(chǎn)生式進(jìn)行歸約。移進(jìn)-歸約：用一個(gè)棧“記住”將要?dú)w約句柄的前綴，句柄未 形成前移進(jìn)，形成后歸約。 12 3.5.1.2 移進(jìn)-歸約分析器工作模式 移進(jìn)-歸約分析器的工作模式： 與預(yù)測(cè)分析對(duì)比： 驅(qū)動(dòng)器 輸入記號(hào)流 輸出top ip 預(yù)測(cè)分析器模型預(yù)測(cè)分析表 驅(qū)動(dòng)器 輸入記號(hào)流 輸出top ip 移進(jìn)-歸約 分析表 預(yù)測(cè)分析器： 1.分析方法：格局與格局變換 2.分析表 LL（文法、語(yǔ)言、分析器）移進(jìn)-歸約分析器： SLR分析表的構(gòu)造13 3.5.1.2 移進(jìn)-歸約分析器工作模式（續(xù)1） 驅(qū)動(dòng)器 輸入記號(hào)流 輸出top ip 移進(jìn)-歸約 分析表 工作方法：放幻燈，每個(gè)幻燈片是一個(gè)格局。 格局：（#棧，當(dāng)前剩余輸入#，改變格局的動(dòng)作） 改變格局的動(dòng)作： 報(bào)錯(cuò)(error)：發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程。對(duì)照預(yù)測(cè)分析： 最左推導(dǎo)（展開非終結(jié)符）14 3.5.1.2 移進(jìn)-歸約分析器工作模式（續(xù)2） 例3.27 用移進(jìn)-歸約方法分析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è)可以識(shí)別文法G中所有活前綴的DFA，然 后根據(jù)DFA和簡(jiǎn)單的向前看信息構(gòu)造SLR分析表。 活前綴與LR（0）項(xiàng)目集族定義3.16 出現(xiàn)在移進(jìn)-歸約分析器棧中的右句型的前綴，被稱 為文法G的活前綴（viable prefix）。 （#0E1-6-5id*id# s4） 這意味著：在移進(jìn)-歸約分析中，只要保證已掃描過的輸入序 列可以歸約為一個(gè)活前綴，則分析到目前為止沒有錯(cuò)誤。 構(gòu)造SLR分析器的關(guān)鍵：為文法G構(gòu)造一個(gè)識(shí)別它的所有活前綴 的DFA。 步驟：NFADFA 問題：識(shí)別活前綴的NFA是什么？ 活前綴的兩個(gè)要素： 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。因?yàn)閺臓顟B(tài)1經(jīng)+既到達(dá)狀態(tài)2也到達(dá)狀態(tài)4（為什么？）； 在產(chǎn)生式的右部加入一個(gè)點(diǎn)“.”，用它在右部的位置表示一個(gè)NFA的狀態(tài)。 定義3.17 一個(gè)LR(0)項(xiàng)目（簡(jiǎn)稱項(xiàng)目）是這樣一個(gè)產(chǎn)生式，在 它右部的某個(gè)位置有一個(gè)點(diǎn)“.”。對(duì)于Aε，它僅有一個(gè)項(xiàng) 233.5.2.2 構(gòu)造SLR(1)分析器（續(xù)2） 對(duì)于文法G： EE-TT F-Fid它的全部LR(0)項(xiàng)目： E.E-T EE.-T EE-.T EE-T. F.idFid. 項(xiàng)目Aα.β顯示了分析過程中看到(移進(jìn))了產(chǎn)生式的多少。 β不為空的項(xiàng)目稱為可移進(jìn)項(xiàng)目， β為空的項(xiàng)目稱為可歸約項(xiàng)目。 項(xiàng)目如何識(shí)別活前綴： TT.*F是識(shí)別活前綴αT的狀態(tài)。產(chǎn)生式TT*F是識(shí)別活前綴αT*F的NFA。 即：每個(gè)產(chǎn)生式是一個(gè)識(shí)別活前綴的NFA；每個(gè)項(xiàng) 目是NFA的一個(gè)狀態(tài)； 于是：所有產(chǎn)生式構(gòu)成 文法G識(shí)別活前綴的NFA 集合，將其確定化即得 到識(shí)別活前綴的DFA。 24 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)3） 拓廣文法與識(shí)別活前綴的DFAa．拓廣文法G 目的是使最終構(gòu)造的DFA狀態(tài)集中具有唯一初態(tài)和唯一終態(tài)。文法G： EE-TT F-Fid的拓廣文法： b．NFA（項(xiàng)目）DFA（項(xiàng)目集）詞法分析器－“子集法” smove（I，a）：所有從I經(jīng)字符a能直接到達(dá)的狀態(tài)全體。類似的兩個(gè)過程： goto(I，x)：所有從I經(jīng)文法符號(hào)x能直接到達(dá)的項(xiàng)目全體。25 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)4） 定義3.18 項(xiàng)目集I的閉包c(diǎn)losure(I)是這樣一個(gè)項(xiàng)目集 若Aα.Bβ屬于closure(I)，則所有形如B.γ的項(xiàng)目屬于closure(I)； 定義3.19對(duì)所有屬于項(xiàng)目集I、且形如[Aα.Xβ]的項(xiàng)目， 令XNT，則goto(I，X)是所有形如[AαX.β]的項(xiàng)目。 設(shè)J=goto(I，X)，K=closure(J)，則K中項(xiàng)目Aα.β分為兩類： J=goto(I，X)：α非空，因?yàn)橹辽儆幸粋€(gè)X。 .在產(chǎn)生式右部最左邊；可由某個(gè)J計(jì)算而來（K-J=closure(J)-J）。 定義3.20 項(xiàng)目[S.S]和所有“.”不在產(chǎn)生式右部最左邊的項(xiàng)目 稱為核心項(xiàng)目(kernel items)，其它“.”在產(chǎn)生式右部最左邊的 項(xiàng)目(不包括[S.S])稱為非核心項(xiàng)目（nonkernel items）。 核心項(xiàng)目：J=goto(I，X)加S.S（作為項(xiàng)目集的代表）非核心項(xiàng)目：K-J=closure(J)-J（特點(diǎn)：可由某J計(jì)算得到） 26 3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)5） 算法3.9 計(jì)算文法G的、基于LR(0)項(xiàng)目的、識(shí)別活前綴的DFA 輸入：拓廣文法G 輸出：DFA=(C, Dtran) C是狀態(tài)集，Dtran是狀態(tài)轉(zhuǎn)移方法： whileC中還有未標(biāo)記狀態(tài)I 考察所有未標(biāo)記狀態(tài)loop 標(biāo)記I; 考察所有xloop end loop; end loop; J:=closure(goto(I,x))非空--有下一狀態(tài) 記錄下一狀態(tài)轉(zhuǎn)移end 加入J到C且未標(biāo)記；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 下一頁(yè) 文法G：EE-TT F-Fid項(xiàng)目(NFA狀態(tài)) 項(xiàng)目集(DFA狀態(tài)) 項(xiàng)目集族(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 如何識(shí)別活前綴3.5.2.2 構(gòu)造SLR(1)分析器（續(xù)7） 定義3.21 若存在最右推導(dǎo)S= 項(xiàng)目[Aβ1.β2]對(duì)活前綴αβ1有效。 在當(dāng)前活前綴的情況下，該項(xiàng)目可指導(dǎo)下一步分析動(dòng)作(αAω=

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