構文解析
最近の構文解析では統計学的手法を部分的に取り入れている。すなわち、事前に構文解析済みのトレーニング用データ群を使う手法である。この場合、システムは特定の文脈でどのような構文が出現しやすいかという頻度情報を持つことになる(機械学習参照)。この手法では確率文脈自由文法(PCFG)を使うもの、最大エントロピー原理を使うもの、ニューラルネットワークを使うものがある。成果を上げているシステムでは、「字句」統計をとっていることが多い(すなわち、品詞も含めた単語の出現順の統計をとる)。しかし、この種のシステムは過剰適合の問題があり、効果を上げるにはある種の平滑化が必要となる。
自然言語の構文解析アルゴリズムは、形式言語のように「良い」特性を持つ文法に依存することはできない。上述のように文法によってはコンピュータが扱いにくい場合がある。一般にたとえ目的とする構造が文脈自由でなかったとしても、最初に文脈自由な近似を文法に施して構文解析を行うことがある。文脈自由文法を使ったアルゴリズムはCYK法に基づく場合が多く、時間を節約するためにそれに何らかのヒューリスティックを加えることが多い(チャートパーサなど)。最近では、構文解析器が複数の解析結果を返し、上位のシステムがそれらの中で最も良いと思われるものを選択する手法もある。
機械翻訳などの自然言語処理などで構文解析の対象となる自然言語の場合も、ごく基本的には前の節までで述べた形式言語の場合と同様である。しかし、自然言語の構文にはアドホックな変形などが多いという複雑さや、多くの言語では曖昧さもあり、さらには意味を考えなければ構文が決定できないこともあるなど、独特の難しさがある。また、プログラミング言語などの場合の字句解析に相当するのは形態素解析である。
形式言語の場合はもっぱら文脈自由文法ベースの手法で構文解析されるが、自然言語の場合は前述の難しさなどの理由から、言語学的に見た目的やコンピュータでの扱いやすさなどを考慮し、さまざまな文法や手法を検討する必要がある。
例えば、いくつかの構文解析システムは語彙機能文法(LFG)を使用するが、一般にこの種の文法の構文解析はNP完全問題であることが知られている。他にも主辞駆動句構造文法(HPSG)もよく使われるが、最近ではより単純な形式文法の研究が盛んで、Penn Treebank などが挙げられる。シャロー(浅い)構文解析では、名詞句などの大まかな構文の境界だけを見つけ出す。句構造文法ベースではなく依存文法や格文法などを検討することもある。一方でかな漢字変換など、即座に結果が得られればそれで良いものなどは、「教科書的な橋本文法」(いわゆる学校文法)に橋本文法の連文節の概念など、実用上の改造を加えたようなものが使われていることもある。