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 剖析器的工具。
LR 剖析器的结构
以表格为主（table-based）由下而上的剖析器可用图一描述其结构，它包含：
- 一个输入缓冲区，输入的源代码储存于此，剖析将由第一个符号开始依序向后扫描。
- 一座堆叠，储存过去的状态与化简中的符号。
- 一张状态转移表（goto table），决定状态的移转规则。
- 一张动作表（action table），决定目前的状态碰到输入符号时应采取的文法规则，输入符号指的是终端符号（Terminals）与非终端符号（Non-terminals）。
剖析算法
LR 剖析过程如下：
- 将结尾字元 $ 与起始状态 0 依序压入空堆叠，之后的状态与符号会被压入堆叠的顶端。
- 根据目前的状态以及输入的终端符号，到动作表中找到对应动作：
- 移位（shift） sn:
- 将目前的终端符号由输入缓冲区中移出并压入堆叠
- 再将状态 n 压入堆叠并成为最新的状态
- 化简（reduce） rm:
- 考虑第 m 条文法规则，假设该文法的右边（right-hand side）有 X 个符号，则将 2X 个元素从堆叠中弹出
- 此时过去的某个状态会回到堆叠顶端
- 在状态转移表中查找此状态遇到文法左边（left-hand side）的符号时的状态转移
- 将文法左手边的符号压入堆叠
- 将查找到的新状态压入堆叠
- 接受，输入字串解析完成。
- 无对应动作，此情形即为文法错误。
- 移位（shift） sn:
- 重复步骤二直到输入的字串被接受或侦测到文法错误。
范例
考虑以下文法：
- (1) E → E * B
- (2) E → E + B
- (3) E → B
- (4) B → 0
- (5) B → 1
待剖析的输入字串是:
- 1 + 1
动作表与状态转移表
LR(0) 剖析器使用的表格如下：
| 动作 | 状态转移 | |||||||
| 状态 | * | + | 0 | 1 | $ | E | B | |
| 0 | s1 | s2 | 3 | 4 | ||||
| 1 | r4 | r4 | r4 | r4 | r4 | |||
| 2 | r5 | r5 | r5 | r5 | r5 | |||
| 3 | s5 | s6 | acc | |||||
| 4 | r3 | r3 | r3 | r3 | r3 | |||
| 5 | s1 | s2 | 7 | |||||
| 6 | s1 | s2 | 8 | |||||
| 7 | r1 | r1 | r1 | r1 | r1 | |||
| 8 | r2 | r2 | r2 | r2 | r2 | |||
动作表 用以表示目前状态遇到终端符号（包含结尾字元 $）的对应动作，栏位中可能有三种动作：
- 移位，记为 'sn'，表示下个状态是 n
- 化简，记为 'rm'，表示使用第 m 条文法规则化简堆叠中的内容。
- 接受，记为 'acc'，表示剖析正确的完成，输入的字串被文法所定义的语言接受．
状态转移表 用以表示简化后的状态遇到非终端符号时的转移规则。
剖析过程
下表是剖析过程中的各步骤，堆叠的顶端在最右边，状态的转移与堆叠的化简都以上表为依据，而特殊字元 '$' 也被加到输入串的尾端表示结尾。
| 目前的状态 | 堆叠 | 输入 | 将采取的动作 |
|---|---|---|---|
| 0 | $ 0 | 1+1$ | Shift 2 |
| 2 | $ 0 '1' 2 | +1$ | Reduce 5 |
| 4 | $ 0 B 4 | +1$ | Reduce 3 |
| 3 | $ 0 E 3 | +1$ | Shift 6 |
| 6 | $ 0 E 3 + 6 | 1$ | Shift 2 |
| 2 | $ 0 E 3 + 6 '1' 2 | $ | Reduce 5 |
| 8 | $ 0 E 3 + 6 B 8 | $ | Reduce 2 |
| 3 | $ 0 E 3 | $ | Accept |
范例说明
剖析起始时堆叠会包含元素 $ 与 0：
- [$ 0]
剖析器首先从输入缓冲区看到符号 '1'，根据动作表当状态 0 碰到终端符号 '1' 时采用移位动作 s2，即是将 '1' 从输入缓冲区中移出并推入堆叠，再将新的状态 2 也推入堆叠，这时堆叠会变成：
- [$ 0 '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 压入堆叠：
- [$ 0 E 3]
继续尚未处理的符号 '+'，当状态 3 遇到 '+' 时的对应动作是 s6，将 '+' 从输入中移出并压入堆叠，再将新的状态 6 也压入堆叠：
- [$ 0 E 3 '+' 6]
下一个符号是 '1'，在状态 6 看到 '1' 时的动作是 s2，将 '1' 从输入中移出并压入堆叠，再将新的状态 2 也压入堆叠：
- [$ 0 E 3 '+' 6 '1' 2]
最后看到的输入符号是 $，状态 2 遇到 $ 时的动作是 r5，以第五条文法规则化简堆叠内容。此化简动作与第二步骤相似，堆叠弹出两个元素后回到状态 6，这时再压入符号 B 后会进入状态 8（根据状态转移表），因此也将 8 压入堆叠：
- [$ 0 E 3 '+' 6 B 8]
在状态 8 看到符号 $ 时剖析器会继续化简，根据动作表执行 r2 化简动作，采用第二条文法规则 E → E + B 简化堆叠。由于该规则的右手边有三个符号，故从堆叠中弹出六个元素。这时回到状态 0，将规则左边的符号 E 推入堆叠后，进入新状态 3（根据状态转移表），将之压入后堆叠为：
- [$ 0 E 3]
最后在状态 3 看到符号 $，对应的动作是 acc，表示剖析顺利完成。
建构 LR(0) 剖析表
LR(0) 项目（Items）
建构剖析表的过程须使用 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），现在我们要找出这组状态可能的转移情形。