主要內容 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 方法不依賴輸入流 直接判定歸約 容易出現沖突 SLR 1 方法簡單地把非終極符的follow集做為可歸約的依據 并不精確 一個非終極符在不同的位置上出現 它所允許的后繼符是不同的 而SLR 1 沒有加以區分 LR 1 針對不同產生式上的非終極符 分別定義其后繼符集 展望符集Reducelookup 減少了移入 歸約沖突 任何SLR 1 都一定是LR 1 文法 1 構造文法的LR 1 自動機2 由LR 1 自動機構造LR 1 分析表 Action表和Goto表 3 根據當前狀態和輸入符號查分析表確定要執行的操作 進行相應的語法分析 LR 1 分析步驟 LR 1 分析方法 LR 1 方法研究的對象是二元組 b 其中 是活前綴 而b是一個輸入符號 我們稱上述 b 為LR1前綴模式 活前綴 規范活前綴 若規范前綴 不含句柄或含一個句柄并且具有形式 是句柄 則稱規范前綴 為規范活前綴 簡稱活前綴 前綴中若有句柄 則句柄在前綴的最右端 物理含義 在歸約過程中 若符號棧中的內容為活前綴 則表示到目前為止 語法正確 可以繼續進行移入或歸約操作 LR 1 分析方法 LR 1 方法研究的對象是二元組 b 其中 是活前綴 而b是一個輸入符號 我們稱上述 b 為LR1前綴模式 如果 是文法的歸約活前綴 b是 的合法后繼續符 則稱 b 為LR1歸約前綴模式 歸約活前綴 移入活前綴 如果活前綴不中不包含簡單短語 句柄 則稱為移入型活前綴 因為此時只能進行移入操作 不能進行歸約操作 歸約活前綴 若活前綴 是含句柄的活前綴 即有 且 是句柄 則稱活前綴 為歸約規范活前綴 即含有句柄的規范活前綴 是可以歸約的 不確定活前綴 如果一個活前綴既是移入型的又是歸約型的 則稱為不確定活前綴 例 S abcS ab則ab既是移入型活前綴 又是歸約型活前綴 LR 1 分析方法 LR 1 方法研究的對象是二元組 b 其中 是活前綴 而b是一個輸入符號 我們稱上述 b 為LR1前綴模式 如果 是文法的歸約活前綴 b是 的合法后繼續符 則稱 b 為LR1歸約前綴模式 LR1歸約前綴的派生定理 假設 0是拓廣產生式的右部 是輸入流的結束符 則有 0 p 是LR1歸約前綴模式 設 A p b 是LR1歸約前綴模式 且A 是q產生式 則 q a 也是LR1歸約前綴模式 其中a First b 派生定理的目的是要求得項目集合的閉包CLOSURE IS LR 1 項目 A a LR 0 項目及一個VT 的展望符 輸入符 集合 IS LR 1 項目集IS X 目的 產生下一個狀態 IS X A X a A X a IS CLOSURE IS IS B b A B a CLOSURE IS B 是產生式 b First a 目的 產生派生項目 LRSM1的構造算法 初始項目集 ISS CLOSURE Z S 若所有狀態都處理完 則結束選一未處理完狀態IS 對所有語法符號X VT VN 求ISX 令IS CLOSURE ISX 若IS 不為空 若IS 為新狀態 則增加ISIS 把IS 加入LRSM1中 否則為圖中某個狀態ISj 則在IS和ISj之間增加一條轉換邊 ISISj轉到步驟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狀態存在移入 歸約沖突歸約 Follow R Follow S Follow L 因此不是SLR 1 文法 展望符不一樣 做為不同的狀態 LR 1 文法 投影函數 2 用來求分析表 2 StateSet VT 2 2 S a Reducej B a S B 是產生式j Shift A a b S 如果LR 1 狀態機的任一狀態S和輸入符a 都使得 2 S a 1 則稱文法為LR 1 文法 LR 1 分析表的構造 Action表的構造 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表的構造 GoTo S X Si若S與Si狀態有X轉向邊 X為非終極符 Action表 輸入a時 由0狀態轉入5狀態 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狀態歸約到R后 轉入3狀態 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狀態輸入 時 按3產生式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 驅動程序 LR 1 的驅動程序與SLR 1 的驅動程序是相同的 可共用一個 狀態棧符號棧輸入串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