Mercury 入門 (8) DCG (確定節文法)

DCG

DCG(確定節文法)は状態を受け渡す述語を簡単に書くための構文です． Haskell の do記法のようなもので，主な用途に構文解析の記述があります．

まずは，これまでの知識を使って，"12,34"のようにコンマで区切られた 文字列を構文解析するプログラムを示します．

実行結果

46

言語が大規模になると，Strm の受け渡しが次第に面倒になってきます． DCG を使うとこの Strm の受け渡しが自動化できます．

DCG の述語は，

Goal0 --> Goal1, ..., Goaln

のように記述され，自動的に状態を受け渡す関数に変換されます．

DCG で使える代表的な記法は以下の4つです．

DCG_Goal1 , DCG_Goal2

DCG_Goal1を処理してDCG_Goal2を処理する．

DCG_Goal1 ; DCG_Goal2

DCG_Goal1とDCG_Goal2を並列に処理する．

{ Goal }

DCGでないゴールを処理する．

[ 項 ]

リスト上のDCGの状態の先頭要素と項を単一化して， 残りのリストを新たな状態にする．

これらを使うと，例えば前のプログラムの

parse_intpair({N1, N2}, Strm1, Strm4) :-
  parse_int(N1, Strm1, Strm2),
  parse_comma(Strm2, Strm3),
  parse_int(N2, Strm3, Strm4).

は，

parse_intpair({N1, N2}) -->
  parse_int(N1),
  parse_comma,
  parse_int(N2).

のようになります．

プログラム全体を以下に示します．

実行結果

46

DCG と 入出力

DCG を使って入出力の状態も管理できますが， これは，プログラミングスタイル的に非推奨だそうです． しかし，古いプログラムではこの手法が使われているので例を示します．

実行結果

hello, world.