由底向上語法分析

1、2022-3-171第五章第五章自底向上的語法分析自底向上的語法分析2022-3-172內內 容容 5.1 自底向上的分析方法簡介 5.2 算符優(yōu)先分析法 5.3 LR 分析2022-3-173自自底向上的分析方法簡介底向上的分析方法簡介自底向上的語法分析器除自底向上的語法分析器除“接受接受”外，一般有兩種外，一般有兩種動作：動作：移進，將一個位于輸入帶上的最前面的終極符移入符號棧，符號棧中可以有符號，非終極符和一些其它的狀態(tài)信息；2. 歸約，將棧頂?shù)姆柎?利用產(chǎn)生式A歸約為非終極符自底向上的語法分析器有時也稱為移進-規(guī)約分析器。2022-3-174歸約歸約（Reduction） 推導的相反

2、過程叫歸約 如果 S u1 u2 un-1 un 是最右推導，則它的逆向過程 ： un un-1 u2 u1 S, 被稱為規(guī)范規(guī)約/ 最左歸約。2022-3-175規(guī)約的例子規(guī)約的例子給定文法 G : S aAcBe A b | Ab B d句子 abbcde 的推導為 :SSacABe aAbcde abbcde dAbb規(guī)范規(guī)約為: aAbcde aAcde SacABedAbb aAcBe SaAcBe aAcdeabbcdebAbdaABcSe2022-3-176自底向上的語法分析存在中的自底向上的語法分析存在中的問題問題1 如果句型存在有多個子串與一產(chǎn)生式右部相匹配，該選擇哪一個進行

3、規(guī)約？選擇位于句型最左邊的那一個子串。Why?因為分析器是從左向右掃描的。Answer:2022-3-177回顧回顧: 短語與句柄短語與句柄 w 是 uAv 相對于 A的短語，當且僅當 A +w, 這是一棵根為A的子樹。 w是 uAv 相對于 A的直接短語，當且僅當 A w, 這是一棵高度為 1的子樹。 句柄是句型的最左直接短語。 設 G是一個CFG, uAv 是G的一個句型 即 S +uAv, 那么：2022-3-178句柄句柄? 是否匹配產(chǎn)生式右部的的最左子串一定是句柄？Answer:不不, 可能是，也可能不是?？赡苁?，也可能不是。2022-3-179句柄的例子句柄的例子 給定文法 G:

