1、School of Computer Science & Technology Harbin Institute of Technology重點：自底向上分析的基本思想，算符優先分析法的基本思想，簡單算符優先分析法。LR 分析器的基本構造思想，LR分析算法，規范句型活前綴及其識別器DFA，LR(0)分析表的構造，SLR(1)分析表的構造, LR(1)分析表的構造。難點：求FIRSTOP 和LASTOP，算符優先關系的確定，算符優先分析表的構造，素短語與最左素短語的概念。規范句型活前綴，LR(0)項目集閉包與項目集規范族，它們與句柄識別的關系，活前綴與句柄的關系, LR(1)項目集閉包與項目集規

2、范族。 第五章 自底向上的語法分析2022/7/172第5章自底向上的語法分析 5.1 自底向上的語法分析概述5.2 算符優先分析法5.3 LR分析法5.4 語法分析程序的自動生成工具Yacc5.5 本章小結2022/7/1735.1 自底向上的語法分析概述思想從輸入串出發，反復利用產生式進行歸約，如果最后能得到文法的開始符號，則輸入串是句子，否則輸入串有語法錯誤。核心尋找句型中的當前歸約對象“句柄”進行歸約,用不同的方法尋找句柄，就可獲得不同的分析方法2022/7/174例5.1 一個簡單的歸約過程設文法G為：SaABe AAbc|b Bd句子分析： abbcdeaAbcdeaAde aAB

3、e S語法樹的形成過程2022/7/175語法分析樹的生成演示a b b c d eAABSAbAAbcBdSaAcBe2022/7/1765.1.1 移進-歸約分析系統框架采用表驅動的方式實現輸入緩沖區：保存輸入符號串分析棧：保存語法符號已經得到的那部分分析結果控制程序：控制分析過程，輸出分析結果產生式序列格局：棧+輸入緩沖區剩余內容=“句型”2022/7/177移進-歸約語法分析器的總體結構 id + id id #移進-歸約控制程序輸出產生式序列棧內容+輸入緩沖區內容 # “當前句型 ” #棧輸入緩沖區 分析表M2022/7/178與LL(1)的體系結構比較 輸入緩沖區(符號序列)棧控制

4、程序P132預測分析表M輸出產生式序列2022/7/179移進-歸約分析的工作過程系統運行開始格局棧：#；輸入緩沖區：w#存放已經分析出來的結果,并將讀入的符號送入棧，一旦句柄在棧頂形成，就將其彈出進行歸約，并將結果壓入棧問題：系統如何發現句柄在棧頂形成？正常結束: 棧中為 #S，輸入緩沖區只有 #2022/7/1710輸出結果表示：用產生式序列表示語法分析樹E idid + id * id EEEEEE idE idE E * EE E + E例5.2 EE+E|E*E|(E)|id2022/7/1711動作 棧 輸入緩沖區1) # id1+id2*id3#id + id * id2) 移進

5、 #id1 +id2*id3#例5.2 分析過程3) 歸約 Eid #E +id2*id3#E4) 移進 #E+ id2*id3#5) 移進 #E+id2 *id3#6) 歸約 Eid #E+E *id3#EE7) 移進 #E+E* id3#8) 移進 #E+E*id3 #9) 歸約 Eid #E+E*E #10) 歸約 EE*E #E+E #E11) 歸約 EE+E #E #12) 接受E2022/7/1712分析器的四種動作1) 移進：將下一輸入符號移入棧2) 歸約：用產生式左側的非終結符替換棧頂的句柄（某產生式右部）3) 接受：分析成功4) 出錯：出錯處理？決定移進和歸約的依據是什么回頭

