为什么我的轮班减少/冲突')'而不是'('?

Question

我有类似

%(var)

and

%var

的 语法 (var)

我的规则类似于

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

CommaLoop:
    val | CommaLoop',' val

Expr:
    MoreRules
    | '(' val ')'

问题是它似乎无法判断 ) 是否属于 %(CommaLoop) 或 % (val) 但它抱怨) 而不是 (。到底是什么？它不应该抱怨 ( 吗？我应该如何修复错误？我认为制作 %( 一个令牌是一个很好的解决方案但我想在执行此操作之前确定为什么 $( 不是错误。

Answer 1

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

在您的示例中，看到 % ( val 后，这就是堆栈上的内容（顶部位于当前瞻为 ) 时，它无法决定是否应该弹出 val 并通过规则 CommaLoop: val 进行归约，或者是否应该这样做。移动)，这样它就可以弹出 3 个东西，并使用规则 Expr: '(' val ')' 减少

我在这里假设你有一些额外的规则，例如as CommaLoop: Expr，否则你的语法实际上不匹配任何内容，并且 bison/yacc 会抱怨未使用的非终结符。

Answer 2

现在，你的解释和你的语法似乎不相符。在您的解释中，您将所有三个短语显示为具有“var”，但您的语法显示以“%”开头的短语允许逗号分隔的列表，而没有的短语仅允许单个“val”。

目前，我假设所有三个都应该允许使用逗号分隔的列表。在这种情况下，我会像这样分解语法：

optExpr: '%' aList

aList: CommaLoop
    | parenList

parenList: '(' CommaLoop ')'

CommaLoop: 
    | val 
    | CommaLoop ',' val

Expr: MoreRules
    | parenList

我更改了 optExpr 和 Expr，因此两者都不能匹配空序列 - 我的猜测是您可能不打算这样做。我已经充实了它，足以通过 byacc 运行它；它不会产生警告或错误。