LR 语法分析

LR 语法分析是一种针对确定性上下文无关文法的、由表驱动的自底向上方法。L 表示从左到右读取词法单元；R 表示分析器以逆序构造最右推导。

移进-归约机 #

分析器维护一个由状态和文法符号组成的栈。对于每个状态和向前看词法单元，动作表会选择以下操作之一：

1. Shift（移进）：消费该词法单元，并将目标状态压入栈中。
2. Reduce（归约）：将产生式右侧替换为其左侧的非终结符，然后使用 goto 表选择下一个状态。
3. Accept（接受）：在输入结束时识别增广开始产生式。
4. Error（错误）：报告不存在有效的后续操作。

push state 0
repeat
  action = ACTION[top_state, lookahead]
  if action is shift s: consume lookahead; push s
  if action is reduce A → β: pop |β| grammar symbols and states; push GOTO[top_state, A]
  if action is accept: return syntax tree
  otherwise: report a syntax error

语义动作通常在归约时执行。并行的值栈存储待归约符号对应的 AST 节点或其他值。

项与向前看 #

LR 项记录一个产生式以及一个表示已识别输入的点，例如 E → E + · T。项集构成分析器状态。closure 会添加点后非终结符所需的产生式，而 goto 会跨过一个文法符号推进该点。

LR(0) 的归约没有向前看信息，因此能够接受的文法类别较小。SLR 使用 FOLLOW 集合限制归约。Canonical LR(1) 为每个项附加一个向前看集合，因此能够识别更多文法。LALR(1) 合并兼容的 LR(1) 状态以减小表的大小；这种合并可能引入 Canonical LR(1) 中不存在的冲突。

移进/归约冲突表示表无法确定应当消费一个词法单元还是执行归约。归约/归约冲突表示存在两种可能的归约。优先级声明可以解决预期的表达式冲突，但由有歧义的语言结构引起的冲突应当通过修正文法来解决，或在语言规范中明确规定。