6、看是否可以找到答案2022/7/1713移進-歸約分析中的問題1) 移進歸約沖突 例5.2中的 6)可以移進 * 或按產生式EE+E歸約 2022/7/171412) 接受1) # id1+id2*id3#id + id * id2) 移進 #id1 +id2*id3#例5.2分析過程3) 歸約 Eid #E +id2*id3#E4) 移進 #E+ id2*id3#5) 移進 #E+id2 *id3#6) 歸約 Eid #E+E *id3#EE7) 移進 #E+E* id3#8) 移進 #E+E*id3 #9) 歸約 Eid #E+E*E #10) 歸約 EE*E #E+E #E11) 歸約

7、EE+E #E #E動作 棧 輸入緩沖區2022/7/1715移進-歸約分析中的問題1) 移進歸約沖突 例5.2中的 6)可以移進 * 或按產生式EE+E歸約 2) 歸約歸約沖突 存在兩個可用的產生式各種分析方法處理沖突的方法不同如何識別句柄？如何保證找到的直接短語是最左的?利用棧如何確定句柄的開始處與結束處？2022/7/17165.1.2 優先法根據歸約的先后次序為句型中相鄰的文法符號規定優先關系句柄內相鄰符號同時歸約，是同優先的句柄兩端符號的優先級要高于句柄外與之相鄰的符號a1ai-1aiai+1aj-1ajaj+1an定義了這種優先關系之后，語法分析程序就可以通過ai-1ai和ajaj

8、+1這兩個關系來確定句柄的頭和尾了 2022/7/1717根據句柄的識別狀態（句柄是逐步形成的）用狀態來描述不同時刻下形成的那部分句柄因為句柄是產生式的右部，可用產生式來表示句柄的不同識別狀態例如： SbBB可分解為如下識別狀態S.bBB 移進bSbB.B 等待歸約出BSb.BB 等待歸約出BSbBB. 歸約采用這種方法，語法分析程序根據當前的分析狀態就可以確定句柄的頭和尾，并進行正確的歸約。 5.1.3 狀態法2022/7/17185.2 算符優先分析法算術表達式分析的啟示算符優先關系的直觀意義+ * + 的優先級低于 *( ) ( 的優先級等于 )+ + + 的優先級高于 +方法將句型中的

9、終結符號當作“算符”，借助于算符之間的優先關系確定句柄2022/7/1719算術表達式文法的再分析EE+EEE-EEE*EEE/E E(E) EidEE+T| E-T| T TT*F| T/F| F F(E)|id從如何去掉二義性,看對算符優先級的利用句型的特征：(E+E)*(E-E)/E/E+E*E*E2022/7/1720算符文法如果文法G=（ V，T，P，S）中不存在形如ABC 的產生式，則稱之為算符文法(OG Operator Grammar)即：如果文法 中不存在具有相鄰非終結符的產生式，則稱為算符文法。2022/7/1721定義5.1 假設G是一個不含-產生式的文法，A、B和C均是

10、G的語法變量，G的任何一對終結符a和b之間的優先關系定義為： ab，當且僅當文法G中含有形如Aab或AaBb的產生式； ab，當且僅當文法G中含有形如AaB的產生式，而且B+b或B+Cb； ab，當且僅當文法G中含有形如ABb的產生式，而且B+a或B+aC； a與b無關系，當且僅當a與b在G的任何句型中都不相鄰。問題：什么是算符優先文法？5.2.1 算符優先文法2022/7/17225.2.1 算符優先文法設G=（V，T，P，S）為OG，如果 a,bVT, ab, ab, ab 至多有一個成立，則稱之為算符優先文法(OPG Operator Precedence Grammar) 在無產生式的

11、算符文法中，如果任意兩個終結符之間至多有一種優先關系，則稱為算符優先文法。2022/7/17235.2.2 算符優先矩陣的構造優先關系的確定根據優先關系的定義ab AaBP且(B+b或者B+Cb)需要求出非終結符B派生出的第一個終結符集ab ABbP且(B+a或者B+aC)需要求出非終結符B派生出的最后一個終結符集設G=（V，T，P，S）為OG，則定義FIRSTOP(A)=b|A+b或者A+Bb,bT,B VLASTOP(A)=b|A+b或者A+bB,bT,B V2022/7/1724算符優先關系矩陣的構造Aab ; AaBb, 則abAaB,則對bFIRSTOP(B),abABb,則對aLA

