yacc - 为什么我在 ')' 而不是 '(' 上有移位减少/冲突？

Question

我有类似的语法

%(var)

和

%var

和
(变量)

我的规则是这样的

optExpr:
    | '%''('CommaLoop')'
    | '%' CommaLoop

CommaLoop:
    val | CommaLoop',' val

Expr:
    MoreRules
    | '(' val ')'

问题是它似乎无法判断 ) 是否属于 %(CommaLoop)或 % (val)但它提示的是 ) 而不是 (。到底是什么？它不应该提示 ( 吗？我应该如何修复错误？我认为让 %( 成为一个 token 是一个很好的解决方案，但我想知道为什么 $( 在执行此操作之前不是错误。

Answer 1

这是由于 LR 解析的工作方式。 LR 解析实际上是自下而上的，根据语法规则的 RHS 将标记组合在一起，并用 LHS 替换它们。当解析器“移动”时，它会在堆栈上放置一个标记，但实际上还没有匹配规则。相反，它通过当前状态跟踪部分匹配的规则。当它达到与规则结束相对应的状态时，它可以减少，将 RHS 的符号从堆栈中弹出并将表示 LHS 的单个符号推回。因此，如果存在冲突，则在解析器到达某个规则的末尾并且无法决定是否减少(或减少什么)之前，它们不会出现。

在您的示例中，在看到 后% ( val ，这就是堆栈中的内容(顶部在此处的右侧)。当前瞻为 ) ，它无法决定是否应该通过规则 CommaLoop: val 弹出 val 和 reduce，或者是否应该移动 ) 所以它可以弹出 3 个东西并用规则 Expr 减少:'(' val ')'

我在这里假设你有一些额外的规则，比如 CommaLoop: Expr，否则你的语法实际上不匹配任何东西，bison/yacc 会提示未使用的非终端。