構文解析
構文解析（こうぶんかいせき、Syntactic Analysis）とは、ある文章の文法的な関係を説明すること(parse)。計算機科学の世界では、構文解析は字句解析（Lexical Analysis）とともに、コンピュータ言語などの形式言語の解析に使用される。また、自然言語処理に応用されることもある。
構文解析を行う機構を構文解析器（Parser）と呼ぶ。
Parsing は本来、自然言語の文法で文の図式化を行うことを指す用語であり、ロマンス諸語やラテン語のような語形変化のある言語の文法の図式化を現在でも Parsing と呼ぶ。
形式言語
一般的に、プログラムにおける構文解析では、コンピュータ言語などの形式言語で記述された入力から、字句解析を通してトークン列を受け取り、構文木や抽象構文木のようなデータ構造を生成し、その後の処理に渡す。構文解析と同時に、目的の処理をおこなってしまう場合もある。
形式言語とオートマトンの対応は、良く理論付けられており、構文解析のアルゴリズムは、その入力である形式言語に対応するオートマトンの実装にほかならない。
プログラミング言語の場合、実用上、プログラムとして正しい入力のみを受け付けるような構文規則を定めることは現実的でない。そのため、一般に構文解析器は制約を弱めて本来の言語の文法よりも広い範囲の構文を受け付け（つまり、不正な構文も受け付ける）、後で不正なものを排除するようにすることが多い。
構文解析器を一から作るのではなく、パーサジェネレータで生成することも広く行われている。
処理概要
以下では、字句文法と構文文法という2段階の文法を持つコンピュータ言語の構文解析を例として説明する。
まず第一段階として字句（トークン）を生成する。これを字句解析と呼ぶ。入力文字列は正規表現による文法で定義された意味のあるシンボルに分割される。例えば、電卓プログラムに "12*(3+4)^2" と入力されたとき、これを 12, *, (, 3, +, 4, ), ^, 2 という字句（トークン）に分割する。各トークンは電卓プログラムの数式として意味のあるシンボルである。字句解析を含む構文解析器は *, +, ^, (, ) といった文字が新たなトークンの先頭になるという規則を持っているため、"12*" や "(3" といった無意味な字句の切り分けは発生しない。
次の段階で実際の構文解析を行う。構文解析では、トークンの並びが文法に照らして正しい表現となっているかを判定する。このため、文脈自由文法を参照して再帰的に規則を適用していく。ただし、プログラミング言語の構文規則は文脈自由文法だけでは表現できない。例えば、データ型が正しいか、識別子の宣言が正しいかなどは文脈自由文法の範囲外の話である。そのような規則は形式的には属性文法で表される。
最後に、意味的な解析が行われ、構文が確認された表現の意味を識別して、適当な行動をとる。電卓プログラムの場合、適当な行動とは式の評価（計算）であり、コンパイラならコードの生成である。属性文法もそのような行動決定に関与する。
手法
構文解析にはさまざまな手法が提案されており、それぞれの構文解析法に対して適用可能な文法の範囲が存在する。構文解析法は大まかに演算子順位法、トップダウン構文解析法、ボトムアップ構文解析法に分類でき、歴史的には、演算子順位法、トップダウン構文解析法は構文解析理論によって後から説明が加えられ、ボトムアップ構文解析法は理論主導で作成された。
演算子順位法とトップダウン構文解析法の手続きは人力で作成されることがコンパイラの初期の時代にはあった。特に、トップダウン構文解析法である再帰下降構文解析法はそのプログラムの実際のコードが文法の記述によく一致することが知られている。しかし、一般にボトムアップ構文解析は非常に多くの内部状態とその間の遷移規則を必要とし、その手続きを人力で作成するのは困難である。
現在は、主にボトムアップ構文解析法であるLALR(1)を使用した構文解析器がパーサジェネレータによって生成されることが多い。この手法を使用するパーサジェネレータにはyaccやbisonなどがあり、どちらも代表的なパーサジェネレータである。これらのパーサジェネレータがこの手法を採用する理由としては、適用可能な文法範囲が十分に大きく、効率もそこそこ悪くないことなどが挙げられる。その他に、トップダウン構文解析法であるLL法が使用・生成される場合もままある。
具体例
たとえば、インターネット上の Webページやメールアドレスをあらわす URL は、次のような構文をもっている:
- http://サーバ名/パス名（webページをあらわす場合, "http://www.yahoo.com/index.html"など）
- mailto:ユーザ名@ドメイン名（電子メールアドレスをあらわす場合, mailto:god@heaven.mil など）
Webブラウザに "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 ) )
構文解析の結果は構文木としても表すことができる。構文解析はコンパイラにおけるもっとも中心的な過程のひとつであり、その手法は従来からさまざまな研究がなされている。
一般に、形式言語の構文解析は曖昧でない言語を対象としている。ある言語が曖昧であるとは、ひとつの文にたいして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」という文が埋めこまれているとする解釈である。elseに対応するifがどちらかはっきりしないことからその名がある。
ふつうコンピュータの動作には厳密さが要求され、このように複数の解釈があることは許されないため、一般的にはエラーを出すか、elseは一番近いthenと結び付くように定めるなどして、文法の曖昧性を解消している。
自然言語
機械翻訳システムや自然言語処理システムでは、人間の言語（自然言語）をコンピュータプログラムで構文解析する。自然言語の文には構文上の曖昧さがあるため、それをプログラムで構文解析することは容易ではない。自然言語データを構文解析するには、まずその言語の文法を選択しなければならない。文法の選択は、言語学的考慮とコンピュータでの扱いやすさを考慮して行われる。例えば、いくつかの構文解析システムは語彙機能文法(LFG)を使用するが、一般にこの種の文法の構文解析はNP完全問題であることが知られている。他にも主辞駆動句構造文法(HPSG)もよく使われるが、最近ではより単純な形式文法の研究が盛んで、Penn Treebank などが挙げられる。シャロー（浅い）構文解析では、名詞句などの大まかな構文の境界だけを見つけ出す。また、言語学的議論を避けた手法としては依存文法による構文解析がある。
最近の構文解析では統計学的手法を部分的に取り入れている。すなわち、事前に構文解析済みのトレーニング用データ群を使う手法である。この場合、システムは特定の文脈でどのような構文が出現しやすいかという頻度情報を持つことになる（機械学習参照）。この手法では確率文脈自由文法(PCFG)を使うもの、最大エントロピー原理を使うもの、ニューラルネットワークを使うものがある。成果を上げているシステムでは、「字句」統計をとっていることが多い（すなわち、品詞も含めた単語の出現順の統計をとる）。しかし、この種のシステムは過剰適合の問題があり、効果を上げるにはある種の平滑化が必要となる。
自然言語の構文解析アルゴリズムは、プログラミング言語の人工的な文法のように「良い」特性を持つ文法に依存することはできない。上述のように文法によってはコンピュータが扱いにくい場合がある。一般にたとえ目的とする構造が文脈自由でなかったとしても、最初に文脈自由な近似を文法に施して構文解析を行うことがある。文脈自由文法を使ったアルゴリズムはCYK法に基づく場合が多く、時間を節約するためにそれに何らかのヒューリスティックを加えることが多い（チャートパーサなど）。最近では、構文解析器が複数の解析結果を返し、上位のシステムがそれらの中で最も良いと思われるものを選択する手法もある。
自然言語の曖昧さの例
構文解析の観点からみた形式言語と自然言語のちがいは、それが曖昧であるかないかということである。
プログラミング言語とは違って、自然言語は通常何十通りもの解釈が存在する。たとえば形態素解析の項で挙げた「うらにわにはにわとりがいる」のような例の他にも、次のような文:
には少なくとも2つの解釈が存在する。「水車小屋が美しい」場合と、「乙女が美しい」場合である。自然言語は本質的に曖昧であり、その解釈を決定するにはその文が書かれているまわりの文脈や、それを書いた人の心理までも考慮に入れなければならないこともある。
- ここでいう「曖昧」とは、文の意味を知るために、その文が置かれた状況、言い換えるとコンテキスト、フレーム情報などを考慮しなければ、同定できないということを指す。決して自然言語では曖昧な表現しかできないという意味ではないことに注意するように。
日本語の構文解析は、おもに文節間の係り受け構造を発見することである。たとえば、上の文が以下のような係り受け構造をもっている場合、「美しい」のは水車小屋ではなく乙女のほうであり、「水車小屋の美しい乙女」という言い換えも可能である。
いっぽう、もし文が以下のような係り受け構造をもっていたとすれば、この場合「美しい」のは水車小屋のほうである。
（ちなみに原文のドイツ語では「水車小屋の娘」が一語であるため、美しいのが乙女であるのは明らかである。）
