構文解析
構文解析︵こうぶんかいせき、英語: parsing, syntactic analysis, syntactic analysis︶は、ある言語において、その形式文法に従って記号の文字列を分析する手続きである。構文解析を行う機構を構文解析器︵parser︶と呼ぶ。
一般に、形式言語の構文解析は曖昧でない言語を対象としている。ある言語が曖昧であるとは、ひとつの文にたいして2通り以上の構文解析が可能であることをいう。プログラミング言語でよく知られている例に﹁宙ぶらりんelse問題︵dangling else problem︶﹂がある。たとえば以下のような文脈自由文法であらわされる言語を考える:
●いっぽう、もし文が以下のような係り受け構造をもっていたとすれば、この場合﹁美しい﹂のは水車小屋のほうである。
さらには、
Colorless green ideas sleep furiously.
のように、構文的には何の問題も無いが、意味を解するのが困難な文、といったものもある。
概要[編集]
文章︵具体的にはマークアップなどの注記の入っていないベタの文字列︶を対象として、 ●自然言語であれば、形態素に切分け、さらにその間の関連︵修飾-被修飾など︶といったような、統語論的関係を図式化するなどして明確化・解析する手続きである。 ●プログラミング言語など形式言語の場合は、形式文法に従い構文木を得る手続きである。形式言語[編集]
プログラミング言語の場合は一般にその性質から、文字列︵ソースコード︶から字句︵トークン︶の列を取り出す前処理段階である字句解析︵lexical analysis︶と、そのトークン列を受け取り構文木を作るなどする後処理段階の2段階に分けてその全体を広義の構文解析とし、特に後処理のみを指して狭義の構文解析とすることが多い︵PEGのように融合して扱う場合も多い手法もある︶。以下、その狭義の構文解析について述べる。 構文解析では、構文木や抽象構文木のようなデータ構造を生成し、プログラミング言語のコンパイラであれば、いわゆるコンパイラバックエンドに渡す。サンプルなどによく見られる四則演算の式の演算などのような簡単な場合は、構文解析と同時に、目的の処理をおこなってしまう場合もある。 形式言語とオートマトンの対応は、良く理論付けられており、構文解析のアルゴリズムは、その入力である形式言語に対応するオートマトンの実装にほかならない。 プログラミング言語の場合、実用上、プログラムとして正しい入力のみを受け付けるような構文規則を定めることは現実的でない[1]。そのため、一般に構文規則では言語本来より制約を弱くし︵つまり、本来の言語の文法よりも広く、不正な入力も受け付けるようにし︶後で不正なものを排除するようにすることが多い。 構文解析器を一から作るのではなく、パーサジェネレータで生成することも広く行われている。処理概要[編集]
一般的なプログラミング言語処理系や、簡単なサンプルによくあるいわゆる﹁電卓プログラム﹂などの場合を例として説明する。 まず第一段階として字句︵トークン︶を生成する。これを字句解析と呼ぶ。入力文字列は正規表現などによる定義に従い、意味のあるシンボルに分割される。例えば、電卓プログラムに "12*(3+4)^2" と入力されたとき、これを 12, *, (, 3, +, 4, ), ^, 2 という字句︵トークン︶に分割する。各トークンは電卓プログラムの数式として意味のあるシンボルである。字句解析を含む構文解析器は *, +, ^, (, ) といった文字が新たなトークンの先頭になるという規則を持っているため、"12*" や "(3" といった無意味な字句の切り分けは発生しない。 次の段階は狭義の構文解析である。トークンの並びが構文規則に照らして正しい表現となっているかを判定する。このため、構文規則を参照して再帰的に規則を適用していく。前述したように、構文規則で表現するのは現実的ではない言語上のルール、たとえば関数定義における仮引数名の重複などがあるので、そういったものへの対処も適宜実装する。 以上のように構文解析が終わった後に、意味的な解析が行われ、構文が確認された表現の意味を識別して、適当な行動をとる。電卓プログラムの場合、適当な行動とは式の評価︵計算︶であり、コンパイラならコードの生成である。 yaccなどでは属性文法的な考え方を活用し、トークン列に対するシフトや還元という解析の動作に対して実行すべきコード片を結び付け、それらのコード片により以上で説明したような処理を行う。手法[編集]
構文解析にはさまざまな手法が提案されており、それぞれの構文解析法に対して適用可能な文法の範囲が存在する。歴史的に、もっぱらプログラミング言語を対象に研究が進んだが、大まかに演算子順位法、トップダウン構文解析法、ボトムアップ構文解析法に分類できる。演算子順位法、トップダウン構文解析法は構文解析理論によって後から説明が加えられ、ボトムアップ構文解析法は理論主導で作成された。 演算子順位法とトップダウン構文解析法の手続きは人力で作成されることがコンパイラの初期の時代にはあった。特に、トップダウン構文解析法である再帰下降構文解析法はそのプログラムの実際のコードが文法の記述によく一致することが知られている。しかし、一般にボトムアップ構文解析は非常に多くの内部状態とその間の遷移規則を必要とし、その手続きを人力で作成するのは困難である。 現在は、主にボトムアップ構文解析法である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" を読みとらなければならない。これは構文解析の非常に簡単な例である。一般に、形式言語の構文解析は曖昧でない言語を対象としている。ある言語が曖昧であるとは、ひとつの文にたいして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と結び付くと定めて曖昧さを解消するか、エラーとする。
自然言語[編集]
機械翻訳などの自然言語処理などで構文解析の対象となる自然言語の場合も、ごく基本的には前の節までで述べた形式言語の場合と同様である。しかし、自然言語の構文にはアドホックな変形などが多いという複雑さや、多くの言語では曖昧さもあり、さらには意味を考えなければ構文が決定できないこともあるなど、独特の難しさがある。また、プログラミング言語などの場合の字句解析に相当するのは形態素解析である。 形式言語の場合はもっぱら文脈自由文法ベース[2]の手法で構文解析されるが、自然言語の場合は前述の難しさなどの理由から、言語学的に見た目的やコンピュータでの扱いやすさなどを考慮し、さまざまな文法や手法を検討する必要がある。 例えば、いくつかの構文解析システムは語彙機能文法(LFG)を使用するが、一般にこの種の文法の構文解析はNP完全問題であることが知られている。他にも主辞駆動句構造文法(HPSG)もよく使われるが、最近ではより単純な形式文法の研究が盛んで、Penn Treebank などが挙げられる。シャロー︵浅い︶構文解析では、名詞句などの大まかな構文の境界だけを見つけ出す。句構造文法ベースではなく依存文法や格文法などを検討することもある。一方でかな漢字変換など、即座に結果が得られればそれで良いものなどは、﹁教科書的な橋本文法﹂︵いわゆる学校文法︶に橋本文法の連文節の概念など、実用上の改造を加えたようなものが使われていることもある。 最近の構文解析では統計学的手法を部分的に取り入れている。すなわち、事前に構文解析済みのトレーニング用データ群を使う手法である。この場合、システムは特定の文脈でどのような構文が出現しやすいかという頻度情報を持つことになる︵機械学習参照︶。この手法では確率文脈自由文法(PCFG)を使うもの、最大エントロピー原理を使うもの、ニューラルネットワークを使うものがある。成果を上げているシステムでは、﹁字句﹂統計をとっていることが多い︵すなわち、品詞も含めた単語の出現順の統計をとる︶。しかし、この種のシステムは過剰適合の問題があり、効果を上げるにはある種の平滑化が必要となる。 自然言語の構文解析アルゴリズムは、形式言語のように﹁良い﹂特性を持つ文法に依存することはできない。上述のように文法によってはコンピュータが扱いにくい場合がある。一般にたとえ目的とする構造が文脈自由でなかったとしても、最初に文脈自由な近似を文法に施して構文解析を行うことがある。文脈自由文法を使ったアルゴリズムはCYK法に基づく場合が多く、時間を節約するためにそれに何らかのヒューリスティックを加えることが多い︵チャートパーサなど︶。最近では、構文解析器が複数の解析結果を返し、上位のシステムがそれらの中で最も良いと思われるものを選択する手法もある。自然言語の曖昧性の例[編集]
自然言語の文法からは、場合によっては何通りもの解釈が可能な文も存在する。たとえば形態素解析の記事にある﹁うらにわにはにわとりがいる﹂のような例の他にも、次のような文: 美しい 水車小屋の 乙女 には少なくとも2つの解釈が存在する。﹁水車小屋が美しい﹂場合と、﹁乙女が美しい﹂場合である。この場合には、意味を含めても正しい解釈がどちらであるか不明であり、その文が置かれた前後の状況、言い換えるとコンテキスト、フレーム情報などを考慮しなければ同定できない。 日本語の構文解析は、おもに文節間の係り受け構造を発見することである。 ●たとえば、上の文が以下のような係り受け構造をもっている場合、﹁美しい﹂のは水車小屋ではなく乙女のほうであり、﹁水車小屋の美しい乙女﹂という言い換えも可能である︵ちなみに原文のドイツ語では﹁水車小屋の娘﹂が一語であるため、美しいのが乙女であるのは明らかである︶。
●いっぽう、もし文が以下のような係り受け構造をもっていたとすれば、この場合﹁美しい﹂のは水車小屋のほうである。
さらには、
Colorless green ideas sleep furiously.
のように、構文的には何の問題も無いが、意味を解するのが困難な文、といったものもある。