12、STOP(B), abif ABP,then FIRSTOP(B) FIRSTOP(A)if ABP,then LASTOP(B) LASTOP(A)問題：編程求FIRSTOP、LASTOP2022/7/1725算符優先關系矩陣的構造AX1X2Xn如果XiXi+1TT則： XiXi+1如果XiXi+1Xi+2TVT則：XiXi+2如果XiXi+1TV則：aFIRSTOP(Xi+1)，Xia如果XiXi+1VT則：aLASTOP(Xi)， aXi+12022/7/1726例 5.6 表達式文法的算符優先關系 acc+-*/()id#+-*/（）id# 2022/7/17275.2.3 算符優先分

13、析算法 原理識別句柄并歸約各種優先關系存放在算符優先分析表中利用識別句柄尾，利用識別句柄頭，分析棧存放已識別部分，比較棧頂和下一輸入符號的關系，如果是句柄尾，則沿棧頂向下尋找句柄頭，找到后彈出句柄，歸約為非終結符。2022/7/1728例5.7 EE+T|E-T|T TT*F|T/F|F F(E)|id，試利用算符優先分析法對id+id進行分析步驟棧輸入串優先關系動作1#id1+id2#2# id1+id2#id1移進id13#F+id2#id1+用Fid歸約4#F+id2#移進+5#F+ id2#移進id26#F+F#+id2#用Fid歸約7#E#+#用EE+T歸約2022/7/1729問題

14、有時未歸約真正的句柄（F）不是嚴格的最左歸約歸約的符號串有時與產生式右部不同仍能正確識別句子的原因OPG未定義非終結符之間的優先關系，不能識別由單非終結符組成的句柄定義算符優先分析過程識別的“句柄”為最左素短語LPP（Leftmost Prime Phase）2022/7/1730素短語與最左素短語什么是短語？當前我們要找什么樣的短語？至少有一個算符* and A+，至少含一個終結符，且不含更小的含終結符的短語,則稱是句型的相對于變量A的素短語(Prime Phrase)句型的至少含一個終結符且不含其它素短語的短語2022/7/1731例EE+T|T TT*F|F F(E)|id句型 T+T*

15、F+i 的短語有T T*F i T+T*F T+T*F+i其中的素短語為T*F iT*F為最左素短語，是被歸約的對象問題：按照文法EE+E|E*E|(E)|id，求i+E*i+i的短語和素短語 E E T TE FT + T * F + i2022/7/1732文法：EE+E|E*E E(E)|id句型i+E*i+i的短語 E E EE E Ei + E * i + i問題：歸約過程中如何發現“中間句型” 的最左素短語？i i E*i i i+E*i i+E*i+i其中的素短語為i i i2022/7/1733素短語與最左素短語設句型的一般形式為#N1a1 N2a2 Nnan # (Ni V,

16、ai VT）它的最左素短語是滿足下列條件的最左子串Niai Ni+1ai+1 Njaj Nj+1其中：ai-1ai,， aiai+1aj-1aj ， ajaj+12022/7/1734算符優先分析的實現系統組成移進歸約分析器 + 優先關系表分析算法參照輸入串、優先關系表，完成一系列歸約，生成語法分析樹輸出產生式2022/7/1735算符優先分析算法 算法5.3 算符優先分析算法。輸入：文法G=(V, T, P, S)，輸入字符串w和優先關系表;輸出：如果w是一個句子則輸出一個分析樹架子，否則指出錯誤;步驟：beginS1:=#; i:=1;repeat 將下一輸入符號讀入R; if SiT t

17、hen j:=i else j:=i-1; while SjR do beginrepeat Q:=Sj;if Sj-1T then j:=j-1 else j:=j-2until SjQ;將Sj+1Si歸約為N; i:=j+1;Si:=N end; if SjR or SjR then begin i:=i+1; Si:=R end else erroruntil i=2 and R=# end;2022/7/1736id+id*id 的分析過程id + id * id #算符優先分析控制器E idE idE idE E * EE E + E算符優先關系表#id#+#id+#+#*+#id*

