【LPN】7 Definite Clause Grammars

* 7 Definite Clause Grammars
** 1 Context Free Grammars
 - Prologは多様な目的に利用できるが、発明時の目的と
   してcomputational linguistics (計算言語学？、計
   算機言語学？)があった。
 - Prologにはcomputational linguisticsに有効なツー
   ルがたくさんある。
 - その筆頭がDCGである。
 - DCGは文法を記述するための記法である。
 - そもそも文法って何だ。CFGをもってそれを考える。
 - CFGの説明。
  - CFGはシプサでやったので、用語だけ確認しておく。
  - non-terminal symbols
  - terminal symbols
  - context free rules
  - -> : can consist of, can be built out of.
  - parse tree : parseは品詞を記述する、構成要素に
    分析するという意味らしい。websterだと、Analyze
    syntactically by assingning a constituent
    structure to (a sentence).
  - licensed : "every part of the tree is licesed
    by one of our rules", 認可された
  - strings : ここではstring of wordsというように
    wordの並びをstringという。
  - structure : parse treeのもつ構造のこと。
  - grammatical : the stringが(given grammarにおい
    て)grammaticalであるとは、その文法規則によって
    parse treeを構成できることを言う。
  - language generated by a grammar : その文法要素
    によって生成可能な全てのstringsの総体をこのよ
    うに呼ぶ。
  - recogniser : stringsがgiven grammarにて生成可
    能かどうか判定するプログラム。
  - parser : recogniserの機能に加えて、the
    structureを示すもの。具体的にはparse treeを示
    すもの。
  - context free language : context free grammarで
    文法を記述可能な言語達のこと。英語はCFGと考え
    られている。ドイツ語はCFGでは無いことが証明さ
    れている。

  - まず、CFGのrecognizerをPrologでどう作るか。
  - stringsはlistsとする。
  - 対象CFG。

s -> np vp
np -> det n
vp -> v np
vp -> v
det -> 'a
det -> 'the
n -> 'woman
n -> 'man
v -> 'shoots

  (注)italic表示のかわりに'を頭につけている。
  terminalたちです。

  - appendを使う素朴なやり方。
  - その1。

s(Z) :- np(X), vp(Y), append(X,Y,Z).
np(Z) :- det(X), n(Y), append(X,Y,Z).
vp(Z) :- v(X), np(Y), append(X,Y,Z).
vp(Z) :- v(Z).
det([the]).
det([a]).
n([woman]).
n([man]).
v([shoots]).

  - 動く。しかし、入力情報を探索のガイドにつかって
    いないので非効率的。

  - その2。
  - goalsの順番を変えてみる。

s(Z) :- append(X,Y,Z), np(X), vp(Y).
np(Z) :- append(X,Y,Z), det(X), n(Y).
vp(Z) :- append(X,Y,Z), v(X), np(Y).
vp(Z) :- v(Z).
det([the]).
det([a]).
n([woman]).
n([man]).
v([shoots]).

  - 動く。しかしappendとinstansiationsの組み合わせ
    は非効率的。traceをみる。

[trace]  ?- np([a,woman]).
   Call: (7) np([a, woman]) ? 
   Call: (8) append(_L179, _L180, [a, woman]) ? 
   Exit: (8) append([], [a, woman], [a, woman]) ? 
   Call: (8) det([]) ? 
   Fail: (8) det([]) ? 
   Redo: (8) append(_L179, _L180, [a, woman]) ? 
   Call: (9) append(_G366, _L180, [woman]) ? 
   Exit: (9) append([], [woman], [woman]) ? 
   Exit: (8) append([a], [woman], [a, woman]) ? 
   Call: (8) det([a]) ? 
   Exit: (8) det([a]) ? 
   Call: (8) n([woman]) ? 
   Exit: (8) n([woman]) ? 
   Exit: (7) np([a, woman]) ? 
true 

 - もっとうまい方法はないか。
 - ある。
 - difference listsという方法。(差分リストとでも言
   うのかなぁ)

 - difference listsは、2つのリストの差によって対象
   となるリストを表現する。

 - difference lists版。

s(X,Z) :- np(X,Y), vp(Y,Z).
np(X,Z) :- det(X,Y), n(Y,Z).
vp(X,Z) :- v(X,Y), np(Y,Z).
vp(X,Z) :- v(X,Z).

det([the|W],W).
det([a|W],W).

n([woman|W],W).
n([man|W],W).

v([shoots|W],W).

 - これ、昨日flatten書くときに使った手法だ。
 - この手法にdifferencial listsという名前をつけて、
   汎用化するところが頭いいな。

