Prologプログラミング: 言語処理

非決定性有限オートマトン

Prolog では非決定性有限オートマトンの動作を簡単に シミュレートできます．

たとえば，正規表現 a(a|b)*ab を認識するオートマトンを考えてみましょう． このオートマトンは次のような状態遷移図で表されます．

すなわち状態遷移関数δは次のようになります． 

    δ(q0, a) = {q1}
    δ(q1, a) = {q1, q2}
    δ(q1, b) = {q1}
    δ(q2, b) = {q3}
これを Prolog で次のように書くことにします． 

    delta(q0, a, q1).
    delta(q1, a, q1).
    delta(q1, a, q2).
    delta(q1, b, q1).
    delta(q2, b, q3).
入力文字列をリストで表すことにすると， 与えられたリスト L が受理可能かどうかを調べる述語 ndfa(L) は 次のように書けます． 

    ndfa(L) :- ndfa(q0, L, q3).

    ndfa(Q, [], Q).
    ndfa(Q0, [A|L], Q) :-
        delta(Q0, A, Q1), ndfa(Q1, L, Q).
実行して見ると次のようになります． 

    | ?- ndfa([a,a,b]).
    yes
    | ?- ndfa([a,a,b,a,b]).
    yes
    | ?- ndfa([a,b]).
    no

構文解析

Prolog のプログラム例として， 簡単な英文の文法解析を行うプログラムを紹介します．
Time flies like an arrow.
という文は，文法的には次の 3 つの解釈が可能です．
  1. "Time"を名詞，"flies"を動詞， "like an arrow"を前置詞句とした解釈 「時は矢のように飛ぶ」(光陰矢のごとし)．
  2. "Time"を形容詞，"flies"を名詞，"like"を動詞とした解釈 「時蝿は矢を好む」．
  3. "Time"を動詞(命令文)，"flies"を名詞(目的語)， "like an arrow"を前置詞句とした解釈 「矢のように蝿を調整せよ」．
これらの 3 つの解析結果を出力する文法規則は Prolog で以下のように書けます． 

    s(s(NP,VP), S0, S) :-
	np(NP, S0, S1), vp(VP, S1, S).
    s(s(VP), S0, S) :-
	vp(VP, S0, S).
    np(np(N), S0, S) :-
	n(N, S0, S).
    np(np(A,N), S0, S) :-
	adj(A, S0, S1), n(N, S1, S).
    np(np(D,N), S0, S) :-
	det(D, S0, S1), n(N, S1, S).
    vp(vp(V), S0, S) :-
	v(V, S0, S).
    vp(vp(V,NP), S0, S) :-
	v(V, S0, S1), np(NP, S1, S).
    vp(vp(V,PP), S0, S) :-
	v(V, S0, S1), pp(PP, S1, S).
    vp(vp(V,NP,PP), S0, S) :-
	v(V, S0, S1), np(NP, S1, S2), pp(PP, S2, S).
    pp(pp(P,NP), S0, S) :-
	prep(P, S0, S1), np(NP, S1, S).
s は文， np は名詞句， vp は動詞句， pp は前置詞句， n は名詞， v は動詞， adj は形容詞， det は冠詞， prep は前置詞を表します．

したがって上の規則はそれぞれ次のような文法規則に相当しています．

辞書に相当する部分は次のように書けます． 

    n(n(time), [time|S], S).
    n(n(flies), [flies|S], S).
    n(n(arrow), [arrow|S], S).
    v(v(time), [time|S], S).
    v(v(flies), [flies|S], S).
    v(v(like), [like|S], S).
    adj(adj(time), [time|S], S).
    prep(prep(like), [like|S], S).
    det(det(an), [an|S], S).
実行結果は次のようになります(見やすいように整形してあります)． 

    | ?- s(X, [time,flies,like,an,arrow], []).
    X = s(np(n(time)),
          vp(v(flies),
             pp(prep(like),
                np(det(an),n(arrow))))) ? ;
    X = s(np(adj(time),n(flies)),
          vp(v(like),
             np(det(an),n(arrow)))) ? ;
    X = s(vp(v(time),
             np(n(flies)),
             pp(prep(like),
                np(det(an),n(arrow))))) ? ;
木表現 (構文解析木と呼ばれる) で書くと次のようになります． 
                 s
               /   \ 
             np      vp
             |     /    \
             n    v      pp
             |    |    /   \ 
             |    |  prep   np
             |    |   |    /  \
             |    |   |  det   n
             |    |   |   |    |
          time flies like an arrow


                   s
                 /   \
               np      vp
             /  \      / \
           adj   n    v   np
            |    |    |   |  \
            |    |    |  det  n
            |    |    |   |   |
          time flies like an arrow


                 s
                 |
                 vp
              /  |   \
            v    np    pp
            |    |     |  \ 
            |    n   prep  np
            |    |     |   |  \
            |    |     |  det  n
            |    |     |   |   |
          time flies like an arrow
Prolog の DCG 機能を使うと， 以下のようなプログラムとして簡潔に記述できます． 

    s(s(NP,VP)) --> np(NP), vp(VP).
    s(s(VP)) --> vp(VP).
    np(np(N)) --> n(N).
    np(np(A,N)) --> adj(A), n(N).
    np(np(D,N)) --> det(D), n(N).
    vp(vp(V)) --> v(V).
    vp(vp(V,NP)) --> v(V), np(NP).
    vp(vp(V,PP)) --> v(V), pp(PP).
    vp(vp(V,NP,PP)) --> v(V), np(NP), pp(PP).
    pp(pp(P,NP)) --> prep(P), np(NP).
    
    n(n(time)) --> [time].
    n(n(flies)) --> [flies].
    n(n(arrow)) --> [arrow].
    v(v(time)) --> [time].
    v(v(flies)) --> [flies].
    v(v(like)) --> [like].
    adj(adj(time)) --> [time].
    prep(prep(like)) --> [like].
    det(det(an)) --> [an].
最初に戻る 前へ 次へ