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 個のシフト/リデュースの競合が発生します。

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 のコードを使用する場合は、提出したプロジェクトにソースを記載します。

ありがとう！

4

2 に答える 2

5

書かれているように、あなたの文法はあいまいです。したがって、競合が発生する必要があります。

優先順位をバインドする固有の規則はありません。明らかに、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 + yx * ynon-terminal-1 * non-terminal-2non-terminal-1

于 2013-09-14T15:13:32.130 に答える
2

ありがとう！さらにトラブルシューティングを行い、式と演算子のルールを書き直して、reduce/conflict エラーを修正しました。

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 よりも優先順位が高いなど)。

これにより、組み込みの % precedence 関数を使用せずに、各演算子に異なる優先順位を設定することができました。

すべてのテスト入力ファイルをエラーなしで解析できました。デザインについて何か考えはありますか？

于 2013-09-14T18:15:29.443 に答える