DCG入門

はじめに

O-PrologにDCGを追加実装しました。このテストでわかったこと、調べたことなどを投稿します。

動機

DCGとはdefinite clause grammarの略であり日本語では限定節文法と呼ばれています。何のためにあるのかというとおそらく自然言語処理が当初の動機であったのだろうと思います。
以下はAZ-Prolog@ウィキからの引用です。
ーーー
prologの設計者のAlain Colmerauer氏はこれを作りたくてprologを作ったと
誰かに聞いた覚えがあります。
ーーー
Colmerauerは自然言語を研究していたということです。

例

以下は中島秀之先生の「Prolog」（産業図書）にある例です。

A dog bites a postman.

この英文は構造をもっています。その構造は一定の文法規則に従っています。

文 -> 名詞句、動詞句
名詞句　->冠詞、名詞
冠詞　->a
名詞　->dog
名詞　->postman
動詞句　->動詞、名詞句
動詞　->bites

これを直接にPrologで記述することも可能ではあるのですが、もっと楽な方法があります。それがDCGです。上記の規則をほぼそのままの形で記述することが可能です。

s --> np,vp.
np --> det,n.
det -->[a].
n -->[dog].
n -->[postman].
vp --> v,np.
v -->[bites].

なお、文法カテゴリーは省略形によっています。
文　sentence　s
名詞　noun　n
名詞句　noun　phrase　np
動詞　verb　v
限定詞　determiner　det
動詞句　verb　phrase

これをProlog処理系で動かしてみましょう。たいていのProlog処理系でDCGを使うことができます。O-Prologではライブラリからdcgを呼び出しておいて、recunsultで読み込みます。

O-Prolog Ver 1.27(yoko)
| ?- use_module(library(dcg)).
yes
| ?- ['nakashima.pl'].
yes

O-PrologではライブラリにDCGが収録されています。これを読み込んでから規則をテキストに書いておいたコードを読み込みます。phraseという述語で文が正しいかどうかを確認することができます。

| ?- phrase(s,[a,dog,bites,a,postman]).
yes
| 

このようにリストで与えられた文が与えられた文構造になっていることが確かめられました。間違った文を与えたらどうでしょう？

| ?- phrase(s,[bites,a,dog,a,postman]).
no
|

偽が返っています。文法規則に反しています。

面白いことに文法規則にかなった文を生成させることもできます。

| ?- phrase(s,X).
X = v_1;
X = [a,dog,bites,a,dog];
X = [a,dog,bites,a,postman];
X = [a,postman,bites,a,dog];
X = [a,postman,bites,a,postman];
no
| 

セミコロンを入力しバックトラックさせるといくつかの文がでてきました。意味は変ですが文法規則には則っています。

いろいろ言葉や文法規則を追加して遊ぶことができます。次の文を解析させるにはどうしたらいいでしょうか？　読者の皆さんの課題としてください。
　
Ａ wolf with red eyes ran through the bush.

（中島先生の本にある例ですが、たしか映画「2001年宇宙の旅」でHAL9000のセリフだったと思います。)

ISO-Prolog

DCGをO-Prologで動作させたくてcomp lang prolog　で質問をしていましたら、パウロさんという方からご連絡をいただきました。驚いたことにパウロさんは元ISO-Prologのメンバーでした。ISOでのDCGに関する文書をお送りいただきました。ISO/IEC DTR 13211-3:2006

最新版は公開されており、下記から入手可能です。
https://www.complang.tuwien.ac.at/ulrich/iso-prolog/dcgs/dcgsdin140408.pdf

この文書に参照実装としてISO-Prologで記述したDCGが収録されています。O-Prologはこれを使っています。

The Power of Prologの例題より

例１

as --> [].
as --> [a], as.

as というのは空リスト[]かあるいはaをつなげていったものという意味になります。

| ?- phrase(as,[a,a,a]).
yes
| ?- phrase(as,Ls).
Ls = [];
Ls = [a];
Ls = [a,a];
Ls = [a,a,a];
Ls = [a,a,a,a]
yes
| 

例２

lis([])     --> [].
lis([L|Ls]) --> [L], lis(Ls).

リストの規則を述べています。空リストはリストである。[L|Ls]というリストはLと残りのLsとをつなげたものであるという意味合いです。

| ?- phrase((lis([a,b]),lis([c,d])), Ls).
Ls = [a,b,c,d]

yes

実装方法

O-PrologではISO-Prologの参照実装をそのまま使っています。
下記の述語を追加しました。

phrase(GRBody,SO) :-
    phrase(GRBody,SO,[]).


phrase(GRBody,SO,S) :-
    dcg_body(GRBody,SO,S,Goal),
    call(Goal).

dcg_expand(X) :-
    dcg_rule(X,Y),assertz(Y).

phrase/2 がユーザーとのインターフェイスになります。この第一引数に構文規則、第二引数に解析させたいリストを与えます。

phrase/3がその実体です。phrase/2は単に[]を追加してphrase/3に渡しているだけです。

dcg_expand/1　は　-->　オペレータで与えられた構文規則をPrologのホーン節に変換し、これをassertしています。読み込んだ後でlistingを実行するとどのようなコードに変換されたのかを確認することができます。例えば上記のasは次のようになっています。

| ?- listing(as).
as(_v646,_v645) :-
    _v646=_v645.
as(_v715,_v734) :-
    _v715=[a|_v735],
    as(_v735,_v734).

a-->b は読み込まれた後、処理系内部で X = a-->b にして、dcg_expand(X) を呼び出しています。

参考文献

「Prolog」　中島秀之　著　産業図書

[The Power of Prolog]
https://www.metalevel.at/prolog/dcg