3

以下是我的 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 冲突：

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 中的任何代码，我会在我提交的项目中注明源代码。

谢谢！

4

2 回答 2

5

As written, your grammar is ambiguous. So it must have conflicts.

There is no inherent rule of binding precedences, and apparently you're not allowed to use bison's precedence declarations either. If you were allowed to, you wouldn't be able to use operator as a non-terminal, because you need to distinguish between

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

And you cannot distinguish between them if + and * are replaced with operator. The terminals actually have to be visible.

Now, here's a quick clue:

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

So in non-terminal-1 + non-terminal-2, non-terminal-1 cannot produce x + y or x * y. But in non-terminal-1 * non-terminal-2, non-terminal-1 can produce `x + y

于 2013-09-14T15:13:32.130 回答
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，等等）。

这使我可以在不使用任何内置 % 优先级函数的情况下将每个运算符设置为不同的优先级。

我能够毫无错误地解析我的所有测试输入文件。对设计有什么想法吗？

于 2013-09-14T18:15:29.443 回答