構文解析メモ

自然言語処理 プログラミング

はじめに

「構文解析」まわりについてちょっと調べたのでメモ。
ただ、資料が少なくて内容が怪しい部分が多い。

構文解析とは

  • 入力された文に対して、文を構成しているそれらの構文構造を同定すること
  • 文法規則が定められたプログラミング言語、正規表現、HTML/XMLなどを解析するために使われている
  • 自然言語では、複数の単語で1つの句を形成したりある単語が別の単語を修飾するなどの現象があるので、文法を考え構文解析することで自然文を解析する
構文解析器(Parser)
文の構造
  • 構造とは、要素同士がなんらかの相互作用によって結びついている集合と見れる
    • 「要素」と「それらがどのように関係しあっているか」が重要
構文木(parse tree)
  • 文の構成要素・修飾関係を表現する木構造

直接構成要素分析(immediate constituent analysis)

  • 自然文に対して、直接的に、どのような構成要素からできているかを分析する
    • 「文は、後置詞句と動詞から成る」
    • 「後置詞句は、名詞と助詞から成る」
    • などの知見を得る
  • 文が「句」で構成されていると仮定し、上記の分析から、どのような規則があるかを記述したものが「句構造規則」
  • 句構造規則により記述される文法が「句構造文法」

　

文法

  • 文法は、要素とその要素同士の関係性を記述したもの
  • 「句構造文法」は4つのクラスに分けられる
    • チョムスキー階層
    • Typeの数字が大きいほど記述に関する制限が強い
    • Typeの数字が小さい文法とはより数字が大きい文法を包含している
  • 「生成規則」は、形式文法の構成要素では、「ある規則の左側にある記号を右側の記号列で置き換える」というのを表す
    • 記号は「終端記号(単語、それ以上置き換えができないもの)」「非終端記号(置き換えを行わなければいけないもの)」「開始記号」からなる
      • 終端記号：構文木で葉になるもの
      • 非終端記号：構文木で内部ノードになるもの
      • 開始記号：ルートノードになるもの
【Type0】制限のない文法・句構造文法
  • 以下、すべての文法を包含する文法
  • この文法(＝全ての言語)を解析できるアルゴリズムは見つかっていない
  • 生成規則に制限はない
  • この文法で記述される言語は、チューリングマシンで認識できる
【Type1】文脈依存文法
  • 文脈不自由文法とも
  • さまざまな言語現象を記述できる文法
    • 階層構造や長距離依存性など
  • 効率的な解析アルゴリズムは見つかっていない
  • 生成規則は、「αAβ->αγβ」という制約を持つ
    • Aは非終端記号、α・β・γは終端・非終端記号からなる文字列
  • この文法で記述される言語は、線形拘束オートマトンで認識できる
【Type2】文脈自由文法
  • ある程度の言語現象を記述でき、効率的な解析アルゴリズムがある文法
  • 生成規則は、「A->γ」という制約を持つ
    • Aは非終端記号、γは終端・非終端記号からなる文字列
  • この文法で記述される言語は、非決定性プッシュダウンオートマトンで認識できる
【Type3】正規文法
  • 生成規則は、「左側は必ず一つの非終端記号、右側には必ずひとつの終端記号か一つ以下の非終端記号」という制約を持つ
  • 非常に効率のよい解析アルゴリズムが存在する
  • この文法で記述される言語は、有限オートマトンで認識できる
自然文での生成規則の例
  • 「文は、後置詞句と動詞句から成る」「後置詞句は、名詞と助詞から成る」「動詞句は、副詞と動詞から成る」という規則が合った場合を考える
  • 「太郎がぺろりと食べた」という文の場合
    • 文 -> 後置詞句 動詞句
    • 後置詞句 -> 名詞 助詞
    • 名詞 -> 太郎
    • 助詞 -> が
    • 動詞句 -> 副詞 動詞
    • 副詞 -> ぺろりと
    • 動詞 -> 食べた
  • 非終端記号
    • 「文」「後置詞句」「動詞句」「名詞」「助詞」「副詞」「動詞」
  • 終端記号
    • 「太郎」「が」「ぺろりと」「たべた」
  • 開始記号
    • 「文」
導出
  • 生成規則の右側で、複数の非終端記号が現れた場合、以下の処理の仕方がある
    • 一番左のものから置き換えを実行するのが「最左導出」
    • 一番右のものから置き換えを実行するのが「最右導出」
  • 例えば、「文 -> 後置詞句 動詞句」で、
    • 「後置詞句」の方から置き換えるのが「最左導出」
    • 「動詞句」の方から置き換えるのが「最右導出」

文法の記法

