LR剖析器

LR剖析器是一種由下而上（bottom-up）的上下文無關語法剖析器。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剖析器的工具。