2

Ubuntu Linux でこの bison コードを実行すると、次の警告が表示されます。

- shift/reduce conflict [-Wconflicts-sr]
- reduce/reduce conflicts [-Wcolficts-sr]

より明確にするためのスクリーンショットを次に示します: http://i.imgur.com/iznzSsn.png

編集:reduce/reduceエラーが入っています

line 86 : typos_dedomenwn
line 101: typos_synartisis

シフト/リデュースエラーは次のとおりです。

line 129: entoli_if

それらを修正する方法が見つかりません誰かが助けてくれますか?

バイソンのコードは次のとおりです。

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int totalerrors=0;

extern int yylex();
extern FILE *yyin;
extern int lineno; //Arithmos grammis pou kanei parse

//error handling
void yyerror(const char *msg) {
}
//filling the error array
void printError(char y[],int x){
    //param 1: error string
    //param 2: line number
    char temp[15];
    char temp2[5];
    char final[256];
    sprintf(temp2,"%d: ",x);
    strcpy(temp, "In Line ");
    strcat(temp,temp2);
    strcpy(final,"");
    strcat(final,temp);
    strcat(final,y);
    printf("%d) %s\n",totalerrors+1,final);
    totalerrors++;
}
%}
%start start
%token T_sigkritikos_telestis
%token T_typos_dedomenwn
%token T_typos_synartisis
%token T_stathera
%token T_newline
%token T_kefalida_programmatos
%token T_extern
%token T_void
%token T_return
%token T_if
%token T_else
%token T_plus
%token T_minus
%token T_mult
%token T_div
%token T_percentage
%token T_int
%token T_bool
%token T_string
%token T_true
%token T_false
%token T_id
%token T_semic
%token T_comma
%token T_openpar
%token T_closepar
%token T_ampersand
%token T_begin
%token T_end
%token T_excl
%token T_or
%token T_equals
%token T_semileft
%token T_semiright
%%
start: exwterikes_dilwseis T_kefalida_programmatos tmima_orismwn tmima_entolwn;

exwterikes_dilwseis: exwteriko_prwtotypo exwterikes_dilwseis
    | ;

exwteriko_prwtotypo: T_extern prwtotypo_synartisis;

tmima_orismwn: orismos tmima_orismwn
    | ;

orismos: orismos_metavlitwn
    | orismos_synartisis
    | prwtotypo_synartisis;

orismos_metavlitwn: typos_dedomenwn lista_metavlitwn T_semic;

typos_dedomenwn: T_int
    | T_bool
    | T_string;

loop1: T_comma T_id
    | ;

lista_metavlitwn: T_id loop1;

orismos_synartisis: kefalida_synartisis tmima_orismwn tmima_entolwn;

prwtotypo_synartisis: kefalida_synartisis T_semic;

kefalida_synartisis: typos_synartisis T_id T_openpar lista_typikwn_parametrwn T_closepar
    | typos_synartisis T_id T_openpar T_closepar;

typos_synartisis: T_int
    | T_bool
    | T_void;

lista_typikwn_parametrwn: typikes_parametroi loop2;

loop2: T_comma typikes_parametroi
    | ;

typikes_parametroi: typos_dedomenwn T_ampersand T_id;

tmima_entolwn: T_begin loop3 T_end;

loop3: entoli loop3
    | ;

entoli: apli_entoli T_semic
    | domimeni_entoli
    | sintheti_entoli;

sintheti_entoli: T_semileft loop3 T_semiright;

domimeni_entoli: entoli_if;

apli_entoli: anathesi 
    | klisi_sunartisis
    | entoli_return
    | ;

entoli_if: T_if T_openpar geniki_ekfrasi T_closepar entoli else_clause 
    | T_if T_openpar geniki_ekfrasi T_closepar entoli;

else_clause: T_else entoli;

anathesi: T_id T_equals geniki_ekfrasi;

klisi_sunartisis: T_id T_openpar lista_pragmatikwn_parametrwn T_closepar 
    | T_id T_openpar T_closepar;

lista_pragmatikwn_parametrwn: pragmatiki_parametros loop4;

loop4: T_semic pragmatiki_parametros loop4
    | ;

pragmatiki_parametros: geniki_ekfrasi;

entoli_return: T_return geniki_ekfrasi 
    | T_return;

geniki_ekfrasi: genikos_oros loop5;

loop5: T_or T_or genikos_oros loop5
    | ;

genikos_oros: genikos_paragontas loop6;

loop6: T_ampersand T_ampersand loop6 
    | ;

