構文解析のソースを表示

'''構文解析'''（こうぶんかいせき、Syntactic Analysis）とは、ある[[文章]]の[[文法]]的な関係を説明すること(''parse'')。[[情報工学|計算機科学]]の世界では、構文解析は[[字句解析]]（''Lexical Analysis''）とともに、[[コンピュータ言語]]などの[[形式言語]]の解析に使用される。また、[[自然言語処理]]に応用されることもある。

構文解析を行う機構を'''[[構文解析器]]'''（Parser）と呼ぶ。

Parsing は本来、自然言語の文法で文の図式化を行うことを指す用語であり、[[ロマンス諸語]]や[[ラテン語]]のような[[語形変化]]のある言語の文法の図式化を現在でも Parsing と呼ぶ。

== 形式言語 ==
一般的に、[[プログラム]]における構文解析では、コンピュータ言語などの形式言語で記述された入力から、字句解析を通してトークン列を受け取り、[[構文木]]や[[抽象構文木]]のような[[データ構造]]を生成し、その後の処理に渡す。構文解析と同時に、目的の処理をおこなってしまう場合もある。

形式言語と[[オートマトン]]の対応は、良く理論付けられており、構文解析の[[アルゴリズム]]は、その入力である形式言語に対応するオートマトンの[[実装]]にほかならない。

[[プログラミング言語]]の場合、実用上、プログラムとして正しい入力のみを受け付けるような構文規則を定めることは現実的でない。そのため、一般に構文解析器は制約を弱めて本来の言語の文法よりも広い範囲の構文を受け付け（つまり、不正な構文も受け付ける）、後で不正なものを排除するようにすることが多い。

構文解析器を一から作るのではなく、[[パーサジェネレータ]]で生成することも広く行われている。

=== 処理概要 ===
以下では、字句文法と構文文法という2段階の文法を持つコンピュータ言語の構文解析を例として説明する。

まず第一段階として字句（トークン）を生成する。これを[[字句解析]]と呼ぶ。入力文字列は[[正規表現]]による文法で定義された意味のあるシンボルに分割される。例えば、電卓プログラムに "12*(3+4)^2" と入力されたとき、これを 12, *, (, 3, +, 4, ), ^, 2 という字句（トークン）に分割する。各トークンは電卓プログラムの数式として意味のあるシンボルである。字句解析を含む構文解析器は *, +, ^, (, ) といった文字が新たなトークンの先頭になるという規則を持っているため、"12*" や "(3" といった無意味な字句の切り分けは発生しない。

次の段階で実際の構文解析を行う。構文解析では、トークンの並びが文法に照らして正しい表現となっているかを判定する。このため、[[文脈自由文法]]を参照して再帰的に規則を適用していく。ただし、プログラミング言語の構文規則は文脈自由文法だけでは表現できない。例えば、データ型が正しいか、識別子の宣言が正しいかなどは文脈自由文法の範囲外の話である。そのような規則は形式的には[[属性文法]]で表される。

最後に、意味的な解析が行われ、構文が確認された表現の意味を識別して、適当な行動をとる。電卓プログラムの場合、適当な行動とは式の評価（計算）であり、コンパイラならコードの生成である。属性文法もそのような行動決定に関与する。

=== 手法 ===
構文解析にはさまざまな手法が提案されており、それぞれの構文解析法に対して適用可能な文法の範囲が存在する。構文解析法は大まかに[[演算子順位法]]、[[トップダウン構文解析|トップダウン構文解析法]]、[[ボトムアップ構文解析|ボトムアップ構文解析法]]に分類でき、歴史的には、演算子順位法、トップダウン構文解析法は構文解析理論によって後から説明が加えられ、ボトムアップ構文解析法は理論主導で作成された。

演算子順位法とトップダウン構文解析法の手続きは人力で作成されることがコンパイラの初期の時代にはあった。特に、トップダウン構文解析法である[[再帰下降構文解析|再帰下降構文解析法]]はそのプログラムの実際のコードが文法の記述によく一致することが知られている。しかし、一般にボトムアップ構文解析は非常に多くの内部状態とその間の遷移規則を必要とし、その手続きを人力で作成するのは困難である。

