【正文】 變化，變化過程終止，宣布分析成功 . 4. 若 ACTION(sm , ai)為 報(bào)錯(cuò) ，則三元式變化過程終止，報(bào)告錯(cuò)誤 . 國防科技大學(xué)計(jì)算機(jī)系 602教研室 LR分析器示例： 文法 G(E)： (1) E→E ＋ T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i 國防科技大學(xué)計(jì)算機(jī)系 602教研室 AC TION GOTO狀態(tài) i + * ( ) E T F0 s5 s4 1 2 31 s6 acc2 r2 s7 r2 r23 r4 r4 r4 r44 s5 s4 8 2 35 r6 r6 r6 r66 s5 s4 9 37 s5 s4 108 s6 s119 r1 s7 r1 r110 r3 r3 r3 r311 r5 r5 r5 r5其 LR分析表為 : 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 假定輸入串為 i*i+i， LR分析器的工作過程 : 步驟 狀態(tài) 符號(hào) 輸入串 (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ì)算機(jī)系 602教研室 步驟 狀態(tài) 符號(hào) 輸入串 (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ì)算機(jī)系 602教研室 ? 定義：對于一個(gè)文法，如果能夠構(gòu)造一張分析表，使得它的每個(gè)入口均是唯一確定的，則這個(gè)文法就稱為 LR文法 。 ? 至于 a b和 a b的情形，只須證明其一。 2 對每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn) (包括出發(fā)點(diǎn)自身 )。由于非終結(jié)符對歸約沒有影響，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧 S。 5 WHILE S[j] a DO 6 BEGIN 7 REPEAT 8 Q:=S[j]。 3. G是算符優(yōu)先文法嗎 ? 國防科技大學(xué)計(jì)算機(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ì)算機(jī)系 602教研室 + * ? ( ) i+*?()i?結(jié)論 : G是算符優(yōu)先文法 ? G的算符優(yōu)先關(guān)系表 國防科技大學(xué)計(jì)算機(jī)系 602教研室 算符優(yōu)先分析算法 ? 可歸約串，句型，短語，直接短語，句柄，規(guī)范歸約。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 運(yùn)算： ?如果棧 STACK不空，就將頂項(xiàng)逐出，記此項(xiàng)為 (Q， a)。 ? ?首先需要對 G的每個(gè)非終結(jié)符 P構(gòu)造兩個(gè)集合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ì)算機(jī)系 602教研室 ?有了這兩個(gè)集合之后，就可以通過檢查每所有終結(jié)符對。 ? 所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找 “ 可歸約串 ” 和進(jìn)行歸約 。 E F F T T T i1 + * E F i3 i2 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 定義：假定 ?是文法 G的一個(gè)句子，我們稱序列 ?n， ?n1， ? ， ?0 是的一個(gè) 規(guī)范歸約 ，如果此序列滿足： 1 ?n= ? 2 ?0為文法的開始符號(hào)，即 ?0=S 3 對任何 i， 0 ? i ? n， ?i1是從 ?i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號(hào)而得到的。 LR分析法：規(guī)范歸約 國防科技大學(xué)計(jì)算機(jī)系 602教研室 歸約 ? 采用 “ 移進(jìn)－歸約 ” 思想進(jìn)行自下而上分析。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。 特別是，如果有 A??,則稱 ?是句型 ???相對于規(guī)則 A? ?的 直接短語 。歸約順序不同，則計(jì)算的順序也不同，結(jié)果也不一樣。 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 。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 數(shù)據(jù)結(jié)構(gòu)： ?布爾數(shù)組 F[P， a]，使得 F[P， a]為真的條件是，當(dāng)且僅當(dāng) a?FIRSTVT(P)。 ? 使用每個(gè)非終結(jié)符 P的 FIRSTVT(P)和LASTVT(P)，就能夠構(gòu)造文法 G的優(yōu)先表。 1 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ò)。要進(jìn)行一些特殊的判斷。 ? 第一個(gè)關(guān)系可從函數(shù)的構(gòu)造直接獲得。 ?我們將指出，如果 f(a)＝ g(b)，則根本不存在優(yōu)先函數(shù)。E 2. S?→Ed 10. A→dd 18. B→dA A→cB B→ 6: E→aA 這樣 ， 便會(huì)有一個(gè)僅含項(xiàng)目S?→S .的狀態(tài) ， 這就是唯一的 “ 接受 ” 態(tài) 。 X?屬于 I}。A}) ={ E→abB 4: A→ccB B→ d d 9: B→cB 2. 若項(xiàng)目 A→ ? B→ ? … ， Bn→ ? 屬于 Ik，則置 ACTION[k,]為“ acc”。T T→ T→T (E) F→F F→ 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? I I2和 I9都含有“移進(jìn)－歸約”沖突。L I1： S?→Si I5： L→i 國防科技大學(xué)計(jì)算機(jī)系 602教研室 R S = i L R * L * * R i i L 活前綴識(shí)別器1203467589國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? SLR在方法中 ,如果項(xiàng)目集 Ii含項(xiàng)目 A??.而且下一輸入符號(hào) a?FOLLOW(A),則狀態(tài) i面臨 a時(shí) ,可選用“用 A??歸約”動(dòng)作。 ? 向前搜索符串僅對歸約項(xiàng)目 [A→ ??, a]對于活前綴 ?是 有效的 ，如果存在規(guī)范推導(dǎo) ? ? ? ??? ?? AS*其中， 1) ?＝ ??； 2) a是 ?的 第一個(gè)符號(hào)，或者 a為 而 ?為 ?。B ?, a]屬于 CLOSURE(I)， B→ ? 是一個(gè)產(chǎn)生式，那么，對于 FIRST(?a) 中的每個(gè)終結(jié)符 b，如果 [B→ ?令每個(gè) Ik的下標(biāo) k為分析表的狀態(tài)，令含有 [S?→ 4. 若 GO(Ik， A)＝ Ij，則置 GOTO[k, A]=j。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 定義：假定 ?是文法 G的一個(gè)句子，我們稱序列 ?n， ?n1， ? ， ?0 是的一個(gè) 規(guī)范歸約 ，如果此序列滿足： 1 ?n= ? 2 ?0為文法的開始符號(hào)，即 ?0=S 3 對任何 i， 0 ? i ? n， ?i1是從 ?i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號(hào)而得到的。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 按上述算法構(gòu)造的分析表，若不存在多重定義的入口 (即，動(dòng)作沖突 )的情形，則稱它是文法 G的一張 規(guī)范的 LR(1)分析表 。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? 動(dòng)作 ACTION和狀態(tài)轉(zhuǎn)換 GOTO構(gòu)造如下： 1. 若項(xiàng)目 [A→ ? 3. 重復(fù)執(zhí)行步驟 2，直至 CLOSURE(I)不再增大為止。 國防科技大學(xué)計(jì)算機(jī)系 602教研室 ? [A→ ?對于任何移進(jìn)或待約項(xiàng)目 [A→ ?因此，在這種情況下，用“ A?? ”歸約不一定合適。R R→=R R→L 國防科技大學(xué)計(jì)算機(jī)系 602教研室 這個(gè)文法的 LR(0)項(xiàng)目集規(guī)范族為： I0： S?→i I