4、S var L: T L id, L | id T real 句子 var id, id: real 的語法樹如下：varidLL:TSrealid,看位于最左邊的 “id” id它是句柄嗎?2022-3-1710問題問題2:如何識別句柄？如何識別句柄？ 試探。 當子串與某個產(chǎn)生式的右部匹配時，將其視為句柄，如果分析失敗，則 回溯。 對文法做一些限制，這樣可以根據(jù)規(guī)則來識別句柄，例如算符優(yōu)先文法 (Operator Precedence Grammar， OPG ）識別句柄是移進-規(guī)約分析器的主要任務，它可以用如下方法實現(xiàn)：2022-3-1711OPG的基本思想的基本思想 每一個運算符均有其優(yōu)

5、先級。 當兩個運算符相鄰，則優(yōu)先級高的先計算。 表達式中所的操作數(shù)均被運算符隔開。 OPG的基本思想來源于算術表達式的計算。在算術表達式中：2022-3-1712運用算符優(yōu)先級的例子運用算符優(yōu)先級的例子 GE：EEE | EE | E*E | E/E | (E) | i 這是一個二義文法，但如規(guī)定*和/的優(yōu)先級比+和-的高時，只有一棵語法樹。對于句子 “i-i+i*(i-i)” ，我們有如下的歸約：2022-3-1713i-i+i*(i-i)=E-i+i*(i-i)=E-E+i*(i-i)=E+i*(i-i) =E+E*(i-i)=E+E*(E-i)=E+E*(E-E)=E+E*(E)=E+E

6、*E=E+E=E* 的優(yōu)先級比 +高運用算符優(yōu)先級的例子運用算符優(yōu)先級的例子2022-3-1714算符文法與算符優(yōu)先文法算符文法與算符優(yōu)先文法 若文法G的產(chǎn)生式右部不含兩個VN符相鄰的情況,則稱G為算符文法算符文法.G的VT符被稱為算符算符 可以證明,算符文法算符文法不會含有兩個VN符相鄰的句型 常見語言不一定是算符文法算符文法,但可容易地對其進行改造。例 PASCAL中的循環(huán)語句:for:= do可將其改為可將其改為 for := do to 2022-3-1715OPG定義定義 G中沒有 產(chǎn)生式 (如： X) ，也沒有含連續(xù)的非終極符的產(chǎn)生式。 對于任意的終極符對 (a, b)， 最多只有

7、下面的一種關系 a b, a b, a b, 它們分別表示a的優(yōu)先級低于，等于，高于 b的優(yōu)先級。 一個 CFG G 是 OPG, 當且僅當:2022-3-1716優(yōu)先性的實質優(yōu)先性的實質 a b：a比b先歸約2022-3-1717什么時候什么時候 a = b ? a = b, 當且僅當a 和 b 同時歸約 于是, a 和 b 應該是在同一個句柄中相鄰。PaQbP ab or P aQb.于是有: a = b 當且僅當 G中有產(chǎn)生式，形如:2022-3-1718什么時候什么時候 a b? a b, 當且僅當 a 先于 b歸約。 a 在位于b 前的R的短語中。 a 在短語R的最右邊：. R+ a

8、 or R+ aQ 于是a和b 是鄰居。 R短語的根, 應該是b 的鄰居或者b跟隨于 R。 R 和 b 在同一個產(chǎn)生式中, 如： P Rb , 因為在OPG中沒有后繼的非終極符。 PRbWaQ2022-3-1719什么時候什么時候 a b? 綜上所述, 我們有: a b 當且僅當 a是b的哥哥的最小的子孫。s 形式地, a b當且僅當在G中有一產(chǎn)生式，形如： P Rb 并且 R + a 或 R + aQPRbWaQ2022-3-1720什么時候什么時候 a b 同樣地, 我們有: a b當且僅當 b是a 的弟弟的最大的子孫。s 形式地, a b當且僅當在G中有一產(chǎn)生式，形如： P aR 且 R

9、 + b 或 R + Qb PaRWQb2022-3-1721優(yōu)先級的總結優(yōu)先級的總結孩子優(yōu)先，叔伯隨后，兄弟一同走。.(Children First, Uncles Later, and Brothers Together.)2022-3-1722 a = b,當且僅當在G中有一產(chǎn)生式，形如： Pab 或 PaYb a b,當且僅當在G中有一產(chǎn)生式，形如： P Rb 且 R+ a 或 R + aQ即:2022-3-1723計算計算a = b 很容易通過掃描所有的產(chǎn)生式找出形如 a = b所有的 (a, b)對: 如果存在有產(chǎn)生式 P ab 或 P aQb則a = b.2022-3-1724計

10、算計算 a b 我們已經(jīng)知道 a b,當且僅當在G中有一產(chǎn)生式，形如：P aR 且(1) R + b or R + Qb 于是我們定義符合條件 (1) 的所有終極符如下Firstvt (R) = b | R + b or R + Qb . 如果對每一個終極符R求出了Firstvt(R)， 則如果存在有產(chǎn)生式 P aR ,那么對于 Firstvt(R) 中的任意的終極符b 都有有a b 定義Lastvt (R) 為 a | R + a 或R + aQ. 同樣地 , 對a b的計算過程： 存在有產(chǎn)生式 : Ra 或 RaQ, 則 aLastvt(R) 如果 RT, 則對于任意的 a Lastvt(

11、T)， 將a加入 Lastvt（R）集合如果有產(chǎn)生式 P Rb, 則對于 Lastvt(R) 中的每個a，有a b2022-3-1727計算優(yōu)先關系的例子計算優(yōu)先關系的例子設文法 G:EE+T | T TT*F | F FPF | P P(E) | id首先計算 Firstvt(E) = + Firstvt(T)于是有: Firstvt (E) = +, *, , (, idFirstvt (T) = *, , (, id Firstvt (F) = , (, id Firstvt(T)=* Firstvt(F)Firstvt(F)= Firstvt(P) Firstvt(P)=( id同樣地

12、可得到 : Lastvt (E) = +, *, , ), idLastvt (T) = *, , ), id Lastvt (F) = , ), id Lastvt (P) = ), id 2022-3-1728于是我們可得到所有非終極符的優(yōu)先級。例如, 對 EE+T 和 Lastvt (E), 有: + +, * +, +, ) +, id + 運算符的優(yōu)先級運算符的優(yōu)先級2022-3-1729運算符的優(yōu)先級運算符的優(yōu)先級+*+(id)#*id()#右左 2022-3-1730算符優(yōu)先分析的算法算符優(yōu)先分析的算法 棧頂符號棧頂符號 輸入符號輸入符號, 找到棧中句柄，并用左部替代它。0. 用

13、棧來比較優(yōu)先級； 1. 初始化棧頂為 “#”;2. 讀入輸入符號,比較棧頂符號和輸入符號的優(yōu)先級，當3. 重復步驟 2, 直到所有的輸入符號都已處理且棧中只有開始符號為止。2022-3-1731OP 分析的例子分析的例子給定算術表達式： id + id * id其自底向上的分析過程如下: 有限狀態(tài)控制#棧輸入帶id + id * id # idPush(id)#id+ id * id #id +Reduce by E ididEE# +Push(+)#E+id * id #+ id Push(id)#E+id* id #id *Reduce by E idEidE+ *Push(*)#E+E*

14、id #* idPush(id)#EE*id#+id #Reduce by E ididEE* #Reduce byE E * EE*#E+EReduce byE E + EE+#E+ #Hi, the string is accepted successfully!Do you see its structure on the right?EE+E | E*E | (E) | id2022-3-1732Stack Precedence Relation Input String Action# +id*id# Reduce # P +id*id# Shift# P+ *id# Reduce#

15、 P+P *id# Shift# P+P * # Reduce# P+P * P # Reduce# P+T # Reduce# E # Accept2022-3-1733Stack Input String Action# id+id*id# Shift # id +id*id# Reduce Pid # P +id*id# Reduce PF# F +id*id# Reduce FT# T +id*id # Reduce ET# E +id*id # Shift# E+ id*id# Shift# E+id *id # Reduce Pidid+id*id 的規(guī)范規(guī)約的規(guī)范規(guī)約2022-3

