【正文】 i， LR分析器的工作過程 : 步驟 狀態(tài) 符號 輸入串 (1) 0 i*i+i (2) 05 i *i+i (3) 03 F *i+i (4) 02 T *i+i (5) 027 T* i+i (6) 0275 T*i +i (7) 02710 T*F +i (8) 02 T +i (9) 01 E +i (10) 016 E+ i 國防科技大學計算機系 602教研室 步驟 狀態(tài) 符號 輸入串 (11) 0165 E+i (12) 0163 E+F (13) 0169 E+T (14) 01 E (15) 接受 E E * T T + F F F i i i 國防科技大學計算機系 602教研室 ? 定義：對于一個文法，如果能夠構造一張分析表，使得它的每個入口均是唯一確定的，則這個文法就稱為 LR文法 。 ?我們所需證明的是，在這種情況下， f(a)＝g(b)不應成立。 ? 至于 a b和 a b的情形，只須證明其一。 國防科技大學計算機系 602教研室 ? 現在必須證明：若 a b，則 f(a)＝ g(b)；若 a b，則 f(a) g(b)；若 a b，則 f(a) g(b)。 2 對每個結點都賦予一個數，此數等于從該結點出發(fā)所能到達的結點 (包括出發(fā)點自身 )。 ? 優(yōu)點 :便于比較，節(jié)省空間； ? 缺點 :原來不存在優(yōu)先關系的兩個終結符，由于自然數相對應，變成可以比較的。由于非終結符對歸約沒有影響，因此，非終結符根本可以不進符號棧 S。 15 IF S[j] a OR S[j] a THEN 16 BEGIN k:=k+1。 5 WHILE S[j] a DO 6 BEGIN 7 REPEAT 8 Q:=S[j]。 ? 定理：一個算符優(yōu)先文法 G的任何句型的最左素短語是滿足如下條件的最左子串 Njaj…N iaiNi+1， aj1 aj aj aj+1， … ， ai1 ai ai ai+1 國防科技大學計算機系 602教研室 ? 算符優(yōu)先分析算法 ? 使用一個符號棧 S，用它寄存終結符和非終結符， k代表符號棧 S的使用深度。 3. G是算符優(yōu)先文法嗎 ? 國防科技大學計算機系 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????????國防科技大學計算機系 602教研室 + * ? ( ) i+*?()i?結論 : G是算符優(yōu)先文法 ? G的算符優(yōu)先關系表 國防科技大學計算機系 602教研室 算符優(yōu)先分析算法 ? 可歸約串，句型，短語，直接短語，句柄，規(guī)范歸約。 FIRSTVT(P)＝ {a | F[P， a]=TRUE} ? 同理，可構造計算 LASTVT的算法。 國防科技大學計算機系 602教研室 ? 運算： ?如果棧 STACK不空，就將頂項逐出，記此項為 (Q， a)。按其定義，可用下面兩條規(guī)則來構造集合FIRSTVT(P)： 1. 若有產生式 P→a… 或 P→Qa… ，則a?FIRSTVT(P)； 2. 若 a?FIRSTVT(Q)，且有產生式 P→Q… ，則 a?FIRSTVT(P)。 ? ?首先需要對 G的每個非終結符 P構造兩個集合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 ????? ?? 而或 ??國防科技大學計算機系 602教研室 ?有了這兩個集合之后，就可以通過檢查每所有終結符對。對于任何一對終結符 a、 b，我們說： 1. a b 當且僅當文法 G中含有形如P→…ab… 或 P→…aQb… 的產生式； ? 如果一個算符文法 G中的任何終結符對 (a，b)至多只滿足下述三關系之一： a b， a b， a b 則稱 G是一個 算符優(yōu)先文法 。 ? 所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關系，借助于這種關系尋找 “ 可歸約串 ” 和進行歸約 。 ? 歸約即計算表達式的值。 E F F T T T i1 + * E F i3 i2 國防科技大學計算機系 602教研室 ? 定義：假定 ?是文法 G的一個句子，我們稱序列 ?n， ?n1， ? ， ?0 是的一個 規(guī)范歸約 ，如果此序列滿足： 1 ?n= ? 2 ?0為文法的開始符號，即 ?0=S 3 對任何 i， 0 ? i ? n， ?i1是從 ?i經把句柄替換成為相應產生式左部符號而得到的。 核心問題：識別可歸約串 國防科技大學計算機系 602教研室 規(guī)范歸約 ? 定義：令 G是一個文法， S是文法的開始符號，假定 ???是文法 G的一個句型，如果有 且 ?? AS *? ???A則 ?稱是句型 ???相對于非終結符 A的 短語 。 LR分析法：規(guī)范歸約 國防科技大學計算機系 602教研室 歸約 ? 采用 “ 移進－歸約 ” 思想進行自下而上分析。即從樹末端開始，構造語法樹。所謂歸約，是指根據文法的產生式規(guī)則，把產生式的右部替換成左部符號。 ? 基本思想：用一個寄存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當棧頂形成某個產生式的候選式時，即把棧頂的這一部分替換成 (歸約 為 )該產生式的左部符號。 特別是，如果有 A??,則稱 ?是句型 ???相對于規(guī)則 A? ?的 直接短語 。 國防科技大學計算機系 602教研室 把上例倒過來寫，則得到： S ? aAcBe? aAcde ? aAbcde ? abbcde 顯然這是一個最右推導。歸約順序不同，則計算的順序也不同，結果也不一樣。 國防科技大學計算機系 602教研室 ? 首先必須定義任何兩個可能相繼出現的終結符 a與 b的優(yōu)先關系 三種關系 a b a的優(yōu)先級低于 b a b a的優(yōu)先級等于 b a b a的優(yōu)先級高于 b ? 注意：與數學上的 =不同， a b并不意味著 b a 國防科技大學計算機系 602教研室 算符優(yōu)先文法及優(yōu)先表構造 ? 一個文法，如果它的任一產生式的右部都不含兩個相繼 (并列 )的非終結符，即不含如下形式的產生式右部： …QR… 則我們稱該文法為 算符文法 。 2. a b 當且僅當 G中含有形如 P→…aR…的產生式， 而 R b… 或 R Qb… ； ????3. a b 當且僅當 G中含有形如 P→…Rb…的產生式，而 R …a 或 R …aQ 。 ?假定有個產生式的一個候選形為 …aP… 那么，對任何 b?FIRSTVT(P)，有 a b。 國防科技大學計算機系 602教研室 ? 數據結構： ?布爾數組 F[P， a]，使得 F[P， a]為真的條件是，當且僅當 a?FIRSTVT(P)。對于每個形如 P→Q… 的產生式，若 F[P， a]為假，則變其值為真且將 (P， a)推進 STACK棧。 ? 使用每個非終結符 P的 FIRSTVT(P)和LASTVT(P)，就能夠構造文法 G的優(yōu)先表。 ? 一個文法 G的句型的 素短語 是指這樣一個短語，它至少含有一個終結符，并且，除它自身之外不再含任何更小的素短語。 1 k:=1。 9 IF S[j1]?VT THEN j:=j1 ELSE j:=j2 10 UNTIL S[j] Q。S[k]:=a END 17 ELSE ERROR /*調用出錯診察程序 */ 18 UNTIL a=?? 國防科技大學計算機系 602教研室 ? 在算法的工作過程中，若出現 j減 1后的值小于等于 0時，則意味著輸入串有錯。 國防科技大學計算機系 602教研室 ? 算符優(yōu)先分析一般并不等價于規(guī)范歸約。要進行一些特殊的判斷。賦給 fa的數作為 f(a)，賦給 ga的數作為 g(a)。 ? 第一個關系可從函數的構造直接獲得。 國防科技大學計算機系 602教研室 ? 如果 a b，則有從 fa到 gb的弧。 ?我們將指出，如果 f(a)＝ g(b)，則根本不存在優(yōu)先函數。 ? 定義：一個文法，如果能用一個每步頂多向前檢查 k個輸入符號的 LR分析器進行分析，則這個文法就稱為 LR(k)文法 . ? 非 LR結構 ?LR文法不是二義的，二義文法肯定不會是 LR的。E 2. S?→E 6. A→d 10. A→d 14. B→d 18. B→d 國防科技大學計算機系 602教研室 6 7 8 9 10 4 5 3 1 2 11 12 13 14 15 16 18 17 ? ? ? ? ? ? ? a ? ? ? A E b B B c A c d 識別活前綴的 NFA 國防科技大學計算機系 602教研室 識別活前綴的 DFA 0: S?→A A→cA A→cB B→d 11: B→d 6: E→aA 國防科技大學計算機系 602教研室 ? 結論 : 若項目 A?? .B?對活前綴 ?=??是有效的且 B ? ?是一個產生式