LR(1)分析法

LR(1)分析法的提出¶

$SLR$只是简单考察了下一个输入符号$b$是否归属于归约项目$A\to\alpha$相关联的$FOLLOW(A)$，但$b\in FOLLOW(A)$只是归约$\alpha$的一个必要条件，而非充分条件

不含句柄右侧任何一个符号的规范句型前缀称为该句型的活前缀

假设符号栈中符号串为$\delta\alpha$，输入指针指向终结符$a$；如果想要进行归约$A\to \alpha$，那么$\delta A a$应该为某一个规范句型的前缀

将形式为$[A\to\alpha\cdot\beta,a]$的项称为LR(1)项，a是一个终结符(这里将$视为一个特殊的终结符)

它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符

对于一个LR(1)项目：$[A\to \alpha\cdot B\beta, a]$

构建LR(1)项目：$[B\to \cdot \gamma, b]$

其中$b=\text{FIRST}(\beta a)$，当$\beta\Rightarrow^+ \epsilon$的时候，b为继承的后继符（b=a），否则称为自生的后继符