为什么这个语法没有 reduce/reduce 冲突？

Question

考虑以下（诚然荒谬 - 它已被大大简化以说明这一点）语法：

negationExpression
    : TOK_MINUS constantExpression %prec UNARYOP
    | testRule
    ;

constantExpression
    : TOK_INTEGER_CONSTANT
    | TOK_FLOAT_CONSTANT
    ;

testRule
    : negationExpression constantExpression  // call this Rule 1
    | constantExpression   // Rule 2
    ;

当运行这个语法时，Bison 不会抱怨 reduce/reduce 冲突，但对我来说似乎有一个。假设我们已经解析了一个 negationExpression 和一个 constantExpression；在我看来，根据上述定义，解析器现在可以做两件事：

使用上面的规则 1

testRule

使用上面的规则 2 将 constantExpression 缩减为 testRule（在这种情况下，negationExpression 将保持不变，因此解析堆栈将如下所示：negationExpression testRule)

但是没有发出警告，当我查看 Bison 生成的 .output 文件时，似乎没有任何歧义：

state 5

    6 testRule: constantExpression .

    $default  reduce using rule 6 (testRule)
...
state 9

    5 testRule: negationExpression constantExpression .

    $default  reduce using rule 5 (testRule)

根据 Bison docs:

A reduce/reduce conflict occurs if there are two or more rules that apply to the same sequence of input.

这里不正是这样吗？

Answer 1

不，这里不适用。

"Sequence of input" 是一个不幸的措辞；真正的意思是 "same input"，或者更明确地说，"same prefix subsequence of a valid input"。换句话说，如果有两个或更多规则可以应用于整个输入，直到当前读取点（并考虑前瞻）。

在你的语法中，testRule从不跟随任何东西。它（和 negationExpression ）只能在某些推导的一开始就减少。因此，如果（部分减少的）输入以 negationExpression constantExpression 结尾，则不可能将 constantExpression 减少为 testRule，因为起始符号的推导不能包含 testRule 在非-初始位置。

为什么这个语法没有 reduce/reduce 冲突？

Why doesn't this grammar have a reduce/reduce conflict?

parsing

bison

reduce-reduce-conflict