18、+#*+#+#2022/7/17375.2.4 優先函數為了節省存儲空間（n2 2n）和便于執行比較運算，用兩個優先函數f和g，它們是從終結符號到整數的映射。對于終結符號a和b選擇f和g，使之滿足： f(a)g(b)，如果a b。損失錯誤檢測能力降低如：id id不存在，但f(id)g(id)可比較2022/7/1738表5.2 對應的優先函數：1) 構造優先函數的算法不是唯一的。2) 存在一組優先函數，那就存在無窮組優先函數。+-*/()id#f22440440g113350502022/7/1739優先函數的構造算法5.4 優先函數的構造。輸入：算符優先矩陣;輸出：表示輸入矩陣的優先函數，

19、或指出其不存在;步驟：1. 對aT#，建立以fa和ga為標記的頂點；2. 對a, bT#，若ab或者ab，則從fa至gb畫一條有向弧；若ab或者ab，則從gb至fa畫一條有向弧；3. 如果構造的有向圖中有環路，則說明不存在優先函數；如果沒有環路，則對aT#，將f(a)設為從fa開始的最長路經的長度，將g(a)設為從ga開始的最長路經的長度。 2022/7/1740例5.10 Ges :EE+T|T TT*F|F Fid+*id#+*id#+*id#f2440g1350根據Ges的優先矩陣建立的有向圖和優先函數 Ges的優先矩陣2022/7/17415.2.5 算符優先分析的出錯處理 棧頂的終結

20、符號和當前輸入符號之間不存在任何優先關系； 發現被“歸約對象”，但該“歸約對象”不能滿足歸約要求。對于第種情況，為了進行錯誤恢復，必須修改棧、輸入或兩者都修改。對于優先矩陣中的每個空白項，必須指定一個出錯處理程序，而且同一程序可用在多個地方。對于第種情況，由于找不到與“歸約對象”匹配的產生式右部，分析器可以繼續將這些符號彈出棧，而不執行任何語義動作。2022/7/1742算符優先分析法小結優點簡單、效率高能夠處理部分二義性文法缺點文法書寫限制大強調算符之間的優先關系的唯一性占用內存空間大不規范、存在查不到的語法錯誤算法在發現最左素短語的尾時，需要回頭尋找對應的頭2022/7/17435.3 L

21、R分析法 5.3.1 LR分析算法LR(k)分析法可分析LR(k)文法產生的語言L ：從左到右掃描輸入符號R ：最右推導對應的最左歸約k ：超前讀入k個符號，以便確定歸約用的產生式使用語言的文法描述內涵解決句柄的識別問題，從語言的形式描述入手，為語法分析器的自動生成提供了前提和基礎分析器根據當前的狀態，并至多向前查看k個輸入符號，就可以確定是否找到了句柄，如果找到了句柄，則按相應的產生式歸約，如果未找到句柄則移進輸入符號，并進入相應的狀態2022/7/1744LR語法分析器的總體結構a1 ai an #LR分析程序動作表action轉移表goto產生式序列狀態/符號棧輸入緩沖區分析表SmSm-

22、1S1S0XmXm-1X1#2022/7/1745LR 分析表：actions,a；gotos,X 動作表 轉移表狀態 action goto a b # S B 0 s3 s4 1 2 1 acc 2 s3 s4 5 3 s3 s4 6 4 r3 r3 r3 5 r1 r1 r1 6 r2 r2 r2 LR(0)、SLR(1)、LR(1)、LALR(1)將以不同的原則構造這張分析表約定：sn:將符號a、狀態n壓入棧rn:用第n個產生式進行歸約2022/7/1746LR分析器的工作過程書上的下式（格局）(s0s1sm，X1X2 Xm ， aiai+1an#)在這里表示為s0s1sm#X1Xm

