

OCamlYaccやMenhirを使ったりするのですが、コンフリクトが発生した場合の解消はトライアンドエラーでなんとなく消しています。

何かツールの使い方やコツ等ご存知の方いましたら教えてください。


CC BY-SA 3.0
2015-04-01T07:10:53.083
8643
2015-04-01T11:04:18.783
2015-04-01T09:04:58.867
898
7532
question
ocaml
OCamlYaccやMenhirでコンフリクトを消す方法


YACC の shift/reduce, reduce/reduce conflict
の解消はパーサーの教科書もしくはネット情報に沢山書かれているます。まず、YACC の基本動作原理とともにそれなりに理解してください。たとえば
<http://guppy.eng.kagawa-u.ac.jp/2006/ProgLang/bison-1.2.8/bison-ja_8.html>
など。

どの教科書にもありますが、だいたい、

  * ルールが大雑把過ぎるのが原因であることが多いので、ジェネレータが conflict で迷わないようになるまでルールを書き下す。
  * トークンの優先順位と結合方向を指定することで適用可能なルールの数を減らす
  * reduce/reduce は解消したほうがよい
  * shift/reduce の場合は shift 優先なので、それで満足ならほっておく (ただしあなたの YACC 経験値は上がりません)

ことで解消します。どこを直すべきかは、各パーサジェネレータの conflict レポートをよく読む。これしかないと私は思います。

私は一般的なパーサの知識はあまりないので、ここからは OCaml 特定の情報のみを紹介します。

### Menhir を使う

OCaml では、 OCamlYacc は古いのでもう使わない Menhir を使う。  
そして、 `menhir --explain` を使ってどこに conflict があるかちゃんと理解する、くらいでしょうか。

### Menhir のレポートの読み方

次の例を使って `<basename>.conflicts` の読み方を説明します。 Bison などのドキュメントで出て来る reduce/reduce
の例に少し足したものです:

[code]

    %token WORD
    %token START
    
    %start <int> statement
    
    %%
    
    statement:
      | START sequence { $2 }
      ;
    
    sequence:
      | /* empty */ { 0 }
      | maybeword { $1 }
      | sequence WORD { $1 + $2 }
      ;
    
    maybeword:
      | /* empty */ { 0 }
      | WORD { 1 }
      ;
    
    %%
    
[/code]

上のコードを `menhir --explain x.mly` とすると次のような `x.conflicts` ファイルが出来ます。`.conflicts`
ファイルは `** Conflict (...) in state XXX.` というラインから始まる conflict
の説明の集合からなっています。レポートを読んでいて、 `** Conflict (..)` が出てきた時は別の conflict
の説明に移っていることに注意すると読み易い:

[code]

    ** Conflict (shift/reduce/reduce) in state 1.
    ** Tokens involved: WORD #
    ** The following explanations concentrate on token WORD.
    ** This state is reached from statement after reading:
    
    START 
    
[/code]

WORD に対する処理回りで conflict が起っています。これは `statement` からはじめて `START`
を読み込んだ後、発生します。shift/reduce と reduce/reduce が同時に起っているようですね。

[code]

    ** The derivations that appear below have the following common factor:
    ** (The question mark symbol (?) represents the spot where the derivations begin to differ.)
    
    statement 
    START sequence 
          (?)
    
[/code]

Conflict を起こす複数の解釈は `statement` を `START sequence` だとする所までは共通ですが、そこから先、
`sequence` をどうするか、の所で発生しています。以下はそれぞれの解釈がどうなっているかの説明です

[code]

    ** In state 1, looking ahead at WORD, reducing production
    ** maybeword -> 
    ** is permitted because of the following sub-derivation:
    
    sequence WORD // lookahead token appears
    maybeword // lookahead token is inherited
    . 
    
[/code]

先読みトークン `WORD` がある時、この `WORD` を消費せず、 reduce を行って `sequence` を得ることができます:
下から読むと、 `(空) -> maybeword -> sequence` という構成法。(さらに先読みトークンの `WORD` を消費すると
`sequence WORD -> sequence` になりますね。) `.` はパーサが見ているところはここ、というマークです。

[code]

    ** In state 1, looking ahead at WORD, shifting is permitted
    ** because of the following sub-derivation:
    
    maybeword 
    . WORD 
    
[/code]

先読みトークン `WORD` がある時に、この `WORD` を shift で消費することで、下から `WORD -> maybeword ->
sequence` という構成が可能。 `. WORD` は今パーサが居るところが `.` で `WORD` は先読みトークンです。

[code]

    ** In state 1, looking ahead at WORD, reducing production
    ** sequence -> 
    ** is permitted because of the following sub-derivation:
    
    sequence WORD // lookahead token appears
    . 
    
[/code]

先読みトークン `WORD` がある時に、この `WORD` を消費せずに reduce して `sequence` が構成できる: 下から `(空) ->
sequence`。（さらに先読みトークンの `WORD` と併せると `sequence WORD -> sequence` を構成できます。）

さて、conflict の解消はとにかく受理可能セットを(それが正しいと仮定して)そのまま保ったまま、  
このように複数のルールの選択可能性をルールを変更したり優先順位を加えたりして狭めていく、  
ということなのですが、とにかくこうしろ、という機械的な方法はないのではないでしょうか。  
(あればそもそもパーサジェネレータが勝手に解消してくれるはずです。)  
もうこれは conflict レポートをよく読んで原因理由を理解するのが一番かと思います。  
何かコツがあれば私も知りたいところです。


CC BY-SA 3.0
2015-04-01T10:43:10.503
8652
2015-04-01T11:04:18.783
2015-04-01T11:04:18.783
898
898
8643
answer