LR Parse

个人学习理解，可能有许多理解或者表达上的错误，若有发现错误，欢迎帮我纠正～

L: left to right parsing
R: rightmost derivation

LR 分析器结构

Table-based
Actions
- Shift （移进）
- Reduce （归约）
Data Structures
- Stack of states/symbols {s}
- Action table: action[s, a]; a是终结符
- Goto table: goto[s, X]; X是非终结符

LR(K) 代表: 从左至右分析、最右边推导、超前查看 k 个单词

Bottom-up 自底向上的分析

Bottom-up 方式，最终得到的是开始符号s，换句话讲，构建语法分析树的时候，从叶子结点得到根，如图

LR 就是一种常见的使用 bottom-up分析的语法分析器。

Bottom-up 语法分析器的分类

LR(0) -> SLR(1) -> LR(1) -> LALR(1)

Shift & Reduce

移进（Shift）、归约（Reduce）是 LR 分析器工作中对输入符号进行处理的两种操作。

移进（Shift）操作：将输入的符号压入到 LR 分析栈。
归约（Reduce）操作：将 LR 分析栈顶部的某一项或多项用某个产生式归约。换句话说，若栈顶的某些项符合某条产生式的右部，则将这几项出栈，然后将产生式的左部入栈。例如，栈顶有 ABC 三项，有产生式P -> A B C 则将 A B C 出栈，将 P 入栈，最终栈中只剩下 P。

Action table 和 Goto table 用来指导 LR 分析器进行 Shift 还是 Reduce 操作。

Action & Goto Table

这就有点像有限自动机了， LR 分析栈中的值实际上是状态的 ID。

action 表的说明： action[s, a]

s: State ，类似 DFA 中的状态，输入符号可以转移状态。
a: 符号，类似 DFA 中的符号，输入符号可以转移状态。

每一行都是一个状态( State ), 列是非终结符和终结符组成，非终结符部分构成 Goto 表，用来记录归约后切换的目标状态。

action 表的值有 4 种类型:

SX : Shift X X代表状态的 ID
- push state X 把 X 状态压入到分析栈
- read new a 读取一个新的字符 a
RX: Reduce X
- 使用产生式 X: $P->Y_1Y_2…Y_k$ 归约
- 弹出栈中 k 项，后取栈顶状态 u
- 压栈： goto [ u, P ]
A： Accept 识别句子成功
无值：语法错误

Goto 表，goto [ u, p ]

u 是归约后栈顶的状态 ID，P 是非终结符，其实就相当于切换到状态 u 中 P 非终结符的表格的值对应的状态。

Action/Goto 表的构造算法

这一块很抽象，涉及到很多离散数学中的理论，目前我还没系统学习离散数学，理解和表达可能有一些偏差和错误。

构造思路与 NFA 转 DFA 所采用的子集构造法类似。首先找出文法中独立的状态，然后计算每个状态对字母表中每一个字符的转移状态，最后合成一张表。

Configuration Set

每一个集合代表一个状态

“点” 记号

$T->T·F$

这里的 ·是记号，在 F 的左侧，可以预测所有 F 可以推出的产生式，例如:
$T->T·F$
$F->·(T)$
$F->·id$
这些产生式构成的集合就是 Configuration Set

Closure

Closure 性质
如果 $T->X_1…X_i·X_{i+1}…X_n$ 在集合中，$X_{i+1}$是非终结符，那么$X_{i+1}->·Y_1Y_2…Y_n$ 也在该集合中。

若 $Y_1$ 是非终结符，则继续像集合中添加 $Y_1->·Z_1Z_2Z_3…Z_n$ 直到 ·遇到终结符。
Configuration 初始： $closure(S’->·S)$
Compute as fixed point

Closure 计算例子