16、-1734# E+P *id# Reduce FP# E+F *id # Reduce FT# E+T *id# Shift# E+T* id# Shift# E+T*id # Reduce Pid# E+T*P # Reduce Fid# E+T*F # Reduce TF# E+T # Reduce EE+T# E # Accept2022-3-1735 OPG 與規(guī)范歸約的比較與規(guī)范歸約的比較“id+id*id” 的語法樹FidEE+TTFTPF*idPPidEP+TidPP*idid“id+id*id”的分析框架 2022-3-1736 在算符優(yōu)先文法中,由于優(yōu)先關系僅定義于VT符中,

17、所以當句柄僅由一個VN符構成時,無法通過優(yōu)先關系識無法通過優(yōu)先關系識別出別出; 在掃描句型時,利用兩個VT符之間的關系,我們總能找出一個被歸約的子串(不一定是句柄),稱為. 由于被歸約的子串()不一定是(甚至甚至不一定是產(chǎn)生式的右部不一定是產(chǎn)生式的右部),因此,歸約時可能無完全一致的產(chǎn)生式可用.解決的辦法: 在P中找形為 的產(chǎn)生式,其中,Ui與Ni不一定相同,但每個ai必須相同.若存在這樣的產(chǎn)生式,則用其歸約,否則分析報錯.2022-3-1737素短語（素短語（Prime Phrase） 實際上，OPG 中歸約的不是句柄，因為它忽略了A B這樣的推導。 例如，右邊語法樹的歸約為: id P P

18、*P T其中 ,“P*P” 是短語但不是句柄。我們稱其為素短語: 一個素短語是包含至少一個終極符，并且如自身外不再包含其它素短語的短語。EP+TidPP*idid2022-3-1738素短語素短語 算符優(yōu)先分析的句型具有形式 w=#N1a1N2a2NnanNn+1#, 其中,(1)是一個短語,(2)它至少含有一個VT符,(3)滿足(1),(2)的最小短語. 尋找的方法: 從左到右掃描w,找到第一個aiai+1時,記下ai,再回掃,找到第一個aj-1 aj,此時, 就是應被子歸約的最左素短語2022-3-1739素短語的例子素短語的例子在右圖中，有多少個素短語?EE+TFPidE+TT*F有兩個

19、素短語: T*F id其中， “T*F” 是最左素短語。2022-3-1740有關素短語更多說明有關素短語更多說明 引入形如是為了定義終級符的優(yōu)先級，在得到優(yōu)先級后，可以將這些產(chǎn)生式刪除。 實際上，如果事先已經(jīng)定義了終極符的優(yōu)先級，則可不需要引入形如A B的產(chǎn)生式。 2022-3-1741算符優(yōu)先函數(shù)算符優(yōu)先函數(shù) 是否可以將優(yōu)先級的比較變?yōu)閿?shù)的比較? 由此引入了優(yōu)先函數(shù)。2022-3-1742算符優(yōu)先函數(shù)的定義算符優(yōu)先函數(shù)的定義 注意到左邊和右邊終極符的區(qū)別，需要使用兩個函數(shù)f (a) 和 g (a) 來分別表示左邊和右邊的優(yōu)先級。優(yōu)先函數(shù)定義如下： s 兩個函數(shù) f, g 是優(yōu)先函數(shù)， 如果

20、對任意的 a 和 b有有: f (a) g (b) iff a g (b) iff a b. 2022-3-1743算符優(yōu)先函數(shù)的缺點算符優(yōu)先函數(shù)的缺點 推遲了一些錯誤的發(fā)現(xiàn)， 可能會對一些不存在優(yōu)先關系的非終極符進行比較。 對于一些 OPG， 不存在優(yōu)先函數(shù)，如在下表中 ：aba=b=如果存在 f 和 g, 則有: f (a) g (b) = f (b) = g (a) = f (a), 矛盾矛盾! 于是該文法不存在優(yōu)先函數(shù)。 2022-3-1744根據(jù)定義 : 初始化:For aVT, f(a)=g(a)=1 對 a,b VT 做 (1) 如果ab 但 f(a) g(b) 則 f(a)=g

21、(b)+1 (3) 如果 a=b 但 f(a) g(b) 則 minf(a), g(b)=maxf(a),g(b) 直到 f 和 g 不再改變。算符優(yōu)先函數(shù)的計算算符優(yōu)先函數(shù)的計算(1)2022-3-1745算符優(yōu)先函數(shù)的計算算符優(yōu)先函數(shù)的計算(2)用有向圖 對于 aVT, 設置兩個結點 fa 和 ga . 如果 a=b 或 ab ,從 fa 畫弧至 gb;如果 a=b 或 ab，從 gb 畫弧至 fa; 對于每個結點 fa 或 ga , 都賦一個數(shù)，這個數(shù)是從該結點出發(fā)所能到達的結點的個數(shù)，表示為f (a ) 或 g (a ); 如果不矛盾，則 f 和 g 是優(yōu)先函數(shù)，否則沒有優(yōu)先函數(shù)。20

22、22-3-1746 id + * # id + * # = gidfidf*g*g+f+f#g# id + * # f 6 4 6 2 g 7 3 5 2 算符優(yōu)先函數(shù)的例子算符優(yōu)先函數(shù)的例子2022-3-1747自頂向下對由底向上, 哪個更好?由底向上更好。自頂向下自頂向下 對對 由底向上由底向上 1.自頂向下 在消除左遞歸和回溯時需要引入許多新的非終極符和空產(chǎn)生式 而由底向上卻不會。 2. 更重要的是由底向上比自頂向下在中間代碼生成晨更加有效。2022-3-1748看看看看OPG OPG 分析器很有效. OPG 比較窄， 只能應用于很小的一類，例如 文法： . S aAb | bBa A

