%
% problem11.pl
%
% 無向グラフ上の始点から終点までのパス（経路）を探す
graph(Goal,Goal,Log,H,T):-
H=[[Goal|Log]|T].
graph(Goal,Start,Log,H,T):-
neighb(Start,Neighb),
check_next(Goal,Start,Neighb,Log,H,T).
check_next(_,Node,[],_,H,T):-
H=T.
check_next(Goal,Node,[N|Ns],Log,H,T):-
passed(N,Log,Result),
go_next(Result,Goal,N,[Node|Log],H,T1),
check_next(Goal,Node,Ns,Log,T1,T).
go_next(true,_,_,_,H,T):-
H=T.
go_next(false,Goal,Node,Log,H,T):-
graph(Goal,Node,Log,H,T).
passed(_,[],false).
passed(X,[X|_],true).
passed(X,[A|Y],R):-
passed(X,Y,R).
neighb(a,[b,c]).
neighb(b,[a,c,d]).
neighb(c,[a,b,e]).
neighb(d,[b]).
neighb(e,[c]).
neighb節がグラフのデータです。グラフのノード（節点）とそのノードに隣接するノードのリストを引数としています。ですから、このグラフは下図に示すようなものとなります。
図13.1 無向グラフ
?- graph(a,d,[],Ans,[]).
Ans=[[a,b,d],[a,c,b,d]]
Ｐｒｏｌｏｇの答えは[a,b,d]つまりノードaからbを通ってdへ至るパスと、[a,c,b,d]つまりノードaからcへ行ってからbを通ってdへ至るパスと２通りのパスがあることを示しています。
the girl smiles
という文章があります。「彼女、こっち見て笑ってるぜ」って状況です。さて、この文章を理解するためには、[the]が定冠詞で名詞[girl]にかかっている、[girl]は今言った通りに名詞、そしてこの[the]と[girl]が名詞部になって、動詞部は動詞[smiles]である、ということが把握できなければなりません。厳密には動詞の変化とかいろいろあるのですが、ここでは割愛しましょう。そして、[girl]が名詞だということが判るためには名詞の辞書を持っていなければなりません。ということは、この名詞の辞書には[girl]の他にも多くの単語が記載されていなければなりませんね。でも、辞書があまりに膨大になると処理が遅くなりますし、第一みんなが理解しにくくなるので、ここでは簡単にするために辞書は大変にコンパクトなものにしましょう。
[構文規則]
sentence->gtnoun_phrase+verb.
sentence->gtnoun_phrase+verb_phrase.
noun_phrase->gtdeterminer+noun_expression.
noun_expression->gtnoun.
noun_expression->gtadjective+noun_expression.
verb_phrase->gtverb_expression+noun_phrase.
verb_expression->gtverb.
verb_expression->gtadverb+verb.
verb->gtlikes|kicks|smiles|admires|eats.
determiner->gtthe|a|an.
noun->gtboy|girl|table|tree|apple|ball.
adverb->gtquickly|easily.
adjective->gtbig|small|lazy|eager|bad|good.
後に構文解析を行うプログラムを示しますが、そのプログラムの中にgrammer節とdictionary節としてこの構文規則を記述してあります。
図13.2 構文解析木
P=sentence(noun_phrase(determiner(the),noun_expression(noun(girl))),verb(smiles)).さて、最後にこの構文解析を行うＰｒｏｌｏｇのプログラムを示します。長いですから頑張ってね。
%
% problem12.pl
%
% 簡単な構文解析を行う
parse(S,P):-
parse_sub(S,sentence,P).
parse_sub([],_,_):-false.
parse_sub([Word],Form,Parse):-
dictionary(Form,Dict),
member(Word,Dict),
Parse=..[Form,Word].
parse_sub(Words,Form,Parse):-
grammar(Form,Exp),
expanisions(Words,Exp,ParseList),
Parse=..[Form|ParseList].
expanisions(Word,[Exp1,Exp2],Parse):-
one_expanision(Words,Exp1,Parse)
;
one_expanision(Words,Exp2,Parse).
expanisions(Words,[Exp],Parse):-
one_expanision(Words,Exp,Parse).
one_expanision(Words,[Form1,Form2],[Parse1,Parse2]):-
splittings(Words,Splits),
splits_parse(Splits,Form1,Form2,Parse1,Parse2).
one_expanision(Words,[Form],[Parse]):-
parse_sub(Words,Form,Parse).
splits_parse([pair(Front,Back)|Splits],Form1,Form2,Parse1,Parse2):-
parse_sub(Front,Form1,Parse1),
parse_sub(Back,Form2,Parse2).
splits_parse([Split|Splits],Form1,Form2,Parse1,Parse2):-
splits_parse(Splits,Form1,Form2,Prase1,Parse2).
splittings([],[pair([],[])]).
splittings([H|T],[pair([],[H|T])|Insertions]):-
splittings(T,Tsplits),
front_insert(H,Tsplits,Insertions).
front_insert(T,[],[]).
front_insert(T,[pair(F,B)|Pairs],[pair([T|F],B)|InsertedPairs]):-
front_insert(T,Pairs,InsertedPairs).
grammar(sentence,[[noun_phrase,verb],[noun_phrase,verb_phrase]]).
grammar(noun_phrase,[[determiner,noun_expression]]).
grammar(noun_expression,[[noun],[adjective,noun_expression]]).
grammar(verb_phrase,[[verb_expression,noun_phrase]]).
grammar(verb_expression,[[verb],[adverb,verb]]).
dictionary(verb,[likes,kicks,smiles,admires,eats]).
dictionary(determiner,[the,a,an]).
dictionary(noun,[boy,girl,table,tree,apple,ball]).
dictionary(adverb,[quickly,easily]).
dictionary(adjective,[big,small,lazy,eager,bad,good]).
このプログラムの実行するには、以下のように入力します。
?- parse([the,girl,smiles],P).
?- parse([the,boy,eats,the,apple],P).
目次に戻る