LALR 中的 \[$end\] 前瞻

Question

我想了解 bison 如何为这个简单的语法构建 tables：

input: rule ;
rule: rule '+' '1' 
    | '1' ;

我能够计算 LR(1) 转换 table 和项目集，但我不明白状态 3 是如何构建和工作的：

State 3

1 input: rule .  [$end]
2 rule: rule . '+' '1'

'+'  shift, and go to state 5

$default  reduce using rule 1 (input)

对于默认的缩减规则，我应该将 'r1' 放入每个符号的 GOTO table 的所有单元格中。但是对于转换规则，我应该将 's5' 放入“+”终端的列中（此单元格已包含 'r1'）。对我来说，这看起来像是 shift/reduce 冲突。但不是野牛。请解释'[$end]'lookahead symbol是如何出现在这个状态中的，以及这个状态是如何被LR状态机整体处理的。

Answer 1

default 表示 "everything else"，而不是 "everything"。换句话说，您首先填写指定的操作，然后使用任何其他前瞻符号的默认操作。

如果没有默认操作，则任何未指定的先行符号的操作都是错误的。默认减少操作通常用于减少 table 大小，否则算法会触发错误。这种优化可能会延迟错误报告的结果，但错误总是会在另一个输入被消耗之前被检测到，这正是因为错误操作永远不会被默认班次取代。（事实上，许多解析器生成器根本不使用默认的移位操作。）
如果您查看 .output 文件开头显示的语法，您会发现它已通过产生式进行了扩充：
```
0 $accept: input $end
```
Yacc/bison 总是添加这样的产生式以确保完整的输入与开始符号相匹配。（当然，非终结符号 input 将被任何用 %start 指令声明的起始符号或语法中的第一个非终结符号替换。）

除了减少 $accept 符号导致输入被接受之外，这条规则没有什么特别之处。（你可以在状态 4 中看到）。

$end是检测到EOF时自动生成的特殊终端符号。（更准确地说，它是令牌值为 0 的终端，扫描器 returns 指示文件结束：(f)lex 生成的扫描器自动执行此操作。

LALR 中的 \[$end\] 前瞻

\[$end\] lookaheads in LALR

parsing

lalr

bison

lookahead

shift-reduce-conflict