lr分析器序471lr分析器的邏輯結(jié)構(gòu)及工作過程472-資料下載頁
2025-07-17 13:56本頁面
【正文】 ? r m ? r m 33 因?yàn)橛幸?guī)范淮導(dǎo) S ccCcd cccCcd 故項(xiàng)目［ C→ cC,c]對活前綴 ccc是 有效的。 若項(xiàng)目 [ A→α Bβ,a]對活前綴 γ=δα是有效的，則存在一個(gè)規(guī)范推導(dǎo) S δAax δαBβax 假定 βax by， 則對每一個(gè)形如B→η 的產(chǎn)生式我們有規(guī)范推導(dǎo) S ??Bby ??? by * ? r m ? r m * ? r m ? r m * ? r m * ? r m ? r m 34 于是 ,項(xiàng)目［ B→η ,b] 對于活前綴 γ=δα 也是有效的。注意到 b或者是從 β推出的第一 個(gè)終結(jié)符號(hào)，或者 β ε而 b＝ a。 這兩種可能性 結(jié)合在一起，則 b∈ FIRST(βa)。 定義 設(shè) I是 G的一個(gè) LR(1)項(xiàng)目集，closure(I)是從 I出發(fā)用下面三個(gè)規(guī)則構(gòu)造的項(xiàng)目集 ： 1 ．每一個(gè) I中的項(xiàng)目都屬于 closure(I)。 2 ．若項(xiàng)目［ A→α Bβ， a]屬于 closure(I) 且 B→η ? P,則對任何 b∈ FIRST(βa),把 ［ B→η ,b]加進(jìn) closure(I)中 。 3．重復(fù)執(zhí)行 (2)直到 closure(I)不再增大為止。 * ? r m 35 定義 4． 13 設(shè) I是 G的一個(gè) LR(1)項(xiàng)目集， X是一 個(gè)文法符號(hào)，定義 go(I， X) ＝ closure(J) , 其中 J={[A→ ? Xβ,a] |當(dāng)［ A→ ? Xβ,a］ ?I時(shí) } 算法 計(jì)算 LR(1)的 closure(I)和go(I,x) FUNCTION closure(I:SET OF item):SET OFitem。 { REPEAT FOR 任一 [A→ ? Bβ,a] IN I FOR 任一 B→η IN P FOR 任一 b IN FIRST(βa) I:=I∪ {[B→ η,b]} UNTIL I不再增大 。 Return (I) 。 } 36 FUNCTION go(I:SET OF item。x∈ {VT∪ VN}): VAR J:SET OF item 。 SET OF item。 { J:={ }。 FOR ?[A→α Xβ,a] IN I J:=J∪ {[A→α Xβ,a]} Return (closure(J)) 。} 算法 LR(1)項(xiàng)目集規(guī)范族的構(gòu)造方法： PROCEDURE items(G180。)。 { C:={closure( {[ S’→S, ＄ ]}) }。 REPEAT FOR ? 項(xiàng)目集 I∈ C和 ? x∈ {VT∪ VN} 把 go(I,X)加入到 C中 UNTIL C不在增大 。} 37 三 . 例示 LR(1)項(xiàng)目集及規(guī)范族的構(gòu)造 G(S180。): (0) S180。?S (1) S ?CC (2) C ?cC (3) C ?d I0 [S180。??S, $] 若 [A ?????,a] ?I 且 B ?? ? P 則 [B???,b] ?I 其中 b ?FIRST(?a) [S ??CC,$] [C ??cC,c/d] [C ??d,c/d] 38 [S180。??S,$] [S??CC,$] [C??cC,c/d] [C??d,c/d] I0 S [S180。?S?,$] I1 C [S?C?C,$] [C??cC,$] [C??d,$] I2 c [C?c?C,c/d] [C? ? cC,c/d] [C??d,c/d] I3 d [C?d?,c/d] I4 C [S?C?C,$] I5 c [C?c?C,$] [C??cC,$] [C??d,$] I6 C [C?cC ?,$] I9 d [C?d?,$] I7 c d c C [C?cC ?,c/d] I8 d 39 五 . 構(gòu)造 LR(1)分析表 c d $ S C0 S3S41 21 acc2 S6S753 S3S484 r3r35 r16 S6S797 r38 r2r29 r340 作業(yè)：
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1