在 Bison 中解析函数调用（例如 `exp '(' exp ')'`）：导致 shift/reduce 错误（优先级问题）

Question

我正在尝试解析一个函数调用（目前只有一个参数，但当我让它工作时我会考虑多个参数）。

假设exp定义为

%left '+'
%precedence CALL

exp:
    exp '+' exp { ... }
|   exp '(' exp ')' %prec CALL { ... }
|   LITERAL { ... }
;

这会产生歧义。如果我使用 -Wcounterexamples 那么它说 exp '+' exp · '(' exp ')' 可以用两种方式解析，在 '('.

处移动或减少

calc.y: warning: shift/reduce conflict on token '(' [-Wcounterexamples]
  Example: exp '+' exp • '(' exp ')'
  Shift derivation
    exp
    ↳ exp '+' exp
              ↳ exp • '(' exp ')'
  Example: exp '+' exp • '(' exp ')'
  Reduce derivation
    exp
    ↳ exp             '(' exp ')'
      ↳ exp '+' exp •

它似乎不知道调用的优先级应该高于或低于 +。我该怎么做才能确保它知道 x+y(z) 应该等同于 x+(y(z)) 而不是 (x+y)(z)？

似乎相关。

Answer 1

您告诉 bison 产生式 exp: exp '(' exp ')' 和先行符号 + 的相对优先级。但是您还没有告诉 bison 产生式 exp: exp '+' exp 和先行符号 ( 的相对优先级。这就是为什么你在前瞻符号 '('

上有冲突

请记住，优先级比较总是在产生式（可能会减少）和先行符号（可能会移动）之间进行。我知道 yacc/bison 让它看起来像是在两个符号之间进行比较，但这是一种错觉。每个产品都由一个符号表示——默认情况下是最右边的终端——但仅此而已。这种约定对于简单的情况很直观，但在其他情况下会造成混淆，恕我直言。

最简单的解决方案是用符号 ( 来标识调用产生的优先级，而不是发明一个伪令牌。也就是说，将 %prec 声明更改为 %prec '(' 并在您的优先规则中将 CALL 替换为 (。

（事实上，您并不真正需要 %prec 声明，因为与 + 前瞻标记不可能发生冲突。）

在 Bison 中解析函数调用（例如 `exp '(' exp ')'`）：导致 shift/reduce 错误（优先级问题）

Parsing a function call (e.g. `exp '(' exp ')'`) in Bison: results in shift/reduce errors (precedence issue)

bison

operator-precedence

shift-reduce-conflict

flex-lexer