【正文】 iFF I R ST V TiTF I R ST V T????????+ * ? ( ) iE √ √ √ √ √T √ √ √ √F √ √ √P √ √}{ ) ,)(}),*,{)(}),{)(}),{ *,)(iPL A ST V TiEL A ST V TiFL A ST V TiTL A ST V T????????國防科技大學(xué)計(jì)算機(jī)系 602教研室 + * ? ( ) i+*?()i?結(jié)論 : G是算符優(yōu)先文法 ? G的算符優(yōu)先關(guān)系表 國防科技大學(xué)計(jì)算機(jī)系 602教研室 算符優(yōu)先分析算法 ? 可歸約串，句型，短語，直接短語，句柄，規(guī)范歸約。 ? 一個(gè)文法 G的句型的 素短語 是指這樣一個(gè)短語，它至少含有一個(gè)終結(jié)符，并且，除它自身之外不再含任何更小的素短語。 ? 最左素短語 是指處于句型最左邊的那個(gè)素短語。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 考慮下面的文法 G(E)： (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i E E F + * T i F T F T P + E T P 句型： T+F*P+i 短語： T+F*P+i, T, F， P, F*P, i, T+F*P 直接短語： T, F, P, i 句柄： T 素短語： F*P, i 最左素短語： F*P 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 算符優(yōu)先文法句型 (括在兩個(gè)＃之間 )的一般形式寫成： N1a1N2a2…N nanNn+1 其中，每個(gè) ai都是終結(jié)符， Ni是可有可無的非終結(jié)符。 ? 定理：一個(gè)算符優(yōu)先文法 G的任何句型的最左素短語是滿足如下條件的最左子串 Njaj…N iaiNi+1， aj1 aj aj aj+1， … ， ai1 ai ai ai+1 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 算符優(yōu)先分析算法 ? 使用一個(gè)符號棧 S，用它寄存終結(jié)符和非終結(jié)符， k代表符號棧 S的使用深度。 1 k:=1。 S[k]:=??。 2 REPEAT 3 把下一個(gè)輸入符號讀進(jìn) a中； 4 IF S[k]?VT THEN j:=k ELSE j:=k1。 5 WHILE S[j] a DO 6 BEGIN 7 REPEAT 8 Q:=S[j]。 9 IF S[j1]?VT THEN j:=j1 ELSE j:=j2 10 UNTIL S[j] Q。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 11 把 S[j+1]…S[k] 歸約為某個(gè) N； 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=?? 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 在算法的工作過程中，若出現(xiàn) j減 1后的值小于等于 0時(shí)，則意味著輸入串有錯(cuò)。在正確的情況下，算法工作完畢時(shí)，符號棧S應(yīng)呈現(xiàn)： N 。 ? 算法的第 11行中的 N是指那樣一個(gè)產(chǎn)生式的左部符號，此產(chǎn)生式的右部和S[j+1]…S[k] 構(gòu)成如下一一對應(yīng)關(guān)系：自左至右，終結(jié)符對終結(jié)符，非終結(jié)符對非終結(jié)符，而且對應(yīng)的終結(jié)符相同。由于非終結(jié)符對歸約沒有影響，因此，非終結(jié)符根本可以不進(jìn)符號棧 S。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約。 E E + * i T P + i P i P i P E E F + * T i F T F T P + E T i F P i P i P 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 算符優(yōu)先分析法特點(diǎn)： ?優(yōu)點(diǎn) : 簡單，快速 ?缺點(diǎn) : 可能錯(cuò)誤接受非法句子，能力有限 . ? 算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。 ?用于分析各類表達(dá)式 ?ALGOL 60 國防科技大學(xué)計(jì)算機(jī)系 602教研室 優(yōu)先函數(shù) ? 把每個(gè)終結(jié)符 ?與兩個(gè)自然數(shù) f(?)與 g(?)相對應(yīng)，使得 若 ?1 ?2，則 f(?1) g(?2) 若 ?1 ?2，則 f(?1) = g(?2) 若 ?1 ?2，則 f(?1) g(?2) f稱為入棧優(yōu)先函數(shù)， g稱為比較優(yōu)先函數(shù)。 ? 優(yōu)點(diǎn) :便于比較，節(jié)省空間； ? 缺點(diǎn) :原來不存在優(yōu)先關(guān)系的兩個(gè)終結(jié)符，由于自然數(shù)相對應(yīng)，變成可以比較的。要進(jìn)行一些特殊的判斷。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 文法 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國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 有許多優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)，如： a bab 不存在對應(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ù)存在，則不唯一 (無窮多 ) 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 如果優(yōu)先函數(shù)存在，則可以通過以下三個(gè)步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù) : 1 對于每個(gè)終結(jié)符 a，令其對應(yīng)兩個(gè)符號 fa和 ga，畫一以所有符號和為結(jié)點(diǎn)的方向圖。如果 a b，則從 fa畫一條弧至 gb，如果 a b，則畫一條弧從 gb至 fa 。 2 對每個(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)造出來的函數(shù) f和 g是否與原來的關(guān)系矛盾。若沒有矛盾，則 f和 g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 現(xiàn)在必須證明：若 a b，則 f(a)＝ g(b)；若 a b，則 f(a) g(b)；若 a b，則 f(a) g(b)。 ? 第一個(gè)關(guān)系可從函數(shù)的構(gòu)造直接獲得。因?yàn)?，?a b，則既有從 fa到 gb的弧，又有從 gb到 fa的弧。所以， fa和 gb所能到達(dá)的結(jié)是全同的。 ? 至于 a b和 a b的情形，只須證明其一。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 如果 a b，則有從 fa到 gb的弧。也就是，gb能到達(dá)的任何結(jié) fa也能到達(dá)。因此，f(a)? g(b)。 ?我們所需證明的是，在這種情況下， f(a)＝g(b)不應(yīng)成立。 ?我們將指出，如果 f(a)＝ g(b)，則根本不存在優(yōu)先函數(shù)。假若 f(a)＝ g(b)，那么必有如下的回路： 國防科技大學(xué)計(jì)算機(jī)系 602教研室 因此有 a b, a1 b, a1 b1, …, a m bm, a bm 對任何優(yōu)先函數(shù) f?和 g?來說，必定有 f?(a) g?(b)? f?(a1)? g?(b1)? … ? f?(am)? g?(bm)? f?(a) 從而導(dǎo)致 f?(a) f?(a)，產(chǎn)生矛盾。因此，不存在優(yōu)先函數(shù) f和 g。 fa1 fa fam gb1 gb gbm … … 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 例 :取前面文法 G(E) (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i 的終結(jié)符 +， *， ↑ ， i 國防科技大學(xué)計(jì)算機(jī)系 602教研室 + * ? i+*?if+ f* f? fi g+ g* g? gi + * ↑ if 2 4 4 7g 1 3 6 6國防科技大學(xué)計(jì)算機(jī)系 602教研室 LR分析法 ? LR分析法： 1965年 由 Knuth提出 分析表產(chǎn)生器 文法 分析表 輸入 輸出 ? 產(chǎn)生分析表 ? LR分析器工作 LR分析總 控程 序 分析表 國防科技大學(xué)計(jì)算機(jī)系 602教研室 主要介紹 1. 總控程序 (LR分析器 )的處理思想 2. LR分析表的構(gòu)造方法及原理 國防科技大學(xué)計(jì)算機(jī)系 602教研室 LR分析器 ?規(guī)范歸約 的關(guān)鍵問題是尋找 句柄 . ?“歷史”：已移入符號棧的內(nèi)容 ?“展望”：根據(jù)產(chǎn)生式推測未來可能遇到的輸入符號 ?“現(xiàn)實(shí)”：當(dāng)前的輸入符號 X n 輸入串 ? X 2 a ?? X 1 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? LR分析方法：把 歷史 及 展望 綜合抽象成狀態(tài)；由棧頂?shù)臓顟B(tài)和現(xiàn)行的輸入符號唯一確定每一步工作 LR分析 程 序 狀態(tài) 符號 SmXm? ?S1X1S0分析棧 action goto LR分析表 a1a2? ai ? an 輸入串 輸出 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? LR分析器的核心是一張分析表： ?ACTION[s， a]：當(dāng)狀態(tài) s面臨輸入符號 a時(shí)，應(yīng)采取什么動(dòng)作 . ?GOTO[s， X]：狀態(tài) s面對文法符號 X時(shí)，下一狀態(tài)是什么 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 每一項(xiàng) ACTION[s， a]所規(guī)定的四種動(dòng)作 : 1. 移進(jìn) 把 (s， a)的下一狀態(tài) s?和輸入符號 a推進(jìn)棧，下一輸入符號變成現(xiàn)行輸入符號 . 2. 歸約 指用某產(chǎn)生式 A??進(jìn)行歸約 . 假若 ?的長度為 r， 歸約動(dòng)作是， 去除棧頂 r個(gè)項(xiàng)，使?fàn)顟B(tài) smr變成棧頂狀態(tài)，然后把 (smr, A)的下一狀態(tài) s?=GOTO[smr, A]和文法符號 A推進(jìn)棧 . 3. 接受 宣布分析成功，停止分析器工作 . 4. 報(bào)錯(cuò)