第五章-lalr(1)方法(已修改)
2025-08-17 20:16 本頁面
【正文】 LR(1)分析存在的問題 ? 為消除沖突，引入太多的狀態(tài) 。 ? 有些狀態(tài)含有完全相同的 LR(0)項(xiàng)目部分，只有展望符部分是不同的 。 ? LR(1)項(xiàng)目的心 ：如果 (A????, ss) 是一個(gè) LR(1)項(xiàng)目，則其中的 LR(0)項(xiàng)目部分稱為它的心 。 ? LR(1)自動機(jī) 狀態(tài)的心 ：一個(gè)狀態(tài)所含有的所有LR(1)項(xiàng)目的心 。 ? 同心狀態(tài) ：如果兩個(gè) LR(1)狀態(tài)具有相同的心，則稱這兩個(gè)狀態(tài)為同心狀態(tài)。 LALR(1) 分析 ?主要思想 – 合并文法 G的 LR(1)自動機(jī)中的同心狀態(tài)，得到的自動機(jī)稱為 LALR(1)自動機(jī)； – 若這個(gè)得到的 LALR(1)自動機(jī)沒有沖突，則稱文法 G是 LALR(1)文法。 ? LALR(1)分析過程 – 構(gòu)造 LALR(1)自動機(jī) – 構(gòu)造 LALR(1)分析表 (同 LR(1)分析表構(gòu)造方法 ) – LALR(1)驅(qū)動程序 = LR(1)驅(qū)動程序 如何構(gòu)造 LALR(1)自動機(jī) ?第一種途徑： – 首先構(gòu)造 LR(1)自動機(jī) – 然后合并其中的同心狀態(tài) – 該方法簡單，但不現(xiàn)實(shí) (not practical)! Step1:構(gòu)造 LR(1)自動機(jī) VT = {a, b, =} VN = {S, L, R} S = S P: {(1) S ? L = R (2) S ? R (3) L ? aR (4) L ? b (5) R ? L } 0 Z ? ? S , {} S ? ?L = R, {} S ? ?R, {} R 3 S ? R?, {} R ? ?L , {} 1 Z?S?, {} S b 4 L ? b?, {=, } L 5 S ? L?=R, {} R ? L?, {} L ? ?aR, {=, } L ? ?b , {=, } = a 6 S ? L=?R, { } R ? ?L , {} L ? ?aR, {} L ? ?b , {} 12 L ? a?R, {=, }
電大資料相關(guān)推薦
鄂ICP備17016276號-1