構文解析

構文解析（こうぶんかいせき、Syntactic Analysis）

構文解析とは、ある文章の文法的な関係を説明すること(parse)。
計算機科学の世界では、構文解析は字句解析(Lexical Analysis)とともに、
おもにプログラミング言語などの形式言語の解析に使用される。
また、自然言語処理に応用されることもある。

形式言語の構文解析

たとえば、インターネット上の Webページやメールアドレスをあらわす URL は、次のような構文をもっている:

http://サーバ名/パス名 (webページをあらわす場合"http://www.yahoo.com/index.html/"など) 
mailto:ユーザ名@ドメイン名 (電子メールアドレスをあらわす場合, mailto:god@heaven.mil など)

ブラウザに "http://ja.wikipedia.org/index.html" などの文字列を入力した場合、
ブラウザはそこからサーバ名 "ja.wikipedia.org" とパス名 "index.html" を
読みとらなければならない。これは構文解析の非常に簡単な例である。

より複雑な構文解析は、C や JAVA などのプログラミング言語において次のような数式を計算する場合に必要となる。

2 + ( a + b × c ) ÷ ( d - e )

この場合、コンピュータはどこから計算を始めなければならないかと言うと、
まずかっこの中を先に計算しなければならない。
しかし数学では

同一のかっこの中でもかけ算を足し算より先に行わなければならない

という規則がある （演算子の優先順位）。
このため、実際にコンピュータが計算する順序は次のようになるだろう。

まず b × c の値を計算する。
そこに a の値を足し、これをかりに X と名づける。~ それとは別個に d - e の値を計算し、これをかりに Y と名づける。
X ÷ Y を計算する。
そこに 2 を足す。
しかしこの順序は式を一見しただけではなかなかわからない。
そこで構文解析器（パーサ）は与えられた数式に以下のような「註釈」をつけ、
それぞれの項の関係をより明確な形で表現する:

数値:2 + 式:( 式:( 変数:a + 式:( 変数:b × 変数:c ) ) ÷ 式:( 変数:d - 変数:e ) ) 

構文解析の結果は構文木としても表すことができる。
構文解析はコンパイラにおけるもっとも中心的な過程のひとつであり、
その手法は従来からさまざまな研究がなされている。
現在ほとんどのプログラミング言語で使われている手法は
LR法を改良したLALR法であり、これは構文解析器を手軽に設計するための
yacc や bison などといったツールが普及したことによる。

一般に、形式言語の構文解析は曖昧でない言語を対象としている。
ある言語が曖昧であるとは、ひとつの文にたいして2通り以上の構文解析が可能であることをいう。
初期のプログラミング言語にはよく知られた「elseぶら下がり問題(dangling-else problem)」が存在した。
たとえば以下のような文脈自由文法 であらわされる言語を考える:

文 ::= if 文 then 文 
文 ::= if 文 then 文 else 文 

すると、以下の文には 2通りの解釈が考えられる:

if A then if B then C else D 

ひとつは「if A then - 」と「if B then C else D」という2つの連なった文からなるとする解釈。
もうひとつは「if A then - else D」という文の中に「if B then C」という文が埋めこまれているとする解釈である。

ふつうコンピュータの動作には厳密さが要求され、
このように複数の解釈があることは許されないため、
このような曖昧な文法をもつプログラミング言語は現在では存在していない。

自然言語の構文解析

構文解析の観点からみた形式言語と自然言語のちがいは、それが曖昧であるかないかということである。

プログラミング言語とは違って、自然言語は通常何十通りもの解釈が存在する。
たとえば形態素解析の項で挙げた
「うらにわにはにわとりがいる」のような例の他にも、次のような文:

美しい 水車小屋の 乙女 

にはすくなくとも 2つの解釈が存在する。
水車小屋が美しい場合と、乙女が美しい場合である。
自然言語は本質的に曖昧であり、その解釈を決定するにはその文が書かれているまわりの文脈や、
それを書いた人の心理までも考慮に入れなければならないこともある。

ここでいう「曖昧」とは、文の意味を知るために、その文が置かれた状況、
言い換えるとコンテキスト、フレーム情報などを考慮しなければ、同定できないということを指す。
決して自然言語では曖昧な表現しかできないという意味ではないことに注意せよ。
日本語の構文解析は、おもに文節間の係り受け構造を発見することである。
たとえば、上の文が以下のような係り受け構造をもっている場合、
「美しい」のは水車小屋ではなく乙女のほうである(その場合、水車小屋の美しい乙女という表現が可能)。


いっぽう、もし文が以下のような係り受け構造をもっていたとすれば、
この場合「美しい」のは水車小屋のほうである。