1、3.4自下而上語法分析，牙齒部分為1 .要熟悉自下而上語法分析的基本思想和基本概念。2.運算符首先理解語法分析3。掌握方向盤的定義和判定4。理解規(guī)范歸屬過程和LR分析過程的實現(xiàn)5。了解LR語法分析的實現(xiàn)過程，示例回顧：簡單的歸化過程，語法設置Abcde，語法樹的自下而上構建過程，文章分析：AB BCDE Abcde Aacde Aacde Acbes，最右側的推導，注意：每個回歸都是句柄，3.4.1如果重復牙齒過程，直到堆棧中只剩下語法的起始符號，分析就會成功。這被稱為“轉入-回藥”方法。從語法樹的角度來看：從語法樹的樹葉開始逐步構建配置分析樹，直到形成根節(jié)點。是推理的逆過程。“移動-減少”分

2、析、移動-減少分析器使用分析堆棧和輸入緩沖區(qū)。1，文章表示法：堆棧內容輸入緩沖區(qū)內容#當前文章模式#，2，分析器結構，“移動-減少”分析的堆棧實現(xiàn)“移動-減少”分析器使用保留堆棧和輸入符號字符串W的緩沖區(qū)。分析器的初始狀態(tài)是：堆棧輸入W操作過程。從左到右將字符串W的符號移動到堆棧中，在堆棧頂部形成可還原字符串(如句柄)時，就承諾了。牙齒減少可能會持續(xù)很多次，直到堆棧頂部不再出現(xiàn)控制柄。然后是堆棧輸入S，2)折疊：當堆棧頂部符號字符串形成可折疊字符串(例如句柄)時，直接折疊(即，將堆棧頂部的句柄替換為結果左側的非終結器)。3)接受：在堆棧底部只有“#”和開始符號，輸入也是在到達右端符號“#”時識

3、別符號字符串是句子，表示分析成功的特殊情況。4)發(fā)生錯誤：堆棧頂部的內容與輸入符號相反。也就是說，如果識別器發(fā)現(xiàn)輸入符號字符串不是句子，則會出錯。注：決定轉入和歸藥的依據(jù)是什么？堆棧頂部是否顯示可收攏的符號字符串。修剪語法樹以演示復合，S，AB，AAB，BD，SAACBE AB | B BD，合同是將堆棧頂部的符號字符串替換到語法生成表達式的左側。合同可以多次重復，也可以繼續(xù)移動。如果最終可以歸于成文法的起始符號，那么分析是成功的。否則，將出現(xiàn)錯誤。牙齒方法通常通過最右側的導數(shù)得到，因為它總是用非終止符替換文章模式最左側的可還原字符串。核心：如何標識可收攏的符號字符串？徐璐通過不同的自下而上分

