c语言 - 编程语言语法的野牛移位/减少冲突

Question

我正在编写一个编程语言解析器，但我陷入了这种转移/减少冲突。

这是解析器中的冲突状态.输出文件通过运行带有 -v 的野牛获得

State 1
24 ident: TIDENT .
26 call: TIDENT . TLPAREN args TRPAREN
TLPAREN  shift, and go to state 24
TLPAREN   [reduce using rule 24 (ident)]
$default  reduce using rule 24 (ident)

当我尝试实现呼叫规则时发生冲突，它似乎与正常的识别规则冲突。

这是语法的某些部分，(为简单起见删除了操作，但不需要它们。 我也不确定定义规则的顺序是否重要，如果我错了，请纠正我)

(大写字母是令牌)

识别规则很简单

ident: TIDENT
;

参数，由调用使用。

args: /* empty */
|
expr
|
args TCOMMA expr
;

调用函数

call:
TIDENT TLPAREN args TRPAREN
;

表达式的表达式

expr:
number
|
ternary
|
bool
|
string
|
ident
|
call
|
TLPAREN expr TRPAREN
|
expr TPLUS expr
|
expr TMINUS expr
|
expr TSLASH expr
|
expr TSTAR expr
|
expr TGT expr
|
expr TGE expr
| 
expr TLT expr
|
expr TLE expr
;

问题：为什么语法有移位/减少冲突，你如何解决它？我见过类似的样式解析器，它们没有冲突，这真的很奇怪。

如果您需要查看完整的语法以进行复制，这里有一个匆忙的 https://hasteb.in/zozifopi.shell

如果您需要有关其他任何内容的更多详细信息，请在评论中告诉我，我将相应地编辑问题。

Answer 1

这里的根本问题是你的语法是模棱两可的，因为语句不需要终止(stmts: stmts stmt)，语句可以是一个表达式。因此，两个表达式可以一个接一个地出现，没有任何标点符号。这意味着f(3)可以是一个表达式(函数调用)或两个表达式(f和(3))。

如果你很高兴解析器总是将其解释为函数调用(这是它的默认行为，因为它更喜欢移位)，那么你可以添加几个优先级声明，以便调用的优先级高于减少：

%precedence TIDENT
//...
%precedence TLPAREN
// ...
%%
expr : ident %prec TIDENT

这只会掩盖歧义，并可能导致令人惊讶的解析。但唯一的其他解决方案是使语言明确。

Answer 2

问题是，当解析器移动了 TIDENT 标记并展望TLPAREN标记时，语法允许两种替代方法：

1. 将TIDENT降低到ident，或
2. 转移TLPAREN.

Bison通常会通过选择转移来解决移位/减少冲突，如果这是您想要的，那么您可以简单地忽略警告。

但是，在这种特殊情况下，您应该能够通过更改call生产的规则来解决冲突：

call:
ident TLPAREN args TRPAREN
;

有了这条规则，在不首先将TIDENT降低到ident的情况下转移TLPAREN不再是一种选择。

或者，您可以考虑完全删除非终端ident，而是直接使用TIDENT现在使用ident。 可能还有其他选择。 哪个最适合您可能取决于您尝试对语义操作执行的操作。 我不能更具体地评论这一点，因为您选择将语义操作排除在我们的考虑范围之外。

Answer 3

默认情况下，Bison会生成一个LR解析器，这是一个自下而上的解析器，可以决定是移动令牌还是减少令牌，可以决定每个状态。

冲突非常简单，输出本身很好地解释了(我想知道什么不清楚)，它告诉你：

如果我找到一个IDENTIFIER我应该通过规则 24 将其减少到ident非终端，还是应该按照规则将其call移动？

这是因为一旦减少你就无法转移，反之亦然，这确实造成了冲突。

要解决冲突，您需要将该选择移动到解析器的相同状态，以便它能够根据上下文做出决定。

由于ident只有一个终端IDENT规则，并且同样适用于呼叫，因此您可以轻松地在同一级别移动所有内容以使其始终移动：

expr: 
IDENT | 
IDENT LPAREN args RPAREN |
...

或者对call和expr本身使用相同的非ident终端，因此它将始终减少它。