第六章 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对应的含义理解清楚就好了,每一次移进、规约注意状态就可以。有的老师是将状态和字符写在一行的,但是海轰还是习惯于写在上面一行,不会遗漏。这个就看个人的习惯和老师的要求吧。

算法总结

© 版权声明
THE END
喜欢就支持以下吧
点赞0赞赏
分享
评论 抢沙发

请登录后发表评论