genikos_paragontas: T_excl genikos_protos_paragontas
    | genikos_protos_paragontas;

genikos_protos_paragontas: apli_ekfrasi tmima_sigrisis
    | apli_ekfrasi;

tmima_sigrisis: T_sigkritikos_telestis apli_ekfrasi;



apli_ekfrasi: aplos_oros loop7;

loop7: T_plus aplos_oros loop7
    | T_minus aplos_oros loop7
    | ;

aplos_oros: aplos_paragontas loop8;

loop8: T_mult aplos_paragontas loop8
    | T_div aplos_paragontas loop8
    | T_percentage aplos_paragontas loop8
    | ;

aplos_paragontas: T_plus aplos_prot_oros
    | T_minus aplos_prot_oros
    | aplos_prot_oros;

aplos_prot_oros: T_id
    | stathera
    | klisi_sunartisis
    | T_openpar geniki_ekfrasi T_closepar;

stathera: T_true
    |T_false;

%%
int main(int argc, char *argv[]){
    ++argv; --argc;  //agnooume to onoma tou exe
    if (argc==1) {
        FILE *fp = fopen(argv[0],"r");
        if (fp!=NULL) {
            printf("Reading input from file: %s\n",argv[0]);
            printf("Output:\n\n");
            yyin = fp;
            yyparse();
        } else {
            printf("File doesn't exist\n");
            return 1;
        }
    } else if (argc>1) {
        printf("Only one file allowed for input...\n");
        return 1;
    } else {
        printf ("Parsing from stdin..\n");
        yyparse();
    }
    if (totalerrors==0) {
        printf("All good!\n");
        printf("===================================\n");
        printf("Parsing complete! No errors found!!\n");
    } else {
        printf("===================================\n");
        printf("Total Errors: %d\n",totalerrors);
    }
    return 0;
}
4

1 に答える 1

8

A. 冗長な非端末

縮小/縮小の競合は、異なるタイプを集めるためだけに存在する 2 つの非端末があるためです。

typos_dedomenwn: T_int
    | T_bool
    | T_string;

typos_synartisis: T_int
    | T_bool
    | T_string;

これらの非終端記号が使用されている場合、パーサーはどれが適用されるかを知ることができません。宣言がさらに進むまで、それはわかりません。しかし、それは問題ではありません。単一の非終端記号を定義して、typos全体で使用できます。

typos: T_int
    | T_bool
    | T_string;

orismos_metavlitwn: typos lista_metavlitwn T_semic;
kefalida_synartisis: typos T_id T_openpar lista_typikwn_parametrwn T_closepar
    | typos T_id T_openpar T_closepar;
typikes_parametroi: typos T_ampersand T_id;

B. 他にぶら下がっている

shift/reduceの競合は、「C」スタイルのifステートメントの典型的な問題です。これらのステートメントは、あいまいではない方法で説明するのが困難です。検討:

if (expr1) if (expr2) statement1; else statement2;

が2 番目elseの と一致する必要があることがわかっているため、上記は次と同等です。 if

if (expr1) { if (expr2) statement1; else statement2; }

しかし、文法は次のような他の可能な解析とも一致します:

if (expr1) { if (expr2) statement1; } else statement2;

