【文章內(nèi)容簡介】 ? [S]= ? ? [A]=a+[A] ? [B]=aAc 令 ?={[S’]， [S]， [A]， [B]， a，A,c} 則方程兩邊都是 ?上的正規(guī)式 而 [A]=a+[A] 即為 [A]=a | [A] 由正規(guī)式所表示的正規(guī)集 ? 得： [A]=a G[S]: (0) S’?S (1) S ?a A c B e (2)A ?b (3) A ?Ab (4)B ?d 定義 (產(chǎn)生式的 LR(0)左文 ) LR(0)LC(A??)={?| ? =??且 S’??A?? ???, ??Vt*} 有推論： LR(0)LC(A ??)=LC(A).{?} 則有 : LR(0)LC(S’?S)=S LR(0)(LC(S?aAcBe)=aAcBe LR(0)LC(A?b)=ab LR(0)LC(A?Ab)=aAb LR(0)LC(B?d)=aAcd (? =Vn?Vt)上的正規(guī)式 R * R x 5 ④ ⑧ 9 ① 2 14 3 0 6 7 10 11 12 16 15 ⒀ 17 18 ⒆ S a a a a A A A b c c b d e B ? ? ? ? ? DFA x 2 3 5 7 8 9 6 4 1 A b a S b c B e d 構(gòu)造 LR(0)項目集規(guī)范族 ? LR(0)項目集規(guī)范族 (構(gòu)成識別一個文法的活前綴的DFA的狀態(tài)的全體 ) 。 ? LR（ 0） 項目或配置 （ item or configuration） . ? 在右端某一位置有圓點的 G的產(chǎn)生式 A? xyz A?.xyz A? A? A?xyz. 如： S→aAd S→ .aAd S→a .Ad S→aA .d S→aAd . 活前綴與句柄的關(guān)系： ? G[S]: ? 若 S = α Aω =α β ω r是 αβ的前綴，則 ? 稱 r是 G的一個活前綴 ? ，表明產(chǎn)生式 A→ β 的 右部 β 已出現(xiàn)在棧頂 ? A→ β 1β 2的右部子串 β 1已出現(xiàn)在棧頂，期待從輸入串中看到 β 2推出的 符號 ? 3. 活前綴不含有句柄的任何符號，此時期望 A→ β 的右部所推出的符號串 R * R 活前綴 ,與句柄 ,與 LR(0)項目 ? 為刻劃這種分析過程中的文法 G的每一個產(chǎn)生式的右部符號已有多大一部分被識別 （ 出現(xiàn)在棧頂 ） 的情況 ， 分別用標有圓點的產(chǎn)生式來指示位置 。 A→ β ． 刻劃產(chǎn)生式 A→ β 的 右部 β 已出現(xiàn)在棧頂 A→ β 1． β 2 刻劃 A→ β 1β 2的右部子串 β 1已出現(xiàn)在棧頂 ，期待從輸入串中看到 β 2推出的 符號 A→ ． β 刻劃沒有句柄的任何符號 在棧頂 ， 此時期望 A→ β的右部所推出的符號串 ? 對于 A→ ε 的 LR(0)項目只有 A→ ． 構(gòu)造識別活前綴的 DFA ? LR（ 0） 項目集的閉包Ｃ LOSURE, GO 函數(shù) ， function CLOSURE (I)。 /* I 是項目集 */ { J:= I。 repeat for J 中的每個項目 A ?? .B ? 和產(chǎn)生式 B? ? ， 若 B? .? 不在 J中 do 將 B? .? 加到 J中 until 再沒有項目加到 J中 return J }。 GO (I,x)=== CLOSURE(J) 。 其中 ， I:項目集 ， x: 文法符號 ， J={任何形如 A?? x. ? 的項目 |A?? .x ? ?I} LR（ 0） 項目集的閉包Ｃ LOSURE ?若當前處于 A – X?YZ刻劃的情況，期望移進 First(Y)中的某些符號，假如有產(chǎn)生式 Y – u | w . 那么 Y – ?u和 Y – ?w這兩個項目便是刻劃期望移進 First(Y)中的某些符號的情況 . ? A – X?YZ ? Y – ?u ? Y – ?w 這三個項目對應移進歸約分析的同一個狀態(tài) ,這三個項目構(gòu)成一個 配置集 , 對應每個配置集，分析表將有一個狀態(tài) . LR(0)項目集規(guī)范族 ? 計算 LR（ 0） 項目集規(guī)范族 ? C={I0 ， I1 , ... In } ? Procedure itemsets(G’)。 ? Begin C := { CLOSURE ({S’?.S})} ? Repeat ? For C 中每一項目集 I和每一文法符號 x ? Do if GO(I,x) 非空且不屬于 C ? Then 把 GO(I,x) 放入 C中 ? Until C 不再增大 ? End。 ? 例：文法 G: ? （ 0） S`→E (1) E→aA (2) E→bB ? (3) A→cA (4) A→d (5) B→cB ? (7) B→d ? LR(0) 項目集規(guī)范族（ 識別 G的活前綴的 DFA)： I0: S`→ ． E I1: S`→E ． I2: E→a ． A ? E→ ． aA A→.cA ? E→ ． bB A→ ． d ? ? I3: E→b ． B I4: A→c .A I5: B→ ． cB A→ ． cA B→c ． B B→ ． d A → .d B→ ． cB B→ ． d I6: I7: I8: E→aA ． E→bB ． A→cA ． I9: B→cB ． I10: A→d ． I11: B→cB ． LR(0)分析表的構(gòu)造 ? 假定 C={I0, I1,…… ， In}， 令每個項目集 Ik的下標 k 為分析器的一個狀態(tài) ， 因此 ， G` 的 LR(0)分析表含有狀態(tài) 0， 1， …… ， n。 令那個含有項目 S`→ ． S的 Ik的下標 k為初態(tài) 。 ACTION和 GOTO可按如下方法構(gòu)造： 187。 若項目 A→ α ． aβ 屬于 Ik且 GO (Ik, a)= Ij, a為終結(jié)符 ， 則置 ACTION[k, a]為 “ 把狀態(tài) j和符號 a移進棧 ” ， 簡記為“ sj”。 187。 若項目 A→ α ． 屬于 Ik, 那么 ， 對任何終結(jié)符 a, 置ACTION[k, a]為 “ 用產(chǎn)生式 A→ α 進行規(guī)約 ” ， 簡記為“ rj”。其中 ， 假定 A→ α 為文法 G`的第 j個產(chǎn)生式； 187。 若項目 S`→S ． 屬于 Ik, 則置 ACTION[k, ]為 “ 接受 ” ， 簡記為 “ acc”。 187。 若 GO (Ik, A)= Ij, A為非終結(jié)符 ， 則置 GOTO(k, A)=j。 187。 分析表中凡不能用規(guī)則 1至 4填入信息的空白格均置上 “ 出錯標志 ” 。 ? 按上述算法構(gòu)造的含有 ACTION和 GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法 G的一張 LR(0)表。具有 LR(0)表的文法 G稱為一個 LR（ 0） 文法。 ? LR(0)文法是無二義的。 ACTION GOTO a c b d E A B 0 S2 S3 1 1 acc 2 S4 S10