474lalr分析表的構(gòu)造lalr(lookahead-lr)技術(shù)。這種方(已修改)
2025-10-23 16:34 本頁面
【正文】 LALR分析表的構(gòu)造 LALR(lookaheadLR)技術(shù)。這種方法在實際中是經(jīng)常使用的。 定義 如果兩個 LR(1)項目集去掉搜索符之后是相同的 ,則稱這兩個項目集具有相同的心 (core)。 一個心就是一個 LR(0)項目集。 定義 除去初態(tài)項目集外，一個項目集的核 (kernel)是由此集中那些圓點不在最左端的項目組成。 LR(1)初態(tài)項目集的核含有也僅含有 [S39?！?S,$]。 2 [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?CC ?,$] 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 3 改進(jìn)思路： 合并同心集可達(dá)到縮小構(gòu)造分析表的狀態(tài)數(shù)目；利用核代替項目集可以達(dá)到縮小項目集所占用的存儲空間。介紹兩種方法： 第一種方法：對于 G， 構(gòu)造 LR(1)項目集規(guī)范族 (DFA)， 然后，合并同心集，若合并后的同心集中沒有移進(jìn)歸約沖突，則用其構(gòu)造 LR分析表 , 這種分析表稱作 LALR分析表。 圖 I3 和 I6 I4和 I7 I8和 I9 4 [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?CC ?,$] 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 c [ c? ,c/ /$] [C?? , / /$] [C ? , / /$] /$] 47 [C?cC ?,c/d/$] 89 36 I47 5 討論： 1. 由于 go(I， X)僅僅依賴于 I的心，因此 LR(1) 項目集合并后的轉(zhuǎn)換函數(shù) go(I， X)隨 自身的 合并而得到。 2. 動作 action應(yīng)當(dāng)進(jìn)行修改，使得能反映各被 合并集合的既定動作。 3. 把同心的項目集合并為一，有可能導(dǎo)致沖突， 這種沖突不會是移進(jìn) 歸約沖突 。但可能引起 歸約 歸約沖突。 Ik:{[A???,u1] [B???a?,b] } a?u1=? Ij:{[A???,u2] [B???a?,c] } a?u
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1