2

バイソンで文法を説明しようとしていますが、それができるかどうかわかりません。私の意図する文法はこれです：

%token A B C D SEP

%%

items          : /* empty */
               | items_nonempty
               ;

items_nonempty : item
               | items_nonempty SEP item
               ;

item           :       B
               |       B       SEP D
               |       B SEP C
               |       B SEP C SEP D
               | A SEP B
               | A SEP B       SEP D
               | A SEP B SEP C
               | A SEP B SEP C SEP D
               ;

" "は、トークンで区切られたitems（空の可能性がある）要素のシーケンスです。itemSEP

各アイテムは、最大4つのトークン（A B C D）で構成され、この順序で。で区切られSEPます。アイテム内のA、、、CおよびDトークンはオプションです。

各アイテム内、およびアイテム自体の間で同じセパレータトークンSEPが再利用されていることに注意してください。

意図した文法が明確であることを願っています。明確だと思いますが、バイソンで解析できるように十分に制限されているかどうかはよくわかりません。残念ながら、パーサーの知識はかなり錆びています。

与えられた文法を使用して、bisonは4つのshift/reduceの競合を報告します。「出力」を見ると、それらがどこで発生し、その理由がわかります。しかし、S / Rの競合を取り除くために、意図した文法をどのように（そしてもし）書くことができるのか、私は途方に暮れています。

私は%expect宣言を使いたくありません。同様に、スキャナーにセパレータートークンを渡してもらうのではなく、セパレータートークンを消費させたくありません。

この文法をサニタイズする方法についてのヒントをいただければ幸いです。

4

4 に答える 4

1

基本的な問題は、記述された文法では、いつ an の終わりを見つけたのかを判断するために先読みの 2 つのトークンが必要であり、したがってそれを減らすことができるか、または先読みの次の文字として認識されるitem現在のアイテムの後に別の部分があるかどうかです。SEP

あなたが試すことができるいくつかのアプローチがあります

  • btyacc または bison の GLR サポートを使用して、先読みを効果的に取得します。

  • 単一項目の任意のリストを受け入れるように文法を記述し、ポストパスを使用してそれらを少なくとも 1 つの項目を持つ 1 ～ 4 項目のセットに再グループ化し、B不正な形式のセットを拒否します (これは Gunther の提案です)。

  • スキャナーを使用してより多くの先読みを行います-単純なSEPトークンを返す代わりに、次のトークンが何であるSEP_BEFORE_A_OR_Bかに応じて返します。SEP_NOT_BEFORE_A_OR_BSEP

  • スキャナでトークンを結合 --SEP_CとSEP_Dを単一のトークンとして返します (セパレータの後にCorが続きますD)

于 2012-04-06T00:24:11.120 に答える
0

SEP次のトークンを1つのルールに含めることができます。非常に簡潔に書かれているので、あなたのグラマーは次のように表現できます。

%token A B C D SEP
%%
items : /* empty */ | item | itemsSEP item ;
item : a B | a b C | a b c D ;
itemsSEP : itemSEP | itemsSEP itemSEP ;
itemSEP : a b c d ;
a : /* empty */ | A SEP ;
b : B SEP ;
c : /* empty */ | C SEP ;
d : /* empty */ | D SEP ;

だから今私はitemSEPセパレーターが続くアイテムのために持っていますが、セパレーターがitem続かない最後のもののために。これらは小文字の1文字の非終端記号で構成されており、それぞれに次の区切り文字も含まれており、オプションの引数もあります。の最後の引数のみitemが常にrawターミナルです。これは、それに続くセパレーターがないためです。

このように表現された文法を使用すると、文法がLALR（1）であるため、shift-reduceの競合が発生することはありません。そのルールの要点が1つを取り除くことである場合でも、すべてのステップで、適用する削減を正確に把握しているSEPため、1つのトークンをさらに先に見ることができます。

于 2012-07-20T13:23:39.033 に答える
0

これには、シフト/リデュースの競合が 1 つあります。

%token A B C D SEP

%%

items
    : /* empty */
    | items_nonempty
    ;

items_nonempty
    : item
    | items_nonempty SEP item
    ;

item
    : opt_a B opt_c_d_list
    ;

opt_a
    :   /* Nothing */
    |   A SEP
    ;

opt_c_d_list
    :   /* Nothing */
    |   opt_c_d_list c_or_d
    ;

c_or_d
    :   SEP C
    |   SEP D
    ;

ルールだけで、S/R カウントが 4 から 2 に変更されます。opt_a残りの問題は、同じ SEP が B の後に C または D を分離することであり、Yacc は先を見通すことができません。「B SEP D SEP C」を非合法化するには、セマンティック チェックが必要です。上記のルールはそれを許可します。

SEP C を読み取ると C を返し、SEP D を読み取ると D を返すようにトークナイザーを変更することを検討できますか? で字句フィードバックと開始条件を使用flexして、B を読み取るときにスイッチを切り替えて、SEP C が C として返され、SEP D が D として返されるようにすることもできます。これが可能であれば、次の明確な文法は、S/R 競合なしで機能します。

%token A B C D SEP

%%

items
    : /* empty */
    | items_nonempty
    ;

items_nonempty
    : item
    | items_nonempty SEP item
    ;

item
    : opt_a B opt_c opt_d
    ;

opt_a
    :   /* Nothing */
    |   A SEP
    ;

opt_c
    :   /* Nothing */
    |   C
    ;

opt_d
    :   /* Nothing */
    |   D
    ;
于 2012-04-05T21:33:25.087 に答える