重写 Bison 语法以修复转移/减少冲突

Question

以下是我的 Bison 语法规则的相关部分：

statement:
  expression ';' |
  IF expression THEN statement ELSE statement END_IF ';' 
  ;

expression:
  IDENTIFIER |
  IDENTIFIER '('expressions')' |
  LIT_INT |
  LIT_REAL |
  BOOL_OP |
  LOG_NOT expression |
  expression operator expression |
  '('expression')'
  ;

expressions:
  expression |
  expressions ',' expression  
  ;

operator: 
  REL_OP |
  ADD_OP |
  MULT_OP |
  LOG_OR  |
  LOG_AND
  ;

编译时，我得到 10 个 shift/reduce 冲突：

LOG_NOT表达式规则引起的5个冲突：

State 45

   25 expression: LOG_NOT expression .
   26           | expression . operator expression

    REL_OP   shift, and go to state 48
    ADD_OP   shift, and go to state 49
    MULT_OP  shift, and go to state 50
    LOG_OR   shift, and go to state 51
    LOG_AND  shift, and go to state 52

    REL_OP    [reduce using rule 25 (expression)]
    ADD_OP    [reduce using rule 25 (expression)]
    MULT_OP   [reduce using rule 25 (expression)]
    LOG_OR    [reduce using rule 25 (expression)]
    LOG_AND   [reduce using rule 25 (expression)]
    $default  reduce using rule 25 (expression)

    operator  go to state 54

5 冲突是由表达式操作符表达式规则引起的：

State 62

   26 expression: expression . operator expression
   26           | expression operator expression .

    REL_OP   shift, and go to state 48
    ADD_OP   shift, and go to state 49
    MULT_OP  shift, and go to state 50
    LOG_OR   shift, and go to state 51
    LOG_AND  shift, and go to state 52

    REL_OP    [reduce using rule 26 (expression)]
    ADD_OP    [reduce using rule 26 (expression)]
    MULT_OP   [reduce using rule 26 (expression)]
    LOG_OR    [reduce using rule 26 (expression)]
    LOG_AND   [reduce using rule 26 (expression)]
    $default  reduce using rule 26 (expression)

    operator  go to state 54

我知道这个问题与优先级有关。例如，如果表达式是：

a + b * c

Bison 在 a + 之后移动并希望找到一个表达式，还是将 a 简化为一个表达式？我有一种感觉，这是由于 Bison 1-token 前瞻限制，但我不知道如何重写规则来解决冲突。

我的教授会因为转移/减少冲突而扣分，所以我不能使用 %expect。我的教授也说过我们不能使用 %left 或 %right 优先级值。

这是我在 Stack 上的第一篇文章，所以如果我发布的这些都是错误的，请告诉我。我搜索了现有的帖子，但这似乎真的是个案。如果我使用 Stack 中的任何代码，我会在我提交的项目中注明来源。

谢谢！

Answer 1

正如所写，你的语法是模棱两可的。所以肯定有冲突。

没有约束优先级的固有规则，显然你也不允许使用野牛的优先级声明。如果您被允许，您将无法operator用作非终端，因为您需要区分

expr1 + expr2 * expr3             expr1 * expr2 + expr3
  |       |       |                 |       |       |
  |       +---+---+                 +---+---+       |
  |           |                         |           |
  |          expr                      expr         |
  |           |                         |           |
  +-----+-----+                         +-----+-----+         
        |                                     |
       expr                                  expr

如果+和*替换为 ，则无法区分它们operator。终端实际上​​必须是可见的。

现在，这里有一个快速的线索：

expr1 + expr2 + expr3    reduces expr1 + expr2 first
expr1 * expr2 + expr3    reduces expr1 * expr2 first

所以在 中non-terminal-1 + non-terminal-2，non-terminal-1不能产生x + y或x * y。但是在non-terminal-1 * non-terminal-2，non-terminal-1可以产生`x + y