資源描述：
《ch6自底向上算符優(yōu)先語法分析》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、自底向上算符優(yōu)先語法分析第6章1主要內容：規(guī)范歸約，自上而下的算符優(yōu)先分析方法及其相關概念。重點掌握：掌握自下而上分析的基本思想，規(guī)范規(guī)約的概念及過程；算符優(yōu)先文法、算符優(yōu)先關系的判定，最左素短語、句柄的定義與判定，構造算符優(yōu)先關系表，能用算符優(yōu)先分析法進行表達式分析。6.1自底向上優(yōu)先分析概述2G=({E},{i,+,*,(,)},P,E) P：E?E+EE?E*EE?(E)E?i最左推導：E?E*E?(E)*E?(E+E)*E?(i+E)*E?(i+i)*E?(i+i)*i最右推導：E?E*E?E*i?(E+E)*i?(E+i)*i?(i+i)*i例：判定輸入串(i+i)*i
2、是否是下述文法的句子？結論：自上而下語法分析采用最左推導，每一步推導使用哪個產生式要視當前非終結符匹配輸入字符串中的哪個符號來確定。自下而上語法分析是最右推導的逆過程，由輸入符號串反向推導到文法的開始符號。3自下而上的語法分析實現(xiàn)思想：“移進-歸約”方法設置一個棧，將輸入符號逐個移進棧中，棧頂形成某產生式的右部時(句柄)，就用左部去代替，稱為歸約。重復這一過程，直到棧中只剩下文法的開始符號，就確認輸入串是文法的句子，分析成功，否則出錯。語法樹：從樹葉開始，逐步向上歸約構造分析樹，直到形成根結點。是推導的逆過程。核心尋找句柄進行規(guī)約。用不同的方法尋找句柄，就可獲得不同的分析方法。4
3、最左推導(Left-mostDerive)每一步推導都替換當前句型的最左邊的非終結符。——其逆過程稱為最右歸約最右推導(Right-mostDerive)每一步推導都替換當前句型的最右邊的非終結符?！淠孢^程稱為最左歸約(規(guī)范歸約)，得規(guī)范句型例：設有文法G[S]：(1)S?aAcBe (2)A?b (3)A?Ab (4)B?d使用最右推導：因為SaAcBeaAcdeaAbcdeabbcde，所以abbcde是文法G的句子。5步驟動作(1)S?aAcBe (2)A?b (3)A?Ab (4)B?d最左歸約過程是最右推導的逆過程，對輸入串abbcde的歸約過程如下：該分析過程反復
4、執(zhí)行“移進”和“歸約”兩個動作，直到棧中只有開始符號為止。abAcS1移進aAa移進b4a歸約35cAa移進d7cAa歸約48BcAa移進e910歸約1移進b2a歸約23ab移進c6AadBeA6語法分析樹的生成演示abbcdeAABSA→bA→AbB→dS→aAcBe(1)S?aAcBe (2)A?b (3)A?Ab (4)B?d7規(guī)范歸約分析過程具有如下特點：從輸入串的開始依次讀入單詞(移進棧中)。一旦發(fā)現(xiàn)可歸約串（某個產生式的右端）就立即歸約。歸約就是將棧頂的一串符號用文法產生式的左部代替，歸約可能重復多次。若最終能歸約成文法的開始符號，則分析成功。由于總是將句型的最左邊的
5、可歸約串替換成非終結符，該方法與最右推導對應。關鍵是如何判斷可歸約串？8問題的提出：①在構造語法樹的過程中，何時歸約？當可歸約串出現(xiàn)在棧頂時就進行歸約。②如何知道在棧頂符號串中已經形成可歸約串？如何進行歸約？不同的自下而上的分析方法對可歸約串的定義是不同的，但分析過程的一個共同特點是：邊移進邊歸約。規(guī)范歸約：使用句柄來定義,如簡單優(yōu)先分析算符優(yōu)先分析：使用最左素短語來定義LR分析方法：使用活前綴來定義9規(guī)范歸約的概念有文法G，開始符號為S,如果有S=>xβy,則xβy是文法G的句型，x,y是任意的符號串如果有S=>xAy,且有A=>β,則β是句型xβy相對于非終結符A的短語如果有
6、S=>xAy,且有A->β,則β是句型xβy相對于A->β的直接短語位于一個句型最左邊的直接短語稱為句柄.**+*注意:規(guī)范規(guī)約中每次歸約的部分必須是句柄(最右推導)。關鍵的問題是如何識別句柄10例：考慮如下文法：求句型i1*i2+i3的短語、直接短語和句柄。E?T
7、E+TT?F
8、T*FF?i
9、(E)因此：短語有：i1,i2,i3,i1*i2,i1*i2+i3直接短語有：i1,i2,i3句柄是：i1E=>F*i2+i3E=>i1*F+i3E=>i1*i2+FE=>T+i3（T=>T*F=>i1*i2）E=>i1*i2+i3F?ii2+i3不是短語，因為E=>i1*E（E=>i2+
10、i3）*++++++11從語法分析樹來識別：一棵子樹是由樹的某個結點連同它的所有子孫組成的。子樹的所有端末結點自左至右排列成一個相對子樹根的短語。直接短語：只有父子兩代結點形成的短語。句柄：最左子樹的直接短語。EE+TTFi3i2i1T*FF從語法樹可以看出：i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短語直接短語有：i1,i2,i3句柄是：i1E?T
11、E+TT?F
12、T*FF?i
13、(E)句型i1*i2+i3的語法樹如圖：12對下述文法，求句型E+T*F+
