[解決済み] シフト／リデュース カップ付きエラー

質問

こんにちは、私は大学で使用しているプログラミング言語のパーサーを、jflexとCupを使って書いています。 プロセスや変数宣言など、最初の基本的な構造だけから始めました。

次のようなエラーが発生します。

  Warning : *** Shift/Reduce conflict found in state #4   
  between vardecls ::= (*)  
  and     vardecl ::= (*) IDENT COLON vartyp SEMI   
  and     vardecl ::= (*) IDENT COLON vartyp EQEQ INT SEMI  
  under symbol IDENT  
  Resolved in favor of shifting.      

  Warning : *** Shift/Reduce conflict found in state #2   
  between vardecls ::= (*)    
  and     vardecl ::= (*) IDENT COLON vartyp SEMI    
  and     vardecl ::= (*) IDENT COLON vartyp EQEQ INT SEMI   
  under symbol IDENT  
  Resolved in favor of shifting.   

私のCupでのコードは次のようなものです。

non terminal programm;
non terminal programmtype;
non terminal vardecl;
non terminal vardecls;
non terminal processdecl;
non terminal processdecls;
non terminal vartyp;


programm ::= programmtype:pt vardecls:vd processdecls:pd
                {: RESULT = new SolutionNode(pt, vd, pd); :} ;


programmtype ::= IDENT:v 
                {: RESULT = ProblemType.KA; :} ;


vardecls ::= vardecl:v1 vardecls:v2
                {:  v2.add(v1);
                    RESULT = v2; :}

            | 
                {:  ArrayList<VarDecl> list = new ArrayList<VarDecl>() ;
                    RESULT = list;   :} 
            ;

vardecl ::= IDENT:id COLON vartyp:vt SEMI
                {: RESULT = new VarDecl(id, vt); :}
            | IDENT:id COLON vartyp:vt EQEQ INT:i1 SEMI
                {: RESULT = new VarDecl(id, vt, i1); :} 
            ;


vartyp ::= INTEGER 
            {: RESULT = VarType.Integer ; :} 
            ;


processdecls ::= processdecl:v1 processdecls:v2
                {:  v2.add(v1);
                    RESULT = v2; :}
            | {:    ArrayList<ProcessDecl> list = new ArrayList<ProcessDecl>() ;
                    RESULT = list;   :} 
            ;

processdecl ::= IDENT:id COLON PROCESS vardecls:vd BEGIN END SEMI
                {: RESULT = new ProcessDecl(id, vd); :}
            ;

Process Declaration と VariableDeclaration の両方が Identifiers で始まり、 ":" と Terminal PROCESS または Terminal like INTEGER で始まるため、エラーが発生するのだと思われます。もしそうなら、私のパーサーにもう少し先を見るように指示する方法を知りたいです。あるいは、可能な限りの解決策を。

ご回答ありがとうございました。

どのように解決するのですか？

あなたの診断はまったく正しいです。なぜなら、パーサーは IDENT が開始されます。 processdecl または vardecl を削減したことを知ることができません。 vardecl を見ていて IDENT を見ようとしているのか、別の vardecl または processdecl .

最初のケースでは、単に IDENT の一部として、以下のように vardecl . 2番目のケースでは、まず空の vardecls を、順次リデュースしていきます。 vardecls 完全なリストを作成するまで。

シフト・リデュースの衝突をなくすには、パーサーの意思決定を単純化する必要があります。

最も単純な解決策は、パーサーがどのような順序で宣言を受け入れてもよいようにすることです。そうすると、次のようなものが出来上がります。

program ::= program_type declaration_list ;

declaration_list ::=
            var_declaration declaration_list
          | process_declaration declaration_list
          |
          ;

var_declaration_list ::=
            var_declaration var_declaration_list
          |   
          ;

process_declaration ::=
            IDENT:id COLON PROCESS var_declaration_list BEGIN END SEMI ;

(個人的には、宣言リストを右帰納ではなく左帰納にしたいのですが、リストのアクションでappendとprependのどちらを優先するかは人それぞれです。左再起動の方がパーサーのスタック使用量が少なくて済みます)

もし、すべての変数宣言がプロセス宣言の前に来ることを強く希望する場合は declaration_list .

また、宣言リストの種類を右再帰ではなく左再帰にすることから始めることもできます。そうすると ほとんど これは、最初のプロセス宣言が削減される前に、空のプロセス宣言リストを削減する必要があるためです。

幸いなことに、これを回避するのは簡単です。プロセス宣言のリストが空でなければ問題はないので、プロダクションを並べ替えればよいだけです。

program ::= program_type var_declaration_list process_declaration_list
          | program_type var_declaration_list
          ;

var_declaration_list ::=
            var_declaration var_declaration_list
          |   
          ;

process_declaration_list ::=
            process_declaration_list process_declaration
          | process_declaration
          ;

最後に、醜いけれども可能な代替案として、変数宣言リストを左再起に、プロセス宣言リストを右再起にする方法があります。この場合、最後の変数宣言と最初のプロセス宣言の間に空のプロダクションは存在しない。