資源描述：
《編譯原理第五章.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、編譯原理第五章語法分析——自下而上分析第五章語法分析——自下而上分析自上而下分析法(Top-down)自下而上分析法(Bottom-up)南昌航空大學(xué)大學(xué)計算機應(yīng)用系語法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它從文法的開始符號出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找"匹配"的推導(dǎo)。遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個相應(yīng)的子程序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實現(xiàn)對輸入串的識別。預(yù)測分析程序優(yōu)點：直觀、簡單和宜于手工實現(xiàn)。南昌航空大學(xué)大學(xué)
2、計算機應(yīng)用系語法分析的方法：自下而上分析法(Bottom-up)基本思想：從輸入串開始，逐步進行“歸約”，直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。適合分析表達式。LR分析法：規(guī)范歸約南昌航空大學(xué)大學(xué)計算機應(yīng)用系G(E)：E?i
3、E+E
4、E-E
5、E*E
6、E/E
7、(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE南昌航空大學(xué)大學(xué)計算機應(yīng)用系5.1.1歸約采用“移進－歸約”思想進行自
8、下而上分析。基本思想：用一個寄存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當(dāng)棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號。南昌航空大學(xué)大學(xué)計算機應(yīng)用系例：設(shè)文法G(S)：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d試對abbcde進行“移進－歸約”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae南昌航空大學(xué)大學(xué)計算機應(yīng)用系南昌航空大學(xué)大學(xué)計算機應(yīng)用系bdbaceSABA分析樹和語法樹不一定一致。自下
9、而上分析過程：邊輸入單詞符號，邊歸約。核心問題：識別可歸約串南昌航空大學(xué)大學(xué)計算機應(yīng)用系5.1.2規(guī)范歸約定義：令G是一個文法，S是文法的開始符號，假定???是文法G的一個句型，如果有且則?稱是句型???相對于非終結(jié)符A的短語。特別是，如果有A??,則稱?是句型???相對于規(guī)則A??的直接短語。一個句型的最左直接短語稱為該句型的句柄。南昌航空大學(xué)大學(xué)計算機應(yīng)用系考慮文法G(E)：E?T
10、E+TT?F
11、T*FF?(E)
12、i和句型i1*i2+i3：E?E+T?E+F?E+i3?T+i3?T*F+i3?T*i2+i3?F*i2+i3
13、?i1*i2+i3短語：i1，i2，i3，i1*i2，i1*i2+i3直接短語：i1，i2，i3句柄：i1南昌航空大學(xué)大學(xué)計算機應(yīng)用系在一個句型對應(yīng)的語法樹中，以某非終結(jié)符為根的兩代以上的子樹的所有末端結(jié)點從左到右排列就是相對于該非終結(jié)符的一個短語，如果子樹只有兩代，則該短語就是直接短語。EFFTTTi1+*EFi3i2南昌航空大學(xué)大學(xué)計算機應(yīng)用系可用句柄來對句子進行歸約句型歸約規(guī)則abbcde(2)A?baAbcde(3)A?AbaAcde(4)B?daAcBe(1)S?aAcBeS南昌航空大學(xué)大學(xué)計算機應(yīng)用系定義：假定?是
14、文法G的一個句子，我們稱序列?n，?n-1，?，?0是的一個規(guī)范歸約，如果此序列滿足：1?n=?2?0為文法的開始符號，即?0=S3對任何i，0?i?n，?i-1是從?i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號而得到的。南昌航空大學(xué)大學(xué)計算機應(yīng)用系把上例倒過來寫，則得到：S?aAcBe?aAcde?aAbcde?abbcde顯然這是一個最右推導(dǎo)。規(guī)范歸約是關(guān)于是一個最右推導(dǎo)的逆過程最左歸約規(guī)范推導(dǎo)由規(guī)范推導(dǎo)推出的句型稱為規(guī)范句型。南昌航空大學(xué)大學(xué)計算機應(yīng)用系bdbaceSABAdbaceSABAdaceSABaceSABS南昌航空大
15、學(xué)大學(xué)計算機應(yīng)用系5.1.3符號棧的使用和分析樹的表示棧是語法分析的一種基本數(shù)據(jù)結(jié)構(gòu)。’#’作為棧底符號考慮文法G(E)：E?T
16、E+TT?F
17、T*FF?(E)
18、i輸入串為i1*i2+i3，分析步驟為：南昌航空大學(xué)大學(xué)計算機應(yīng)用系步驟符號棧輸入串動作0#i1*i2+i3#預(yù)備1#i1*i2+i3#進2#F*i2+i3#歸，用F→i3#T*i2+i3#歸，用T→F4#T*i2+i3#進G(E)：E?T
19、E+TT?F
20、T*FF?(E)
21、i南昌航空大學(xué)大學(xué)計算機應(yīng)用系步驟符號棧輸入串動作4#T*i2+i3#進5#T*i2+i3#進6
22、#T*F+i3#歸，用F→i7#T+i3#歸，用T→T*F8#E+i3#歸，用E→T9#E+i3#進G(E)：E?T
23、E+TT?F
24、T*FF?(E)
25、i南昌航空大學(xué)大學(xué)計算機應(yīng)用系步驟符號棧輸入串動作9#E+i3#進10#E+i3#進11#E+F#歸，用F→i12#E+T#歸
