编译原理学习笔记（六）~LR分析

LR分析法

概念：LR文法(Knuth,1963)是最大的、可以构造出相应移入归约语法分析器的文法类
名词解释：

• L:对输入进行从左到右的扫描
• R:反向构造出一个最右推导序列

LR(k)分析：需要向前查看k个输入符号的LR分析。k=0和k=1这两种情况具有实践意义。当省咯(k)时，表示k=1

那么什么是最右推导呢？

注意：这里的R是反向最右推导。其实本质就是上图中的最左规约。举个形象的例子吧（图中序号表示规约的顺序 可以看出 其实就是最左规约：反向最右推导）简单的理解就是对于下图中的生成树从底到上逆推。

LR分析法的基本原理

注释：在进行LR分析的时候，我们加入了 "状态"表示句柄的识别程度（状态这里表示为一个点）。那么具体是什么意思呢？
比如：S→b.BB
我的理解：点前面的字符表示已经读入，已经入栈。而后面的字符表示尚未入栈。S→b.BB表示此时b已经入栈，假设下一个读入的字符为B，则变为S→bB.B，表示再将B入栈。为啥B可以入栈呢？因为根据已知我们可以知道S→bBB，也就是说当栈中出现了bBB的时候，我们可以将其规约为S。但是字符只能一个一个读入，所以利用状态表示整个规约的过程。

LR分析器（自动机）

LR分析表

解释：利用这个分析表，LR自动机可以根据表中的一种准则进行自动分析语法。（简单的理解就是验证我们输入的一串字符是否满足文法要求）

举例说明：

• sn:将符号a、状态n压入栈
• rn:用第n个产生式进行归约（这个n是图中左边文法中对应序号）

上图就是图中左边文法的LR分析表，那么具体怎么使用呢？

注：其实这里只需要把sn、rn对应的含义理解清楚就好了，每一次移进、规约注意状态就可以。有的老师是将状态和字符写在一行的，但是海轰还是习惯于写在上面一行，不会遗漏。这个就看个人的习惯和老师的要求吧。

算法总结

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/105550024