（转载请表明出处 http://www.cnblogs.com/BlackWalnut/p/4472772.html）
前面已经介绍过LL（1），以及如何使用LL（1）文法。但是LL（K）文法要求在看到K个字母的情况下必须做出预测，这相比于LR（K）文法而言就逊色很多。
LR（K）文法的定义是：从左至右分析，最右推导，超前查看K个单词。先看一个例子，来对LR文法有个大致的印象。
以上就是使用LR文法对源码进行分析的例子。注意到在LR文法中只有三个动作：移进，规约和接受，这三个动作也是通过查表来得到的。任何时候如果都是唯一确定这三个动作中的一个，我们就能让LR文法正确的运行。为了更好的理解LR（K）文法，我们先介绍以下最简单的LR（0）文法。
因为动作是根据表来确定，所以，表的构建依然是我们构建的重点，先来看看一个表的最终形式：
首先要说明的是，构建这张表的时候，我们使用到了状态机，行标就代表状态。列标由两部分组成，分别是终结符，和非终结符。s代表移进，r代表规约，g代表跳转，a代表接受，他们后面跟着的数字，除了r以外，都是状态的标号，只有r后面的数字指的时规约到第几个产生式。所有空的地方都代表出现错误。可见在非终结符下只有跳转。
为了构建这个表，我们首先构建状态机。我们从一个基本的文法开始，文法如下：
我们向产生式中添加一个点，形成
我们称第一个产生式为核心项，其他为普通项。这个状态我们称为状态1，所有的状态都是由这个状态中每个项的点的移动得到的。例如，状态1吃掉一个终结符x时，状态1的第二个项中的点要向右移动一位。得到状态2：
当然，状态1也可以吃掉一个终结符（，得到状态3:
状态3中的第一个项就是核心项。上面就我们说的移进操作。
如果状态1吃掉的是一个非终结符S，那么我们称状态需要跳转，起始和移进时相似的效果。那么得到如下状态：
我们再来看状态2，目前点的位置已经到了产生式的最后面，那么意味着这个产生式已经完全匹配了，那么就可以将其规约。具体操作根据r的下标，选择产生式，将栈中的产生式的右部字符串全部弹出，将产生式的左部符号压栈，然后跳转到相应的状态。这个规约还是不太好理解，那么我们对最上面那张图的最后四个规约来举例解释一下。
首先，要说明的是，在实际的使用过程中，在栈中的内容不包含任何的符号，只有状态编号，第一张图是为了方便大家理解，所以才将符号都放入栈中。那么，在规约弹出栈的时候，我们弹出的也都是状态编号。
那么，对于最后四个规约的第一个规约，栈顶符号以此是 +16 (8 S12 ,18 E21 )22这六个符号以及六个个状态，只有最上面的四个满足规约，此时如果用项来表示的话，可以表示为E->(S,E).也就是说在 . 之前我们已经得到一个完整的产生式的右部，可以对其规约。需要把右部所涉及到的所有符号全部弹出，但是我们实际弹出的是状态，所以，原来的16 8 12 18 21 22 弹出状态后，得到的栈为16，我们弹出的字符串规约成为了非终结符E，此时，可以将E看作是在输入队列中输入端，得到 E????，栈顶依然是16。然后将E压栈，对应的16号状态遇到E跳转到17状态，此时栈顶为16E17。然后以此往下进行。
以上，就是对基本概念移进，规约，跳转（可以理解为移进），接受的分析，他们都是基本的动作。根据刚才的推导过程，我们可以构建一个状态机，根据状态机我们能构建一张我们需要的表。表如果我们得到的分析表中的每一项都只有一个动作，那么我们就说这是一个无二义性的LR（0）文法。但是LR（0）文法还是可能出现二义性，我们称为移进规约冲突。首先来看一张有冲突的表：
很显然，＋号位置有冲突。我们来分析一下冲突产生的原因。如果输入队列输入端是＋号，则状态3可以将＋进栈，称为移进，到状态4，也可以进行规约，规约到产生式2。那么能不能规约呢？如果规约的话，（此时＋依然在输入队列中）则规约到的E会先放到输入队列输入端，然后将E压栈，接下来＋号也一定会进栈。那么在栈顶前两位中就出现了E＋这样的字符串，这表面＋号必须要是E的follow符号集合中一个才行。通过分析，我们知道，＋不可能是E的follow集合中终结符。所以，也就不存在规约这个选项。
所以，我们在构建表的时候，可以对终结符进行follow测试，只有在这个集合中符号才能进行规约。伪代码和最后结果如下：
注意，第二个for中，处理的是 . 已经到产生式最末尾的项。最后得到的集合R是可以放产生式A->α的非终结符，在这些非终结符下，都可以规约到A->α。
上面这种针对LR（0）冲突的解决方式称为SLR（0）。这是一种比较简单的解决方式，但是不代表能完美解决所有冲突。因为它使用follow集合并不是一种很精确的冲突预判集合。还是有可能出现冲突。
那么，为什么follow集合不精确呢？我们假设有一个项包含这样的字符串αF.β，我们知道，F的follow集合包含字符串β的first集合。因此我们在SLR（0）中使用的follow集合不一定能正确的预测出产生式。但是，如果使用first集合，就能精准的预测出产生式。所以，我们重新定义了项，它包含产生式，标记状态的点，超前查看符号集合，这三个部分。使用以下的算法来计算一个状态的中每项的具体内容：
其中Closure（I），是根据状态集合I中的核心项来产生其他的一些项，可以看出，使用到了first集合。goto就是移进操作。可见，如果当项中的 . 后有字符时，它直接开始移进，如果项中的 . 后没有字符，且输入端得字符在该项的超前查看符号集合，则规约。最后一个R集合就是规约可以进行A->α规约的非终结符集合。
使用以上算法，我们得到的就是LR（1）文法，显然，它的状态机和其他的LR（0）以及SLR（0）的状态机包含的项是不一样的。这里我们给一个例子，是关于C语言的：
可以看出，在状态机中，有很多的状态，他们除了预测符号集合不一样以外，其他都是一样的。我们可以把这些状态合并，这样可以简化LR（1）分析表的大小。我们把合并后的状态机所描述的文法称为LALR（1）（LA：Look Ahead）文法。它需要用来存储表的空间更小 ，但是它的缺点是，有可能出现 规约—规约 冲突，但是在实际过程中，这种冲突的影响很小。
通过这几次的讨论，我们直达了，一个语法分析程序最重要的是分析表的建立 。
对于LL（K）类文法，他们的分析表是终结符和非终结符组成的行列索引，在表中填的是产生式。对于LR（K），他们是状态和终结符，非终结符组成的索引，表中填的是各种动作。
从分析过程上来说，LL（K）文法是自顶向下分析（由第二个L决定了遇到非终结符就开始向下分析），而LR（K）文法则是自下向上分析（R决定的）。
其实，造成LR的能力高于LL的原因是，LL必须每输入一个字符就要决定所使用的产生式，它是关注于当下的。但是LR则会一直到获得得信息足够确定一个产生式后，才去确定，这都是在项中使用 . 带来得好处（回顾过去，展望未来）。
以下是各种文法能力大小得比较：
