3

Bisonの文法全体を通して、私は右再帰を使用しています。最初にスタック全体を構築する必要がないため、左再帰の方が優れていることを読みました。

しかし、それらのいずれかで左再帰に切り替えようとすると、常に多くの競合が発生し、その理由がわかりません。

右の代わりに左の再帰を使用すると競合が発生する一般的な例を誰かに教えてもらえますか（右の再帰が競合を引き起こさない場合）。次に、そのような競合を修正するために左に切り替えるときに何をする必要がありますか。基本的な例は、自分の文法を修正するだけでは不十分だと思います。

編集：
しかし、私の理解は完全ではないので、とにかく特定の例を含める必要があると思います:-)「listseparatorcommand」を「commandseparatorlist」に変更すると競合が解決します。

State 9 conflicts: 3 shift/reduce


Grammar

    0 $accept: input $end

    1 input: error NEWLINE
    2      | input NEWLINE
    3      | input list NEWLINE
    4      | /* empty */

    5 list: command
    6     | command separator
    7     | list separator command

    8 separator: SEMI
    9          | L_OR
   10          | L_AND

   11 command: variable_assignment
   12        | external_w_redir
   13        | external_w_redir AMP
   14        | pipeline
   15        | pipeline AMP

...

state 9

    5 list: command .
    6     | command . separator

    SEMI   shift, and go to state 18
    L_AND  shift, and go to state 19
    L_OR   shift, and go to state 20

    SEMI      [reduce using rule 5 (list)]
    L_AND     [reduce using rule 5 (list)]
    L_OR      [reduce using rule 5 (list)]
    $default  reduce using rule 5 (list)

    separator  go to state 22
4

2 に答える 2

4

編集：

元の回答を撤回する必要があります。私が最初に思ったように、あなたの左再帰文法はあいまいではないようです。最後のセパレーターをオプションにするために使用される追加のルールに混乱したと思います。

以下は、元の右再帰文法の単純化されたバージョンです。

list: COMMAND
      | COMMAND SEPARATOR
      | COMMAND SEPARATOR list
      ;

この文法は、入力 C、CS、CSC、CSCS、CSCSC、CSCSCS などに一致します (私が思っているよりも混乱していなければ、もちろん可能性はあります)。つまり、SEPARATOR で区切られた一連のコマンド、最後にオプションの SEPARATOR を付けます。

そして、これは左再帰文法の単純化されたバージョンであり、Bison でシフト/リデュースの競合を引き起こします。

list: COMMAND
      | COMMAND SEPARATOR
      | list SEPARATOR COMMAND
      ;

正しく展開すると、この文法は入力 C、CS、CSC、CSSC、CSCSC、CSSCSC などと一致します。あいまいではありませんが、左再帰文法と同等ではありません。COMMAND のリストの末尾に SEPARATOR を含めることはできず、COMMAND 間の SEPARATOR を 2 倍にすることができます。

シフト/リデュースの競合の理由は、Bison がシフトするかリデュースするかを決定するときに 1 つのトークンだけ先を見ているためだと思います。

最後のセパレータがオプションであり、文法が左再帰でなければならないことが重要である場合は、次のように書き直すことをお勧めします。

list: separatedlist
      | separatedlist SEPARATOR
      ;

separatedlist: COMMAND
               | separatedlist SEPARATOR COMMAND
               ;

しかし、リストが非常に長いか、非常に限られたハードウェアでパーサーを実行するつもりでない限り、左または右について心配する必要はありません。最近のデスクトップ コンピューターでは、それほど重要ではないと思います。

于 2009-11-08T18:34:00.333 に答える
1

混乱/エラーは、リストの制作に起因しているようです。左の再帰バージョンは次のとおりです。

list: command
    | command separator
    | list separator command

正しい再帰バージョンは次のとおりです。

list: command
    | command separator
    | command separator list

これら 2 つのルール セットは実際にはまったく異なり、異なるものに一致します。最初のものは、1 つまたは複数のcommandと、それらの間にセパレーターがあり、オプションで各コマンドの後に追加のセパレーターがあります。2 番目のコマンドも同様ですが、 LASTコマンドの後に追加のオプションの区切り文字しか許可されていません。

あなたが本当に欲しいのは後者の左再帰バージョンであると仮定すると、あなたが望むのは

list_no_trailer: command
               | list_no_trailer separator command

list: list_no_trailer
    | list_no_trailer separator

あなたのバージョンの競合は、「コマンド」を解析し、lookahed でセパレーターを確認した後、コマンドの後にオプションのセパレーターとしてそれを取り込むか、それとも仮定の下でコマンドを削減するかがわからないという事実から生じます。それはリスト区切りであり、その直後に別のコマンドがあります。そのためには2文字の先読みが必要になるため、文法はLR(2)ですが、LR(1)ではありません

于 2009-11-08T23:53:12.007 に答える