现代编译原理－－第二章（语法分析之LR（1））

　　（转载请表明出处 ）

前⾯已经介绍过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后⾯的数字指的时规约到第⼏个产⽣式。所有空的地⽅都代表出现错误。可见在⾮终结符下只有跳转。

　　为了构建这个表，我们⾸先构建状态机。我们从⼀个基本的⽂法开始，⽂法如下：　　

　　我们向产⽣式中添加⼀个点，形成这种形式，称为项。这个点的位置告诉我们当前在状态是什么。点每移动⼀次，我们跳转⼀个状态。点前⾯的字符串表⽰我们已经读取的历史，点后⾯的字符串表⽰我们希望得到的。也就是这种表达⽅式，既可以展望未来，也可以回顾过去。上⾯这个起始项中，我们希望得下⼀次得到⼀个S⾮终结符，可以看出1和2产⽣式是S的等价形式，如果我们得到1和2产⽣式的右部，我们就相当于得到了⾮终结符S，所以，我们的起始状态为：

　　我们称第⼀个产⽣式为核⼼项，其他为普通项。这个状态我们称为状态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则会⼀直到获得得信息⾜够确定⼀个产⽣式后，才去确定，这都是在项中使⽤ . 带来得好处（回顾过去，展望未来）。　　以下是各种⽂法能⼒⼤⼩得⽐较：