Menhir を使用してパーサーを作成していますが、常につまずく動作があり、理解できません。それを示すために、次の最小限の例を作成しました。これは、Go 言語 ( http://golang.org/ref/spec#Method_declarations )のメソッド宣言でのレシーバー引数の宣言を示しています。
%{
%}
%token <string> T_identifier
%token T_star
%start <unit> demo
%%
(* This rule has a shift/reduce conflict
demo:
| option(T_identifier) option(T_star) T_identifier { () }
*)
(* This rule is okay. *)
demo:
| T_identifier T_star T_identifier { () }
| T_identifier T_identifier { () }
| T_star T_identifier { () }
| T_identifier { () }
私が見る限り、両方のルールは意味的に同等です。オプションの識別子 (レシーバーの名前)、オプションのスター (ポインターかどうか)、および必須の型名 (レシーバーの型) を探しています。ただし、最初のルール (コメント アウトされたルール) ではシフト/リデュースの競合が発生しますが、2 番目のルールは正常に機能します。
これが発生するたびに複数のルールに置き換えることでパーサーを進歩させることができましたがoption、なぜそれが起こっているのか理解できないことに悩まされています.
(menhir を知らない場合、これは LR(1) パーサー ジェネレーターなので、他の同様のツールがどのように機能するかについての知識がおそらく適用されます。)