LR parsing
- LR grammar is shift-reduction parser
- L = 从左到右扫描输入
- R = 做最右规约（right-most reduction）
- LR(k) = 允许向前看 k 个输入符号
可以理解为：
- 输入串从左往右读
- 读到一定程度后，不断把“已经识别出的句柄”规约成非终结符
- 最终把整个串规约成开始符号，就接受
LR (0) Parsing
关键组件：
| 组件 | 功能 |
|---|---|
| input buffer | 存储待分析输入串 a₁...aᵢ...aₙ$ |
| state/symbol stack | 保存已经历的状态序列 S₀ S₁ ... Sₘ 和符号 X₁ ... Xₘ |
| ACTION table | ACTION[S, a]：根据当前状态 S 和输入符号 a 决定动作 |
| GOTO table | GOTO[S, X]：根据状态 S 和非终结符 X 确定下一状态 |
Action[S, a]
表示：
- 当前在状态 S
- 当前输入符号是 a
- 接下来该做什么动作
PPT 给出 4 种可能动作：
- shift：记作
s n - reduce：记作
r m - acc：接受
- blank：报错
也就是：
s n：移进，并进入状态 nr m：按第 m 条产生式规约acc：分析成功blank：语法错误
Goto[S, X]
表示：
- 当前状态是 S
- 刚刚识别出了某个非终结符 X
- 那么接下来转到哪个状态
所以：
- Action 主要管“看见终结符怎么办”
- Goto 主要管“规约出非终结符后去哪儿”
| 动作 | 写法 | 做什么 |
|---|---|---|
| shift | sₙ | 读输入 + 压状态 |
| reduce | rₘ | 弹栈 + goto |
| accept | acc | 成功 |
| error | 空 | 报错 |