資源描述：
《編譯原理第五章 語法分析.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、編譯原理第五章語法分析—自下而上分析1自下而上分析法(Bottom-up)基本思想：從輸入串開始，逐步進行“歸約”，直到文法的開始符號。所謂歸約，是指根據文法的產生式規(guī)則，把產生式的右部替換成左部符號。從語法樹的角度看：從語法樹的樹葉開始，逐步向上歸約構造分析樹，直到形成根結點。是推導的逆過程。算符優(yōu)先分析法：按照算符的優(yōu)先關系和結合性質進行語法分析。適合分析表達式。LR分析法：規(guī)范歸約2G(E)：E?i
2、E+E
3、E-E
4、E*E
5、E/E
6、(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE35.1.1歸約采用“移進－歸約
7、”思想進行自下而上分析?；舅枷耄簭妮斎敕柎_始，從左到右進行掃描，將輸入符號逐個移入一個棧中，邊移入邊分析，一旦棧頂符號串形成某個產生式的右部時，就用該產生式的左部非終結符代替，稱為歸約。重復這一過程，直到歸約到棧中只剩下文法的開始符號時，則分析成功，稱為“移進-歸約”方法。5.1自下而上分析基本問題4例：設文法G(S)：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d試對abbcde進行“移進－歸約”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae56b
8、dbaceSABA自下而上分析過程：邊輸入單詞符號，邊歸約。核心問題：識別可歸約串75.1.2規(guī)范歸約定義：令G是一個文法，S是文法的開始符號，假定???是文法G的一個句型，如果有且則?稱是句型???相對于非終結符A的短語。特別是，如果有A??,則稱?是句型???相對于規(guī)則A??的直接短語。一個句型的最左直接短語稱為該句型的句柄。8考慮文法G(E)：E?T
9、E+TT?F
10、T*FF?(E)
11、i和句型i1*i2+i3：E?E+T?E+F?E+i3?T+i3?T*F+i3?T*i2+i3?F*i2+i3?i1*i2+i3短語：i1，i2，i3，
12、i1*i2，i1*i2+i3直接短語：i1，i2，i3句柄：i19短語：在一個句型對應的語法樹中,以某非終結符為根的一棵子樹的所有葉子自左至右排列起來形成一個相對于子樹根的短語。直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號串。句柄：一個句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。EFFTTTi1+*EFi3i2短語：i1，i2，i3，i1*i2，i1*i2+i3直接短語：i1，i2，i3句柄：i110E?E+T?T+T?F+T?a1+T?a1+T*F?a1+F*F?a1+a2*FE+TT
13、,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*Fa1,a2,a1+a2*F,a2*Fa1,a2,a3,a2*a3a1+a2*a3EE+TTFa1T*FFa2a3?a1+a2*a3短語11可用句柄來對句子進行歸約句型歸約規(guī)則abbcde(2)A?baAbcde(3)A?AbaAcde(4)B?daAcBe(1)S?aAcBeS12定義：假定?是文法G的一個句子，我們稱序列?n，?n-1，?，?0是的一個規(guī)范歸約，如果此序列滿足：1?n=?2?0為文法的開始符號，即?0=S3對任何i，0?i?n，?i-
14、1是從?i經把句柄替換成為相應產生式左部符號而得到的。13把上例倒過來寫，則得到：S?aAcBe?aAcde?aAbcde?abbcde顯然這是一個最右推導。規(guī)范歸約是關于是一個最右推導的逆過程最左歸約規(guī)范推導由規(guī)范推導推出的句型稱為規(guī)范句型。14bdbaceSABAdbaceSABAdaceSABaceSABS利用修剪語法樹的方法闡述自下而上分析法15移進-歸約分析器使用了一個分析棧和一個輸入緩沖區(qū)。1、句型表示a1a2a3#………X1X2X3#“移進-歸約”分析程序輸出棧(存放句型前綴)輸入串即：分析棧內容+輸入緩沖區(qū)內容＝#當前句型
15、#一般形式分析棧的內容剩余輸入串初態(tài)：#輸入串#終態(tài)：#S#2、分析器結構5.1.3符號棧的使用和分析樹的表示棧是語法分析的一種基本數據結構。’#’作為棧底符號16３、“移進-歸約”分析法的棧實現(xiàn)“移進–歸約”分析器使用一個棧和一個存放輸入符號串w的緩沖器。分析器的初始狀態(tài)為:棧????????輸入 ??????????＃w＃工作過程：自左至右把串w的符號一一移進棧里，一旦棧頂形成可歸約的串（如句柄）時，就進行歸約。這種歸約可能持續(xù)多次，直至棧頂不再呈現(xiàn)句柄為止。然后，繼續(xù)向棧里移進符號，重復這個過程，直至最終形成如下格局： ??棧???
16、?????輸入 ????????????＃S＃17步驟符號棧輸入串動作0#i1*i2+i3#預備1#i1*i2+i3#進2#F*i2+i3#歸，用F→i3#T*i2+i3#歸，用T→F4#T*