この問題には、次の 3 つの解決策があります。

  1. 何もしない。ここでは、Bison は設計上、正しいことを行います。常に "reduce" よりも "shift" を優先します。これが意味することは、 anelseが open ステートメントと一致する場合if、bison は常にそれを行うということです。これについては、特にドラゴンの本にかなり良い説明があります。elseif

    このソリューションの問題点は、シフト/リデュースの競合に関する警告が引き続き表示され、"OK" 競合と新しく作成された "not OK" 競合を区別するのが難しいことです。Bison は%expect宣言を提供するので、予想される競合の数を伝えることができます。これにより、正しい数が見つかった場合に警告が抑制されますが、それでもかなり脆弱です。

  2. 優先順位宣言を使用します。これらはbison のマニュアルに記載されています。そして、ダングリングelseの問題を解決する際のそれらの使用は、その章の実行中の例です. あなたの場合、次のようになります。

    %precedence T_then  /* Fake terminal, needed for %prec */
    %precedence T_else
     /* ... */
    %%
     /* ... */
    
    entoli_if: T_if T_openpar geniki_ekfrasi Tw_closepar entoli T_else entoli
       | T_if T_openpar geniki_ekfrasi T_closepar entoli %prec T_then
    

    ここでは、トークンelse_clauseを隠すため、不要な非終端記号を削除しました。else何らかの理由でそれを保持したい場合は、それを使用するプロダクション%prec T_elseの最後に a を追加する必要があります。entoli_if

    この%precedence宣言は、bison 3.0 以降でのみ使用できます。以前のバージョンの bison を使用している場合は、%nonassoc代わりに宣言を使用できますが、これにより他のエラーが隠される可能性があります。

  3. 文法を修正します。明確な文法を作成することは実際には可能ですが、少し手間がかかります。

    重要な点は次のとおりです。

    if (expr) statement1 else statement2
    

    statement1if一致しないステートメントにすることはできません。ステートメントの場合statement1は、句を含める必要があります。それ以外の場合、外側の in は内側のと一致します。そして、それは次のような の末尾のステートメントに再帰的に適用されますifelseelseififstatement1

    if (e2) statement2; 
      else if (e3) statement3
      else /* must be present */ statement;
    

    ifこれは、ステートメントを「一致する」ステートメント (すべてが によって一致する場合) と「一致しない」ステートメントに分割することで表現できelseます。アイデアをあなたの文法に合わせてください)。

    statement: matching_statement | non_matching_statement ;
    matching_statement: call_statement | assignment_statement | ...
        | matching_if_statement
    non_matching_statement: non_matching_if_statement
        /* might be others, see below */
    
    if_condition: "if" '(' expression ')' ;
    
    matching_if_statement:
          if_condition matching_statement "else" matching_statement ;
    non_matching_if_statement:
          if_condition statement
        | if_condition matching_statement "else" non_matching_statement
        ; 
    

    whileC では、ステートメント ( , )で終了できる他の複合ステートメントがありますfor。これらのそれぞれには、最終ステートメントが一致するか一致しないかに応じて、「一致する」バージョンと「一致しない」バージョンもあります。

    while_condition: "while" '(' expression ')' ;
    matching_while_statement: while_condition matching_statement ;
    non_matching_while_statement: while_condition non_matching_statement ;
    

    私の知る限り、これはあなたの言語には当てはまりませんが、将来的にはそのようなステートメントを含めるように拡張することをお勧めします。

C.バイソンスタイルに関する注意事項

  1. Bison では、一重引用符で囲んだ単一文字トークンをそのまま使用できます。したがって、それを使用する詳細なルールを宣言してから記述する代わりに、次のT_openparように記述できます'('。宣言する必要さえありません。(フレックスまたはその他のスキャナーでは、return '(';代わりに を使用return T_openparします。そのため、トークンを宣言する必要はありません。) 通常、これにより文法が読みやすくなります。

  2. Bison では、トークンに人間が読める名前を指定することもできます。(この機能はすべてのyacc派生物にあるわけではありませんが、かなり一般的です。)これにより、文法が読みやすくなります。たとえば、次のようにifおよびelseトークンに名前を付けることができます。

    %token T_if "if"
    %token T_else "else"
    

    そして、文法規則で引用符で囲まれた文字列を使用できます。(dangling-else 問題の最後の例でそれを行いました。) flex スキャナーでは、トークン記号T_ifT_else.

  3. のような 2 つのシンボル トークンがある&&場合、通常は、パーサーが 2 つの連続したトークンを認識するのではなく、スキャナーがそれを認識して 1 つのトークンを返す方が適切です&。2 番目のケースでは、パーサーは以下を認識します。

    boolean_expr1 &  & boolean_expr2
    

    あたかも書かれているかのように

    boolean_expr1 && boolean_expr2
    

    ただし、最初のものは報告されるべきエラーである可能性が最も高いです。

  4. Bison は、ボトムアップ LALR(1) パーサー ジェネレーターです。左再帰を削除する必要はありません。ボトムアップ パーサーは左再帰を好み、通常、左再帰文法はより正確で読みやすいです。たとえば、次のように宣言することをお勧めします。

    apli_ekfrasi: aplos_oros
        | apli_ekfrasi '+' aplos_oros
        | apli_ekfrasi '-' aplos_oros;
    

    LL スタイルの繰り返しサフィックスを使用するよりも (loop7文法で)。左再帰文法は、パーサー スタックを拡張せずに解析でき、式の構文構造をより正確に表現するため、パーサー アクションをより簡単に記述できます。

    文法には、再訪したくなる箇所が他にもたくさんあります。

    (このアドバイスは、バイソンのマニュアルから直接引用したものです。「常に左再帰を使用する必要があります。これは、制限されたスタック スペースを持つ任意の数の要素のシーケンスを解析できるためです。」)

于 2015-09-28T15:32:15.170 に答える