LR(1)分析算法
概念
LR(1) 在每个项目中增加搜索符，例如有$A → α·Bβ$，则还需将$B$的规则也加入。
[X -> α ● β, a] 的含义是：
- α在栈顶上
- 剩余的输入能够匹配 βa
当归约 X -> αβ时， a是前看符号
- 把 reduce by X -> αβ ，填入ACTION[s, a]
构造方法，其他和LR(0)相同，仅闭包的计算不同：
- 对项目[X -> α ● Y β , a] ，添加[Y -> ● γ , b]到项目集，其中b∈FIRST_S(βa) 。
修改后的构造：
以状态0为例，根据产生式S' -> ● S ,$，
- 计算S闭包。即
S -> ● L = R ,$、S -> ● R ,$， - 第一步得出的栈顶符号是非终结符L和R，所以继续计算 L 和 R 的闭包。即
L -> ● * R ,=,$、L -> ● id ,=,$、R -> ● L ,$。 - L已经计算过，不再计算。
- 前看符号是上一个产生式的
FIRST_S(βa)
优化
LALR分析算法 把类似的项目集进行合并（比如上述的5和11,8和10），修改ACTION表和GOTO表以反映合并的效果。
特点：不会产生“移进－归约”冲突 ，但会产生“归约－归约”冲突
- - - 结束 - - -