現在は、主にボトムアップ構文解析法である[[LALR法|LALR]](1)を使用した構文解析器がパーサジェネレータによって生成されることが多い。この手法を使用するパーサジェネレータには[[yacc]]や[[bison]]などがあり、どちらも代表的なパーサジェネレータである。これらのパーサジェネレータがこの手法を採用する理由としては、適用可能な文法範囲が十分に大きく、効率もそこそこ悪くないことなどが挙げられる。その他に、トップダウン構文解析法である[[LL法]]が使用・生成される場合もままある。

=== 具体例 ===
たとえば、[[インターネット]]上の [[ウェブページ|Webページ]]や[[メールアドレス]]をあらわす [[Uniform Resource Locator|URL]] は、次のような構文をもっている:
* <tt><nowiki>http://サーバ名/パス名</nowiki></tt>（webページをあらわす場合, <tt><nowiki>"http://www.yahoo.com/index.html"</nowiki></tt>など）
* <tt><nowiki>mailto:ユーザ名@ドメイン名</nowiki></tt>（電子メールアドレスをあらわす場合, <tt><nowiki>mailto:god@heaven.mil</nowiki></tt> など）
[[ウェブブラウザ|Webブラウザ]]に <tt><nowiki>"http://ja.wikipedia.org/index.html"</nowiki></tt> などの[[文字列]]を入力した場合、ブラウザはそこからサーバ名 <tt>"ja.wikipedia.org"</tt> とパス名 <tt>"index.html"</tt> を読みとらなければならない。これは構文解析の非常に簡単な例である。

より複雑な構文解析は、[[C言語|C]]や[[Java]]などのプログラミング言語において次のような数式を計算する場合に必要となる:
 2 + ( a + b &times; c ) &divide; ( d - e )
この場合、コンピュータはどこから計算を始めなければならないかというと、まずかっこの中を先に計算しなければならない。しかし[[数学]]では同一のかっこの中でもかけ算を足し算より先に行わなければならないという規則がある（[[演算子の優先順位]]）。このため、実際にコンピュータが計算する順序は次のようになるだろう:
* まず<code>b &times; c</code>の値を計算する。
* そこにaの値を足し、これをかりに<code>X</code>と名づける。
* それとは別個に<code>d - e</code>の値を計算し、これをかりに<code>Y</code>と名づける。
* <code>X &divide; Y</code>を計算する。
* そこに2を足す。
しかしこの順序は式を一見しただけではなかなかわからない。そこで[[構文解析器]]（パーサ）は与えられた数式に以下のような「註釈」をつけ、それぞれの項の関係をより明確な形で表現する:
 数値:2 + 式:( 式:( 変数:a + 式:( 変数:b &times; 変数:c ) ) &divide; 式:( 変数:d - 変数:e ) )
構文解析の結果は[[構文木]]としても表すことができる。構文解析は[[コンパイラ]]におけるもっとも中心的な過程のひとつであり、その手法は従来からさまざまな研究がなされている。

一般に、[[形式言語]]の構文解析は[[曖昧]]でない言語を対象としている。ある言語が曖昧であるとは、ひとつの文にたいして2通り以上の構文解析が可能であることをいう。プログラミング言語でよく知られている例に「宙ぶらりんelse問題（dangling else problem）」がある。たとえば以下のような[[文脈自由文法]] であらわされる言語を考える:
 文 ::= if 文 then 文
 文 ::= if 文 then 文 else 文
すると、以下の文には 2通りの[[解釈]]が考えられる:
 if A then if B then C else D
ひとつは「<code>if A then - </code>」と「<code>if B then C else D</code>」という2つの連なった文からなるとする解釈。もうひとつは「<code>if A then - else D</code>」という文の中に「<code>if B then C</code>」という文が埋めこまれているとする解釈である。elseに対応するifがどちらかはっきりしないことからその名がある。

ふつうコンピュータの動作には厳密さが要求され、このように複数の[[解釈]]があることは許されないため、一般的にはエラーを出すか、elseは一番近いthenと結び付くように定めるなどして、文法の[[曖昧]]性を解消している。

== 自然言語 ==
[[機械翻訳]]システムや[[自然言語処理]]システムでは、人間の言語（[[自然言語]]）をコンピュータプログラムで構文解析する。自然言語の文には構文上の曖昧さがあるため、それをプログラムで構文解析することは容易ではない。自然言語データを構文解析するには、まずその言語の[[文法]]を選択しなければならない。文法の選択は、言語学的考慮とコンピュータでの扱いやすさを考慮して行われる。例えば、いくつかの構文解析システムは[[語彙機能文法]](LFG)を使用するが、一般にこの種の文法の構文解析は[[NP完全問題]]であることが知られている。他にも[[主辞駆動句構造文法]](HPSG)もよく使われるが、最近ではより単純な形式文法の研究が盛んで、Penn [[ツリーバンク|Treebank]] などが挙げられる。[[シャローパーサ|シャロー（浅い）構文解析]]では、[[名詞句]]などの大まかな構文の境界だけを見つけ出す。また、言語学的議論を避けた手法としては[[依存文法]]による構文解析がある。