バッカス・ナウア記法(Backus-Naur Form)
  • 文脈自由文法を記述するための記法の一つ
    • いくつか拡張されたものが存在する
  • 「<記号> ::= <記号列>」「<記号> ::= <記号列> | <記号列>」のような形式の導出規則の集合
    • 左の<記号>に出てくる記号=非終端記号
    • 左の<記号>に一度も出てこない記号=終端記号
    • 縦棒「|」は、どちらかの"選択"を表す記号
  • BNFによるBNFの文法表現(from wikipedia)
 <syntax> ::= <rule> | <rule> <syntax>
 <rule> ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" 
            <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""  ……… "" は空文字列を表す
 <expression> ::= <list> | <list> "|" <expression>
 <line-end> ::= <opt-whitespace> <eol> | <line-end> <line-end>
 <list> ::= <term> | <term> <opt-whitespace> <list>
 <term> ::= <literal> | "<" <rule-name> ">"
 <literal> ::= '"' <text> '"' | "'" <text> "'"
拡張BNF
  • Extended BNF
  • BNFについて、記号の扱いや、繰り返し、オプション表現などを追加・修正した記法
ABNF
  • Augmented BNF
  • 通信プロトコルなどの言語の記述のために拡張された記法
  • 構文規則や生成規則がBNFとは異なる

解析アルゴリズム

  • 文法(生成規則)が与えられるとして、その文法がどのように構成されているかを求めるアルゴリズム
  • (字句解析や形態素解析された)文に対して構文木を出力する
    • (正規文法を包含する)文脈自由文法の解析アルゴリズムは古くからよく研究されている
  • 以下、文脈自由文法に関する解析アルゴリズム
チャート法
  • 完成した部分木と解析途中の部分木をチャートと呼ばれるデータ構造で扱う
    • 頂点が入力文中の位置、弧が解析途中の状態を表す有効グラフ
    • 弧には、ラベル(文法規則の左辺の記号)と空所リスト(未解析の記号リスト)を持つ
    • 空所を持つ弧(空所リストが空でない)は、解析途中の部分木を表す(活性弧)
    • 空所を持たない弧(空所リストが空)は、完成した部分木を表す(不活性弧)
  • アルゴリズム
    • 1.チャートの初期化
      • 終端記号に対応する不活性弧を待機弧リストに入れる
      • トップダウン解析の場合は、さらに、文法の開始ラベルとする活性弧を待機弧リストの先頭へ入れる
    • 2.解が見つかるか、待機弧リストが空になるまで以下を繰り返す
      • a.弧の選択
        • 待機弧リストから弧を取り出し、チャートへ登録
      • b.弧の結合
        • 活性弧の場合、その右側の不活性弧と結合する
        • 不活性弧の場合、その左側の不活性弧と結合する
        • 結合は、活性弧の空所リストの第1要素と不活性弧のラベルが一致すれば可能
      • c.弧の登録
        • 結合でき、その弧と同じものがチャート・待機弧リストに含まれなければ、待機弧リストに登録
      • d.活性弧の提案
        • トップダウンの場合、現在の弧が活性弧ならば、この活性弧の空所リストの第1要素を左辺とする生成規則から、この活性弧の終了位置に新しい活性弧を作成。待機弧リストへ登録
        • ボトムアップの場合、現在の弧が不活性弧ならば、この不活性弧を右辺の第1要素とする生成規則から、この不活性弧の開始位置に新しい活性弧を作成。待機弧リストに登録
CYK(Cocke-Younger-Kasami)アルゴリズム
  • アルゴリズム
    • 0.テーブルTを初期化
    • 1.「A->a」からTの対角要素を求める
      • for i in N
      • T(i,i) = {A | A->w_i}
    • 2.「A->BC」から対角要素以外の部分を求める
      • for k=1 to N-1
      • for i=1 to N-k
      • T(i,i+k) = ∪^{k}_{j=1} {A | A->BC, B∈T(i,i+j-1), C∈T(i+j,i+k)}
    • 3.T(1,N)が開始記号集合に含まれる非終端記号であれば、導出可能
アーリー法
  • アルゴリズム
    • 1.入力字句列w1..wnに対して、辞書引きを行い、wkの文法カテゴリがTの場合、[T wk]という不活性弧を位置k-1からkの間に張る
    • 2.最後に、位置0から0までという(特殊な)間に[S ?]という活性弧を張る
    • 3.位置jとk(j<=k)の間のすべての弧に対し、再帰的に重複がない限り繰り返す
    • 3-a.活性弧で最初の空所が[B ?]という形式の場合、規則B->XY..があれば、位置kとkの間に[B [X ?][Y ?]..]という項の活性弧を張る
      • 規則を適用して新しい活性弧を作る
    • 3-b.不活性弧で[X ..]という形式の場合、位置iからjの間の活性弧の項Aで、最も左の空所を含む構造が[X ?]であれば、A中の[X ?]を[X ..]で置き換えた項をA'として、位置iからkの間にこうA'の弧を張る
      • 活性この中の最も左の食う書に結合して新しい弧を作る
    • 4.位置0からnの間に[S ..]という項の不活性弧が少なくとも1つ張られていれば、解析成功
      • 曖昧性がある場合に1つ以上張られる
