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 剖析器很难以人工的方式设计，一般使用“剖析产生器（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 剖析器的工具。
[隐藏]
以表格为主（table-based）由下而上的剖析器可用图一描述其结构，它包含：
LR 剖析过程如下：
考虑以下文法：
(1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1待剖析的输入字串是:
1 + 1LR(0) 剖析器使用的表格如下：
动作表 用以表示目前状态遇到终端符号（包含结尾字符 $）的对应动作，字段中可能有三种动作：
状态转移表 用以表示简化后的状态遇到非终端符号时的转移规则。
下表是剖析过程中的各步骤，堆栈的顶端在最右边，状态的转移与堆栈的化简都以上表为依据，而特殊字符 '$' 也被加到输入串的尾端表示结尾。
| 目前的状态 | 堆栈 | 输入 | 将采取的动作 |
|---|---|---|---|
剖析起始时堆栈会包含元素 $ 与 0：
[$ 0]
剖析器首先从输入缓冲区看到符号 '1'，根据动作表当状态 0 碰到终端符号 '1' 时采用移位动作 s2，即是将 '1' 从输入缓冲区中移出并推入堆栈，再将新的状态 2 也推入堆栈，这时堆栈会变成：
（为避免终端符号与状态混淆，故堆栈中的终端符号都加上单引号区别）
接着看到的终端符号是 '+'，根据动作表无论状态 2 碰到任何终端符号，都执行 r5 动作（以第五条文法规则 B → 1 化简堆栈内容）。此化简的动作表示剖析器已经在堆栈中认出第五条文法规则的右手边部分，因此可以用该规则的左手边符号 B 取代。因为第五条文法的右边有一个符号，因此我们将两个元素（1 × 2 = 2）自堆栈弹出，此时会回到状态 0，再推入符号 B，并查找转移表中状态 0 遇到非终端符号 B 后的新状态。新的状态是 4，完成此步骤后的堆栈是：
[$ 0 B 4]
由于上一个终端符号 '+' 尚未被处理，因此仍保留在输入缓冲区中。依据动作表，在状态 4 碰到 '+' 时做 r3 化简。根据第三条文法 E → B，我们将 4 与 B 从堆栈弹出，回到状态 0。接着压入 E ，根据状态转移表，当状态 0 遇到非终端符号 E 时需转移至状态 3 ，因此将 3 压入堆栈：
继续尚未处理的符号 '+'，当状态 3 遇到 '+' 时的对应动作是 s6，将 '+' 从输入中移出并压入堆栈，再将新的状态 6 也压入堆栈：
下一个符号是 '1'，在状态 6 看到 '1' 时的动作是 s2，将 '1' 从输入中移出并压入堆栈，再将新的状态 2 也压入堆栈：
最后看到的输入符号是 $，状态 2 遇到 $ 时的动作是 r5，以第五条文法规则化简堆栈内容。此化简动作与第二步骤相似，堆栈弹出两个元素后回到状态 6，这时再压入符号 B 后会进入状态 8（根据状态转移表），因此也将 8 压入堆栈：
在状态 8 看到符号 $ 时剖析器会继续化简，根据动作表执行 r2 化简动作，采用第二条文法规则 E → E + B 简化堆栈。由于该规则的右手边有三个符号，故从堆栈中弹出六个元素。这时回到状态 0，将规则左边的符号 E 推入堆栈后，进入新状态 3（根据状态转移表），将之压入后堆栈为：
最后在状态 3 看到符号 $，对应的动作是 acc，表示剖析顺利完成。
建构剖析表的过程须使用 LR(0) 项目（以下简称为“项目”），这些项目是在文法规则的右手边插入一个特殊的符号“‧”所产生。例如文法 E → E + B 有下列四个对应的项目：
E → ‧ E + B E → E ‧ + B E → E + ‧ B E → E + B ‧若文法规则的形式是 A → ε ，则对应的唯一项目是：
A → ‧建立项目的用意是要决定剖析器的状态，例如 E → E ‧ + B 的意义是“剖析器已经在输入的符号中认出 E 的部分，目前正等著看到一个 '+' 符号与接续的 B 的部份”。
结论：LR(0)项目是由文法规则所产生
在一般的情形中，剖析器不能预知未来要用哪一条文法规则来化简堆栈内容，因此很难以单一个项目决定状态。例如以下文法：
E → E + B E → E * B当剖析器认出堆栈中的 E 部分时，它无法预测未来会继续看到 '+' 或 '*'，因此这时的状态须以两个项目表示：
E → E ‧ + B E → E ‧ * B故我们使用项目的集合 { E → E ‧ + B, E → E ‧ * B } 来表示“剖析器认出 E 并期待 + B 或 * B”的状态。
结论：LR(0)项目可以形成集合并描述剖析过程的状态
如前段叙述，剖析器总是期待在下个输入中看到项目中的 '‧' 之后的符号。如果 '‧' 之后的符号是非终端符号，则应加入该符号所推演出的文法规则，如此才能正确的描述状态。例如规则：
E → E + B B → 0 B → 1当我们来到状态 E → E + ‧ B 时，剖析器期待看到非终端符号 B，而 B 又可推演为终端符号 0 与 1。因此这时的状态应表示为：
E → E + ‧ B B → ‧0 B → ‧1即是“已辨认出 E + 部分，目前期待看到 B，而 B 也就是 '0' 与 '1'”之意。此现象可以描述为：
若项目集合中包含 A → x‧By 形式的项目，其中 B 为非终端符号，则对所有的文法规则 B → w 而言，B → ‧w也会被加入项目集合中。每个项目集合都应该以此规则扩充，将潜在的项目加到集合中直到所有在 ‧ 之后的非终端符号都处理过。如此所产生的新集合称作该项目集合的“封闭集”，符号的表示为 closure(I) ，其中 I 表示原项目集合。剖析过程中的各种状态即是由这些封闭集所构成。
结论：项目的封闭集才能完整的描述剖析过程的状态
在决定状态间的转移前，我们必须先加入一条扩充文法：
(0) S → E其中 S 是新的起始符号（start symbol）而 E 是原先的起始符号。考虑以下文法：
(1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1加入扩充文法后，我们使用下列规则来决定项目集合与状态：
(0) S → E (1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1结论：建构剖析表前必须先加入扩充文法
建构剖析表的第一步是找出封闭集合之间的转移。封闭集可以视为自动机中的状态，而状态间的转移则由终端符号与非终端符号决定。起始状态是由扩充的第 0 条文法规则对应的项目所形成的封闭集：
Item set 0 S → ‧ E E → ‧ E * B E → ‧ E + B E → ‧ B B → ‧ 0 B → ‧ 1集合中的第一个项目是该集合的核心，透过集合的封闭规则，我们加入其他项目补足集合使其封闭。这组封闭集合是第一个状态（I0），现在我们要找出这组状态可能的转移情形。
显示▼一些非中文的文字因为尚未翻译而被隐藏，欢迎参与翻译。
显示▼一些非中文的文字因为尚未翻译而被隐藏，欢迎参与翻译。
显示▼一些非中文的文字因为尚未翻译而被隐藏，欢迎参与翻译。
显示▼一些非中文的文字因为尚未翻译而被隐藏，欢迎参与翻译。
E->E+T/T T->T*F/F F->id
S->AA A->aA/b
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。