[$end\] LALR中的看头

Question

我想了解bison是如何为这种简单的语法构建表的：

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

我能够计算LR(1)转换表和项集，但我不明白状态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表的每个符号的所有单元格中。但是对于shift规则，我应该将's5‘放在'+’终端的列中(这个单元格已经包含'r1')。对我来说，这看起来像是转移/减少冲突。但不适合野牛。请解释该“$end”lookahead symbol是如何在此状态中出现的，以及该状态是如何由LR状态机整体处理的。

Answer 1

1. default的意思是“其他一切”，而不是“一切”。换句话说，首先填写指定的操作，然后对任何其他前瞻性符号使用默认操作。 如果没有默认操作，则任何未指定的前瞻性符号的操作都是错误。默认的约简操作通常用于缩小表的大小，否则算法会触发错误。这种优化可能会导致延迟报告错误，但是在使用另一个输入之前总是会检测到错误，这正是因为错误操作从未被默认的移位所取代。(实际上，许多解析器生成器根本不使用默认的shift操作。)
2. 如果您查看.output文件开头显示的语法，您会发现它已经被产品增强了： 0 $accept:输入$end Yacc/bison总是添加这样的产品，以确保完整的输入与开始符号匹配。(当然，非终端input将被用%start指令声明的任何开始符号替换，或者用语法中的第一个非终结符代替。) 除了减少$accept符号导致输入被接受之外，这个规则没有什么特别之处。(在状态4中可以看到这一点)。 $end是一种在检测到EOF时自动生成的专用终端符号。(更准确地说，它是标记值为0的终端，扫描仪返回该终端以指示文件结束：(F)lex生成的扫描器自动完成此操作。