Prolog の Definite Clause Grammar を試す

DCG (Definite Clause Grammar) はProlog に組み込みのパーサ記法のようなもので、以下のような感じで文法を表現すると構文解析ができるようになる。

sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.
determiner --> [the].
noun --> [man].
noun --> [apple].
verb --> [eats].
verb --> [sings].

基本的には上記の通り文脈自由文法なんだけど非終端記号がパラメタを持つことができて、その単一化を利用して例えば自然言語の性や数の一致を文法への制約として付け加えたりもできる。

ところで非終端記号に付加情報がついたものといわれて Indexed Grammar を連想した。たまたま本で数ページ紹介されているのを読んだ程度の知識しか無いのだが、Indexed Grammar というのは基本的には文脈自由文法なのだけど、非終端記号に index と呼ばれるシンボルの列をくっつけることができて、文法規則はこのシンボル列を左辺から右辺の非終端記号に引き継いだり、追加したり削除したりできる。ただし追加と削除はスタック的な操作しか許されない。こういう仕組みによって Indexed Grammar は文脈自由文法と文脈依存文法の中間の生成力を持つ。らしい。

文脈自由文法で表現できないが Indexed Grammar で表現できる言語としては以下のものがある。

{ a^n b^n c^n : n >= 0 } （同じ数の a,b,c のこの順に並べた文を生成する）
{ xx : x ∈ {a,b}* } （a と b からなる文字列を2回繰り返した文を生成）
{ a^n b^n^2 : n >= 1 } （a を n 回、b を n^2 回繰り返した文を生成）

最初の言語を Indexed Grammar 風の DCG で表現すると以下のようになる。

s              --> t([]).
t(Indices)     --> a(Indices), b(Indices), c(Indices).
t(Indices)     --> t([i|Indices]).
a([])          --> [].
b([])          --> [].
c([])          --> [].
a([i|Indices]) --> [a], a(Indices).
b([i|Indices]) --> [b], b(Indices).
c([i|Indices]) --> [c], c(Indices).

つまり t(Indices) --> t([i|Indices]). のプロダクションが i という index を任意の数まで増やす役目をしていて、t(Indices) --> a(Indices), b(Indices), c(Indices). でその数を a,b,c に引き継ぐ。a,b,c の規則はそのインデクスを1つずつ消費していく。これを試してみると、

?- s([], []).

Yes
?- s([a,b,c], []).

Yes
?- s([a,a,b,b,c,c], []).

Yes
?- s(X, []).

X = [] ;

X = [a, b, c] ;

X = [a, a, b, b, c, c] ;

X = [a, a, a, b, b, b, c, c, c]

Yes

という感じでここまでは嬉しいくらいうまくいく。でも言語に属さない文を与えると止まらなくなってしまった。

?- s([a,a,b,c,c], []).
ERROR: Out of global stack
?- s([a,a,c,c], []).
ERROR: Out of global stack

先の2つ目の言語は Indexed Grammar だと以下のように定義できる。

s                  --> t([]).
t(Indices)         --> front(Indices), rear(Indices).
t(Indices)         --> t([a|Indices]).
t(Indices)         --> t([b|Indices]).
front([])          --> [].
front([a|Indices]) --> [a], front(Indices).
front([b|Indices]) --> [b], front(Indices).
rear([])           --> [].
rear([a|Indices])  --> [a], rear(Indices).
rear([b|Indices])  --> [b], rear(Indices).

ここでは t の下2つの規則がインデクスとして任意の a,b の列を作りだす。ひとしきり作り終わったところで front と rear の規則に引き継いでそれぞれ作り出されたとおりの文字列を生成する。これは DCG としてうまくいくだろうか。

?- s(X,[]).

X = [] ;

X = [a, a] ;

X = [a, a, a, a] ;

X = [a, a, a, a, a, a] ;

X = [a, a, a, a, a, a, a, a]

Yes
?- s([],[]).

Yes
?- s([a,a], []).

Yes
?- s([a,a,a,a], []).

Yes
?- s([a,b], []).
ERROR: Out of local stack
   Exception: (27,925) t([a, a, a, a, a, a, a, a|...], [a, b], []) ? abort
% Execution Aborted
?- s([a,a,b,b], []).
ERROR: Out of local stack
   Exception: (27,868) t([a, a, a, a, a, a, a, a|...], [a, a, b, b], []) ? abort
% Execution Aborted

インスタンス化されていない変数を与えた場合は front と rear が同じつまらない文しか生成してくれなくなった。さらに言語に含まれるかどうかの判定では言語に含まれているものでも front と rear が違う文だと止まらなくなってしまった。（2008-06-03追記: 訂正！front と rear が違う文は言語に含まれません。ひどい勘違い。[a,b,a,b] みたいなのをつまらなくない文法的な文の例として出すべきところでした。「言語に含まれているものでも～」という部分は正しくないです。）

3つめの言語は以下のように書ける。

s              --> t([]).
t(Indices)     --> a(Indices), b(Indices).
t(Indices)     --> t([i|Indices]).
a([])          --> [a].
a([i|Indices]) --> [a], a(Indices).
b([])          --> [b].
b([i|Indices]) --> [b], b(Indices), z(Indices), z(Indices).
z([])          --> [b].
z([i|Indices]) --> [b], z(Indices).

実験結果。これは1つ目と同じような感じだ。

?- s(X,[]).

X = [a, b] ;

X = [a, a, b, b, b, b] ;

X = [a, a, a, b, b, b, b, b, b|...] [write]

X = [a, a, a, b, b, b, b, b, b, b, b, b] ;

X = [a, a, a, a, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b]

Yes
?- s([a,b],[]).

Yes
?- s([a,a,b,b,b,b],[]).

Yes
?- s([a,a,b,b,b],[]).
ERROR: Out of global stack

それで以上のような結果をどう整理したらいいのかというと、実はよく理解できていない。多分再帰下降型のパーサが文脈自由文法のある制限された形しか扱えないのと同様に、DCG でも文法が表現できるということと、それがそのまま Prolog のトップダウン/バックトラック付きのパーシングで解析できるかどうかというのは別の話だということだろうか。

2008-05-15追記:なんか Indexed Grammar の例を考え出したせいで複雑になったけど、単純に Prolog 一般と同様に DCG でも左再帰がだめってことの気がしてきた。