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