オプションの非終端子をサポートするyaccコードを構成する方法

Question

yaccでオプションのデータをモデル化する最良の方法は何ですか？

StmtBlock   : '{' VariableDeclList StmtList '}' { $$ = new StmtBlock($2, $3); } 
        ; 

どちらも、VariableDeclListとStmtListはオプション（イプシロン）されているので、次のように私はそれらをモデル化：私は、次のステートメントを持っている

VariableDeclList : VariableDeclList VariableDecl { ($$=$1)->Append($2); } 
        | { $$ = new List<VarDecl*>; } 

と

StmtList   : StmtList Stmt { ($$=$1)->Append($2); } 
        | { $$ = new List<Stmt*>; } 
        ; 

唯一の問題はときです私はこれがshift/reduceの衝突を引き起こすと思います。私のコードをコンパイルしようとすると、y.ouputファイルは次のようになります。

State 74 conflicts: 1 shift/reduce 
... 
state 74 

    38 StmtBlock: '{' VariableDeclList . StmtList '}' 
    39 VariableDeclList: VariableDeclList . VariableDecl 

    T_Bool  shift, and go to state 2 
    T_Int   shift, and go to state 3 
    T_Double  shift, and go to state 4 
    T_String  shift, and go to state 5 
    T_Identifier shift, and go to state 8 

    T_Identifier [reduce using rule 18 (Epsilon)] 
    $default  reduce using rule 18 (Epsilon) 

    VariableDecl go to state 80 
    Variable  go to state 13 
    Type   go to state 34 
    Epsilon  go to state 81 
    StmtList  go to state 82 
... 

これをモデル化するより適切な方法はありますか？

Answer 1

あなたが注意したように、これは/シフトを引き起こすのstmtとVariableDeclが彼らの最初のトークンで区別することができない場合は、競合を削減する - あなたの例T_Identifierのいずれかで始まるかもしれません。

• がVariableDeclOrStmtListに二つのリストを組み合わせのstmtまたはいずれかの方法で混在VariableDeclのいずれかを含めることができます。あなたが試すことができます事柄がいくつかあります。これは、あなたが持っているものよりも一般的であるので、あなたは最初のstmt

• 使用後の差を決定するために、より先読みなしVariableDeclsが存在しないことを保証するために、ポストチェック必要があります - のいずれかがバイソン年代を使用します何かが、それは明確に区別するためにこれらの構築物の初めに

• 使用異なるトークンを決定するのに十分なのを見たまでのstmtまたはVariableDeclであるかどうかを決める延期することができますGLRモード、またはbtyaccのようなもの。これらはあなたの言語の本物のトークンか、またはレクサーがいくつかの追加の文脈に基づいて挿入する合成トークン（基本的にはレクサーでもっと先読みをすることを意味します）のいずれかです。

最初の提案のために編集

、あなたのようなルールがあるでしょう：NodeはVarDeclとStmtの共通の基底クラスである

VarDeclOrStmtList : VarDeclOrStmtList VariableDecl { ($$=$1)->Append($2); } 
        | VarDeclOrStmtList Stmt   { ($$=$1)->Append($2); } 
        | { $$ = new List<Node *>; } 
        ; 

。次に、StmtBlockアクションで、List<VarDecl *>とList<Stmt *>に分割し、正しく整形されていないとエラーメッセージを表示する関数List<Node *>を呼び出します。