【正文】 R R→L I3： S→R I4： L→*R R→L L→*R L→i I5： L→i I6： S→L=R R→L L→*R L→i I7： L→*R I9： S→L=R I8： R→L 國防科技大學計算機系 602教研室 R S = i L R * L * * R i i L 活前綴識別器1203467589國防科技大學計算機系 602教研室 ? SLR在方法中 ,如果項目集 Ii含項目 A??.而且下一輸入符號 a?FOLLOW(A),則狀態(tài) i面臨 a時 ,可選用“用 A??歸約”動作。但在有些情況下 ,當狀態(tài) i顯現(xiàn)于棧頂時 ,棧里的 活前綴 未必允許把 ?歸約為 A，因為可能根本就不存在一個形如“ ?Aa”的規(guī)范句型。因此，在這種情況下，用“ A?? ”歸約不一定合適。 ? 如上例 ，當狀態(tài) 2顯現(xiàn)于棧頂而且面臨輸入符號為‘ =?時，實際上不能用對棧頂 L進行歸約，因為這個文法不含“ R=”為前綴的規(guī)范句型。 國防科技大學計算機系 602教研室 規(guī)范 LR分析表的構造 ? 我們需要重新定義項目，使得每個項目都附帶有 k個終結符。每個項目的一般形式是 [A→ ??, a1a2…a k] ，這樣的一個項目稱為一個 LR(k)項目 。項目中的 a1a2…a k 稱為它的 向前搜索符串 (或 展望串 )。 ? 向前搜索符串僅對歸約項目 [A→ ?，a1a2…a k]有意義。對于任何移進或待約項目 [A→ ??, a1a2…a k], ???，搜索符串 a1a2…a k 沒有作用。 國防科技大學計算機系 602教研室 ? 歸約項目 [A→ ?, a1a2…a k]意味著：當它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的 k個輸入符號為 a1a2…a k 時，才可以把棧頂上的 ?歸約為 A。 ? 我們只對 k?1的情形感興趣，向前搜索 (展望 )一個符號就多半可以確定“移進”或“歸約”。 ? 形式上我們說一個 LR(1)項目 [A→ ??, a]對于活前綴 ?是 有效的 ，如果存在規(guī)范推導 ? ? ? ??? ?? AS*其中， 1) ?＝ ??； 2) a是 ?的 第一個符號，或者 a為 而 ?為 ?。 國防科技大學計算機系 602教研室 ? 為構造有效的 LR(1)項目集族我們需要兩個函數(shù) CLOSURE和 GO。 國防科技大學計算機系 602教研室 ? [A→ ?B ?, a]對活前綴 ?＝ ??是 有效的，則對于每個形如 B??的產生式， 對任何b?FIRST(?a)， [B→ ?, b]對 ?也是有效的。 ? 證明：若項目 [A→ ?B ?, a]對 ?＝ ??有效， 則有規(guī)范推導 ?????? aBAaS ??* ??? ?)a(FI R S Tb ?? ?是產生式若 ??B????????? bBbaBS ??? **則是有效的對于項目 ?? ],.[ bB ????? ba *??國防科技大學計算機系 602教研室 ?項目集 I 的閉包 CLOSURE(I)構造方法： 1. I的任何項目都屬于 CLOSURE(I)。 2. 若項目 [A→ ?B ?, a]屬于 CLOSURE(I)， B→ ? 是一個產生式，那么，對于 FIRST(?a) 中的每個終結符 b，如果 [B→ ?, b]原來不在CLOSURE(I)中，則把它加進去。 3. 重復執(zhí)行步驟 2，直至 CLOSURE(I)不再增大為止。 國防科技大學計算機系 602教研室 ? 令 I是一個項目集， X是一個文法符號，函數(shù) GO(I， X)定義為： GO(I， X)＝ CLOSURE(J) 其中 J＝ {任何形如 [A→ ?X?, a]的項目 | [A→ ?X ?, a]?I} 國防科技大學計算機系 602教研室 ? 文法 G?的 LR(1)項目集族 C的構造算法： BEGIN C:={CLOSURE({[S?→S ， ]})}。 REPEAT FOR C中每個項目集 I和 G?的每個符號 X DO IF GO(I， X)非空且不屬于 C， THEN 把 GO(I， X)加入 C中 UNTIL C不再增大 END 國防科技大學計算機系 602教研室 ? 構造 LR(1)分析表的算法。 ?令每個 Ik的下標 k為分析表的狀態(tài)，令含有 [S?→S, ] 的 Ik的 k為分析器的初態(tài)。 國防科技大學計算機系 602教研室 ? 動作 ACTION和狀態(tài)轉換 GOTO構造如下： 1. 若項目 [A→ ?a ?, b]屬于 Ik且 GO(Ik, a)＝ Ij， a為終結符，則置 ACTION[k, a]為 “ sj”。 2. 若項目 [A→ ?， a]屬于 Ik，則置 ACTION[k, a]為 “ rj”；其中假定 A→ ?為文法 G?的第 j個產生式。 3. 若項目 [S?→S, ] 屬于 Ik，則置 ACTION[k, ]為 “ acc”。 4. 若 GO(Ik， A)＝ Ij，則置 GOTO[k, A]=j。 5. 分析表中凡不能用規(guī)則 1至 4填入信息的空白欄均填上“出錯標志”。 國防科技大學計算機系 602教研室 ? 按上述算法構造的分析表，若不存在多重定義的入口 (即，動作沖突 )的情形，則稱它是文法 G的一張 規(guī)范的 LR(1)分析表 。 ? 使用這種分析表的分析器叫做一個 規(guī)范的LR分析器 。 ? 具有規(guī)范的 LR(1)分析表的文法稱為一個LR(1)文法 。 ? LR(1)狀態(tài)比 SLR多， LR(0)?SLR ? LR(1) ?無二義文法 國防科技大學計算機系 602教研室 ? 例 ()的拓廣文法 G( S?) (0) S?→S (1) S→BB (2) B→aB (3) B→b 國防科技大學計算機系 602教研室 LR(1)的項目集 C和函數(shù) GO I0: S’??S, S??BB, B??aB, a/b B? ?b, a/b S I1: S’?S ?, B I2: S?B ? B, B??aB, B? ?b, a I3: B?a?B, a/b B??aB, a/b B? ?b, a/b b I4: B? b ?, a/b B I5: S?BB?, a I6: B?a?B, B??aB, B? ?b, b I7: B? b ?, B I8: B? aB?, a/b a b a I9: B? aB?, B b 國防科技大學計算機系 602教研室 AC TI ON GOTO狀態(tài) a b S B0 s3 s4 1 21 acc2 s6 s7 53 s3 s4 84 r3 r35 r16 s6 s7 97 r38 r2 r29 r2LR(1)分析表為 : 國防科技大學計算機系 602教研室 ? 例 : 按上表對 aabab進行分析 步驟 狀態(tài) 符號 輸入串 0 0 aabab 1 03 a abab 2 033 aa bab 3 0334 aab ab 4 0338 aaB ab 5 038 aB ab 6 02 B ab 7 026 Ba b 8 0267 Baa 9 0269 BaB 10 025 BB 11 01 S acc 國防科技大學計算機系 602教研室 ? 例 : 按上表對 abab進行分析 步驟 狀態(tài) 符號 輸入串 0 0 abab 1 03 a bab 2 034 ab ab 3 038 aB ab 4 02 B ab 5 026 Ba b 6 0267 Bab 7 0269 BaB 8 025 BB 9 01 S acc 國防科技大學計算機系 602教研室 基本概念 ? 定義：令 G是一個文法， S是文法的開始符號，假定 ???是文法 G的一個句型，如果有 且 ?? AS *? ???A則 ?稱是句型 ???相對于非終結符 A的 短語 。 特別是，如果有 A??,則稱 ?是句型 ???相對于規(guī)則 A? ?的 直接短語 。一個句型的最左直接短語稱為該句型的 句柄 。 國防科技大學計算機系 602教研室 ? 定義：假定 ?是文法 G的一個句子，我們稱序列 ?n， ?n1， ? ， ?0 是的一個 規(guī)范歸約 ，如果此序列滿足： 1 ?n= ? 2 ?0為文法的開始符號，即 ?0=S 3 對任何 i， 0 ? i ? n， ?i1是從 ?i經(jīng)把句柄替換成為相應產生式左部符號而得到的。 國防科技大學計算機系 602教研室 作業(yè) ? P133—1， 2， 3 ? P134—5 (1)， (2)， (3), (4) ? P134—8(選作