構文解析の例

この節では "I saw a girl with a telescope." という文を例にして， Enju で構文解析がどのように行われているかを見ていきます．

• 前処理
• 語彙項目の作成
• チャートによる構文解析
  • エッジ
  • チャート
  • リンク
• 出力

前処理

前処理の節で示したように， 前処理はsentence_to_word_lattice/2で行われます．

入力文はまずexternal_tagger/2により品詞タガーにかけられます．

"I/PRP saw/VBD a/DT girl/NN with/IN a/DT telescope/NN ./."

語彙項目の作成

up に語彙項目の sign を渡すには，lexical_entry/2と lexical_entry_sign/2が使われます．

lexical_entry/2は， 前処理の結果得られた 'extent_word' 型の word 素性の値に対して呼び出されます． その値は 'word' 型のリストになっているので、その各要素に対して lookup_lexicon/2により対応するテンプレートのリストを得ます． lookup_lexicon/2では，lexicon_lookup_keyや unknown_word_lookup_key/2で得られるキーによって， 辞書のデータベースを引きます． 上の "saw" に対応する 'extent_word' 型の場合， word 素性は要素一つのリストです．その要素に対して lexicon_lookup_key/2が対応させるキーは， 単語の base form と 品詞を取り出したもので，次のようになります．

次に，残った 'lex_entry' 型に対してlexical_entry_sign/2が 呼ばれます．lexical_entry_sign/2ではまず， lookup_template/2により 'lex_entry' 型の LEX_TEMPLATE 素性の 値をキーにして，テンプレートデータベースを引きます． 上の 'lex_entry' 型の場合， このようなテンプレートが得られます． そのテンプレートに単語依存情報を付加します． 具体的には，引数で渡された 'lex_entry' 型の LEX_WORD\INPUT 素性と， PHON 素性の値を単一化するなどの処理を行います． その結果のsignが， lexical_entry_sign/2の返り値となります．

得られた sign は reduce_sign/3 によって factoring という処理をされます． factoring では，sign のなかの一部の情報を切り捨てることで， 複数の等価な sign がひとつの sign に縮退され， 後の構文解析では縮退した sign が使われます． reduce_sign/3では，sign を与えると 縮退した sign と切捨てられた情報を返すようにすることで， factoring 処理を指定します． (詳しくはリンクの節を参照して下さい) その後fom_terminal/4に，'lex_entry' 型，対応する縮退した sign， 縮退した時に切り捨てられた情報をわたすと，FOM が計算されます． ここでも FOM が低かった sign は足切りされます．

チャートによる構文解析

UPではエッジ，チャート，リンクと呼ばれるデータ構造を使って構文解析を行います．

エッジ

エッジは，概念的には<左ポジション，右ポジション，sign，リンクのリスト，FOM> の5つの組で表現されます．ポジ ションは単語の境界位置をあらわします．つまり，エッジは 文中のある位置からある位置までに対応する sign をあらわしている，という ことになります．また，パーズツリーを構文解析後に復元するための情報がリ ンクリストに入っており，曖昧性解消のためのスコアがFOMにはいって います．

チャート

パーザには，チャートと呼ばれる構文解析状態を保存するデータがあります． チャートは，二次元テーブルになっていて，各要素をCKYセルと呼びます． 文 "I saw a girl with a telescope" が入力されたとき，チャートは次のようになります．

リンク

構文解析の際には子のエッジにid_schema_unary/4と id_schema_binary/5によって定義された文法規則を適用して， 新たに親ができます． 例えば，S[1][2]に格納されたエッジと S[2][4]に格納されたエッジに文法適用した 結果はS[1][4]に格納されます．この際に，同じCKYセル中の複数の等価な sign は， reduce_sign/3で指定された方法でfactoring と呼ばれる処理をされ， ひとつの sign に縮退されます． factoring の処理においては，構文解析後に復元できる情報は切り捨てられるの で，構文解析後に復元できるようリンクと呼ばれるデータ構造にそれらの情報 を格納しています．例えば，子供のサインは切り捨てられる代表的な情報です． 他にも意味構造なども切り捨てて，全てリンクに格納します． 縮退されると複数のエッジが一つのエッジになるため， 一つのエッジに複数のリンクが対応します． 構文解析後，エッジとリンクを相互にたどることによって 全パーズツリーを参照することができます．

文"I saw a girl with a telescope."の場合， S[1][2]に格納されたエッジにはこのような signを 持つものがあります．またS[2][4]に格納されたエッジには このような signを持つものがあります． これらの sign には，id_schema_binary/5で定められた 'head_comp_schema' が適用できます． id_schema_binary/5では，スキーマの名前， 左右の娘の素性構造，親の素性構造，スキーマ適用後に実行する lilfes プログラムが 指定されています(id_schema_unary/4では娘の素性構造がひとつになります)． 'head_comp_schema' の場合，左右の娘の素性構造は大体次のように指定されています．

構文解析が文全体に対応する CKY セル (この例の場合 S[0][7]) まで終わると， そのセル内の全てのエッジについて，fom_root/2によって それらのFOM が 計算されます．fom_root/2では，文の root node の sign が渡されると その sign に対する FOM が返されるようになっています． これら文の root node のエッジが， parse tree の root としての条件を 満たしているかどうかは， root_sign/1 によって最後にチェックされます． 文 "I saw a girl with a telescope." の場合， セル S[0][7] の中の エッジのうち，root_sign/1を満たしかつ最も FOM が高いものは， このような signを持っています． この sign は, ふたつ sign が縮退してひとつになったものです． それぞれ "with a telescope" が動詞句にかかる場合と名詞句にかかる場合に 対応しています． エッジとリンクを相互にたどり FOM の高いほうを選ぶことによって， 最も FOM の高い signを復元することができます．

出力

上記の構文解析によって得られた最も FOM の高い sign をもとにして 出力が行われています． 上の例の場合，"enju/outputdeps.lil" による出力は次のようになります．

ROOT  ROOT  ROOT  ROOT  -1  ROOT  saw       see       VBD  VB   1
saw   see   VBD   VB     1  ARG1  I         i         PRP  PRP  0
saw   see   VBD   VB     1  ARG2  girl      girl      NN   NN   3
a     a     DT    DT     2  ARG1  girl      girl      NN   NN   3
a     a     DT    DT     5  ARG1  telescope telescope NN   NN   6
with  with  IN    IN     4  ARG1  saw       see       VBD  VB   1
with  with  IN    IN     4  ARG2  telescope telescope NN   NN   6