重写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个移位/规约冲突：

其中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个令牌向前查看的限制，但我无法弄清楚如何重写规则以解决冲突。

我的教授会因移位/规约冲突而扣分，因此我不能使用%expect。我的教授还声明我们不能使用%left或%right优先级值。

这是我在Stack上的第一篇文章，请告诉我是否发布不当。我已搜索现有的帖子，但这似乎是一个逐案例的事情。如果我从Stack中使用任何代码，我将在提交的项目中注明来源。

谢谢！

- teerow

Answer 1

你写的语法存在歧义，因此必然会发生冲突。

并不存在绑定优先级的固有规则，而显然你不能使用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

所以在非终端符1 + 非终端符2中，非终端符1不能生成x + y或x * y。但在非终端符1 * 非终端符2中，非终端符1可以生成x + y。

- rici

---

谢谢！我曾经认为通过更改一个标记可以解决问题，但现在我意识到整个表达式语法结构导致了冲突。我想我可能已经解决了这些冲突。 - teerow

Answer 2

谢谢！我进行了更多的故障排除，并通过重写表达式和运算符规则来修复了减少/冲突错误：

expression:
  expression LOG_OR term1 |
  term1
  ;

term1:
  term1 LOG_AND term2 |
  term2
  ;

term2:
  term2 REL_OP term3 |
  term3
  ;

term3:
  term3 ADD_OP term4 |
  term4
  ;

term4:
  term4 MULT_OP factor |
  factor
  ;

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

expressions:
  expression |
  expressions ',' expression  
  ;

我不得不重新排列实际上是表达式和实际上是因子的内容。我制定了一个因子规则，包括所有因子（终止符），该规则具有最高优先级。然后，我为每个表达式制定了一个term#规则，这也将它们设置在不同的优先级水平上（term5的优先级高于term4，term4的优先级高于term3等）。

通过这样做，我能够在不使用任何内置的%优先级函数的情况下将每个运算符设置为不同的优先级。

我能够解析所有测试输入文件而没有错误。对于设计有什么想法吗？

- teerow