【正文】 編譯原理 之 優(yōu)先分析法 華東交通大學軟件學院 萬仲保 第 06章 自底向上優(yōu)先分析法 ?自底向上優(yōu)先分析概述 ?簡單優(yōu)先分析法 ?算符優(yōu)先分析法 自底向上分析方法概述 ? 自底向上分析方法，也稱 移進 歸約 分析法。 ? 實現思想是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，就用該產生式的左部非終結符代替相應右部的文法符號串，這稱為一步歸約。 ? 重復這一過程直到歸約到棧中只剩文法的開始符號時則為分析成功，也就確認輸入串是文法的句子。 ? 示例 a b b c d e 步驟 符號棧 輸入符號串 動作 1） abbcde 移進 2） a bbcde 移進 A 3） ab bcde 歸約 (A→b) 4） aA bcde 移進 A 5） aAb cde 歸約 (A→Ab) 6） aA cde 移進 7） aAc de 移進 B 8） aAcd e 歸約 (B→d) 9） aAcB e 移進 11） S 接受 S 10） aAcBe 歸約 (S→aAcBe) 分析符號串 abbcde是否 G[S]的句子 對輸入串 abbcde的移進 規(guī)約分析過程 S ? aAcBe ? aAcde ? aAbcde ? abbcde 最右推導： 示例 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 簡單優(yōu)先分析法 ? 按照文法符號（包括終結符和非終結符）的優(yōu)先關系確定句柄。 ? 定義 ? 優(yōu)先關系 ? 簡單優(yōu)先文法 ? 優(yōu)先關系矩陣： 表示文法符號之間關系的矩陣。 ? 算法 ? 示例 ?優(yōu)先關系 ? X ?Y： 表示 X、 Y的優(yōu)先關系相同，當且僅當 文法 G中存在產生式 A→ ...XY… ； ? X?Y： 表示 X的優(yōu)先性比 Y的要低 ， 當且僅當文法 G中存在產生式 A→ ...XB...， 且 B Y... ? X?Y： 表示 X的優(yōu)先性比 Y的要高 ， 當且僅當文法 G中存在產生式 A→ ...BD...， 且 B ...X，D Y ?????*優(yōu)先關系的定義 簡單優(yōu)先文法的定義 ? 滿足以下條件的文法是簡單優(yōu)先文法： ? （ 1）在文法符號集 V中，任意兩個符號之間最多只有一種優(yōu)先關系成立； ? （ 2）在文法中任意兩個產生式沒有相同的右部。 簡單優(yōu)先分析法 —— 算法 ? 根據已知優(yōu)先文法構造相應優(yōu)先關系矩陣，并將文法的產生式保存，設置符號棧 S， 算法步驟如下： 1. 將輸入符號串 a1a2a3...an依次逐個存入符號棧S中，直到遇到棧頂符號 ai的優(yōu)先性 .下一個待輸入符號 aj時為止。 2. 棧頂當前符號 ai為句柄尾，由此向左在棧中找句柄的頭符號 ak， 即找到 ak1?ak為止。 3. 由句柄 ak...ai在文法的產生式中查找右部為 ak...ai的產生式，若找到則用相應左部代替句柄，若找不到則為出錯，這時可斷定輸入串不是該文法的句子。 4. 重復上述三步，直到歸約完輸入符號串，棧中只剩文法的開始符號為止。 簡單優(yōu)先文法分析示例 ? 文法 G [S]： ? (1) S → bAb (2) A → (B|a (3) B → Aa) ? 確定文法符號之間的關系 ? 求出文法的簡單優(yōu)先關系矩陣 ? 對輸入串進行分析 （輸入串 b(aa)b ） 確定文法符號之間的關系 1. 求 ?關系： ? 由 (1)： b ?A A ?b ? 由 (2)： (?B ? 由 (3)： A ?a a ?) 2. 求 ?關系： ? 由 (1)(2)： b?( b? a ? 由 (2)(3)： (? A (?( (? a 3. 求 ?關系： ? 由 (1)： B ?b a ?b ) ?b ? 由 (3)： B ?a a ?a ) ?a 求出文法的簡單優(yōu)先關系矩陣 S b A ( B a ) S b = A = = ( = B a = ) = “ ” 用來表示語句括號，其優(yōu)先關系低于所有與其有相鄰關系的文法符號。 對輸入串進行分析 （輸入串 b(aa)b ） 步驟 符號棧 輸入符號串 動作 1） b(aa)b ?b,移進 2） b (aa)b b?(,移進 3） b( aa)b (?a,移進 4） b(a a)b a.a,歸約 A→a 5） b(A a)b A.=a,移進 6） b(Aa )b a.=),移進 7） b(Aa) b ).b,歸約 B→Aa) 8） b(B b B.b,歸約 A→(B 9） bA b A.=b,移進 10） bAb b.,歸約 S→bAb 11） S 接受 S b A ( B a ) S b = A = = (