4、析算法徐璐不同的算法對可還原字符串徐璐有不同的定義，但在分析過程中都有共同的特征。也就是說，邊緣向內，進行邊藥()。(David aser，Northern Exposure(美國電視電視劇，英語)，specification down:使用句柄定義可還原字符串運算符。使用最左側的子面域定義可還原字符串。自下而上語法分析主要有三種茄子簡單的優(yōu)先級分析(規(guī)范減少)語法：根據(jù)特定原則規(guī)定語法符號的優(yōu)先關系。運算符優(yōu)先級分析(非標準返回)指定運算符之間的優(yōu)先級關系。LR分析方法(規(guī)格減少)LR(0)、LR(1)、SLR(1)和LALR(1)。，規(guī)范歸約相關概念復習，語法G，開始符號S，S=xy的話，

5、xy是語法G的文章模式，x，y是任意符號字符串。文章xy的語法，相對于非終結器A(如果S=xAy存在而A=存在)。如果S=xAy且具有a，則為相對于a的文章xy的直接球體。一個文章圖案最左側的直接球體稱為手柄。文章模式語法直接語法句柄*、*、*、*、*、注3360使用規(guī)范減少算法，每個合同部分都是解析為句柄的字符串。因此，規(guī)格回歸中的重要問題將轉換為標識句柄的方法。練習語法如下： EE T | T TT * F | F F F(E)| id分析輸入字符串id*id，提供文章“移動-減少”解析過程。堆棧輸入緩沖區(qū)操作# id id*id#移動#id id*id#減少Fid #F id*id#減少

6、TF #T id*id#減少ET #E id*id#移動# 轉至E=E T=E T * f=E T * id=E f * id=E id * id=T id * id=f id * id=id id * id，轉至回歸分析期間出現(xiàn)的問題以上實例9 收闔-收闔沖突具有兩個可選處理碼，用于收闔堆疊頂部符號。例如，在上述步驟12)中，您可以使用TF承諾，或按TT*F承諾。在各種分析方法中處理沖突的技術不同！3.4.2運算符優(yōu)先級分析，運算符優(yōu)先級分析的想法源于表達式分析，利用相鄰終止符號之間的關系尋找可還原字符串。將文章模式中的結束符號視為“運算符”，并通過運算符之間的優(yōu)先級關系確定文章模式中的“可

7、收縮字符串”。在一個符號字符串中，兩個相鄰的結束符號A和B之間只能有四個茄子優(yōu)先級關系，其中(1) a，B優(yōu)先級相同，記錄為a b。(2) a優(yōu)先于b，寫為a b。(3) a優(yōu)先級低于b，記錄為a b。(4) a和B不能相鄰。也就是說，牙齒字符串不是文章模式(出現(xiàn)錯誤)。如果上述四種茄子關系都不能同時成立，可以根據(jù)終止符號之間的歸約關系進行句法分析。附注：在整個合約過程中起決定性作用的是連接兩個終結器的優(yōu)先關系。1，運算符語法：上/下相關語法G，沒有P，沒有P.QR.如果(P，Q，R是非終結器)，則G是運算符語法。2，定義運算符優(yōu)先級關系：假設GS是沒有算術的運算符語法。對于所有終結器A和B對

8、：a b，對于GS，P.ab.或P.aQb.只有存在的情況下(相同的生產(chǎn)方式)；g表示P.Rb.具有的生成表達式，R=.a或R=.aQ (ab相鄰)，運算符優(yōu)先語法，yes語法ge:ee | e * e | (e)，因為ee，EE*E有*，而ee * e，EE有*，所以運算符優(yōu)先語法不是，3 .運算符優(yōu)先語法運算符方法G的終止符a，b之間可能沒有優(yōu)先級關系。如果有優(yōu)先關系，大部分情況下其中一個成立，G就是運算符優(yōu)先語法。以表格格式表示運算符優(yōu)先級關系表的配置，以及每個結束符號的優(yōu)先級關系。這些表格稱為優(yōu)先順序表格。配置優(yōu)先級關系表的方法根據(jù)定義的手動計算使用算法，F(xiàn)(E)中的(=)，yes語法

9、ge 3360 ee T | T TT * F | F F F F(E)| I查找運算符優(yōu)先級表。終結器#、終結器#、終結器#和與其他終結器A相關的關系： # #、GE的運算符優(yōu)先級關系表：優(yōu)先級表中的空部分是無效關系。同一終結器之間的優(yōu)先級關系不一定是這樣的。如果有A b，則不一定有b a(沒有傳遞性)。運算符優(yōu)先級僅定義相鄰運算符之間的優(yōu)先級關系。a，b相鄰時，b，a不一定相鄰。a，b之間可能沒有優(yōu)先關系。，描述，1，F(xiàn)IRSTVT集合定義：每個非終止符P，F(xiàn)IRSTVT(P)=a|P=a.或P=Qa.針對、aVT、Q VN，根據(jù)以下兩個茄子規(guī)則配置first生成的PR.如果有牙齒并且有a

10、FIRSTVT(R)，則位于a FIRSTVT(P)中。2，LASTVT集合定義：LASTVT(P)=a|P=.a或P=P.aQ、aVT、Q VN和以下兩個茄子規(guī)則構成LASTVT集合：生成P時生成的P.R如果有牙齒并且有aLASTVT (R)，則為a LASTVT (P)。3，如果每個FIRSTVT和LASTVT集(而不是配置優(yōu)先級關系表終結點)已知，則可以配置優(yōu)先級關系表。在生成式的右側.應收帳款.如果，則每個bFIRSTVT(R)都有a b。在生成式的右側.如果存在Rb，則每個aLASTVT(R)集都有a b。如果生成格式等于Pab或PaQb，則存在ab。示例3.11語法ge:ee t

11、| t TT * f | f f f (e) | I試驗性地配置運算符優(yōu)先級表。配置FIRSTVT集。(1)根據(jù)規(guī)則，EE為first vt(E)=；在TT*中，first vt(T)=*；F(和Fi中的FIRSTVT(F)=(，I；(2)根據(jù)規(guī)則，F(xiàn)IRSTVT(F )=(，I和TF為FIRSTVT(T)=*，(，I；FIRSTVT(T)=*，(，I和ET得到FIRSTVT(E)=，*，(，I)。配置LASTVT集。(1)根據(jù)規(guī)則，E T中的last vt(E)=；在T*F中，last vt(T)=*；F)和Fi中的LASTVT(F)=)，I；(2)根據(jù)規(guī)則，LASTVT(F )=)，I和T

12、F為LASTVT(T)=*，)，I；LASTVT(T)=*，)，I和ET得到LASTVT(E)=，*，)，I。ee TT TT * ff (e) | i，3，配置優(yōu)先級關系表。(1)根據(jù)規(guī)則，“(e)”得到()。(2)根據(jù)規(guī)則，E T表示FIRSTVT(T)，即*，(，I；在T*F中，輸入* FIRSTVT(F)或*(，I；F(E (FIRSTVT(E)，即(，*，(，I；(3)根據(jù)規(guī)則，EE為LASTVT(E)，即*，)，I；在TT*中，LASTVT(T) *，即*，)，I *；FE)得到LASTVT(E)，即*，)，I)。GE中的運算符優(yōu)先級關系表：此外，#E#中的# # #；# FIRS

13、TVT(E)或#，*，(，I；LASTVT(E) #，即*，)，i #。通過比較終結符之間的優(yōu)先級關系，實現(xiàn)了運算符優(yōu)先級分析的設計。根據(jù)優(yōu)先級分析的原理：解析器的任務是繼續(xù)移動到輸入符號，識別可還原字符串，并簽訂合同。問題：如何識別可還原字符串？分析的基本方法：根據(jù)優(yōu)先級關系“上”識別可還原字符串的結尾，根據(jù)優(yōu)先級關系“下”識別可還原字符串的頭。分析堆棧保留標識的部分，比較堆棧頂部與下一個輸入符號的關系，如果是可折疊字符串的末尾，則沿著堆棧頂部查找可折疊字符串的頭部，找到后彈出，將其分類為非終結符。附注：各種優(yōu)先關系已經(jīng)存在于優(yōu)先關系表中。分析輸入字符串：I I # # # # # # #

14、# # # # E #，表達式語法ge : ee t | t TT * f | f f f f(E)| I，如您所見，每個回歸都不是句柄最左側的小球：表示文章圖案最左側的小球。回憶：怎么找到小球和最左邊的小球？是表達式語法的文章模式：T * F I查找球體、子球體和最左側的子球體。ee TT tT * Ff (e) | I，短語I，T * F，T * F I像素短語：I，T * F最左邊的像素短語：T * F，運算符語法g之一Ai VT)# n1a 1 n1.ai-1ai、aiai 1；摘要：運算符優(yōu)先級分析過程文章模式的通用格式： # N1 A1 N2 A2.NNA NNNNN1 #(其中ai是終結點，Ni是可選的非終結點)從左到右掃描每個符號，然后依次查看運算符優(yōu)先級表并繼續(xù)移動，直到找到滿足ai ai 1的終結點。從Ai開始向左掃描，直到找到滿足關系aj-1 aj的終結點。牙齒時的NJAJ NJ1 AJ1.子字符串(如NIAI NI 1)是最左邊的像素，必須約定。分析進程結束：分析堆棧中的#S，輸入字符串為#。，k=1；sk=#；Do將以下輸入符號讀取為a:if(sk Vt)j=k else j