Exercise 7-1

• これは講義ページにヒントPDFも出ていますのでそちらを参照。

Exercise 7-2 (a)

Earley 法

• 参考文献 : 私(amylase)はこれを参考に実装しました。擬似コードがあるので何とかなります。
  
  

• Earley 法概要

  • このアルゴリズムで構文木を作成する手順は次の２段階に分かれます。
    

  • 状態テーブルの生成 : 入力された字句列の各部分に対して、それが生成規則のどの部分にマッチングしているかを考えられる限りすべて列挙したテーブルを作ります。

  • 構文木の生成 : 作ったテーブルを参照して構文木を作ります。

• 実装の指針
  ※以下、上に示した参考文献 145 ページ, 151 ページの擬似コードを前提とした解説を行います。

  • 状態テーブルの生成

    • 状態テーブルの各要素 M_i,j に入れるべき要素は簡単に言うと「i番目の後ろから j番目の文字までを解析するときに取りうる導出の状態」です（入力文字は 1-based index）。
      で、ここでいう状態というのは言語処理系論の講義で扱ったLR構文解析でも見た「導出ルールの一箇所にどこまで読んだかを示すドットを加えたもの」です。実装する際には（ルールの左辺，ルールの右辺，ドットの位置）の３つ組で表すとよいでしょう。
      文献では非終端記号を導出する規則とそうでない規則を区別していないので、それらを統一的に扱う述語を用意しておくと便利かと思われます。
      では、擬似コードの解説に入ります。文献示されているA,B,C,Dの4つの部分についてそれぞれ説明します。

      • A : 初期状態の設定
        • 先頭から1文字も読んでいない状態の時は当然、開始記号からの導出で全く解析が進んでいない状態がテーブルに含まれているはずです。従って、開始記号 S を左辺に持つ規則をすべて M_0,0 に突っ込んでおきます。
      • B : 走査
        • A ∈ M_i,j すなわち、Aはi+1文字目からj文字目までを解析する途中の状態であるとき、ドットの後ろの文字がa_j+1だったらそれをシフトすることで解析が進みますよね。そういうことです。これでj+1文字目までが解析完了するので新しい状態は M_i,j+1 に入れます。
      • C : 完了
        • A ∈ M_i,j で、ドットの後ろの文字が非終端記号（これをBと呼ぶことにします）だったら処理は２通り（CとD）あります。Cの完了とは、ある程度先の部分で今問題となっている非終端記号Bの解析が完了している状態を見つけてくる操作です。もう少し具体的に言えば、ある自然数 k を持ってきて j+1 文字目から k 文字目まで解析したところ B の解析が終わっていた、つまり B → （導出記号列）・ ∈ M_j,k となっていればいいわけですね。これに成功すると、最初の A は k 文字目まで読むことで B を解析できるということになるので、 A のドットをひとつずらしたものを M_i,k 加えます。
      • D : 予測
        • DはCとは逆に j+1 文字目からから B を左辺とする導出があるかも知れないと考えるパターンです。これは A と同じように考えて, B を左辺に持つ規則をすべて M_j,j に突っ込めばOKです。

      テーブルを作成するには、はじめに A を実行したあと加える要素がなくなるまで B,C,D を繰り返します。状態テーブルは CKY 法で使ったものを使い回せばよいでしょう。注意すべきことは cky_chart.lil の get_chart 述語は何度でも成功して同じ内容を返し続けるということです。これによって無限ループに陥る危険があるので、不安ならば get_chart の後ろにカットを入れるとよいかもしれません（筆者未検証）。
      

  • 構文木の生成

    • 目標は parse(（ルールの左辺，ルールの右辺，ドットの位置）の３つ組, i, j) → i+1 語目から j 語目までを解析した構文木 となるような関数 parse() を実現することです。これさえ出来れば、あとは S が左辺であって右辺の一番最後がドットであるような３つ組, 0, （入力語の長さ）をparseに投げれば欲しい構文木が出ます。
      parseですべきことは、もらった３つ組のうちのルールの右辺の各要素に対して導出していくことです。右辺の要素のうち終端記号はそのまま、非終端記号ならあるポイント（アルゴリズム中での r）から今解析中の語の末尾(l)までを導出するルールをM_r,lから探してきて構文木の子ノードとすれば良いのです。

※8年前の講義資料：超わかりやすいよ。これ書いてる途中（つまり実装が完成したあと）でfuragaに教えてもらいました。あ、ありがとう……orz。

Exercise 7-2 (b)

• できた方が加筆してくれることでしょう。

Categoryノート