4

文法は次のとおりです。

1. program -> declaration-list
2. declaration-list -> declaration-list declaration | declaration
3. declaration -> var-declaration | fun-declaration
4. var-declaration -> type-specifier ID ; | type-specifier ID [ NUM ] ;
5. type-specifier -> int | void
6. fun-declaration -> type-specifier ID ( params ) compound-stmt
7. params -> param-list | void
8. param-list -> param-list , param | param
9. param -> type-specifier ID | type-specifier ID [ ]
10. compound-stmt -> { local-declarations statement-list }
11. local-declarations -> local-declarations var-declarations | empty
12. statement-list -> statement-list statement | empty
13. statement -> expression-stmt | compound-stmt | selection-stmt |
iteration-stmt | return-stmt
14. expression-stmt -> expression ; | ;
15. selection-stmt -> if ( expression ) statement |
if ( expression ) statement else statement
16. iteration-stmt -> while ( expression ) statement
17. return-stmt -> return ; | return expression ;
18. expression -> var = expression | simple-expression
19. var -> ID | ID [ expression ]
20. simple-expression -> additive-expression relop additive-expression |
additive-expression
21. relop -> <= | < | > | >= | == | !=
22. additive-expression -> additive-expression addop term | term
23. addop -> + | -
24. term -> term mulop factor | factor
25. mulop -> * | /
26. factor -> ( expression ) | var | call | NUM
27. call -> ID ( args )
28. args -> arg-list | empty
29. arg-list -> arg-list , expression | expression

bison -d-vxyz.lを介して発生するシフト削減の競合は状態97にあります

state 97

   29 selection-stmt: IF LFT_BRKT expression RGT_BRKT statement .
   30               | IF LFT_BRKT expression RGT_BRKT statement . ELSE statement

    ELSE  shift, and go to state 100

    ELSE      [reduce using rule 29 (selection-stmt)]
    $default  reduce using rule 29 (selection-stmt)

しかし、私はこの対立を解決する方法を知りません。答えを待っています。

4

4 に答える 4

8

'else'をシフトすることを優先して、競合を解決する必要があります。幸いなことに、bisonはそれを自動的に実行します（ただし、それでも通知されます）。

バイソンマニュアルのセクション5.2は、まさにこのシフト/削減の競合についてです。%expectそこに書かれているように、宣言を使用したい場合は、警告メッセージを削除できます。elseまたは、 bison / yaccの優先順位宣言を使用して、「優先シフト」の解決を明示的に宣言することもできます。トークンに、句のないプロダクションelseよりも高い優先順位を与えます。（デフォルトでは、プロダクションは最後のターミナルの優先順位を持っているため、プロダクション自体のようなものを使用することをお勧めします。この場合は、右括弧になります。）ifelse%prec IF

yaccこの特定のシフト/削減の競合は、 yaccに関する歴史的な論文、またはDragonの本で説明されているように、元のパーサジェネレータの解決戦略の動機の大部分でした。文法。この質問の解決策は優れた頭の体操ですが、実際には、通常、優先順位宣言またはBisonに組み込まれているあいまいさの排除を使用する方が簡単で保守しやすくなります。

この問題は、ドラゴンブックの演習の1つです。ソリューションの基本的な概要は次のようになります。

  1. statementinif (expression) statementがifステートメントでなくても、問題は発生しません。elseステートメントを開始できないため、先読みif ( 0 ) break;で減らすことはできません。else問題はif (0) if (0) break; else、elseをシフトする必要があるか（したがって、ifを2番目にアタッチする必要があるか）、2番目ifを減らして、をelse1番目にシフトする必要があるかどうかが明確ではないことifです。通常の慣行（およびyaccのあいまいさ解決アルゴリズム）が最初の方法を指示します。

  2. それでは、完全なifステートメントと不完全なifステートメントを区別しましょう。不完全なifステートメントは、else句で完了する可能性のあるステートメントであるため、すぐに続けることはできませんelse（が含まれているためelse）。完全なステートメントをelseで拡張することはできないため、不完全なステートメントで終了してはなりません。

したがって、次のようなことを試すことができます。

statement              : complete_statement
                       | incomplete_conditional

complete_statement     : complete_conditional
                       | statement_other_than_conditional

complete_conditional   : "if" '(' expression ')' complete_statement "else" complete_statement

