語法分析自下而上分析

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

1、第五章語法分析—自下而上分析內(nèi)容自下而上分析基本問題算符優(yōu)先分析語法分析器的自動產(chǎn)生工具YACC5.1自下而上分析基本問題自下而上分析：從輸入開始，逐步進行“歸約”，直至歸約到文法的開始符號。5.1.1歸約自下而上分析法是一種“移進-歸約”法。基本思想：用一個寄存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當(dāng)棧頂形成某個產(chǎn)生式的候選式時，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號。5.1.1歸約例：設(shè)文法G[S]：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d試對abbcde

2、進行“移進-歸約”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaS5.1.1歸約例：設(shè)文法G[S]：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d試對abbcde進行“移進-歸約”分析。5.1.1歸約分析樹和語法樹不一定一致。自下而上分析過程：邊輸入單詞符號，邊歸約。核心問題：識別可歸約串bdbaceSABA5.1.2規(guī)范歸約簡述定義：令G是一個文法，S是文法的開始符號，假定???是文法G的一個句型，如果有且則?稱是句型???相對于

3、非終結(jié)符A的短語。特別是，如果有A??,則稱?是句型???相對于規(guī)則A??的直接短語。一個句型的最左直接短語稱為該句型的句柄。5.1.2規(guī)范歸約簡述例：文法G[E]：E→E+T

4、TT→T*F

5、FF→(E)

6、–F

7、id考慮文法G[E]上的句子id1+id2*id3。其最右推導(dǎo)和分析樹如圖5.1(a)、(b)所示。分析樹中的葉子與短語、直接短語和句柄有下述關(guān)系。①短語：以非終結(jié)符為根的子樹中所有從左到右排列的葉子；②直接短語：只有父子關(guān)系的樹中所有從左到右排列的葉子(樹高為2)；③句柄：最左邊父子關(guān)系樹中所

8、有從左到右排列的葉子(句柄是唯一的)。圖5.1id1+id2*id3的最右推導(dǎo)、分析樹與短語(a)最右推導(dǎo)；(b)分析樹；(c)短語根據(jù)定義，從文法開始符號經(jīng)過0步推導(dǎo)得到E1，從E1經(jīng)過若干步推導(dǎo)得到id1+id2*id3，所以id1+id2*id3是句型id1+id2*id3相對于E1的短語(其中α和δ均為ε，β是句子的全體)?？紤]推導(dǎo)E1=>E2+id2*id3=>T2+id2*id3=>F1+id2*id3=>id1+id2*id3，id1是相對于非終結(jié)符E2、T2和F1的短語(其中α為ε，δ為

9、+id2*id3)，特別是相對于F1的直接短語，也是句柄。id1+id2不是句型id1+id2*id3中相對于任何非終結(jié)符的短語，因為找不到任何一個非終結(jié)符，它的子樹中的所有葉子構(gòu)成id1+id2。EFFTTTi1+*EFi3i25.1.2規(guī)范歸約簡述例：考慮文法G[E]：E?T

10、E+TT?F

11、T*FF?(E)

12、i和句型i1*i2+i3：在一個句型對應(yīng)的語法樹中，以某非終結(jié)符為根的兩代以上的子樹的所有末端結(jié)點從左到右排列就是相對于該非終結(jié)符的一個短語，如果子樹只有兩代，則該短語就是直接短語。E?E+T?

13、E+F?E+i3?T+i3?T*F+i3?T*i2+i3?F*i2+i3?i1*i2+i3短語：i1，i2，i3，i1*i2，i1*i2+i3直接短語：i1，i2，i3句柄：i15.1.2規(guī)范歸約簡述可用句柄來對句子進行歸約例：設(shè)文法G[S]：(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d句型歸約規(guī)則abbcde(2)A?baAbcde(3)A?AbaAcde(4)B?daAcBe(1)S?aAcBeS5.1.2規(guī)范歸約簡述定義：假定?是文法G的一個句子，我們稱序列?n，?n-1，?，?0是

14、的一個規(guī)范歸約，如果此序列滿足：1?n=?2?0為文法的開始符號，即?0=S3對任何i，0?i?n，?i-1是從?i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號而得到的。5.1.2規(guī)范歸約簡述把上例倒過來寫，則得到：S?aAcBe?aAcde?aAbcde?abbcde顯然這是一個最右推導(dǎo)。規(guī)范歸約是關(guān)于是一個最右推導(dǎo)的逆過程最左歸約規(guī)范推導(dǎo)由規(guī)范推導(dǎo)推出的句型稱為規(guī)范句型。規(guī)范歸約的中心問題：確定句型的句柄。5.1.2規(guī)范歸約簡述最右推導(dǎo)，推導(dǎo)的每一步結(jié)果都是一個右句型。該推導(dǎo)即分析樹“剪句柄”的全過程。圖3.

15、18剪句柄的過程(a)句子；(b)剪去b之后；(c)剪去Abc之后；(d)剪去d之后；(e)開始符號5.1.3符號棧的使用與語法樹的表示從分析樹上直觀地看，“剪句柄”的方法十分簡單。但是若在語法分析器中實現(xiàn)剪句柄，則有兩個問題必須解決：①確定右句型中將要歸約的子串(確定句柄)；②確定如何選擇正確的產(chǎn)生式進行歸約。具體實現(xiàn)采用移進—歸約方法，用一個棧“記住”將要歸約句柄的前綴，并用一個分析表來確定何時棧頂已形成句柄，以及形成句柄后選擇哪個產(chǎn)生