資源描述：
《編譯原理自下而上語法分析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、自下而上語法分析掌握自底相上分析的基本思想，基本概念掌握算符優(yōu)先關(guān)系的判定，求FIRSTVT集,LASTVT集,構(gòu)造算符優(yōu)先關(guān)系表，能運用算符優(yōu)先分析方法進行表達式分析掌握最左素短語、句柄的定義與判定理解規(guī)范規(guī)約與算符優(yōu)先歸約的區(qū)別LR(0)和SLR文法的理解自下而上的語法分析實現(xiàn)思想從輸入符號串開始，從左到右進行掃描，將輸入符號逐個移入一個棧中，邊移入邊分析，一旦棧頂符號串形成某個產(chǎn)生式的右部時，就用該產(chǎn)生式的左部非終結(jié)符代替，稱為歸約。重復(fù)這一過程，直到歸約到棧中只剩下文法的開始符號時，則分析成功，稱為“移
2、進-歸約”方法。從語法樹的角度看：從語法樹的樹葉開始，逐步向上歸約構(gòu)造分析樹，直到形成根結(jié)。是推導的逆過程。核心尋找可歸約串(這是關(guān)鍵)進行規(guī)約。用不同的方法尋找可歸約串，就可獲得不同的分析方法。最左推導(Left-mostDerive)每次推導都替換當前句型的最左邊的非終結(jié)符?！c最右歸約對應(yīng)最右推導(Right-mostDerive)每次推導都替換當前句型的最右邊的非終結(jié)符?！c最左歸約(規(guī)范歸約)對應(yīng)，得規(guī)范句型例：設(shè)有文法G[S]：(1)S?aAcBe(2)A?b (3)A?Ab(4)B?d使用最右
3、推導：因為S=>aAcBe=>aAcde=>aAbcde=>abbcde，所以abbcde是文法G的句子。步驟動作(1)S?aAcBe(2)A?b (3)A?Ab(4)B?d最左歸約過程是最右推導的逆過程，對輸入串a(chǎn)bbcde的歸約過程如下：該分析過程反復(fù)執(zhí)行“移進”和“歸約”兩個動作，直到棧中只有開始符號為止。abaAabAaAacAadcAaBcAaeBcAaS1移進a2移進b3歸約24移進b5歸約36移進c7移進d8歸約49移進e10歸約1語法分析樹的生成演示abbcdeAABSA→bA→AbB→dS→a
4、AcBe(1)S?aAcBe(2)A?b (3)A?Ab(4)B?d這種分析過程具有如下特點：從輸入串的開始依次讀入單詞(移進棧中)。一旦發(fā)現(xiàn)可歸約串(某個產(chǎn)生式的右端)就立即歸約。歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進。若最終能歸約成文法的開始符號，則分析成功。關(guān)鍵是如何判斷可歸約串？問題的提出：①在構(gòu)造語法樹的過程中，何時歸約？當可歸約串出現(xiàn)在棧頂時就進行歸約。②如何知道在棧頂符號串中已經(jīng)形成可歸約串？如何進行歸約？通過不同的自底向上的分析算法來解釋，不同的算法對可歸
5、約串的定義是不同的，但分析過程都有一個共同的特點：邊移進邊歸約。規(guī)范歸約：使用句柄來定義可歸約串。算符優(yōu)先：使用最左素短語來定義可歸約串規(guī)范歸約概念有文法G，開始符號為S,如果有S=>xβy,則xβy是文法G的句型，x,y是任意的符號串如果有S=>xAy,且有A=>β,則β是句型xβy相對于非終結(jié)符A的短語如果有S=>xAy,且有A->β,則β是句型xβy相對于A->β的直接短語位于一個句型最左邊的直接短語稱為句柄。**+*注:每次歸約的部分必須是稱之為句柄的字符串(最右推導)。關(guān)鍵的問題是如何識別句柄例子下面
6、的例子說明作為短語的兩個條件缺一不可。[例]考慮表達式文法：E?T
7、E+TT?F
8、T*FF?i
9、(E)對于句型i*i+i推導E?E+T?E+F?E+i?T+i?T*F+T?T*i+i?F*i+i?i*i+i盡管有E?+i+i但是,i+i并不是該句型的一個短語，因為不存在從E(文法開始符）到i*E的推導。句型的短語和句柄舉例文法：S→(T)
10、εT→S
11、T,S
12、a短語：句型((a),S)S=*>(T,S)T=+>(a)句型((T,S),S)S=*>((T),S)T=+>T,S句型(a,(T),(T,S))直接短語以
13、及句柄：S=*>(T,(T),(T,S))T=>aS=*>(a,S,(T,S))S=>(T)S=*>(a,(T),(T))T=>T,S短語與語法樹的關(guān)系短語：語法樹子樹的葉子結(jié)點組成的符號串。直接短語：語法樹簡單子樹（只有父子兩代）的葉子結(jié)點組成的符號串。句柄：語法樹最左邊簡單子樹的葉子結(jié)點組成的符號串。短語與語法樹關(guān)系的例子句型(a,(T),(T,S))的語法樹：S()TTS,T,S(T)a(T)T,S用句柄對句子abbcde進行歸約用句柄對句子進行歸約的過程與用移進-歸約過程是一致的，使用歸約的產(chǎn)生式及其順
14、序是一致的。句型歸約規(guī)則abbcde(1)S?aAcBe(2)A?b (3)A?Ab(4)B?d(2)A?b(3)A?AbaAbcdeaAcde(4)B?d(1)S?aAcBeaAcBeS規(guī)范歸約的定義假定α是文法G的一個句子，如果序列：αn,αn-1,……,α0(=S)滿足如下條件，則序列αn,αn-1,……,α0是一個規(guī)范歸約:(1)αn=α是給定的句子(2)α0=S是文法的開始符
