編譯原理-自下而上的語(yǔ)法分析-資料下載頁(yè)
2025-05-13 04:33本頁(yè)面
【正文】 ? 12 k:=j+1。 ? 13 S[k]:=N ? 14 END OF WHILE。 ? 15 IF S[j]≮ a OR S[j]≒ a THEN ? 16 BEGIN k:=k+1。 S[k]:=a END ? 17 ELSE ERROR /*調(diào)用出錯(cuò)診察程序 */ ? 18 UNTIL a=‘’ 算符優(yōu)先分析算法 ? 在算法的工作過(guò)程中，若出現(xiàn) j減 1后的值小于等于 0時(shí)，則意味著輸入串有錯(cuò)。在正確的情況下， 算法工作完畢時(shí)，符號(hào)棧 S應(yīng)呈現(xiàn)： N 。 ? 算法的第 11行中的 N是指那樣一個(gè)產(chǎn)生式的左部符號(hào)，此產(chǎn)生式的右部和S[j+1]… S[k] 構(gòu)成如下一一對(duì)應(yīng)關(guān)系：自左至右，終結(jié)符對(duì)終結(jié)符，非終結(jié)符對(duì)非終結(jié)符，而且對(duì)應(yīng)的終結(jié)符相同。由于非終結(jié)符對(duì)歸約沒(méi)有影響，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧 S。 算符優(yōu)先分析算法 ? 算符優(yōu)先分析 一般并 不等價(jià) 于 規(guī)范歸約 E E + * i T P + i P i P i P i E E F + * T i F T F T P + E T i F P P i P 優(yōu)先函數(shù) ? 把每個(gè)終結(jié)符 ?與兩個(gè)自然數(shù) f(?)與 g(?)相對(duì)應(yīng)，使得 ?若 ?1 ≮ ?2，則 f(?1) g(?2) ?若 ?1 ≒ ?2，則 f(?1) = g(?2) ?若 ?1 ≯ ?2，則 f(?1) g(?2) f稱(chēng)為入棧優(yōu)先函數(shù) ， g稱(chēng)為比較優(yōu)先函數(shù) 。 ? 優(yōu)點(diǎn) :便于比較，節(jié)省空間； ? 缺點(diǎn) :原來(lái)不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于自然數(shù)相對(duì)應(yīng)，變成可以比較的。要進(jìn)行一些特殊的判斷。 優(yōu)先函數(shù) ? 文法 G[E] (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i 的優(yōu)先函數(shù)如下表： + * ↑ ( ) i F 2 4 4 0 6 6 0G 1 3 5 5 0 5 0? 有許多優(yōu)先關(guān)系表 不存在優(yōu)先函數(shù) ，如： ? 不存在對(duì)應(yīng)的優(yōu)先函數(shù) f和 g ? 假定存在 f和 g，則有 ? f(a)=g(a)， f(a)g(b)， f(b)=g(a)， f(b)=g(b) ? 導(dǎo)致如下矛盾 : ? f(a) g(b) = f(b) = g(a) = f(a) ? 如果優(yōu)先函數(shù)存在，則不唯一 (無(wú)窮多 ) 優(yōu)先函數(shù) a b a ≒ ≯ b ≒ ≒ ? 如果優(yōu)先函數(shù)存在，則可以通過(guò)以下三個(gè)步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù) : ?1 對(duì)于每個(gè)終結(jié)符 a，令其對(duì)應(yīng)兩個(gè)符號(hào) fa和 ga，畫(huà)一以所有符號(hào) fa和 ga為結(jié)點(diǎn)的方向圖。如果a≯≒b ，則從 fa畫(huà)一條弧至 gb，如果 a≮≒b ，則畫(huà)一條弧從 gb至 fa。 ?2 對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)， 此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn) (包括出發(fā)點(diǎn)自身 )。賦給 fa的數(shù)作為 f(a)，賦給 ga的數(shù)作為 g(a)。 ?3 檢查所構(gòu)造出來(lái)的函數(shù) f和 g是否與原來(lái)的關(guān)系矛盾。若沒(méi)有矛盾，則 f和 g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。 優(yōu)先函數(shù) ? 例 :求文法 G(E) (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i 的終結(jié)符 +， *， ↑ ， i所對(duì)應(yīng)的優(yōu)先函數(shù)。 優(yōu)先函數(shù) 優(yōu)先函數(shù) f+ f* f? fi g+ g* g? gi + * ↑ if 2 4 4 7g 1 3 6 6+ * ↑ i + ≯ ≮ ≮ ≮ * ≯ ≯ ≮ ≮ ↑ ≯ ≯ ≮ ≮ i ≯ ≯ ≯ 練習(xí) ? 1 已知文法 G[S]為： S→a|∧ |(T) T→T,S|S ?(1) 計(jì)算 G[S]的 FIRSTVT和 LASTVT。 ?(2) 構(gòu)造 G[S]的算符優(yōu)先關(guān)系表并說(shuō)明 G[S]是否為算符優(yōu)先文法。 ?(3) 給出輸入串 (a,(a,a))的算符優(yōu)先分析過(guò)程。 ? 文法： S→a|∧ |(T) T→T,S|S ? 展開(kāi)為： S→a S→∧ S→(T) T→T,S T→S ? (1) FIRSTVT LASTVT表 非終結(jié)符 FIRSTVT集 LASTVT集 S { a ∧ ( } { a ∧ ) } T { a ∧ ( , } { a ∧ ) , } ? (2)算符優(yōu)先關(guān)系表如下 : 表中無(wú)多重入口所以是算符優(yōu)先（ OPG）文法 。 a ∧ ( ) , a ∧ ( ) , ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≒ ≯ ≯ ≯≯≮≯≯ ≯ ≯ ≯ ≒ ? (3) 輸入串（ a,(a,a)） 的算符優(yōu)先分析過(guò)程為： 棧 當(dāng)前字符 剩余輸入串 動(dòng)作 ( (a (N (N, (N,( (N,(a (N,(N (N,(N, (N,(N,a (N,(N,N (N,(N (N,(N) (N,N (N (N) N ( a , , ( a , , a ) ) ) ) ) ) a,(a,a)) ,(a,a)) (a,a)) (a,a)) a,a)) ,a)) a)) a)) )) ) ) ) Move in Move in Reduce: S→a Move in Move in Move in Reduce: S→a Move in Move in Reduce: S→a Reduce: T→T,S Move in Reduce: S→(T) Reduce: T→T,S Move in Reduce: S→(T)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1