4

メンヒル初心者です。OCaml によく似た自分の言語で OCaml をタプル パターンのように解析する方法を考えています。

たとえば、式let a,b,c = ...では、 のa, b, cように解析する必要がありますTuple (Var "a", Var "b", Var "c")。

ただし、次のパーサーの定義では、上記の例は として解析されTuple (Tuple (Var "a", Var "b"), Var "c")ます。次の定義を修正して、ocaml のようなパターンを解析する方法を考えています。

OCaml の parser.mly を確認しましたが、それを実装する方法がわかりません。私の定義は OCaml の定義に似ていると思います... 彼らはどんな魔法を使っているのでしょうか?

%token LPAREN
%token RPAREN
%token EOF
%token COMMA
%left COMMA
%token <string> LIDENT
%token UNDERBAR
%nonassoc below_COMMA

%start <Token.token> toplevel
%%

toplevel:
| p = pattern EOF { p }

pattern:
| p = simple_pattern        { p }
| psec = pattern_tuple %prec below_COMMA
  { Ppat_tuple (List.rev psec) }

simple_pattern:
| UNDERBAR                  { Ppat_any }
| LPAREN RPAREN             { Ppat_unit }
| v = lident                { Ppat_var v }
| LPAREN p = pattern RPAREN { p }

pattern_tuple:
| seq = pattern_tuple; COMMA; p = pattern { p :: seq }
| p1 = pattern; COMMA; p2 = pattern { [p2; p1] }

lident:
| l = LIDENT { Pident l }

結果は次のとおりです。

[~/ocaml/error] menhir --interpret --interpret-show-cst ./parser.mly
File "./parser.mly", line 27, characters 2-42:
Warning: production pattern_tuple -> pattern_tuple COMMA pattern is never reduced.
Warning: in total, 1 productions are never reduced.
LIDENT COMMA LIDENT COMMA LIDENT
ACCEPT
[toplevel:
  [pattern:
    [pattern_tuple:
      [pattern:
        [pattern_tuple:
          [pattern: [simple_pattern: [lident: LIDENT]]]
          COMMA
          [pattern: [simple_pattern: [lident: LIDENT]]]
        ]
      ]
      COMMA
      [pattern: [simple_pattern: [lident: LIDENT]]]
    ]
  ]
  EOF
]
4

2 に答える 2

5

これには典型的な shift-reduce 競合が含まれており、優先順位を指定することでその解決を間違えました。Yacc による構文解析に関する本を開き、shift-reduce の競合とその解決方法について確認してください。

あなたのルールを使って見てみましょう。次の入力があり、パーサーが 2 番目を先読みしているとします,。

( p1 , p2 , ...
          ↑
         Yacc is looking at this second COMMA token

それらには2つの可能性があります：

  • 削減:p1 , p2として取得しpatternます。の 2 番目のルールを使用します。pattern
  • Shift: トークンCOMMAを消費し、先読みカーソルを右にシフトして、コンマ区切りのリストを長くしようとします。

競合がルール%prec below_COMMAから簡単に削除されていることがわかります。pattern

$ menhir z.mly   # the %prec thing is removed
...
File "z.mly", line 4, characters 0-9:
Warning: the precedence level assigned to below_COMMA is never useful.
Warning: one state has shift/reduce conflicts.
Warning: one shift/reduce conflict was arbitrarily resolved.

多くの Yacc ドキュメントは、この場合、Yacc はシフトを好むと述べており、このデフォルトは通常、あなたのケースを含め、人間の意図と一致します。したがって、解決策の 1 つは単に%prec below_COMMA物を落として警告を忘れることです。

Shift Reduce 競合の警告を表示したくない場合 (これが精神です!)、OCaml の場合と同様に、優先順位を使用して、この場合にどのルールを選択するかを明示的に指定できますparser.mly。(ちなみに、OCamlparser.mlyは shift reduce resolutions の宝石箱です。慣れていない場合は、そのうちの 1 つまたは 2 つを確認してください。)

yacc は、shift reduce conflict で優先順位の高いルールを選択します。シフトの場合、その優先順位は先読みカーソルのトークンの優先順位ですCOMMA。この場合はそうです。%prec TOKENreduce の優先順位は、対応するルールのサフィックスによって宣言できます。これを指定しないと、ルールの優先順位が定義されていないと思います。これが、を削除すると shift reduce conflict が警告される理由です%prec below_COMMA。

では、問題は次のとおりです。どちらが優先順位が高いか、COMMAまたはbelow_COMMA? これは、ファイルのプリアンブルで宣言する必要がありmlyます。（そして、これが私が質問者にその部分を見せるように頼んだ理由です。）

...
%left COMMA
...
%nonassoc below_COMMA

すべての Yacc 本で説明されているはずなので、何%leftを%nonassoc意味するかはスキップします。ここでbelow_COMMA疑似トークンは以下 COMMAです。よりも優先順位がbelow_COMMA高いことを意味しますCOMMA。したがって、上記の例では Reduce を選択( (p1, p2), ...し、意図に反します。

正しい優先順位宣言は逆です。Shift を発生させるには、より上にbelow_COMMA来て、優先順位を低くする必要があります。COMMA

...
%nonassoc below_COMMA
%left COMMA
...

OCaml の を参照してくださいparser.mly。まさにこの通りです。「下のものを上に」置くのは完全にクレイジーに聞こえますが、それはメンヒルのせいではありません. それは Yacc の不幸な伝統です。それを責める。OCamlparser.mlyには既にコメントがあります。

The precedences must be listed from low to high.
于 2015-10-29T03:02:40.533 に答える