語法分析自下而上分析

1、第九講 語法分析—自下而上分析,,1 概念與基本問題,自下而上分析法 ---- 從輸入串開始，逐步進行歸約，直到歸到文法的開始符；或者說，從語法樹的末端開始，步步向上“歸約”，直到根結(jié)點。 算符優(yōu)先分析法 句柄歸約法自上而下 遞歸下降分析法 預(yù)測分析,（1）歸約與分析樹,歸約 “移進—歸約” ---- 將輸入符號一個個地移進到棧里，當棧頂形成某個產(chǎn)生式的一

2、個候選式時，即把棧頂?shù)倪@一部分替換為該產(chǎn)生式的左部符號 E.G. 設(shè)有文法G: (1) S -> aAcBe (2) A -> b (3) A -> Ab (4) B -> d 希望將輸入串a(chǎn)bbcde歸約到S. 解釋P84圖5.1的歸約過程

3、關(guān)鍵概念: 引進可歸約串概念: 句柄 最左素短語,,,b. 分析樹 (分析過程可用一棵樹表示) 等同語法樹：采用規(guī)范歸約方法（句柄歸約）,自下而上分析過程,每步歸約都可畫一棵子樹,隨著歸約的完成,這些子樹被連成一棵統(tǒng)一的樹稱分析樹. 如移進歸約過程 A A B S b

4、 A b d a A c B e b A b d 第3步 5步 8步 第10步

5、 b,,,,,,,,,,,,,,,(2) 規(guī)范歸約,短語 （P85） 例子見P85 設(shè)G是一文法，S是文法的開始符，若???是G的一個句型，如果 S *=> ?A? 且 A +=> ?, 則說?為???相對于非終結(jié)符A的短語. 特別地, 若 A => ?, 則

6、說 ?是句型???相對于規(guī)則 A-> ?的直接短語. 一個句型的最左直接短語稱該句型的句柄.,b. 規(guī)范歸約(最左歸約),設(shè) ? 是文法G的一個句子,我們稱序列?n, ?n-1, …, ?0是?的一個規(guī)范歸約,如果此序列滿足: (1) ?n= ? (2) ?0 為文法開始符,即?0 = S (3) 對任何i(0 < i ?n), ?i-1是從?i經(jīng)把句柄替換 為

7、相應(yīng)產(chǎn)生式的左部符號而得.c. 規(guī)范推導(dǎo)(最右推導(dǎo)) 規(guī)范推導(dǎo)所得句型稱規(guī)范句型d. 規(guī)范歸約是規(guī)范推導(dǎo)的逆過程,e. 句柄和歸約可通過修剪語法樹而得(P87),一個句型的句柄是這個句型的語法樹中最左那棵子樹端末結(jié)的自左至右排列.該子樹只有(而且必須有)父子兩代, 沒有第三代. S S S

8、 S a A c B e a A c B e a A c B e a A c B e A b d A b d d b b為句柄(剪去) 其余類推

9、 S,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,(3) 符號棧的使用與分析樹的表示,分析器工作過程(使用符號棧) P88 初始： 符號棧 輸入串 # ?# 過程：移進、歸約 //反復(fù)進行 終態(tài)：符號棧 輸入串

10、 # S # //S表示開始符號 總之，語法分析對符號棧的使用有四類操作：“移進”、“歸約”、“接受”和“出錯處理”。 移進----由輸入串吃進一個符號到棧中； 歸約----棧頂可歸約串用適當符號去替換； 接受----宣布分析成功?？煽醋魈厥鈿w約形式,,分析樹