【正文】 按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。 LR分析法：規(guī)范歸約 國防科技大學(xué)計算機系 602教研室 歸約 ? 采用 “ 移進－歸約 ” 思想進行自下而上分析。 國防科技大學(xué)計算機系 602教研室 步驟 : 1 2 3 4 5 6 7 8 9 10動作 : 進 a 進 b 歸 (2 ) 進 b 歸 (3 ) 進 c 進 d 歸 (4 ) 進 e 歸 (1 )ed B Bb c c c cb A A A A A A Aa a a a a a a a a S國防科技大學(xué)計算機系 602教研室 b d b a c e S A B A 分析樹和語法樹不一定一致。 核心問題：識別可歸約串 國防科技大學(xué)計算機系 602教研室 規(guī)范歸約 ? 定義：令 G是一個文法， S是文法的開始符號，假定 ???是文法 G的一個句型，如果有 且 ?? AS *? ???A則 ?稱是句型 ???相對于非終結(jié)符 A的 短語 。一個句型的最左直接短語稱為該句型的 句柄 。 E F F T T T i1 + * E F i3 i2 國防科技大學(xué)計算機系 602教研室 ? 定義：假定 ?是文法 G的一個句子，我們稱序列 ?n， ?n1， ? ， ?0 是的一個 規(guī)范歸約 ，如果此序列滿足： 1 ?n= ? 2 ?0為文法的開始符號，即 ?0=S 3 對任何 i， 0 ? i ? n， ?i1是從 ?i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號而得到的。 規(guī)范歸約 是關(guān)于是一個 最右推導(dǎo) 的逆過程 最左歸約 規(guī)范推導(dǎo) 由規(guī)范推導(dǎo)推出的句型稱為 規(guī)范句型 。 ? 歸約即計算表達式的值。 ? 如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進行歸約，則歸約過程是 唯一 的。 ? 所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找 “ 可歸約串 ” 和進行歸約 。 ? 約定： ?a、 b代表任意終結(jié)符； ?P、 Q、 R代表任意非終結(jié)符； ?‘ …? 代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。對于任何一對終結(jié)符 a、 b，我們說： 1. a b 當且僅當文法 G中含有形如P→…ab… 或 P→…aQb… 的產(chǎn)生式； ? 如果一個算符文法 G中的任何終結(jié)符對 (a，b)至多只滿足下述三關(guān)系之一： a b， a b， a b 則稱 G是一個 算符優(yōu)先文法 。 ????國防科技大學(xué)計算機系 602教研室 ? 優(yōu)先關(guān)系表 + * ↑ i ( ) +*?i()國防科技大學(xué)計算機系 602教研室 ? 從算符優(yōu)先文法 G構(gòu)造優(yōu)先關(guān)系表的算法。 ? ?首先需要對 G的每個非終結(jié)符 P構(gòu)造兩個集合FIRSTVT(P)和 LASTVT(P)： F I R S T V T P a P a P Qa a V Q VT N( ) { | , , }? ? ? ? ?? ?? ?或 而},|{)( NT VQVaaQPaPaPL AS T VT ????? ?? 而或 ??國防科技大學(xué)計算機系 602教研室 ?有了這兩個集合之后，就可以通過檢查每所有終結(jié)符對。 ?假定有個產(chǎn)生式的一個候選形為 …Pb… 那么，對任何 a?LASTVT(P)，有 a b。按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P)： 1. 若有產(chǎn)生式 P→a… 或 P→Qa… ，則a?FIRSTVT(P)； 2. 若 a?FIRSTVT(Q)，且有產(chǎn)生式 P→Q… ，則 a?FIRSTVT(P)。開始時，按上述的規(guī)則 (1)對每個數(shù)組元素 F[P， a]賦初值。 國防科技大學(xué)計算機系 602教研室 ? 運算： ?如果棧 STACK不空，就將頂項逐出，記此項為 (Q， a)。 ?上述過程必須一直重復(fù)，直至棧 STACK拆空為止。 FIRSTVT(P)＝ {a | F[P， a]=TRUE} ? 同理，可構(gòu)造計算 LASTVT的算法。構(gòu)造優(yōu)先表的算法是： 國防科技大學(xué)計算機系 602教研室 FOR 每條產(chǎn)生式 P→X 1X2…X n DO FOR i:=1 TO n1 DO BEGIN IF Xi和 Xi+1均為終結(jié)符 THEN 置 Xi Xi+1 IF i?n2且 Xi和 Xi+2都為終結(jié)符 但 Xi+1為非終結(jié)符 THEN 置 Xi Xi+2； IF Xi為終結(jié)符而 Xi+1為非終結(jié)符 THEN FOR FIRSTVT(Xi+1)中的每個 a DO 置 Xi a； IF Xi為非終結(jié)符而 Xi+1為終結(jié)符 THEN FOR LASTVT(Xi)中的每個 a DO 置 a Xi+1 END 國防科技大學(xué)計算機系 602教研室 ? 例 : 考慮下面的文法 G(E)： (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i 1. 計算文法 G的 FIRSTVT和 LASTVT。 3. G是算符優(yōu)先文法嗎 ? 國防科技大學(xué)計算機系 602教研室 + * ? ( ) iE √ √ √ √ √T √ √ √ √F √ √ √P √ √}{ ( ,)(}(,*,{)(}(,{)(}(,{ *,)(iPF I R ST V TiEF I R ST V TiFF 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é)計算機系 602教研室 + * ? ( ) i+*?()i?結(jié)論 : G是算符優(yōu)先文法 ? G的算符優(yōu)先關(guān)系表 國防科技大學(xué)計算機系 602教研室 算符優(yōu)先分析算法 ? 可歸約串，句型，短語，直接短語，句柄，規(guī)范歸約。 ? 最左素短語 是指處于句型最左邊的那個素短語。 ? 定理：一個算符優(yōu)先文法 G的任何句型的最左素短語是滿足如下條件的最左子串 Njaj…N iaiNi+1， aj1 aj aj aj+1， … ， ai1 ai ai ai+1 國防科技大學(xué)計算機系 602教研室 ? 算符優(yōu)先分析算法 ? 使用一個符號棧 S，用它寄存終結(jié)符和非終結(jié)符， k代表符號棧 S的使用深度。 S[k]:=??。 5 WHILE S[j] a DO 6 BEGIN 7 REPEAT 8 Q:=S[j]。 國防科技大學(xué)計算機系 602教研室 11 把 S[j+1]…S[k] 歸約為某個 N； 12 k:=j+1。 15 IF S[j] a OR S[j] a THEN 16 BEGIN k:=k+1。在正確的情況下，算法工作完畢時，符號棧S應(yīng)呈現(xiàn)： N 。由于非終結(jié)符對歸約沒有影響，因此，非終結(jié)符根本可以不進符號棧 S。 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é)計算機系 602教研室 ? 算符優(yōu)先分析法特點： ?優(yōu)點 : 簡單，快速 ?缺點 : 可能錯誤接受非法句子，能力有限 . ? 算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。 ? 優(yōu)點 :便于比較，節(jié)省空間； ? 缺點 :原來不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于自然數(shù)相對應(yīng)，變成可以比較的。 國防科技大學(xué)計算機系 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é)計算機系 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é)計算機系 602教研室 ? 如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù) : 1 對于每個終結(jié)符 a，令其對應(yīng)兩個符號 fa和 ga，畫一以所有符號和為結(jié)點的方向圖。 2 對每個結(jié)點都賦予一個數(shù)，此數(shù)等于從該結(jié)點出發(fā)所能到達的結(jié)點 (包括出發(fā)點自身 )。 3 檢查所構(gòu)造出來的函數(shù) f和 g是否與原來的關(guān)系矛盾。 國防科技大學(xué)計算機系 602教研室 ? 現(xiàn)在必須證明：若 a b，則 f(a)＝ g(b)；若 a b，則 f(a) g(b)；若 a b，則 f(a) g(b)。因為，若 a b，則既有從 fa到 gb的弧，又有從 gb到 fa的弧。 ? 至于 a b和 a b的情形，只須證明其一。也就是，gb能到達的任何結(jié) fa也能到達。 ?我們所需證明的是，在這種情況下， f(a)＝g(b)不應(yīng)成立。假若 f(a)＝ g(b)，那么必有如下的回路： 國防科技大學(xué)計算機系 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) 從而