Parsing

:material-circle-edit-outline: 约 447 个字 :material-clock-time-two-outline: 预计阅读时间 1 分钟

top-down parsing

may require backtracing

自顶向下的方法都没法处理左递归

a special case of recursive descent parsing

no backtracking

looking ahead

需要提取左因子（Left Factoring），否则会遇到多个可选项

语法器如果查到了表中的一个空项，就说明遇到语法错误了

skipp tokens until a token in the FOLLOW set is reached

Shift-Reduce Parsing: a general style of bottom-up parsing

先列出 LR(0) item，再手搓 NFA，再转化为 DFA，再按下图的方法就可以构造出 LR(0) Parsing Table

下图是用表消化一串字符串的例子

先生成 LR(0) DFA，然后计算每一个 non-terminal 的 Follow Set，然后按下面的规则构造表

与 LR(0) 不同的是，SLR(1) 的 reduce 不再只与状态有关，我们需要提前观看下一个符号从而判断进行什么样的 shift 或 reduce 操作。

An LR(1) item consists of an LR(0) item and a lookahead symbol: (A → α.β, x)

[!NOTE]

LR(0)-> SLR(1)-> LR(1)，都是在致力于减少 reduce 导致的冲突项，以兼容更多的文法；第一者是直接无脑让所有终结符都标上 reduce，第二者改用了 FOLLOW，第三者则再细化到实际会出现的情况

LR(1) parsing tables can be very large, with many states.

LALR(1)将产生式一样的、只是 lookahead symbol 不同的状态合并为一个状态，以此减少状态数

根据 DFA 可以构造 LALR(1) Parsing Table，其方法与 LR(1) 完全一致

但是，这有时（虽然很少）也可能引入 reduce-reduce conflict，这里合并后的状态 5&6画预测表时会发现存在 reduce-reduce conflict。这说明这个文法不是 LALR(1) 文法。