編譯原理51-自下而上分析基本問題ppt課件

1、第五章第五章 語法分析語法分析自下而上分析自下而上分析Bottom-up Parsing自下而上語法分析自下而上語法分析優(yōu)先分析法優(yōu)先分析法簡單優(yōu)先分析法簡單優(yōu)先分析法* 算符優(yōu)先分析法算符優(yōu)先分析法LR分析法分析法 YACC第五章第五章 語法分析語法分析5.1 自下而上分析根本問題自下而上分析根本問題5.2 算符優(yōu)先分析算符優(yōu)先分析 5.3 LR分析分析5.4 YACC5.1 自下而上分析根本問題自下而上分析根本問題5.1.1 歸約歸約5.1.2 規(guī)范歸約簡述規(guī)范歸約簡述5.1.3 符號棧的運用和語法樹的表示符號棧的運用和語法樹的表示1. 自下而上分析過程自下而上分析過程2. 自下而上分析面

2、臨的問題自下而上分析面臨的問題1. 自下而上分析過程自下而上分析過程 - 補充例補充例 GS: ScAd Aab Aa識別輸入串識別輸入串 cabd能否該文法的句子能否該文法的句子 ScAdab 自下而上分析過程中的每一步，都是從當(dāng)前串自下而上分析過程中的每一步，都是從當(dāng)前串中選擇一個子串，將它歸約到某個非終結(jié)符號中選擇一個子串，將它歸約到某個非終結(jié)符號, ,該子串稱為該子串稱為“可歸約串可歸約串GS: ScAd Aab AacdabASScAdab2. 自下而上分析面臨的問題自下而上分析面臨的問題 當(dāng)串中的某部分和某個產(chǎn)生式右部匹配時當(dāng)串中的某部分和某個產(chǎn)生式右部匹配時, ,該不該歸約該不該

3、歸約? ? 如何確定如何確定 可歸約串可歸約串?a a不是不是 可歸約串可歸約串 ,ab ,ab是是 可歸約串可歸約串 可歸約串可歸約串最左素短語最左素短語 句柄句柄 算符優(yōu)先分析算符優(yōu)先分析 規(guī)范規(guī)約規(guī)范規(guī)約 如何準確定義如何準確定義 “可歸約串可歸約串 ?本章中心本章中心1. 采用哪一種自下而上分析方法采用哪一種自下而上分析方法?2. 如何定義可歸約串如何定義可歸約串?3. 假設(shè)在當(dāng)前符號串中確定可歸約串假設(shè)在當(dāng)前符號串中確定可歸約串?5.1.1 歸約歸約G:(1) SaAcBe(2) Ab(3) AAb(4) Bd 識別輸入串識別輸入串a(chǎn)bbcde#能否該文法的句子能否該文法的句子 ab

4、bcdeAABSabbcdd e eAABSG:(1) SaAcBe(2) Ab(3) AAb(4) Bd 輸入串輸入串a(chǎn)bbcde#可行的實現(xiàn)方案可行的實現(xiàn)方案: 邊掃描邊掃描, 邊歸約邊歸約最左歸約最左歸約 (規(guī)范歸約規(guī)范歸約)復(fù)習(xí)最左推導(dǎo)、最右推導(dǎo)、最左歸約、復(fù)習(xí)最左推導(dǎo)、最右推導(dǎo)、最左歸約、最右歸約、規(guī)范推導(dǎo)、規(guī)范歸約的概念最右歸約、規(guī)范推導(dǎo)、規(guī)范歸約的概念aG: (1) SaAcBe (2) Ab (3) AAb (4) Bd 輸入串輸入串a(chǎn)bbcde#baAbc何時移進何時移進, ,何時歸約何時歸約? ?歸約誰歸約誰? ? 如何確定如何確定可歸約串可歸約串?aaAaAaAcaAdc

5、aABcaABeS動動作作移移進進移移進進歸歸約約移移進進歸歸約約移移進進歸歸約約歸歸約約移移進進移移進進ab (2) b (3) cd (4) e (1)圖圖5.1 5.1 符號棧的變化符號棧的變化棧頂出現(xiàn)可歸約串即可歸約棧頂出現(xiàn)可歸約串即可歸約 5.1.2 規(guī)范歸約簡述規(guī)范歸約簡述 1. 短語、直接短語、句柄短語、直接短語、句柄 的定義的定義2. 從句型的語法樹上找出句型的短語、從句型的語法樹上找出句型的短語、直接短語、句柄直接短語、句柄 3. 規(guī)范歸約與句柄的關(guān)系規(guī)范歸約與句柄的關(guān)系準確定義規(guī)范歸約過程中的可歸約串準確定義規(guī)范歸約過程中的可歸約串短語短語Phrase S A, 且A ,

