LR分析器是一種由下而上（bottom-up）的上下文無關語法分析器。
基本介紹
- 中文名：LR剖析器
- 學科：計算機
簡介,LR分析器的結構,分析算法,
簡介
LR意指由左（Left）至右處理輸入字元串，並以最右邊優先派生（Right derivation）的推導順序（相對於LL分析器）建構語法樹。能以此方式分析的語法稱為LR語法。而在LR(k)這樣的名稱中，k代表的是分析時所需前瞻符號（lookahead symbol）的數量，也就是除了目前處理到的輸入符號之外，還得再向右引用幾個符號之意；省略（k）時即視為LR(1)，而非LR(0)。
由於LR分析器嘗試由分析樹的葉節點開始，向上一層層透過文法規則的化簡，最後規約回到樹的根部（起始符號），所以它是一種由下而上的分析方法。許多程式語言使用LR(1)描述文法，因此許多編譯器都使用LR分析器分析原始碼的文法結構。LR分析的優點如下：
- 眾多的程式語言都可以用某種LR分析器（或其變形）分析文法。（C++是個著名的例外）
- LR分析器可以很有效率的建置。
- 對所有“由左而右”掃描原始碼的分析器而言，LR分析器可以在最短的時間內偵測到文法錯誤（這是指文法無法描述的字元串）。
然而LR分析器很難以人工的方式設計，一般使用“分析產生器（parser generator）”或“編譯器的編譯器（compiler-compiler，產生編譯器的工具）”來建構它。LR分析器可根據分析表（parsing table）的建構方式，分類為“簡單LR分析器（SLR, Simple LR parser）”、“前瞻LR分析器（LALR, Look-ahead LR parser）”以及“正統LR分析器 (Canonical LR parser)”。這些解析器都可以處理大量的文法規則，其中LALR分析器較SLR分析器強大，而正統LR分析器又比LALR分析器能處理更多的文法。著名的Yacc即是用來產生LALR分析器的工具。
LR分析器的結構
以表格為主（table-based）由下而上的分析器可用圖一描述其結構，它包含：
- 一個輸入緩衝器，輸入的原始碼存儲於此，分析將由第一個符號開始依序向後掃描。
- 一座堆疊，存儲過去的狀態與化簡中的符號。
- 一張狀態轉移表（goto table），決定狀態的移轉規則。
- 一張動作表（action table），決定目前的狀態碰到輸入符號時應採取的文法規則，輸入符號指的是終端符號（Terminals）與非終端符號（Non-terminals）。
分析算法
LR分析過程如下：
- 將結尾字元$與起始狀態0依序壓入空堆疊，之後的狀態與符號會被壓入堆疊的頂端。
- 根據目前的狀態以及輸入的終端符號，到動作表中找到對應動作：
- 考慮第m條文法規則，假設該文法的右邊（right-hand side）有X個符號，則將2X個元素從堆疊中彈出
- 此時過去的某個狀態會回到堆疊頂端
- 在狀態轉移表中查找此狀態遇到文法左邊（left-hand side）的符號時的狀態轉移
- 將文法左手邊的符號壓入堆疊
- 將查找到的新狀態壓入堆疊
- 將目前的終端符號由輸入緩衝器中移出並壓入堆疊
- 再將狀態n壓入堆疊並成為最新的狀態
- 移位（shift）sn:
- 化簡（reduce）rm:
- 接受，輸入字元串解析完成。
- 無對應動作，此情形即為文法錯誤。
- 重複步驟二直到輸入的字元串被接受或偵測到文法錯誤。