最近の構文解析では[[統計学]]的手法を部分的に取り入れている。すなわち、事前に構文解析済みのトレーニング用データ群を使う手法である。この場合、システムは特定の文脈でどのような構文が出現しやすいかという頻度情報を持つことになる（[[機械学習]]参照）。この手法では[[確率文脈自由文法]](PCFG)を使うもの、[[最大エントロピー原理]]を使うもの、[[ニューラルネットワーク]]を使うものがある。成果を上げているシステムでは、「字句」統計をとっていることが多い（すなわち、[[品詞]]も含めた単語の出現順の統計をとる）。しかし、この種のシステムは[[過剰適合]]の問題があり、効果を上げるにはある種の平滑化が必要となる。

自然言語の構文解析アルゴリズムは、プログラミング言語の人工的な文法のように「良い」特性を持つ文法に依存することはできない。上述のように文法によってはコンピュータが扱いにくい場合がある。一般にたとえ目的とする構造が[[文脈自由言語|文脈自由]]でなかったとしても、最初に文脈自由な近似を文法に施して構文解析を行うことがある。文脈自由文法を使ったアルゴリズムは[[CYK法]]に基づく場合が多く、時間を節約するためにそれに何らかの[[ヒューリスティック]]を加えることが多い（[[チャートパーサ]]など）。最近では、構文解析器が複数の解析結果を返し、上位のシステムがそれらの中で最も良いと思われるものを選択する手法もある。

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

プログラミング言語とは違って、自然言語は通常何十通りもの解釈が存在する。たとえば[[形態素解析]]の項で挙げた「うらにわにはにわとりがいる」のような例の他にも、次のような文:
: [[美しき水車小屋の娘|美しい 水車小屋の 乙女]]
には少なくとも2つの解釈が存在する。「'''水車小屋が美しい'''」場合と、「'''乙女が美しい'''」場合である。自然言語は本質的に曖昧であり、その解釈を決定するにはその文が書かれているまわりの文脈や、それを書いた人の心理までも考慮に入れなければならないこともある。
: ここでいう「曖昧」とは、文の意味を知るために、その文が置かれた状況、言い換えると[[コンテクスト|コンテキスト]]、フレーム情報などを考慮しなければ、同定できないということを指す。決して自然言語では曖昧な表現しかできないという意味ではないことに注意するように。

日本語の構文解析は、おもに[[文節]]間の[[係り受け]]構造を発見することである。たとえば、上の文が以下のような係り受け構造をもっている場合、「美しい」のは水車小屋ではなく乙女のほうであり、「水車小屋の美しい乙女」という言い換えも可能である。

[[画像:Kakariuke-sample1.png|係り受け構造の例1]]

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

[[画像:Kakariuke-sample2.png|係り受け構造の例2]]

（ちなみに原文のドイツ語では「水車小屋の娘」が一語であるため、美しいのが乙女であるのは明らかである。）

=== [[フリーソフトウェア|フリー]]で入手可能なもの ===
* [[日本語構文解析システム KNP|KNP]]、[http://nlp.ist.i.kyoto-u.ac.jp/index.php?KNP http://nlp.ist.i.kyoto-u.ac.jp/index.php?KNP]
* [[日本語構文解析システム CaboCha|CaboCha]]、[http://chasen.org/~taku/software/cabocha/ http://chasen.org/~taku/]

== 関連項目 ==
* [[ノーム・チョムスキー]]
* [[言語学]]
* [[生成文法]]
* [[構文木]]
* [[字句解析]]
* [[句構造規則]]
* [[形式文法]]
* [[量子論理]]

[[Category:言語学|こうふんかいせき]]
[[Category:自然言語処理|こうふんかいせき]]
[[Category:構文解析 (プログラミング)|*こうふんかいせき]]
[[Category:数学に関する記事|こうふんかいせき]]
[[Category:統語論|こうふんかいせき]]
[[Category:形式科学|こうふんかいせき]]