パーサーはシフト/リダクションの競合をどのように解決しますか？

Question

私は、テキストファイルの式の数（1行に1つ）を解決する算術式の文法を持っています。 YACCをコンパイルしている間に、私はメッセージ2シフトが競合を減らすようになっています。しかし、私の計算は適切です。パーサが適切な出力を与えている場合、どのようにシフト/コンフリクトの競合が解決されますか？そして私の場合、YACC文法でそれを解決する方法はありますか？

YACC文法

Calc : Expr    {printf(" = %d\n",$1);} 
    | Calc Expr   {printf(" = %d\n",$2);} 
    | error    {yyerror("\nBad Expression\n ");} 
    ; 
Expr : Term    { $$ = $1;   } 
    | Expr '+' Term  { $$ = $1 + $3; } 
    | Expr '-' Term  { $$ = $1 - $3; } 
    ; 
Term : Fact    { $$ = $1;   } 
    | Term '*' Fact  { $$ = $1 * $3; } 
    | Term '/' Fact  { if($3==0){ 
       yyerror("Divide by Zero Encountered."); 
      break;} 
       else 
       $$ = $1/$3;  
        } 
    ; 
Fact : Prim    { $$ = $1;  } 
    | '-' Prim   { $$ = -$2;  } 
    ;  
Prim : '(' Expr ')'  { $$ = $2;  } 
    | Id     { $$ = $1;  } 
    ; 
Id :NUM     { $$ = yylval; } 
    ; 

私は私の文法で、このような矛盾を取り除くためにどのような変更を行う必要がありますか？

Answer 1

Bison/yaccは、シフトを選択することでシフト削減競合を解決します。これについては、bison manualのShift-Reduce conflictsのセクションで説明しています。

あなたの問題は入力がちょうど一連のExprで、それらの間に区切り文字なしで一緒に実行されていることです。

4 - 2 

は一つの式（4-2）することができ、あるいは2つの式（4、-2）することができます：それはことを意味します。バイソン、生成されたパーサは常にシフトすることを好むので、パーサは、それが2行に入力されたされた場合でも、1式としてそれを解析することを選択します：あなたは、ユーザーがそのような彼らの表現を入力できるようにしたい場合は

4 
-2 

、区切り記号がなければ、（それは比較的良性であるため）紛争に生きるか、それを文法にまとめることができますが、それはもう少し作業です。文法に入れるには、Exprという2つの異なるタイプを定義する必要があります。トップレベルで使用するものは単項マイナスで始めることはできません。もう1つは他のどこでも使用できます。単項マイナスで始めることができます。

あなたが本当にやりたいことは、改行や他の種類の式区切りを使用することだと思います。これは、改行をパーサに渡してCalcをCalc: | Calc '\n' | Calc Expr '\n'に変更するのと同じくらい簡単です。

---

これは他の場所に表示されていますが、見つかりません。そこで、式の先頭に単項マイナスを使用しないようにして、区切り文字なしで式を一緒に実行できるようにします。しかし、シフト-reduce衝突を発生させることなく、

input: %empty | input n_expr { /* print $2 */ } 

expr: term | expr '+' term | expr '-' term 
n_expr: n_term | n_expr '+' term | n_expr '-' term 

term: factor | term '*' factor | term '/' factor 
n_term: value | n_term '+' factor | n_term '/' factor 

factor: value | '-' factor 

value: NUM | '(' expr ')' 

あなたの文法と同じ言語を解析しますn_を開始する非端子は単項マイナスで始めることはできません。同じ言語を解析するので、入力はまだ単一の式として解析されます。期待通りの結果を得るには

4 
(-2)