parsing - 重写 Bison 语法以修复 shift/reduce 冲突

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 个移位/归约冲突:

5 个冲突是由LOG_NOT 表达式规则引起的:

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

正如所写，你的语法不明确。所以肯定有冲突。

没有绑定(bind)优先级的固有规则，显然您也不允许使用 bison 的优先级声明。如果允许，您将无法使用 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