第四章7-LR(1)文法.ppt

主要內(nèi)容 LR 1 分析方法 Z EE L E E SL L EL ES idS S Z EE L E E SS idS S 0 E L E S S L L EL EE L E E SS idS S 1 E S S S 2 S 1 S2 Shift Reduce3 即 1 S2 1不成立 Follow E 非SLR 1 文法 LR 0 方法不依賴輸入流 直接判定歸約 容易出現(xiàn)沖突 SLR 1 方法簡單地把非終極符的follow集做為可歸約的依據(jù) 并不精確 一個非終極符在不同的位置上出現(xiàn) 它所允許的后繼符是不同的 而SLR 1 沒有加以區(qū)分 LR 1 針對不同產(chǎn)生式上的非終極符 分別定義其后繼符集 展望符集Reducelookup 減少了移入 歸約沖突 任何SLR 1 都一定是LR 1 文法 1 構(gòu)造文法的LR 1 自動機2 由LR 1 自動機構(gòu)造LR 1 分析表 Action表和Goto表 3 根據(jù)當前狀態(tài)和輸入符號查分析表確定要執(zhí)行的操作 進行相應的語法分析 LR 1 分析步驟 LR 1 分析方法 LR 1 方法研究的對象是二元組 b 其中 是活前綴 而b是一個輸入符號 我們稱上述 b 為LR1前綴模式 活前綴 規(guī)范活前綴 若規(guī)范前綴 不含句柄或含一個句柄并且具有形式 是句柄 則稱規(guī)范前綴 為規(guī)范活前綴 簡稱活前綴 前綴中若有句柄 則句柄在前綴的最右端 物理含義 在歸約過程中 若符號棧中的內(nèi)容為活前綴 則表示到目前為止 語法正確 可以繼續(xù)進行移入或歸約操作 LR 1 分析方法 LR 1 方法研究的對象是二元組 b 其中 是活前綴 而b是一個輸入符號 我們稱上述 b 為LR1前綴模式 如果 是文法的歸約活前綴 b是 的合法后繼續(xù)符 則稱 b 為LR1歸約前綴模式 歸約活前綴 移入活前綴 如果活前綴不中不包含簡單短語 句柄 則稱為移入型活前綴 因為此時只能進行移入操作 不能進行歸約操作 歸約活前綴 若活前綴 是含句柄的活前綴 即有 且 是句柄 則稱活前綴 為歸約規(guī)范活前綴 即含有句柄的規(guī)范活前綴 是可以歸約的 不確定活前綴 如果一個活前綴既是移入型的又是歸約型的 則稱為不確定活前綴 例 S abcS ab則ab既是移入型活前綴 又是歸約型活前綴 LR 1 分析方法 LR 1 方法研究的對象是二元組 b 其中 是活前綴 而b是一個輸入符號 我們稱上述 b 為LR1前綴模式 如果 是文法的歸約活前綴 b是 的合法后繼續(xù)符 則稱 b 為LR1歸約前綴模式 LR1歸約前綴的派生定理 假設(shè) 0是拓廣產(chǎn)生式的右部 是輸入流的結(jié)束符 則有 0 p 是LR1歸約前綴模式 設(shè) A p b 是LR1歸約前綴模式 且A 是q產(chǎn)生式 則 q a 也是LR1歸約前綴模式 其中a First b 派生定理的目的是要求得項目集合的閉包CLOSURE IS LR 1 項目 A a LR 0 項目及一個VT 的展望符 輸入符 集合 IS LR 1 項目集IS X 目的 產(chǎn)生下一個狀態(tài) IS X A X a A X a IS CLOSURE IS IS B b A B a CLOSURE IS B 是產(chǎn)生式 b First a 目的 產(chǎn)生派生項目 LRSM1的構(gòu)造算法 初始項目集 ISS CLOSURE Z S 若所有狀態(tài)都處理完 則結(jié)束選一未處理完狀態(tài)IS 對所有語法符號X VT VN 求ISX 令I(lǐng)S CLOSURE ISX 若IS 不為空 若IS 為新狀態(tài) 則增加ISIS 把IS 加入LRSM1中 否則為圖中某個狀態(tài)ISj 則在IS和ISj之間增加一條轉(zhuǎn)換邊 ISISj轉(zhuǎn)到步驟2 X X 非SLR 1 文法 Z SS L RS RL aRL bR L Z SS L RS RL aRL bR L 非SLR 1 文法 Z SS L RS RL aRL bR L 2狀態(tài)存在移入 歸約沖突歸約 Follow R Follow S Follow L 因此不是SLR 1 文法 展望符不一樣 做為不同的狀態(tài) LR 1 文法 投影函數(shù) 2 用來求分析表 2 StateSet VT 2 2 S a Reducej B a S B 是產(chǎn)生式j(luò) Shift A a b S 如果LR 1 狀態(tài)機的任一狀態(tài)S和輸入符a 都使得 2 S a 1 則稱文法為LR 1 文法 LR 1 分析表的構(gòu)造 Action表的構(gòu)造 Action S a Error若 2 S a Action S Accept若 2 S Reduce1 Action S a Reducej若 2 S a Reducej Action S a Shifti若 2 S a Shift andGoTo S a SiGoTo表的構(gòu)造 GoTo S X Si若S與Si狀態(tài)有X轉(zhuǎn)向邊 X為非終極符 Action表 輸入a時 由0狀態(tài)轉(zhuǎn)入5狀態(tài) R4 13 R5 12 R6 R6 11 R4 R4 10 R6 9 13 9 S12 S8 8 R2 7 7 9 S12 S8 6 10 11 S4 S5 5 R5 R5 4 R3 3 R6 S6 2 Accept 1 3 2 1 S4 S5 0 R L S b a Goto表 由0狀態(tài)歸約到R后 轉(zhuǎn)入3狀態(tài) R4 13 R5 12 R6 R6 11 R4 R4 10 R6 9 13 9 S12 S8 8 R2 7 7 9 S12 S8 6 10 11 S4 S5 5 R5 R5 4 R3 3 R6 S6 2 Accept 1 3 2 1 S4 S5 0 R L S b a Action表 3狀態(tài)輸入 時 按3產(chǎn)生式S R歸約 R4 13 R5 12 R6 R6 11 R4 R4 10 R6 9 13 9 S12 S8 8 R2 7 7 9 S12 S8 6 10 11 S4 S5 5 R5 R5 4 R3 3 R6 S6 2 Accept 1 3 2 1 S4 S5 0 R L S b a LR 1 驅(qū)動程序 LR 1 的驅(qū)動程序與SLR 1 的驅(qū)動程序是相同的 可共用一個 狀態(tài)棧符號棧輸入串ActionGoTo0aab b S50 5aab b S50 5 5aab b S40 5 5 4aab b R5110 5 5 11aaL b R6100 5 5 10aaR b R4110 5 11aL b R6100 5 10aR b