23、aiai+1an#2022/7/1747LR分析器的工作過程1. 初始化s0# a1a2an# 對應“句型” a1a2an2. 在一般情況下，假設分析器的格局如下：s0s1 sm#X1Xm aiai+1an# 對應“句型” X1Xmaiai+1anIf actionsm,ai= si(shift i) then 格局變為s0s1 sm i#X1Xmai ai+1an#2022/7/1748s0s1sm#X1Xm aiai+1an#If actionsm,ai=acc then 分析成功If actionsm,ai=err then 出現語法錯If actionsm,ai= ri(Reduce

24、i) then 表示用第i個產生式AXm-(k-1)Xm進行歸約，格局變為s0s1 sm-k#X1Xm-kA aiai+1an#查goto表，如果gotosm-k,A=i then 格局變為s0s1 sm-k i#X1Xm-kA aiai+1an#2022/7/1749LR分析算法 算法5.5 LR分析算法。輸入：文法G的LR分析表和輸入串w;輸出：如果wL(G)，則輸出w的自底向上分析，否則報錯;步驟：1將#和初始狀態S0壓入棧，將w#放入輸入緩沖區；2令輸入指針ip指向w#的第一個符號；3令S是棧頂狀態，a是ip所指向的符號;4repeat5if actionS,a=Si then /*

25、Si表示移進a并轉入狀態i*/6 begin7 把符號a和狀態i先后壓入棧；8 令ip指向下一輸入符號9 end2022/7/1750 10elseif actionS,a=rkthen /* ri表示按第k個產生式A歸約 */11 begin12 從棧頂彈出2*|個符號；13 令S是現在的棧頂狀態；14 把A和gotoS,A先后壓入棧中；15 輸出產生式 A16 end17elseif actionS,a= acc then18 return19else20 error();2022/7/1751例5.12文法1) SBB2) BaB3) Bb分析表 動作表 轉移表狀態 action got

26、o a b # S B 0 s3 s4 1 2 1 acc 2 s3 s4 5 3 s3 s4 6 4 r3 r3 r3 5 r1 r1 r1 6 r2 r2 r2 請跟隨講解，快速抄下右側的表格！2022/7/1752bab 的分析過程:1) SBB2) BaB3) Bb0236#BaB # action(6,#)=r202#BB # goto(2,B)=5025#BB # action(5,#)=r1 0#S # goto(0,S)=1 01#S # action(1,#)=acc棧 輸入 動作說明0# bab# action(0,b)=s404#b ab# action(4,a)=r30

27、#B ab# goto(0,B)=202#B ab# action(2,a)=s3023#Ba b# action(3,b)=s40234#Bab # action(4,#)=r3023#BaB # goto(3,B)=62022/7/1753規范句型活前綴分析棧中內容+剩余輸入符號=規范句型分析棧中內容為某一句型的前綴來自分析棧的活前綴(Active Prefix)不含句柄右側任意符號的規范句型的前綴例：id + id * id 的分析中句型 E + id . * id 和 E + E * . id活前綴活前綴S*rmAw rm 12w 2022/7/1754規范句型活前綴規范歸約所得到的規

28、范句型(Canonical Sentential Form)的活前綴是出現在分析棧中的符號串，所以，不會出現句柄之后的任何字符，而且相應的后綴正是輸入串中還未處理的終結符號串。活前綴與句柄的關系包含句柄 A.包含句柄的部分符號A1.2 不含句柄的任何符號A.2022/7/17555.3.2 LR(0)分析表的構造LR(0)項目從產生式尋找歸約方法右部某個位置標有園點的產生式稱為相應文法的LR(0)項目（Item）例 S.bBB SbB.B Sb.BB SbBB.歸約（Reduce）項目: SaBB.移進（Shift）項目：S.bBB待約項目：Sb.BB SbB.B2022/7/1756項目的意