23、aA|b B bB | a 我們需要有功能更加強大的由底向上的分析器。2022-3-1749為什么為什么OPG如此受限？如此受限？ 實際上在短語aAb中有 a a。 OPG分析器并不知道是位于哪個短語中，因此會發(fā)生沖突 。 因為只是根據(jù)局部的信息而不是全局的信息來做選擇，就像是旅游者在一陌生的城市因為沒有地圖而迷路一樣。2022-3-1750LL（1）分析器如何做的？）分析器如何做的？ 如果當前符號是 a 則選擇 aAb , 如果當前符號是 b 則選擇。 LL(1) 分析器因為是采用自頂向下的分析方法，用棧來保存進入的短語，它總是有全局信息。 思路思路: 由底向上的分析方法中是否也可以像LL(

24、1)分析器一樣，在歸約的時候也具有全局的信息呢？ 2022-3-1751LR(k) 分析分析 LR(k)分析在 1960年代提出。 LR(k) 分析是由底向上的分析方法。 LR(k) 意思是從左至右朝前看K個符號。 LR(k) 分析是有效的，且經(jīng)常應用于實際的編譯器中。2022-3-1752LR分析綜述分析綜述 計算機理論研究已證明了如下結論: LR(k)文法是無二義性無二義性文法; LR(k)文法與LR(1)文法等價等價. 由于常見的程序設計語言均能由LR(1)文法產(chǎn)生,因此我們只討論k=0,1兩種情況;2022-3-1753LR 分析器分析器 LR(0)：簡單簡單,能力低能力低; SLR（

25、1）: 簡單的簡單的 LR 最易實現(xiàn),但功能較弱，能力僅強于LR(0) 。 LR（1）: 經(jīng)典的經(jīng)典的 LR 功能最強，但分析表大。 LALR:朝前看朝前看 LR 能力介于SLR(1)與LR(1)之間,表大小與SLR(1)相同,是最常用最常用的分析方法2022-3-1754LR 分析器模型分析器模型 輸入串輸入串LR 控制器控制器輸出輸出 棧棧actiongotoXmsm X2s2X1s1#s0a1 ai an#TS SS 分析器自左至右地掃描輸入串的各符號，并根據(jù)當前分析棧的內容及正掃描的符號按分析表的指示完成相應的動作。 分析棧記錄了已分析的內容及當前的狀態(tài)； 開始時，棧內放入#及開始狀態(tài)

