第五章-lalr(1)方法-預(yù)覽頁(yè)
【正文】 14 R4 R4 15 LALR(1) 分析表 Action 表 Goto 表 a b = S L R 0 S12 S4 1 5 3 1 Accept 3 R2 4 R4 R4 5 S6 R5 6 S12 S4 14 7 7 R1 12 S12 S4 14 13 13 R3 R3 14 R4 R4 LALR(1) 自動(dòng)機(jī) ?對(duì)于給定的上下文無關(guān)文法 G – G的 LALR(1)項(xiàng)目跟 LR(1)項(xiàng)目 形式相同 。 ? LR(1)項(xiàng)目的心 ：如果 (A????, ss) 是一個(gè) LR(1)項(xiàng)目，則其中的 LR(0)項(xiàng)目部分稱為它的心 。 ? 有些狀態(tài)含有完全相同的 LR(0)項(xiàng)目部分，只有展望符部分是不同的 。 LALR(1) 分析 ?主要思想 – 合并文法 G的 LR(1)自動(dòng)機(jī)中的同心狀態(tài)，得到的自動(dòng)機(jī)稱為 LALR(1)自動(dòng)機(jī)； – 若這個(gè)得到的 LALR(1)自動(dòng)機(jī)沒有沖突，則稱文法 G是 LALR(1)文法。 – G的 LALR(1) 自動(dòng)機(jī)的 狀態(tài)數(shù)同 LR(0)自動(dòng)機(jī)的狀態(tài)數(shù)相同； – 能不能用 LR(0)自動(dòng)機(jī)構(gòu)造 LALR(1)自動(dòng)機(jī)呢？ 如何構(gòu)造 LALR(1)自動(dòng)機(jī) ?第二種途徑： – 首先構(gòu)造 LR(0)自動(dòng)機(jī) – 然后為每個(gè)狀態(tài)的每個(gè) LR(0)項(xiàng)目計(jì)算展望符集； – 是實(shí)際應(yīng)用中采用的方法！ – 關(guān)鍵是如何計(jì)算展望符呢？ LALR(1)展望符的計(jì)算方法 投影得到的項(xiàng)目 : 展望符集是指向該狀態(tài)的所有狀態(tài)中對(duì)應(yīng)項(xiàng)目的展望符集的合集 。 ?合并同心狀態(tài)只能產(chǎn)生歸約 歸約沖突，不會(huì)產(chǎn)生移入 歸約沖突，為什么？ LR(0), SLR(1), LR(1)和 LALR(1)比較 ? 狀態(tài)數(shù) : – LR(1) LALR(1) = SLR(1) = LR(0) ? 展望符的確定 : – LR(0)沒有展望符； – SLR(1)取 follow集； – LR(1)取不同位置的 follow集； – LALR(1)取同心項(xiàng)的展望符的并集； ? 向前看輸入符 : – SLR(1),LR(1)和 LALR(1)向前看一個(gè)輸入符； – LR(0)
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1