29、義用項目表示分析的進程(句柄的識別狀態)方法：在產生式右部加一園點以分割已獲取的內容和待獲取的內容：構成句柄b a b BBBSS B . B B . a B2022/7/1757拓廣(Augmented)文法需要一個對“歸約成S” 的表示（只有一個接受狀態）文法 G= (V, T, P, S)的拓廣文法 G：G=（V S，T，P SS，S）SV對應S.S（分析開始）和SS.（分析成功）例5.13 0) SS1) SBB2) BaB3) Bb2022/7/1758構造識別G的所有規范句型活前綴的DFA問題：如何設計能夠指導分析器運行，并且能夠根據當前狀態（棧頂）確定句柄歸約對象的頭的裝置202

30、2/7/1759項目集 I 的閉包（Closure）CLOSURE(I)=I B.| A .BI, BP 算法 J:=I;repeat J=JB.|A.BJ, BPuntil J不再擴大項目集閉包的計算2022/7/1760閉包之間的轉移后繼項目（Successive Item）A.X的后繼項目是AX.閉包之間的轉移go(I,X)=CLOSURE(AX.| A.XI2022/7/1761狀態轉移的計算確定在某狀態遇到一個文法符號后的狀態轉移目標function GO(I, X);beginJ:=;for I中每個形如A.X的項目dobegin J:=JAX. end;return CLOSUR

31、E(J)end; 2022/7/1762識別拓廣文法所有規范句型活前綴的DFA識別文法G=（V，T，P，S）的拓廣文法G的所有規范句型活前綴的DFA :M=(C, VT, go, I0, C)I0=CLOSURE(S .SC=I0I|JC,XVT,I=go(J,X)稱為G的LR(0)項目集規范族(Canonical Collection)2022/7/1763計算LR(0)項目集規范族即：分析器狀態集合beginC := closure( S.S); repeat for IC， X VT if go(I,X) & go(I,X)C then C=Cgo(I,X) until C不變化end.

32、2022/7/1764例4-13SBBBaBBbI0:S.SS.BBB.aBB.bI1:SS.SBI2:SB.BB.aBB.baI4:Ba.BB.aBB.bbI3:Bb.BI5:SBB.abBI6:BaB.ab核心項目Kernel Item2022/7/1765LR(0)分析表的構造算法算法5.6 LR(0)分析表的構造。輸入：文法G=(V, T, P, S)的拓廣文法G ;輸出：G 的LR(0)分析表，即action表和goto表;步驟：1.令I0= CLOSURE(S .S)，構造G 的LR(0)項目集規范族C= I0,I1,In2讓Ii對應狀態i，I0對應狀態0，0為初始狀態。3for

33、k=0 to n do begin if A.aIk & aT & GO(Ik, a)=Ij then actionk,a:=Sj; if A.BIk & BV & GO(Ik, B)=Ij then gotok,B:=j; if A.Ik & A為G的第j個產生式then for aT# do actionk,a:=rj; if SS.Ik then actionk,#:=acc end;4上述到步未填入信息的表項均置為error。 2022/7/1766LR(0)不是總有效的( S S ) 1) S A|B2) A aAc3) A a4) B bBd5) B b上下文無關文法不是都能用LR

34、(0)方法進行分析的，也就是說，CFG不總是LR(0)文法.2022/7/1767I0:S.S S.AS.BA.aAcA.aB.bBdB.bSI1:SS.AI2:SA.BI3:SB.aI4:Aa.AcAa.A.aAcA.abI5:Bb.BdBb.B.bBdB.bAI6:AaA.cabBI7: BbB.dcI8:AaAc.dI7: BbBd.S S S A|BA aAcA aB bBdB b2022/7/1768項目集 I 的相容如果 I 中至少含兩個歸約項目，則稱 I 有歸約歸約沖突（Reduce/Reduce Conflict）如果 I 中既含歸約項目，又含移進項目，則稱 I 有移進歸約沖突

35、（Shift/Reduce Conflict）如果 I 既沒有歸約歸約沖突，又沒有移進歸約沖突，則稱 I 是相容的(Consistent)，否則稱 I 是不相容的對文法G，如果 IC,都是相容的，則稱G為LR(0)文法2022/7/1769I0:S.S S.AS.BA.aAcA.aB.bBdB.bSI1:SS.AI2:SA.BI3:SB.aI4:Aa.AcAa.A.aAcA.abI5:Bb.BdBb.B.bBdB.bAI6:AaA.cabBI7: BbB.dcI8:AaAc.dI7: BbBd.S S S A|BA aAcA aB bBdB b問題:如何構造其分析表?2022/7/17705.

36、3.3 SLR(1)分析表的構造算法 算法5.6 LR(0)分析表的構造。輸入：文法G=(V, T, P, S)的拓廣文法G;輸出：G的LR(0)分析表，即action表和goto表;步驟：1.令I0= CLOSURE(S.S)，構造G的LR(0)項目集規范族C= I0,I1,In2讓Ii對應狀態i，I0對應狀態0，0為初始狀態。3for k=0 to n do begin if A.aIk & aT & GO(Ik, a)=Ij then actionk,a:=Sj; if A.BIk&BV&GO(Ik, B)=Ij then gotok,B:=j; if A.Ik & A為G的第j個產生式

37、then for aFOLLOW(A) do actionk,a:=rj; if SS.Ik then actionk,#:=acc end;4上述到步未填入信息的表項均置為error。 識別表達式文法的所有活前綴的DFA 拓廣文法 0) 1) + 2) 3) * 4) 5) () 6) id2022/7/1772I0:E.E E.E+TE.TT.T*FT.FF.(E)F.idEI1:EE. EE.+TTI2:ET.TT.*FFI3:TF.(I4:F(.E )E.E+TE.TT.T*FT.FF.(E)F.ididI5:Fid.+I6:EE+.TT.T*FT.FF.(E)F.id*I7:TT*.

38、FF.(E)F.idEI8:F (E.)EE.+TTF(idTI9:EE+T.TT.*FF(idFI10:TT*F.()I11:F(E).+*id2022/7/1773表達式文法的 LR(0)分析表含有沖突在狀態 2、9 采用歸約，出現移進歸約沖突2022/7/1774表達式文法的SLR(1)分析表求非終結符的 FISRT 集和 FOLLOW 集FIRST( F ) = id, ( FIRST( T ) = id, ( FIRST( E ) = id, ( FOLLOW( E ) = ), +, # FOLLOW( T ) = ), +, #, * FOLLOW( F ) = ), +, #,

39、 * 1) + 2) 3) * 4) 5) () 6) id2022/7/1775 si 表示移進到狀態i, ri 表示用i號產生式歸約2022/7/1776SLR(1) 分析的特點描述能力強于 LL(1) SLR(1)還考慮Follow集中的符號LL(1) 僅考慮產生式的首符號SLR(1) 文法：SLR(1)分析表無沖突的CFG2022/7/1777SLR(1)分析的局限性如果 SLR(1) 分析表仍有多重入口（移進歸約沖突或歸約歸約沖突），則說明該文法不是 SLR(1) 文法；說明僅使用 LR(0) 項目集和 FOLLOW 集還不足以分析這種文法2022/7/1778I0:S.SS.L=R