6、那么稱是 句型 相對于 非終結(jié)符A 的短語 直接短語直接短語 (簡單短語簡單短語, Simple phrase) S A, 且且A , 那么稱那么稱是是 句型句型 相對于相對于 規(guī)那么規(guī)那么A 的直接短語的直接短語 * *+ +* *句柄句柄 (Handle)一個句型的一個句型的 最左直接短語最左直接短語 稱為該句型的句柄稱為該句型的句柄.1. 定義定義找出句型找出句型 i1*i2+i3 的一切的一切 短語短語, 直接短語直接短語, 句柄句柄 . G:ET | E+TTF | T*FF(E) | iTFEE+T*FTFi1i2i3短語短語: i1, i2, i3, i1*i2, i1*i2+i

7、3 直接短語直接短語: i1, i2, i3, 句柄句柄: i1一棵子樹的一切末端結(jié)點自一棵子樹的一切末端結(jié)點自左至右陳列起來就構(gòu)成一個左至右陳列起來就構(gòu)成一個相對子樹根的短語相對子樹根的短語. .2. 從語法樹中從語法樹中p85 例例5.1p85 例例5.2 找出句型找出句型 E+T*F+i 的一切短語的一切短語, 直接短語直接短語, 句柄句柄G:ET | E+TTF | T*FF(E) | i短語短語: E+T*F+i E+T*F, i , T*F直接短語直接短語: T*F, i 句柄句柄: T*FEE + TFiE + TT * FG:(1) SaAcBe(2) Ab(3) AAb(4)

8、 Bd abbcdeAABSabaAbcaaAaAaAcaAdcaABcaABeS移移進進移移進進歸歸約約移移進進歸歸約約移移進進歸歸約約歸歸約約移移進進移移進進ab (2) b (3) cd (4) e (1)圖圖5.1 5.1 符號棧的變化符號棧的變化規(guī)范歸約過程中的規(guī)范歸約過程中的可歸約串是句柄可歸約串是句柄3. 規(guī)范歸約與句柄的關(guān)系規(guī)范歸約與句柄的關(guān)系規(guī)范歸約準確定義規(guī)范歸約準確定義 P86假定假定是文法是文法G的一個句子的一個句子, 假設(shè)序列假設(shè)序列: n, n-1, , 0 滿足如下條件滿足如下條件, 那么那么 n, n-1, , 0 是一個規(guī)范歸約是一個規(guī)范歸約: (1) n =

9、 是給定的句子是給定的句子 (2) 0 = S 是文法的開場符號是文法的開場符號 (3) 對任何對任何i, 0i n，i-1是從是從i 經(jīng)過把經(jīng)過把 句柄句柄 交換為相應(yīng)文法產(chǎn)生式的左部符號交換為相應(yīng)文法產(chǎn)生式的左部符號 而得到的。而得到的。結(jié)論結(jié)論規(guī)范歸約過程中的可歸約串是句柄規(guī)范歸約過程中的可歸約串是句柄規(guī)范歸約的本質(zhì)規(guī)范歸約的本質(zhì): 在移進的過程中在移進的過程中, 當(dāng)發(fā)當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄就用相應(yīng)的產(chǎn)生式的左現(xiàn)棧頂呈現(xiàn)句柄就用相應(yīng)的產(chǎn)生式的左部符號進展交換部符號進展交換. 規(guī)范歸約的中心問題規(guī)范歸約的中心問題: 如何尋覓或確定如何尋覓或確定一個句型的句柄一個句型的句柄? 5.1.3 符號棧的運用和語法樹的表示符號棧的運用和語法樹的表示abaAbcaaAaAaAcaAdcaABcaABeS移移進進移移進進歸歸約約移移進進歸歸約約移移進進歸歸約約歸歸約約移移進進移移進進ab (2) b (3) cd (4) e (1)abaAbcaaAaAaAcaAdcaABcaABeS移移進進移移進進歸歸約約移移進進歸歸約約移移進進歸歸約約歸歸約約移移進進移移進進ab (2) b (3) cd (4) e (1)GS:ScAd Aab AaScAdab分析過程詳見黑板分析過程詳見黑板移進移進- -歸約分析器歸約分析器: