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