lr分析器序471lr分析器的邏輯結構及工作過程472(存儲版)
【正文】 T ?T ? *F I={X ?? ?b ?, A ?? ?, B ?? ?} 若 ?FOLLOW(A) ? FOLLOW(B)=? 則，面對當前讀入符號 a， 狀態(tài) I的解決方法： 1. 若 a=b,則移進。 對同一個活前綴存在若干不同的項目對它是有效的，而且它告訴我們應做的事情可能各不相同，互相沖突。 REPEAT FOR ?I?C 和 ?X ?{VT ∪ VN} 把 go(I,X) 加入到 C中 UNTIL C不在增大 END。 Return (I) END。 Xβ的后繼。η加進 closure(I)中 。 A→α 14 二 . 有效項目集和轉移函數(shù) 定義 (識別活前綴的有效項目 ) 如果存在一個規(guī)范推導 S αAw αβ1β2w 項目 A→β 1 11 SLR分析表的構造 根椐文法 G，構造識別文法 G的所有活前綴的 DFA m，根椐 DFA m構造分析表。 LR分析方法是當前最廣義的無回溯的“移進 歸約”方法。 優(yōu)點：適用范圍廣；分析速度快；報錯準確。 S ?A? ? ?? , ??VT 活前綴： ? ?的 前綴是 右句型 ? ?? 的 活前綴。 Bβ對 識別 活前綴 ? =δα是有效的且若 B→η ?P， 則項目 B→ * ? rm ? rm * ? rm * ? rm ? rm * ? rm ? rm 16 識別 文法 G的某個活前綴 γ的所有有效項目 組成的集合稱為 γ的有效項目集。 17 定義 (轉移函數(shù) ) 若 I是 G的一個 LR(0)項目集 , X ?{VT?VN} go(I,X)=closure(J) 其中 , J={A→α Xβ X I中項目 A→α VAR J:SET OF item。?S (1) S ?aA (2) S ?bB (3) A ?cA (4) A ?d (5) B ?cB (6) B ?d I0 S 180。 例： (0) E 180。 4. 此外，報錯。 R L ? I3 * L ? * * R L ? 對歸約項目 [A???, a1a2…a k]， 僅當前輸入符號串開始的前 k個符號是 a1a2…a k時，才能用 A??進行歸約。 Bβ,a]對活前綴 γ=δα是有效的，則存在一個規(guī)范推導 S δAax δαBβax 假定 βax by， 則對每一個形如B→η 的產(chǎn)生式我們有規(guī)范推導 S ??Bby ??? by * ? r m ? r m * ? r m ? r m * ? r m * ? r m ? r m 34 于是 ,項目［ B→ 3．重復執(zhí)行 (2)直到 closure(I)不再增大為止。 } 36 FUNCTION go(I:SET OF item。)。??S,$] [S??CC,$] [C??cC,c/d] [C??d,c/d] I0 S [S180。} 37 三 . 例示 LR(1)項目集及規(guī)范族的構造 G(S180。 FOR ?[A→α { REPEAT FOR 任一 [A→ ? 定義 設 I是 G的一個 LR(1)項目集，closure(I)是從 I出發(fā)用下面三個規(guī)則構造的項目集 ： 1 ．每一個 I中的項目都屬于 closure(I)。β ,a]對活前綴 γ=??是有效的。 I9 L II8 * II4 id II5 FOLLOW(R)={=,$},非 SLR文法。 id I4 id L ? id ?S ?E? E?E?+T} I2: {E?T? T ?T ? *F} I9:{E ?E+T ? T ?T ?*F} 28 S180。?E? E ?E?+T T E ?T? T ?T?*F ( F ? (? E) E ??E+T E ??T T ??T*F T ??F F ? ?(E) F ??id I0 I1 I2 I6 F T ?F? I3 F ?id? id I5 T I2 F I3 id I5 ( E ?E+ ? T T ??T*F T ??F F ? ?(E) F ??id + * T ?T* ? F F ? ?(E) F ??id I7
環(huán)評公示相關推薦
鄂ICP備17016276號-1