编译器笔记15-语法分析-LR(1)分析

2019-11-24 本文已影响0人衣忌破

LR(1)分析法的提出

SLR分析只是简单地考察下一个输入符号b是否属于与归约项目A→α 相关联的FOLLOW(A)，但b∈FOLLOW(A)只是归约α的一个必要条件，而非充分条件。对于产生式A→α的归约，在不同的使用位置，A会要求不同的后继符号。

不同的后继符号.png

在特定位置，A的后继符集合是FOLLOW(A)的子集。

规范LR(1)项目

将一般形式为[A→α·β, a]的项称为LR(1)项，其中A→αβ是一个产生式，a是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符(lookahead)。

LR(1)中的1指的是项的第二个分量的长度
在形如[A→α·β, a]且β ≠ ε的项中，展望符a没有任何作用
但是一个形如[A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α进行归约（这样的a的集合总是FOLLOW(A) 的子集，而且它通常是一个真子集）

等价LR(1)项目

等价LR(1)项目.png

LR(1)自动机a.png

根据上述转换图可以构造LR(1)分析表，在LR(1)分析表当中其移入项目和待约项目的处理方法与LR(0)分析表的处理是一样的。所不同的是对归约项目的处理。例如，在状态项目集中的项目R→ L.,$在LR(0)分析表中遇到任何符号都采取归约动作，在SLR分析表中遇到R的FOLLOW集才能采取归约动作，而构造LR(1)分析表中只有遇刀$符号时才能进行归约。类似的状态7状态8状态5，只有在遇到=或者$时才能进行归约，而状态10状态12状态13只有遇到$时才能进行归约动作。

赋值语句文法的LR(1)分析表.png

LR(1)自动机b.png

通过观察自动机可知，即便是相同核心的LR(1)项目在不同的状态中其展望符集合也是不一样的，例如状态4中的L → *.R,=/$ 与状态11中的L → *.R,$。因为展望符不是完全由FOLLOW集决定的它还受当前状态的上一个状态所影响。

说明：自动机b中将项目前半部分相同的项目的展望符合并为一个集合变成一个项目。如L→ *.R,=和L→*.R,$合并为L→*.R,=/$

问: 为什么状态10、12、13当下一个输入符为等号时会报错？

答: 因为从初始状态0到这个三个状态必然会经过等号，即进入此三个状态时输入已经出现了一个等号，根据文法可知句子中只能出现一个等号。既然在进入此三状态前已经出现了等号，下一个输入符号为等号必然会报错。

问: 为什么在状态2时输入符为等号时不能进行归约操作呢？

答:
1.假如将栈顶的L归约成R，此时栈顶的L连同状态2一起出栈，状态栈栈顶变为状态0。
2.状态0遇到刚归约的字符R，进入状态3。
3.状态3是一个归约状态，此时状态3连同R一起出栈，露出了压在状态3下的状态0。
4.状态0遇到刚归约出的S,进入状态1。
5.状态1是一个接受状态，只有遇到下一个符号是$时，才采取动作。而此时下一个输入符号是等号，显然会出错。

因此在状态2下一个输入符号为等号时，即使采取归约动作，之后也会出现错误。LR(1)项目使得分析器在状态2时，就能遇见到栈顶的L不是一个句柄，因此不能对它进行归约动作。