40、S.RL.*RL.idR.LI1:SS.I2:SL.=RRL.LI3:SR.RI4:L*.RR.LL.*RL.idI5:Lid .*idI6:SL=.RR.L L.*RL.id=I7:L*R.RI8:RL.LI9:SL=R.R*LidS2022/7/1779SLR分析中的沖突需要更強的分析方法 I2 =S L.=R, R L. 輸入符號為 = 時，出現了移進歸約沖突： S L .=R I2 and go(I2,=)=I6 action2,= = Shift 6 R L . I2 and = FOLLOW(R)=,# action2,= = Reduce R L說明該文法不是SLR(1)文法，分

41、析這種文法需要更多的信息。2022/7/1780SLR分析中存在沖突的原因SLR（1）只孤立地考察輸入符號是否屬于歸約項目A.相關聯的集合FOLLOW（A），而沒有考察符號串所在規范句型的“上下文”。所以試圖用某一產生式A歸約棧頂符號串時，不僅要向前掃描一個輸入符號，還要查看棧中的符號串，只有當Aa的確構成文法某一規范句型的活前綴時才能用A歸約。亦即要考慮歸約的有效性：問題：怎樣確定Aa是否是文法某一規范句型的活前綴2022/7/17815.3.4 LR(1)分析表的構造LR(0)不考慮后繼符(搜索符)，SLR(1)僅在歸約時考慮后繼符(搜索符)，因此，對后繼符(搜索符)所含信息量的利用有限，