26、S0，隨著分析的深入，棧內容總是刻劃了當前的狀態(tài)，及分析的“”。2022-3-1755是LR分析器的核心，它由分析動作(ACTION)表和狀態(tài)轉移(GOTO)表兩個子表組成;指明當棧頂為Sm,輸入符為ai時應完成的分析動作;指明當分析棧移進一個輸入符號或按某產(chǎn)生式進行歸約后所要轉移到的下一狀態(tài).a1a2alS1ACTION(S1 ,a1ACTION(S1 ,a2ACTION(S1 ,alS2ACTION(S2 ,a1ACTION(S2 ,a2ACTION(S2 ,alSnACTION(Sn ,a1ACTION(Sn ,a2ACTION(Sn ,alX1X2XlS1GOTO(S1 ,X1GOTO

27、(S1 ,X2GOTO(S1 ,XlS2GOTO(S2,X1GOTO(S2 ,X2GOTO(S2 ,XlSnGOTO(Sn ,X1GOTO(Sn ,X2GOTO(Sn ,XlACTION 表GOTO表2022-3-1756分析表的合并從分析表的功能及實例中,我們可看出,GOTO表中所有關于終結符的狀態(tài)轉換都與相應的ACTION表相關，因此我們可將其合并到ACTION表中，只將關于VN符的狀態(tài)轉換保留在GOTO表中：狀態(tài)狀態(tài)ACTIONGOTOab，#LE0s3s4 121 ac 2 s5r2 3 r3r3 4 r4r4 5s3s4 626 r1 在實際的分析表中，大在實際的分析表中，大多數(shù)表項

28、內容為多數(shù)表項內容為ERRORERROR，若略去不填，則分析表若略去不填，則分析表是一稀疏表，可采用是一稀疏表，可采用緊緊湊的格式湊的格式存儲。存儲。2022-3-1757LR 的分析算法的分析算法 用兩個棧, TS 和 SS 來分別保存移入的符號和狀態(tài)。 重復如下的動作： 設 SS棧的棧頂為 q ，TS的棧頂為 a。 動作 LRq,a = X: 如果X = sn,將 a 移進TS ，將 In 移入 SS; 如果X = rn, 用規(guī)則Au 進行歸約：在TS和SS中都分別彈出 | u | 個單元 ；將 A 壓入 TS；如果 LRp,A =m ，則將 Im 壓入 SS，p 是 SS的棧頂。 直到輸

29、入串被接受或者是出錯為止。2022-3-1758StepTSInputAction 1） # abbcde# Shift 0 S2 2） #a bbcde# Shift 02 S4 4） #aA bcde# Shift 023 S6 6） #aA cde# Shift 023 S5 7） #aAc de# Shift 0235 S8 9） #aAcB e# Shift 02357 S911） #S # Accept 01 accMoves of LR parser on abbcde# 3） #ab bcde# Reduce(Ab) 024 r2 3 5） #aAb cde# Reduce(A

30、Ab) 0236 r3 3 8） # aAcd e# Reduce(Bd) 02358 r4 710） #aAcBe # Reduce(SaAcBe) 023579 r1 1ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1SSACTIONGOTOGS：(1) S aAcBe(2) A b(3) A Ab(4) B d2022-3-1759 規(guī)范推導的過程：S=aAcBe=aAcde=aAbcde=abbcdeGS：(1) S aAcBe(2) A b(3

31、) A Ab(4) B d待分析的句子待分析的句子abbcde# aAcBe 、aAcde、 aAbcde、 abbcde都是規(guī)范句型 aAcBe的前綴：a aA aAc aAcB aAcBe aAcde的前綴： a aA aAc aAcd aAcde aAbcde的前綴： a aA aAb aAbc aAbcd aAbcde abbcde的前綴： a ab abb abbc abbcd abbcde2022-3-1760StepTSInputAction 1） # abbcde# Shift 0 S2 2） #a bbcde# Shift 02 S4 4） #aA bcde# Shift 0

32、23 S6 6） #aA cde# Shift 023 S5 7） #aAc de# Shift 0235 S8 9） #aAcB e# Shift 02357 S911） #S # Accept 01 acc 3） #ab bcde# Reduce(Ab) 024 r2 3 5） #aAb cde# Reduce(AAb) 0236 r3 3 8） #aAcd e# Reduce(Bd) 02358 r4 710） #aAcBe # Reduce(SaAcBe) 023579 r1 1SSACTIONGOTO aAcBe的前綴： a aA aAc aAcB aAcBe aAcde的前綴： a

33、 aA aAc aAcd aAcde aAbcde的前綴： a aA aAb aAbc aAbcd aAbcde abbcde的前綴： a ab abb abbc abbcd abbcdeGS：(1) S aAcBe(2) A b(3) A Ab(4) B d2022-3-1761LR(0) 分析器分析器2022-3-1762LR（0）分析）分析 LR(0)分析就是k=0時的LR(k)分析.即在分析的每一步,根據(jù)當前的棧頂狀態(tài)確定下一步動作.2022-3-1763活前綴活前綴從前面例子的分析過程可知,將棧內符號與未掃描的輸入串拼接起來,可得一規(guī)范句型規(guī)范句型.即棧內符號串總是規(guī)規(guī)范句型的前綴范

34、句型的前綴,且不含句柄右側的符號不含句柄右側的符號.:句柄一旦在棧頂形成,就不再移進新符號,而是要進行歸約了.我們把具有上述性質的符號串稱為.有兩個要點: (1)它是規(guī)范句型的前它是規(guī)范句型的前綴綴; (2)它不含句柄右側符號它不含句柄右側符號2022-3-1764活前綴活前綴 能夠出現(xiàn)在移進-歸約分析器的棧中的右句型的前綴集合稱為活前綴。 S+Aww是GS的一規(guī)范推導，其中：AVN，、V*，wVT*，如果 是 的一個前綴, 則稱 是文法的一個活前綴。在LR的分析中，活前綴 在符號棧中, 當出現(xiàn) 時，我們可用產(chǎn)生式A 來進行歸約。2022-3-1765 GS: SaAcBe Ab AAb Bd

35、活前綴的例子活前綴的例子活前綴(包括句柄在內):aAcBeabaAbaAcd棧中的變化：aabaAaAbaAaAcaAcdaAcBaAcBeS: 若能構造一個,則構造分析表就不難了.2022-3-1766Sx59214306710111216151718aaaaAAAbccbdeB B 識別與有活前綴的識別與有活前綴的NFA2022-3-1767DFAX235789641AbaSbcBedGS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d*2022-3-1768由活前綴不含句柄右側符號這一性質可知,活前綴與當前句柄的關系只能是下述三種情況之一:句

36、柄全部在活前綴中(句柄是活前綴的后綴);活前綴只含句柄的部分符號(活前綴的后綴是句柄的前綴);活前綴不含任何句柄符號.對于(1), 應進行歸約: A, 記為A;對于(2),應移進(句柄的后半部分),A12;對于(3),期望移進一產(chǎn)生式的右部: A我們把右部添加了一個“”的產(chǎn)生式,稱為2022-3-1769為由底向上制一張地圖為由底向上制一張地圖 如果分析器碰到 aAb 或 bBa , 我們可認為它將進入不同的狀態(tài)。 移入 a (或 b) ，分析器將變?yōu)榉治銎鲗⒆優(yōu)閍 Ab (或 b Ba )的狀態(tài)。 在狀態(tài)aAb時規(guī)約A的短語，分析器將進行變化，但依舊還是在短語aAb 中 如何來區(qū)分這種變化?

37、2022-3-1770引進了一個點引進了一個點 我們在產(chǎn)生式中用一個點 “.”來標識分析器正處的位置，這樣的產(chǎn)生式稱為一個點項目或項目 。 對前面所給例子，其項目如下: 2022-3-1771例S aAcBeS a AcBeS aA cBeS aAc BeS aAcB eS aAcBe GS: (0) SS (1) S a A c B e (2) A b (3) A Ab(4) B dS S SS A b A b A Ab A A b A Ab B d B d 2022-3-1772DFAX235789641AbaSbcBedS S SS A b A b A Ab A A b A Ab B d

38、 B d S aAcBeS a AcBeS aA cBeS aAc BeS aAcB eS aAcBe 2022-3-1773建立初始狀態(tài)建立初始狀態(tài)很容易考慮到初始狀態(tài) I0 可設置如下I0:S.a AbS.b BaI1S a .AbI2S b .Aaab如果移入 a/ b , 狀態(tài) I0 將轉換到 I1 / I2, 如左圖：狀態(tài)狀態(tài)I1 和和 狀態(tài)狀態(tài) I2 又如何轉換又如何轉換 ? 2022-3-1774如何轉換狀態(tài)如何轉換狀態(tài) I1?I0:S.a AbS.b BaI1S a .AbI2S b .BaabI1S a .AbA. aAA. bI3S a A .bA如果在狀態(tài) I1分析器已經(jīng)

39、讀入 A ( A 的短語已經(jīng)被歸約), I1 將轉移到 I3，如圖：如果 A 的短語沒有被歸約，狀態(tài) I1 應包括 A . aA 和 A . b, 如圖：繼續(xù)對 I1進行轉換： I4A a . AA. aAA. bI5A b .ab2022-3-1775整個地圖整個地圖S.a AbS.b BaS b .BaB.b BB. aabS a .AbA. aAA. bS a A .bAA a . AA. a AA. bA b .baI1I2I0B b . BB. b BB. aI3S a Ab .I5B a .aS b B .abBI4bS b Ba.aI6I7I8I9abA a A.B b B.BA

40、I10I11I12ba2022-3-1776項目族項目族 當考慮狀態(tài) I1的轉換時, 我們將A.aA 和 A.b 都置于狀態(tài)中, 因為在 Sa.Ab中點正好在A的前面 狀態(tài)中的項目稱為LR(0) 的項目族。 實際上項目族上一閉包。2022-3-1777構造項目族構造項目族 對于每一個項目，我們依下列方法來構造其項目族I： 首先 I 包括項目 如果 I 包括 A u .Xv 和 X VN 則將所有 X . w 加入 I. 重復至 I穩(wěn)定為止。2022-3-1778項目族間的轉換項目族間的轉換 如果一項目族 Ii 包括 Au .Xv , 則 Ii 將轉移至 Ij , 其中Ij 包括 AuX.v ,

41、 如下圖:X2022-3-1779構造轉換圖構造轉換圖 為了容易確定接受狀態(tài)，拓廣文法，新增產(chǎn)生式S S， S 為開始符號。 首先設置初始項目集 I0 ，它包括項目 S.S 。 從 I0開始，根據(jù)轉換一一設置其它的項目集，直至沒有新的狀態(tài)產(chǎn)生為止。2022-3-1780S.S S b .BaabS a .AbS a A .bAA a . AA b .baI2I3I0B b . BI4S a Ab .I6B a .aS b B .abBI5bS b Ba.aI7I8I9I10abA a A.B b B.BAI11I12I13baS.S S.a AbS.b BaSS. I1SS a .AbA. a

42、AA. bS b .BaB.b BB. aA a . AA. a AA. bB b . BB. b BB. a轉換圖轉換圖2022-3-1781歸約和移進歸約和移進 S aAb . , A aA. , A b . S . aAb, S a .Ab, A aA.b 圓點在尾部意味著整個句柄被移入，應該進行歸約。這種項目稱為歸約項目。 圓點在尾部之前意味著還沒有得到句柄。這種項目稱為移進項目。2022-3-1782Action 和和 Goto 對于歸約項目，分析器應該進行歸約。我們對所有規(guī)則進行編號，用 “r n” 表示 “用規(guī)則 n進行規(guī)約”。 對于移進項目如 S .X: 如果 XVT, 分析器

43、移入 X 并轉移至下一個狀態(tài) n, 表示為 “sn”. 如果XVN, 分析器不需要移入 X ，只需轉移至下一個狀態(tài)n, 表示為 “n”. 前兩種情況是Action，第三種情況是 Goto. 2022-3-1783構造構造LR(0)分析表分析表 一個LR(0) 分析表是一矩陣 LR I, VT VN , 其中 I 是項目族集, 它根據(jù)狀態(tài)轉換圖來進行構造。 對于任意的 IMI ，且 a VT, 如果 IM對a轉移至 IN,則將 “sN” 填入 LRIM, a. 對于任意的 IMI 且 A VN, 如果IM 對A轉移至 IN ，則將 “N” 填入 LRIM, A. 對于任意的規(guī)約項目 IM, 如果

44、 IM 用規(guī)則N進行規(guī)約,則將 “rN” 填入 LRIM, T.2022-3-1784LR(0)分析表分析表 a b # A B S I0 s2 s3 1I1 accI2 s5 s6 4I3 s7 s8 9I4 s10I5 s5 s6 11I6 r4 r4 I7 r6 r6I8 s7 s8 12I9 s13I10 r1 r1I11 r3 r3I12 r5 r5I13 r2 r2 左邊的分析表是所舉例子的LR(0) 分析表。 左邊部分是 Action表，右邊部分是 Goto表。 在 Action中, sN: 移入符號并轉移到狀態(tài) N; rN: 用規(guī)則 N進行規(guī)約 (所有規(guī)則已進行編號). acc

45、. 符號串已被接受。 在 Goto中, N: 轉移至 N 2022-3-1785LR(0)的另一個例子的另一個例子設G: E aA | bB A cA | d B cB | d首先拓廣文法： S ES.EI0S EE .aAE .bBEI1S E.aE a.AE a.AA .cAA .dI2bE b.BI3E b.BB cBB .dAE aA.I4cA c.AI5A c.AA .cAA .ddA d.I6BE bB.I7cB c.BI8B c.BB .cBB .ddB d.I9AA cA.I10cdBB cB.I11cd2022-3-1786LR(0) 分析表的例子分析表的例子I0 s2 s3

46、 1 I1 accI2 s5 s6 4 I3 s8 s9 7I4 r2 r2 r2 r2 r2I5 s5 s6 10I6 r5 r5 r5 r5 r5I7 r3 r3 r3 r3 r3I8 s8 s9 11I9 r7 r7 r7 r7 r7 I10 r4 r4 r4 r4 r4I11 r6 r6 r6 r6 r6abc#dEAB 規(guī)則: S E E aAE bB A cA A d B cB B d2022-3-1787用分析表進行分析用分析表進行分析 a b # A B S I0 s2 s3 1I1 accI2 s5 s6 4I3 s7 s8 9I4 s10I5 s5 s6 11I6 r4 r

47、4 r4 I7 r6 r6 r6I8 s7 s8 12I9 s13I10 r1 r1 r1I11 r3 r3 r3 FiniteI12 r5 r5 r5 ControlI13 r2 r2 r2#I0Token Stack (TS)State Stack (SS)Input TapeAt First, we put # in TS and the initial state I0 in SS. Given an input: aaaabb aaabb#For LRI0, a = s2, Push a in TS; Push I2 in SS. #aI0I2aabb#For LRI2, a = s

48、5,Push a into TS;Push I5 into SS.#I0aI2aI5abb#For LRI5, a = s5,Push a into TS;Push I5 into SS.#I0aI2aI5aI5bb#For LRI5, b = s6,Push b in TS;Push I6 in SS.#I0aI2aI5aI5bI6b#For LRI6, b = r4,Reduce by Rule 4: A b;Push A in TS.AbAFor LRI5, A = 11,Push I11 in SS.I11For LRI11, b = r3,Reduce by Rule 3: A aA

49、;Push A in TS .aI5aI2#I0AaAFor LRI5, A = 11,Push I11 in SS .I11For LRI11, b = r3,Reduce by Rule 3: A aA;Push A in TS .aI2#I0AaAFor LRI2, A = 4,Push I4 in SS.I4For LRI4, b=s10,Push b in TS;:Push I10 in SS.#I0aI1AI4b I10#For LRI10, #=r1,Reduce by Rule 1: S aAbPush S in TS;:#I0SabSFor LRI1, #=acc,So th

50、e string is accepted and the parsing is ended.I1For LRI0, S=1,Push I1 in SS.2022-3-1788用用LR(0)分析算術表達式分析算術表達式S .EE .E+TE .TT .T*FT .FF .(E)F .iI0 S E. E E.+TEI1T F.FF (.E)E .E+TE .TT .T*FT .FF .(E) F .i F i.iI3I4I5(E E+.TT .T*FT .FF .(E) F .i E T. T T.*FTT T* .FF .(E) F .i+I6I7 E ( E.) E E.+TETiI5I3F

51、*(I8 E E+T. T T. * FI5I4TI9Fi(I7* T T* F.I10FiI4(+ E (E).)I11I2?2022-3-1789LR(0) 應用討論應用討論 LR(0) 分析方法的應用范圍還是太窄，它對于大部分的語言都有不太適用，甚至對于經(jīng)常使用的諸如算術表達式之類的語言都有不適用。 這是因為對于大部分的語言的項目的狀態(tài)轉換圖都有存在有沖突。如在表達式的例子中，狀態(tài)I1, I2, I9 都有沖突。2022-3-1790SLR(1) 分析器分析器2022-3-1791LR 分析中的沖突分析中的沖突 移進-規(guī)約：如果在一個狀態(tài)中存在有移進項目和規(guī)約項目，那么就產(chǎn)生了移進規(guī)約沖

52、突。 分析器應該如何來選擇，是移進還是規(guī)約？ 規(guī)約-規(guī)約：如果在一個項目中有多于一個規(guī)約項目，則發(fā)生了規(guī)約-規(guī)約沖突，分析器應該如何來選擇進行規(guī)約?2022-3-1792解決沖突的方法解決沖突的方法 朝前看，根據(jù)事件未來的發(fā)展來決定 或 優(yōu)先級, 先做最重要的或最緊急的事件或 嘗試, 如果可能的話。2022-3-1793解決解決LR(0)的沖突的沖突 根據(jù)Follow 集合，這就是 SLR(1)分析的思想。 根據(jù)超前搜索符號集合, 在構造項目時生成超前搜索符號集合，具有不同超前搜索符號集合的項目被認為是不同的項目。這是 LR(1)分析的思想。 根據(jù)優(yōu)先級：可以根據(jù)產(chǎn)生式的優(yōu)先級。2022-3-

53、1794SLR 分析的基本思想分析的基本思想 (1如果當前符號是 b, 則進行移入; (2)如果當前符號屬于 Follow(A) ，則將 u 歸約為 A; (3)如果當前符號屬于 Follow(B) ，則將 u 歸約為 B; (4) 其它情況為錯誤。 2022-3-1795構造構造 SLR 分析表分析表 加入新的項目 S .S, 得到其項目集記為 I0. 構造其項目集的狀態(tài)轉換圖。 根據(jù)轉換圖構造 SLR 分析表，對于每一個項目： 如果沒有沖突，就按LR(0)的方法去做； 如果有沖突，就根據(jù)SLR分析的思想利用 Follow集合解決。2022-3-1796算術表達式的算術表達式的SLR分析表分

54、析表 I0 *I1 *I2 I3 I4 I5 I6 I7 I8*I9 I10 I11i + * ( ) # E T Fs5 s4 1 2 3I1 中有 S E.和 E E.+ T, 這是沖突， Follow(S)= # 不包括 +, 于是如果當前符號是+, 則移入 + ; 如果當前符號是 # 則接受; 其它情況是出錯。 s6accI2 中有 E T.和 T T.* F, 這是沖突， Follow(E)=+, ), # ，其中沒有 *, 于是如果當前符號是 *,則移入 * ; 如果當前符號是 +, ) 或 # 則用 E T進行規(guī)約，其它情況是出錯。 s7r2r2r2I3 中只有規(guī)約項目 T F.

55、我們可用兩種方式處理，一種是對 Follow(T)=+, ), # 中的符號用填寫 r3 ，其它符號則是錯誤，另外一種方法像 LR(0)一樣，對所有的符號均填入 r3 。 r4 r4 r4 r4 s5 s4 8 2 3r6 r6 r6 r6 s5 s49 3 s5 s4 10 s6 s11I9 中包括 E E+T.和 T T.* F, 是沖突， Follow(E)=+, ), # 不包括 *，所以如果 當前符號是 *, 則移入 * ; 如果當前稱號是 +, )或 # 則用產(chǎn)生式E T規(guī)約; 其它情況則是錯誤。r1 s7 r1 r1r3 r3 r3 r3 r5 r5 r5 r52022-3-17

56、97用優(yōu)先級解決沖突用優(yōu)先級解決沖突 在 OPG分析中，非終極符都沒有什么區(qū)別，所以實際上在下面的文法中 ：E E+E | E*E | (E) | i 是用操作符的優(yōu)先級來分析的。 如何用SLR(1)來分析這個文法? E .EE .E+EE .E*EE .(E)E .iI0EE E.E E.+EE E.*EI1(E (.E)E .E+EE .E*EE .(E)E .iI2iE i.I3+E E+.EE .E+EE .E*EE .(E)E .iI4*E E* .EE .E+EE .E*EE .(E)E .iI5EE ( E.)E E.+EE E.*EI6(iEE E+ E.E E.+EE E.*

57、EI7(I2iI3EE E* E.E E.+EE E.*E(iI8) E (E).I9+I4*+*+*?2022-3-1798用優(yōu)先級解決沖突用優(yōu)先級解決沖突 用優(yōu)先級來解決沖突, SLR(1) 分析表如下： i + * ( ) # EI0 s3 s2 1I1 s4 s5 accI2 s3 s2 6I3 r4 r4 r4 r4I4 s3 s2 7I5 s3 s2 8I6 s4 s5 r1 r1I7 r1 s5 r1 r1I8 r2 r2 r2 r2I9 r3 r3 r3 r32022-3-1799用二義文法用二義文法設 G: SiSeS | iS | a 首先拓廣文法 SS .S.SS .iS

58、eSS .iSS .aS i.SeSS i.SS .iSeSS .iSS .aiS .SSS a.aaS iS.eSS iS.SS iSe.SS i.SS .iSeSS .iS S .aI0I3I1I2iieI4I5aS iSeS.I6S由于 Follow(S) = e, #,我們不能用 Follow(S)來解決 I4中的沖突。 2022-3-17100IF語句的語句的SLR(1) 分析表分析表 i e a # S0 s2 s3 11 acc2 s2 s3 43 r3 r3 4 s5 r25 s2 s3 66 r1 r1如果我們約定在狀態(tài)4中移進的優(yōu)先級比歸約要高，即意味著 else 匹配最近

59、的 if, 我們可得到 SLR(1) 的分析表如下:2022-3-17101LR(1) 分析器分析器2022-3-17102SLR 分析器的問題分析器的問題 SLR 分析器在碰到下列情況時會中止 不能確定是移進還是歸約時有多個可能的歸約時,例如：Sid.Eid.idS .SS .E = ES .idE .E + idE .idFOLLOW(S) = #FOLLOW(E) = #,+,=SiSeS | iS | a2022-3-17103經(jīng)典的經(jīng)典的LR 分析器分析器 問題：問題： FOLLOW 不能夠區(qū)分。回顧SLR的思想，狀態(tài) i 中有項目A 且 a 在 follow(A)中，則用規(guī)則A進行規(guī)約。但是在某些情況下，當狀態(tài) i出現(xiàn)在狀態(tài)棧頂， 活前綴 出現(xiàn)在符號棧頂，但是在右句型中A 后不會跟隨有a。 解決：解決： 在構造項目時用超前搜索符號集 (FIRST集) 來消除這樣的沖突。2022-3-17104超前搜索符集超前搜索符集 在S=*