0

我正在编写一个编程语言解析器，但我陷入了这种 Shift/Reduce Conflict。

这是通过使用 -v 运行野牛获得的 parser.output 文件中的冲突状态

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 规则冲突。

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

（大写字母是记号）

ident 规则很简单

ident: TIDENT
          ;

Args，通过调用使用。

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

调用函数

call:
       TIDENT TLPAREN args TRPAREN
       ;

表达式的 expr

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
    ;

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

如果您需要查看完整的复制语法，请查看 hastebin https://hasteb.in/zozifopi.shell

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

4

3 回答 3

2

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

如果您对解析器总是将其解释为函数调用感到高兴（这是它的默认行为，因为它更喜欢移位），那么您可以添加几个优先级声明，以便调用具有更高的优先级减少：

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

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

于 2019-02-14T21:13:14.337 回答
0

问题是，当解析器移动了一个 TIDENT 标记并向前看一个TLPAREN标记时，语法允许两种选择：

  1. 将 减少TIDENT到ident, 或
  2. 转移TLPAREN.

Bison 通常会通过选择换档来解决换档/减少冲突，如果在这种情况下这是你想要的，那么你可以简单地忽略警告。

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

call:
       ident TLPAREN args TRPAREN
       ;

TLPAREN使用该规则，在不先将 减少为TIDENT的情况下，不再可以选择转移ident。

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

于 2019-02-14T18:29:58.833 回答
0

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

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

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

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

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

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

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

或者对两者和自身使用相同的ident非终端，这样它总是会减少它。callexpr

于 2019-02-14T18:32:16.523 回答