LL法
  • LL文法を解析できる構文解析アルゴリズム
    • LLとは、左から文を解析し、最左導出を行うこと
  • LL(k)文法: k個の字句の先読みで次に適用すべき規則が曖昧性なく決定できる、という条件を持つ文法
  • LL構文器は以下で構成される
    • スタック
    • 構文解析表：スタック最上段の記号と入力文字列の字句から適用すべき文法規則を決定するための表
  • アルゴリズム
    • 1.入力ポインタを入力分の先頭にセット、スタックに初期状態Sと特殊な終端記号$をpush
    • 2-a.入力ポインタにある字句aとスタックの最上段の状態で構文解析表から文法規則を決定し、文法規則に従い、スタックへ置き換えた規則をpush
    • 2-b.もし、終端記号ならそのまま取り除く
    • 3.スタックが特殊な記号だけになるか、入力ポインタが終端になるまで2を続ける
    • 4.スタックが特殊な終端記号$だけになり、入力ポインタも終端まで行っていた場合、解析に成功したので終了
    • 5.そうでない場合、解析に失敗し、終了
LR法
  • LR文法を解析できるボトムアップ型構文解析
    • LRとは、左から文を解析し、最右導出を行うこと
  • LR(k)文法: k個の字句の先読みで次に適用すべき規則が合間性なく決定できる、という条件を持つ文法
  • LR構文解析器は以下で構成される
    • スタック
    • 文法から生成されたLR構文解析表(動作(action)表,行き先(goto)表)
      • この構文解析表の作成法でいろんな種類がある(SLR,LALR,正準LRなど)
      • 「yacc」はLALR法による構文解析器を生成
  • アルゴリズム
    • 1.入力ポインタを入力文の先頭にセット、スタックに初期状態を表す0をpush
    • 2.スタック最上段の状態sと入力ポインタの指す字句aにに対して、action[s,a]を調べる
    • 移動
      • action[s,a]が「sn」形式だったら、現在の字句に対応する非終端記号aと状態nをスタックにpushし、入力ポインタを一つ先へ移動
    • 還元
      • action[s,a]が「rn」形式だったら、n番目の文法規則を適用する
      • それが「A->α」とすると、
      • αの構成要素数だけスタックからpop
      • 次に、スタック最上段の状態s'と文法規則Aからgoto[s',A]を調べ、Aとgoto[s',A]をスタックにpush
      • 入力ポインタは進めない
    • 受理
      • action[s,a]が「acc」だったら、受理(導出)されることを示す
    • 誤り
      • action[s,a]がそれ以外の場合、受理(導出)されないことを示す
    • 3.ステップ2に戻り繰り返す
一般化LRアルゴリズム(generalized LR algorithm)
再帰下降法
  • 非終端記号に対応したプロシージャ(関数)を用意し、すべての非終端記号を処理するまで再帰的に呼び出す
  • 以下は、四則演算の再帰下降パーサ例
//再帰下降構文解析による四則演算(解析しながら計算も行う)
//参考:
//http://www.prefield.com/algorithm/string/parser.html
//http://www.slideshare.net/phi16/ss-9401439
/*
  expr ::= term | term '+' term | term '-' term    //式
  term ::= fact | fact '*' fact | fact '/' fact    //項
  fact ::= '(' expr ')' | 数字列                    //因子
 */
#include <iostream>
#include <string>

class shisoku {
  std::string text;
  std::string::iterator itr;
public:
  shisoku(const std::string& str){
    text = str;
    itr = text.begin();
  }

  int expr(){
    int ret = term();
    while(*itr == '+' || *itr == '-'){
      if(*itr == '+'){
	itr++;
	ret += term();
      }
      else if(*itr == '-'){
	itr++;
	ret -= term();
      }
    }
    return ret;
  }
  
  int term(){
    int ret = fact();
    while(*itr == '*' || *itr == '/'){
      if(*itr == '*'){
	itr++;
	ret *= fact();
      }
      else if(*itr == '/'){
	itr++;
	ret /= fact();
      }
    }
    return ret;
  }

  int fact(){
    if(*itr == '('){
      itr++;
      int ret = expr();
      itr++;
      return ret;
    }
    else{
      int ret = 0;
      while('0' <= *itr && *itr <= '9'){
	ret *= 10;
	ret += *itr - '0';
	itr++;
      }
      return ret;
    }
  }
};

int main(){
  std::string str;
  std::cin >> str;

  shisoku ssk(str);

  std::cout << ssk.expr() << std::endl;

  return 0;
}

その他の解析モデル

確率文脈自由文法
  • 文脈自由文法において、生成規則に書き換える条件付き確率を与えたもの
  • 2つ以上の解析が可能な(構文的曖昧性がある)場合、どちらの解釈を優先するかを定量的に表せる

自然言語の文法

  • 自然言語は「文脈自由文法」では表現しきれない
  • 自然言語を最も良く記述できる文法は、「文脈自由文法＋文脈依存性」と言われている
  • このように拡張された文法とその解析アルゴリズムが研究・提案されている
  • 提案されている文法
    • TAG(Tree-adjoining grammar)
    • HPSG(Head-driven Phrase Structure Grammar,主辞駆動句構造文法)
    • CCG(Combinatorial Categorial Grammar)
    • など

参考文献