[$end] lookaheads in LALR

Question

我正在尝试理解，野牛如何为这个简单的语法构建表：

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"放入每个符号的所有单元格中。但是对于Shift规则，我应该将" S5"放入' "终端）的列中（此单元格已经包含" R1"）。对我来说，这看起来像是轮班/减少冲突。但不是野牛。请解释该状态中如何出现" [$ end]" lookahead符号，以及如何在LR状态机器中处理此状态。

Answer 1

1. default的意思是"其他"，而不是"一切"。换句话说，您首先填写指定的操作，然后将默认操作用于任何其他LookAhead符号。

   如果没有默认操作，则任何未指定的LookAhead符号的操作都是错误。默认的减少操作通常用于减小算法会触发错误的算法大小。该优化可能是延迟错误报告的结果，但是在消耗另一个输入之前将始终检测到错误，这正是因为错误操作永远不会被默认偏移替换。（的确，许多解析器生成器绝不使用默认的换档操作。）

2. 如果您查看.output文件开头显示的语法，您会发现它已随着生产而增强：

   0 $accept: input $end
   

   yacc/bison总是添加这样的生产，以确保完整的输入与开始符号匹配。（当然，非末端input将被%start指令或语法中的第一个非末端声明的任何开始符号代替。）

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

   $end是检测到EOF时自动生成的特殊终端符号。（更确切地说，它是该令牌值为0的终端，扫描仪返回到文件结束：（f）Lex生成的扫描仪会自动执行此操作。