[trace]  ?- s([a,woman,shoots,a,man],[]).
   Call: (7) s([a, woman, shoots, a, man], []) ? 
   Call: (8) np([a, woman, shoots, a, man], _L180) ? 
   Call: (9) det([a, woman, shoots, a, man], _L198) ? 
   Exit: (9) det([a, woman, shoots, a, man], [woman, shoots, a, man]) ? 
   Call: (9) n([woman, shoots, a, man], _L180) ? 
   Exit: (9) n([woman, shoots, a, man], [shoots, a, man]) ? 
   Exit: (8) np([a, woman, shoots, a, man], [shoots, a, man]) ? 
   Call: (8) vp([shoots, a, man], []) ? 
   Call: (9) v([shoots, a, man], _L234) ? 
   Exit: (9) v([shoots, a, man], [a, man]) ? 
   Call: (9) np([a, man], []) ? 
   Call: (10) det([a, man], _L252) ? 
   Exit: (10) det([a, man], [man]) ? 
   Call: (10) n([man], []) ? 
   Exit: (10) n([man], []) ? 
   Exit: (9) np([a, man], []) ? 
   Exit: (8) vp([shoots, a, man], []) ? 
   Exit: (7) s([a, woman, shoots, a, man], []) ? 
true 

 - うーん。きれい。
 - さて、differece listsを使ったrecogniserはかきぶ
   りがちょっと汚い。
 - そこでDCGの出番。

** 2 Definite Clause Grammars

 - DCGは、difference listsを隠蔽してくれるa nice
   notation。
 - 例。

s   --> np,vp.
np  --> det,n.
vp  --> v,np.
vp  --> v.
det --> [the].
det --> [a].

n   --> [woman].
n   --> [man].

v   --> [shoots].

 - うむ。構文糖衣というかDSLというか。
 - Prologがこれをdifferece listsを使った先の書きぶ
   りに変換するとのこと。試す。

?- listing(s).
s(A, C) :-
 np(A, B),
 vp(B, C).

true.

?- 

 - ルール追加。

s    --> s,conj,s.
conj --> [and].
conj --> [or].
conj --> [but].

 - このs,conj,sのsが左再帰問題。
 - 語彙を変える。

s --> simple_s.
s --> simple_s,conj,s.
simple_s --> np,vp.
np --> det,n.
vp --> v,np.
vp --> v.
det --> [the].
det --> [a].

n   --> [woman].
n   --> [man].

v   --> [shoots].

conj --> [and].
conj --> [or].
conj --> [but].

  - そっか。CFGでnon-terminalについて名前を工夫し
    ているときってこういう理由だったんだな。PAIPも
    そうやってた。

  - formal languageってnatural languageと対を成す
    単語なんだ。
  - 形式言語(a^n)(b^n)。シプサの世界だ。

s --> [].
s --> l,s,r.

l --> [a].
r --> [b].

** 3 Exercises
 - Exercise 7.1.
s(A,D) :-
        foo(A,B),bar(B,C),wiggle(C,D).
foo([choo|W],W).
foo(X,Z) :-
        foo(X,Y),foo(Y,Z).
bar(X,Z) :-
        mar(X,Y),zar(Y,Z).
mar(X,Z) :-
        me(X,Y),my(Y,Z).
me([i|W],W).
my([am|W],W).
zar(X,Z) :-
        blar(X,Y),car(Y,Z).
blar([a|W],W).
car([train|W],W).
wiggle([toot|W],W).
wiggle(X,Z) :-
        wiggle(X,Y),wiggle(Y,Z).

 - Exercise 7.2.
s --> l,r.
s --> l,s,r.

l --> [a].
r --> [b].

 - Exercise 7.3.
s --> [].
s --> l,s,r,r.

l --> [a].
r --> [b].

** 4 Practical Session
 - 1.
s --> [].
s --> w,s,w.
w --> [a].

 - 2.
s --> core.
s --> a,s,d.
core --> [].
core --> b,b,core,c,c.
a --> [a].
b --> [b].
c --> [c].
d --> [d].

 - 3.
 - propositional logic : 命題論理

prop --> [p].
prop --> [q].
prop --> [r].
prop --> not, prop.
prop --> lparen, prop, or, prop, rparen.
prop --> lparen, prop, and, prop, rparen.
prop --> lparen, prop, imp, prop, rparen.

not --> [not].
or --> [or].
and --> [and].
lparen --> ['('].
rparen --> [')'].
imp --> [implies].

この章おもしろかった。
こつこつ。