LR剖析器是一种由下而上（bottom-up）的上下文无关语法剖析器。LR意指由左（Left）至右处理输入字串，并以最右边优先衍生（Right derivation）的推导顺序（相对于LL剖析器）建构语法树。能以此方式剖析的语法称为LR语法。而在LR(k)这样的名称中，k代表的是剖析时所需前瞻符号（lookahead symbol）的数量，也就是除了目前处理到的输入符号之外，还得再向右参照几个符号之意；省略 （k）时即视为LR(1)，而非LR(0)。 由于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）由下而上的剖析器可用图一描述其结构，它包含： 剖析演算法. LR剖析过程如下： 范例. 考虑以下文法： (1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1 待剖析的输入字串是： 1 + 1 动作表与状态转移表. LR(0)剖析器使用的表格如下： 动作表用以表示目前状态遇到"终端符号"（包含结尾字元$）的对应动作，栏位中可能有三种动作： 状态转移表用以表示简化后的状态遇到"非终端符号"时的转移规则。 剖析过程. 下表是剖析过程中的各步骤，堆叠的顶端在最右边，状态的转移与堆叠的化简都以上表为依据，而特殊字元'$'也被加到输入串的尾端表示结尾。 范例说明. 剖析起始时堆叠会包含元素$与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），现在我们要找出这组状态可能的转移情形。