【正文】 串進(jìn)行分析 （輸入串 b(aa)b ） 確定文法符號(hào)之間的關(guān)系 1. 求 ?關(guān)系： ? 由 (1)： b ?A A ?b ? 由 (2)： (?B ? 由 (3)： A ?a a ?) 2. 求 ?關(guān)系： ? 由 (1)(2)： b?( b? a ? 由 (2)(3)： (? A (?( (? a 3. 求 ?關(guān)系： ? 由 (1)： B ?b a ?b ) ?b ? 由 (3)： B ?a a ?a ) ?a 求出文法的簡單優(yōu)先關(guān)系矩陣 S b A ( B a ) S 3. 由句柄 ak...ai在文法的產(chǎn)生式中查找右部為 ak...ai的產(chǎn)生式，若找到則用相應(yīng)左部代替句柄，若找不到則為出錯(cuò)，這時(shí)可斷定輸入串不是該文法的句子。 簡單優(yōu)先分析法 —— 算法 ? 根據(jù)已知優(yōu)先文法構(gòu)造相應(yīng)優(yōu)先關(guān)系矩陣，并將文法的產(chǎn)生式保存，設(shè)置符號(hào)棧 S， 算法步驟如下： 1. 將輸入符號(hào)串 a1a2a3...an依次逐個(gè)存入符號(hào)棧S中，直到遇到棧頂符號(hào) ai的優(yōu)先性 .下一個(gè)待輸入符號(hào) aj時(shí)為止。 ? 定義 ? 優(yōu)先關(guān)系 ? 簡單優(yōu)先文法 ? 優(yōu)先關(guān)系矩陣： 表示文法符號(hào)之間關(guān)系的矩陣。 ? 重復(fù)這一過程直到歸約到棧中只剩文法的開始符號(hào)時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。編譯原理 之 優(yōu)先分析法 華東交通大學(xué)軟件學(xué)院 萬仲保 第 06章 自底向上優(yōu)先分析法 ?自底向上優(yōu)先分析概述 ?簡單優(yōu)先分析法 ?算符優(yōu)先分析法 自底向上分析方法概述 ? 自底向上分析方法，也稱 移進(jìn) 歸約 分析法。 ? 實(shí)現(xiàn)思想是對輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄時(shí)，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱為一步歸約。 ? 示例 a b b c d e 步驟 符號(hào)棧 輸入符號(hào)串 動(dòng)作 1） abbcde 移進(jìn) 2） a bbcde 移進(jìn) A 3） ab bcde 歸約 (A→b) 4） aA bcde 移進(jìn) A 5） aAb cde 歸約 (A→Ab) 6） aA cde 移進(jìn) 7） aAc de 移進(jìn) B 8） aAcd e 歸約 (B→d) 9） aAcB e 移進(jìn) 11） S 接受 S 10） aAcBe 歸約 (S→aAcBe) 分析符號(hào)串 abbcde是否 G[S]的句子 對輸入串 abbcde的移進(jìn) 規(guī)約分析過程 S ? aAcBe ? aAcde ? aAbcde ? abbcde 最右推導(dǎo)： 示例 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 簡單優(yōu)先分析法 ? 按照文法符號(hào)（包括終結(jié)符和非終結(jié)符）的優(yōu)先關(guān)系確定句柄。 ? 算法 ? 示例 ?優(yōu)先關(guān)系 ? X ?Y： 表示 X、 Y的優(yōu)先關(guān)系相同，當(dāng)且僅當(dāng) 文法 G中存在產(chǎn)生式 A→ ...XY… ； ? X?Y： 表示 X的優(yōu)先性比 Y的要低 ， 當(dāng)且僅當(dāng)文法 G中存在產(chǎn)生式 A→ ...XB...， 且 B Y... ? X?Y： 表示 X的優(yōu)先性比 Y的要高 ， 當(dāng)且僅當(dāng)文法 G中存在產(chǎn)生式 A→ ...BD...， 且 B ...X，D Y ?????*優(yōu)先關(guān)系的定義 簡單優(yōu)先文法的定義 ? 滿足以下條件的文法是簡單優(yōu)先文法： ? （ 1）在文法符號(hào)集 V中，任意兩個(gè)符號(hào)之間最多只有一種優(yōu)先關(guān)系成立； ? （ 2）在文法中任意兩個(gè)產(chǎn)生式?jīng)]有相同的右部。 2. 棧頂當(dāng)前符號(hào) ai為句柄尾，由此向左在棧中找句柄的頭符號(hào) ak， 即找到 ak1?ak為止。 4. 重復(fù)上述三步，直到歸約完輸入符號(hào)串，棧中只剩文法的開始符號(hào)為止。 b A = ( B a = “ ” 用來表示語句括號(hào)，其優(yōu)先關(guān)系低于所有與其有相鄰關(guān)系的文法符號(hào)。 b A = ( B a = 文法 G[S]： (1) S → bAb (2) A → (B|a (3) B → Aa) 算符優(yōu)先分析法 ? 某些文法具有“算符”特性 ? 表達(dá)式運(yùn)算符（優(yōu)先級、結(jié)合性）； ? 人為地規(guī)定其算符的優(yōu)先順序，即給出優(yōu)先級別和同一級別的結(jié)合性； ? 只考慮算符之間的優(yōu)先關(guān)系來確定句柄。 ? 性質(zhì) ? 1：在算符文法中任何句型都不包含兩個(gè)相鄰的非終結(jié)符。（ 反證法 ） 用歸納法 ? 設(shè) ?是句型，即 S?*? ? S=ω0 ?ω1 ?...?ωn1 ?ωn=? ? 推導(dǎo)長度為 n， 歸納起點(diǎn) n=1時(shí)， ? S=ω0?ω1=? ， 即 S ??， 必存在產(chǎn)生式 S→?， 而由算符文法的定義，文法的產(chǎn)生式中無相鄰的非終結(jié)符，顯然滿足性質(zhì) 1。 ? 若 ωn1= ?A?， A為非終結(jié)符。 ? 又若 A→?是文法的產(chǎn)生式，則有 ? ωn1 ?ωn=???= ? ? 而 A→?是文法的原產(chǎn)生式，不含兩個(gè)相鄰的非終結(jié)符，所以???也不含兩個(gè)相鄰的非終結(jié)符。證畢。 ? 注意：含 b的短語必含 A， 含 A的短語不一定含 b。 ? a?b 當(dāng)且僅當(dāng) G中有形如 A? …aB… 的產(chǎn)生式 ,且B?+b… 或 B?+ Cb… ? a?b 當(dāng)且僅當(dāng) G中有形如 A?…Bb… 的產(chǎn)生式 ,且 B?+…a或 B?… aC ? 注意： ? 算符優(yōu)先關(guān)系中不存在遞推關(guān)系，即 a?b b?c ? a?c或 a?b b?c ? a?c或 a?b b?c ? a?c ? 優(yōu)先關(guān)系的語法樹表示方式 優(yōu)先關(guān)系的語法樹表示方式 算符優(yōu)先文法的定義 ? 設(shè) G是不含 ?產(chǎn)生式的算符文法 ,如果對任意兩個(gè)終結(jié)符對 a、 b之間 至多只有一種 算符優(yōu)先關(guān)系存在，則稱 G 為算符優(yōu)先文法 。 算符優(yōu)先關(guān)系表的構(gòu)造 ? 集合的定義： ? FIRSTVT(B)={b|B ?+ b… 或 B ?+ Cb...} ? 對于非終結(jié)符 B， 其往下推導(dǎo)所可能出現(xiàn)的首個(gè)算符（終結(jié)符） ? LASTVT(B)={a|B ?+ … a 或 B ?+... aC} ? 對于非終結(jié)符 B， 其往下推導(dǎo)所可能出現(xiàn)的最后一個(gè)算符（終