自下而上分析

《自下而上分析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第五章自下而上語法分析所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號；或者說，從語法樹末端開始，步步向上“歸約”，直到根結(jié)點。5.1自下而上分析法的基本問題5.1.1自下而上分析法的基本思想5.1.2自下而上分析法的基本概念5.1.3規(guī)范歸約5.2算符優(yōu)先分析法5.2.1優(yōu)先關(guān)系5.2.2算符優(yōu)先文法及優(yōu)先表的構(gòu)造5.2.3算符優(yōu)先分析法5.2.4優(yōu)先函數(shù)5.1.1自下而上分析法中的基本思想自下而上分析法是一種“移進(jìn)—歸約”法。這種方法的大意是，用一個寄存符號的先進(jìn)后出棧（符號

2、棧），把輸入符號一個一個地移進(jìn)棧里，當(dāng)棧頂形成某個產(chǎn)生式的一個候選式時，就把棧頂?shù)倪@一部分替換成（歸約為）該產(chǎn)生式的左部符號。5.1自下而上分析基本問題符號棧的使用移進(jìn)-歸約中的動作有4類移進(jìn)：讀入一個符號并把它入棧。歸約：當(dāng)棧中的部分形成一個句柄（棧頂?shù)姆栃蛄校r，對句柄進(jìn)行歸約。接受：當(dāng)棧中的符號僅有#和文法的開始符號時，輸入符號也到達(dá)結(jié)尾的時候，執(zhí)行接受動作。當(dāng)識別程序覺察出錯誤的時候，表明輸入符號串不是句子，進(jìn)行錯誤處理。[例5.1]考慮文法S→aAcBeA→bA→AbB→d把輸入串a(chǎn)bbcde歸約到S。步

3、驟符號棧輸入串動作01234567891011##a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S#Sabbcde#bbcde#bcde#bcde#cde#cde#de#e#e####預(yù)備進(jìn)棧進(jìn)棧歸A→b進(jìn)棧*歸A→Ab進(jìn)棧進(jìn)棧歸B→d進(jìn)棧歸S→aAcBe接受在上例中，每實現(xiàn)一步歸約都是把棧頂?shù)囊淮栍媚硞€產(chǎn)生式的左部符號來代替。棧頂?shù)倪@樣一串符號稱為“可歸約串”。自下而上語法分析的關(guān)鍵問題，精確定義“可歸約串”，對這個概念的不同定義形成了不同的自下而上的分析方法。在算符優(yōu)先分析中，用“最左

4、素短語”來刻畫“可歸約串”，在規(guī)范歸約分析中，用“句柄”來刻畫“可歸約串”。各種不同的自下而上分析法的一個共同的特點是，邊輸入單詞符號（移進(jìn)符號棧），邊歸約。即在從左到右移進(jìn)輸入串的過程中，一旦發(fā)現(xiàn)棧頂呈現(xiàn)可歸約串就立即進(jìn)行歸約。語法分析過程可以用一個語法分析樹表示出來。在自下而上的分析過程中，每一步歸約都可以畫出一棵子樹來，隨著歸約的完成，這些子樹被連成一棵統(tǒng)一的語法分析樹。例如，在例5.1中的移進(jìn)歸約過程中，第3步把棧頂?shù)腷歸約為A時，就得到圖2子樹(a)。第5步得到子樹(b)；第8步得到子樹(c)；第10步歸約

5、后連接各子樹得到(d)所示的最終語法分析樹。面臨的基本問題如何找出進(jìn)行直接歸約的簡單短語？將找到的簡單短語歸約到哪個非終結(jié)符號？返回5.1.2自下而上分析法中的基本概念句型和句子：設(shè)文法G=(Vt,Vn,S,P)，α∈(Vt∪Vn)*，如有，α∈(Vt∪Vn)*，則稱α是文法G的一個句型，如α∈Vt*則稱是文法G的一個句子，也即只含終結(jié)符的句型是一個句子。短語：設(shè)αβ?是文法G的一個句型，如果有：SαA?并且Aβ則稱β是句型αβ?的關(guān)于非終結(jié)符A的一個短語，或稱β是αβ?的一個短語，特別當(dāng)A→β時，β為句型αβ?的一

6、個直接短語，或簡單短語。規(guī)范推導(dǎo)：句子i+i*i在推導(dǎo)序列中每一步推導(dǎo)都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式右部進(jìn)行替換，這樣的推導(dǎo)稱為最右推導(dǎo)。特別我們將最右推導(dǎo)稱為規(guī)范推導(dǎo)，用來表示。E=>E+E=>E+E*E=>E+E*i=>E+i*i=>i+i*i(2.1)就是句子i+i*i的規(guī)范推導(dǎo)，與規(guī)范推導(dǎo)的方向相反，便是規(guī)范歸約的過程。句柄：一個句型的最左直接短語稱為該句型的句柄。一個句型的直接短語可能不止一個，但最左直接短語則是唯一的，將句型中的句柄用產(chǎn)生式左部代替得到新句型，這便是一次規(guī)范歸約，它恰與規(guī)范推導(dǎo)相反

7、。[例5.2]考慮文法E→T

8、E+TT→F

9、T*FF→i

10、(E)關(guān)于句型i1*i2+i3的短語，直接短語，句柄分別為：E=>E+T=>T+T=>T*F+T=>F*F+F=>F*i2+i3=>i1*i2+i3=>i1*i2+F=>i1*i2+i3=>i1*F+i3=>i1*i2+i3故i1，i2，i3都是句型的（直接）短語。其中i1是最左直接短語，即為句柄。分析樹中短語、直接短語、句柄的對應(yīng)關(guān)系：EET*Fi3+Fi1i2TTF(最左)素短語素短語是指這樣的一個短語，它至少含有一個終結(jié)符，并且，除它自身之外不再含任何更

11、小的素短語。所謂最左素短語，是指處于句型最左邊的那個素短語。例如，考慮下列推導(dǎo)中的一個句型：E=>E+T=>T*F+T=>F*F+T=>F*F+F=>F*F+i因為：E=>F*F+F,F=>i，故i是句型的直接短語。E=>E+i,E=>F*F，故F*F是句型的短語。E=>E,E=>F*F+i，故F*F+i是句型的短語。其中，i和F*F都是句型的