incomplete_conditional : "if" '(' expression ')' statement
                       | "if" '(' expression ')' complete_statement "else" incomplete_conditional

Cのような言語には、囲まれたステートメントで終わることができる他のステートメントタイプがあります（たとえば、ループステートメント）。これらはすべて、終了ステートメントの完全性に応じて、「完全」と「不完全」に分ける必要があります。それがこのソリューションを煩わしくしている理由です。

注：上記の文法は、9年前に投稿された誤ったバージョンから修正されています。いくつかの答えは間違った答えを参照しています。残念ながら、私が見るかもしれないコメントでエラーを知らせるとは誰も考えていませんでした。誰かが間違ったコードを使用した場合はお詫び申し上げます。

于 2012-10-04T04:57:28.363 に答える
4

ここで私の答えを参照してください：シフトを削除するために文法を改革すると、if-then-elseの競合が減少します。私の経験では、「既知の競合」を決して残してはならず、それらを解決してください。N！= 0で％e​​xpect Nを使用することは安全ではありません、私見（もちろん、GLRは別として）。

于 2012-10-04T19:33:37.987 に答える
2

@riciの回答（受け入れられた回答）を試しましたが、失敗します。

statement: conditional | statement_other_than_conditional;
conditional: complete_conditional | incomplete_conditional;
complete_conditional: L_IF '(' expression ')' statement_other_than_conditional L_ELSE statement
| L_IF '(' expression ')' complete_conditional L_ELSE statement;
incomplete_conditional: L_IF '(' expression ')' statement;
statement_other_than_conditional: ';';
expression: IDENTIFIER;

$ bison --report=all rrr.y
rrr.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]

State 14 conflicts: 1 shift/reduce
State 15 conflicts: 1 shift/reduce

State 14

3 conditional: complete_conditional .  [$end, L_ELSE]
6 complete_conditional: L_IF '(' expression ')' complete_conditional . L_ELSE statement

L_ELSE  shift, and go to state 16

L_ELSE    [reduce using rule 3 (conditional)]
$default  reduce using rule 3 (conditional)


State 15

2 statement: statement_other_than_conditional .  [$end, L_ELSE]
5 complete_conditional: L_IF '(' expression ')' statement_other_than_conditional . L_ELSE statement

L_ELSE  shift, and go to state 17

L_ELSE    [reduce using rule 2 (statement)]
$default  reduce using rule 2 (statement)

クリス・ドッドの答えは（少なくともそうですが）良いです。少し適応：

statement: if_statement | noif_statement;

if_statement:
  IF '(' expression ')' statement
| IF '(' expression ')' noif_statement ELSE if_statement
;

noif_statement:
  IF '(' expression ')' noif_statement ELSE noif_statement
| RETURN ';'
;

expression: IDENTIFIER;

さらにステートメントルールがある場合：それが正しく再帰的でない場合（で終わらない場合）、 noif_statement（のようstatementに）に追加します。そうでなければ、例えばRETURN ';'

statement: blah '(' blah ')' statement ;

複製する：

| blah '(' blah ')' if_statement
| blah '(' blah ')' noif_statement

そして、最初のバリアントをif_statementに追加し、2番目のバリアントをnoif_statementに追加します。

于 2018-03-14T22:23:33.597 に答える
0

動作する別の戦略（@riciによって受け入れられた回答は機能しません、Chris Doddへの@RaqaouPiクレジットの回答は機能します）は、コードを一連のif-else / for / whileプレフィックスの後に、おそらく単一のぶら下がりが続くものとして扱うことです。または最後の簡単なステートメント。この例は、このニアリー文法をCのような言語に適合させたものです。

Statement         -> StatementPrefix:* (StatementEnd | DanglingIf)
StatementNoDangle -> StatementPrefix:* StatementEnd

StatementPrefix -> "if" _ "(" _ Expression _ ")" _ StatementNoDangle _ "else" _
                 | "while" _ "(" _ Expression _ ")" _

DanglingIf     -> "if" _ "(" _ Expression _ ")" _ Statement
StatementEnd   -> Simple _ ";"
                | "return" (_ Expression):? _ ";"
                | BlockStatement
                | "break" _ ";"
                | "continue" _ ";"
于 2018-09-10T21:17:05.910 に答える