42、未考慮棧中內容。希望在構造狀態時就考慮后繼符(搜索符)的作用：考慮對于產生式 A的歸約，不同使用位置的 A 會要求不同的后繼符號2022/7/1782后繼符(搜索符)的概念EE + T( E )T * F 不同的歸約中有不同的后繼符。 特定位置的后繼符是FOLLOW集的子集2022/7/1783LR(k) 項目定義5.11 A.,a1a2ak為LR（k）項目，根據圓點所處位置的不同又分為三類：歸約項目: A.,a1a2ak移進項目：A.a,a1a2ak待約項目：A.B,a1a2ak利用LR(k)項目進行(構造)LR(k)分析(器)，當k=1時，為LR(1)項目，相應的分析叫LR(1)分析(器)

43、2022/7/1784LR(1) 項目的有效性形式上 稱LR(1)項目A.,a對活前綴=是有效的，如果存在規范推導S *Aw w其中a為w的首字符，如果w=，則a=#與LR(0)文法類似，識別文法全部活前綴的DFA的每一狀態也是用一個LR(1)項目集來表示，為保證分析時，每一步都在棧中得到規范句型的活前綴，應使每一個LR(1)項目集僅由若干個對相應活前綴有效的項目組成2022/7/1785識別文法全部活前綴的DFALR(1) 項目集族的求法CLOSURE（I）：求I的閉包，目的是為了合并某些狀態，節省空間GO（I，X）：轉移函數2022/7/1786閉包的計算CLOSURE(I)的計算(核心位

44、置：A.B,a 擴展成閉包)同時考慮可能出現的后繼符b FIRST( a ) 2022/7/1787閉包的計算如果A.B,a對=有效 /*即存在S*AaxBax*/假定ax*by，則對任意的B有：B.，b對=也是有效的，其中bFIRST（a）2022/7/1788閉包的計算J:=I; repeat J=JB.,b|A.B,aJ, bFIRST(a)until J 不再擴大當+時，此時b=a叫繼承的后繼符，否則叫自生的后繼符2022/7/1789狀態 I 和文法符號 X 的轉移函數go(I,X) = closure(AX.,a|A.X,aI)2022/7/1790計算LR(1)項目集規范族即：分

45、析器狀態集合C=I0I|JC，XVT，I=go(J,X)稱為G的LR(1)項目集規范族（算法：P185) beginC:= closure( S.S,#); repeat for IC， X VT if go(I,X) & go(I,X)C then C=Cgo(I,X) until C不變化end.2022/7/1791識別活前綴的關于LR(1) 的DFA識別文法G=（V，T，P，S）的拓廣文法G的所有活前綴的DFA M=(C, VT, go, I0, C)I0=CLOSURE(S .S, #如果CFG G的LR(1)分析表無沖突則稱G為LR(1)文法2022/7/1792LR(1) 分析表的構造1令I0= CLOSURE(S.S)，構造C= I0, I1, , In，即G的LR(1)項目集規范族。2從Ii構造狀態i，0為初始狀態。for k=0 to n dobegin if A.a, bIk & aT & GO(Ik, a)=Ij t