3

次の (簡略化された) Bison 文法は、reduce reduce conflict を生成します。

expr
    :    '(' expr ')'
    |    ID
    |    fn
    ;

arg_list
    :    ID
    |    arg_list ID
    ;

fn
    :    '(' ')' fnbody
    |    '(' arg_list ')' fnbody
    ;

fnbody
    :    '{' '}'
    ;

問題はわかります。先読みのトークンが 1 つしかないため、 が であるか(an_idである'(' expr ')'かを判別することは不可能fnです。しかし、どうすれば解決できますか？

4

1 に答える 1

4

さて、最も簡単な答えは、パーサーでより多くの先読みを使用することです-btyaccのようなものを使用するか、bisonの%glr-parserオプションを使用します。

2番目の選択肢は、レクサーに先読みを追加することです。この場合、')'トークンを返す前に、次のトークンがa'{'であるかどうかを確認し、これが終了しようとしているarg_listであることを示す特別なタグを返します。括弧で囲まれた式、または2つを単一のトークンとして返し、必要に応じて文法を変更します。

3番目の選択肢は、文法を因数分解することです。これは必ずしも簡単なことではなく、文法のサイズを大きくする可能性があります。基本的な考え方は、競合するルールを特定し、それらを1つのルールに結合して、パーサーが認識できるようにし、十分に確認できるまで最終的な構成が何であるかについての選択を延期することです。

この例では、競合するケースの新しいルールを追加します。

expr_or_fnhead:  '(' ID ')'  ;

これは、式またはの開始のいずれかである可能性がありfn、次にこれを使用するように他のルールを変更します。fnルールは次のようになります。

fn :  '(' ')' fnbody               /* 0 arg function */
   |  expr_or_fnhead fnbody        /* 1 arg function */
   |  '(' ID arg_list ')' fnbody   /* 2+ arg function */
   ;

ルールはexprもっと複雑です：

expr       : ID
           | non_ID_expr
           ;
non_ID_expr: '(' non_ID_expr ')'
           | expr_or_fnhead
           | fn
           ;
于 2012-05-27T06:23:44.170 に答える