こうぶん‐かいせき【構文解析】
構文解析
【英】parsing
構文解析とは、単語や字句で構成される文を、定義された文法に従って解釈し、文の構造を明確にすることである。
プログラムのソースコードをコンピュータが理解できるようにコンパイルする際は、まず字句解析により、ソースコードをトークンと呼ばれる要素に切り出した後に、構文規則に基づいて構文解析が行われる。構文解析の手法には、上向き解析と下向き解析があり、演算子順位解析は上向き構文解析、LL解析は下向き構文解析である。
英語を日本語に変換する機械翻訳の分野では、英語の構文解析を行い、構文木で解析結果を表現した後に日本語の構文木に変換し、日本語訳を作り出す。
構文解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/31 02:13 UTC 版)
構文解析（こうぶんかいせき、英語: parsing, syntactic analysis, syntactic analysis）は、ある言語において、その形式文法に従って記号の文字列を分析する手続きである。構文解析を行う機構を構文解析器（parser）と呼ぶ。
概要
文章（具体的にはマークアップなどの注記の入っていないベタの文字列）を対象として、
- 自然言語であれば、形態素に切分け、さらにその間の関連（修飾-被修飾など）といったような、統語論的関係を図式化するなどして明確化・解析する手続きである。
- プログラミング言語など形式言語の場合は、形式文法に従い構文木を得る手続きである。
形式言語
プログラミング言語の場合は一般にその性質から、文字列（ソースコード）から字句（トークン）の列を取り出す前処理段階である字句解析（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つの解釈が存在する。「水車小屋が美しい」場合と、「乙女が美しい」場合である。この場合には、意味を含めても正しい解釈がどちらであるか不明であり、その文が置かれた前後の状況、言い換えるとコンテキスト、フレーム情報などを考慮しなければ同定できない。
さらには、
のように、構文的には何の問題も無いが、意味を解するのが困難な文、といったものもある。
日本語の構文解析は、おもに文節間の係り受け構造を発見することである。たとえば、上の文が以下のような係り受け構造をもっている場合、「美しい」のは水車小屋ではなく乙女のほうであり、「水車小屋の美しい乙女」という言い換えも可能である。
いっぽう、もし文が以下のような係り受け構造をもっていたとすれば、この場合「美しい」のは水車小屋のほうである。
（ちなみに原文のドイツ語では「水車小屋の娘」が一語であるため、美しいのが乙女であるのは明らかである。）
フリーで入手可能なもの
- KNP、http://nlp.ist.i.kyoto-u.ac.jp/index.php?KNP
- CaboCha、http://taku910.github.io/cabocha/
- GiNZA、https://megagonlabs.github.io/ginza/
注
構文解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/29 07:08 UTC 版)
S式はよくXMLと比較されるが、主な違いは、S式には点.によるペアという1つの包含形式しかないのに対し、XMLのタグには単純な属性、他のタグ、en:CDATAが含まれ、それぞれ異なる構文を使用できる。単純な用途では、S式はXMLよりもシンプルだが、より高度な用度になると、XMLにはXPathと呼ばれるクエリ言語があり、XMLデータの取り扱いを簡単にする多くのツールやサードパーティのライブラリがある。
※この「構文解析」の解説は、「S式」の解説の一部です。
「構文解析」を含む「S式」の記事については、「S式」の概要を参照ください。
構文解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/03 07:59 UTC 版)
「トップダウン設計とボトムアップ設計」の記事における「構文解析」の解説
詳細は「トップダウン構文解析」および「ボトムアップ構文解析」を参照 構文解析におけるトップダウンとボトムアップという用語、ないしはトップダウン構文解析とボトムアップ構文解析は、設計戦略でもなければ、情報や知識の順序付け戦略でもない。そもそもソフトウェア工学での用語や用法とは全く関係なく、また「組織における意見流通の用語が原義で、行政学や経営学、特に経営学での意思決定論で、日米企業比較の主要な焦点という非常に重要な事項」など（当記事のノートを参照）とも無関係な、単に普通の英語の表現である「トップダウン」と「ボトムアップ」からの用語・用法である。すなわちこの記事の冒頭の定義がまともなものとするならば、この節はこの記事に書かれるべきではない。 句構造文法（生成文法）以外にも形式言語の文法の捉え方にはいくつかあるが、ここではそれらに議論を限定し、そのうちでも特にBNFで定義されている文脈自由文法のことを考える。BNFにおいて各ルールの左側の非終端記号を以下では「左辺の非終端記号」、右側の記号列を「右辺の記号列」と呼ぶ。 トップレベルの左辺の非終端記号（プログラミング言語の場合は〈プログラム〉、一般の言語では〈文〉などといった名前の非終端記号であることが多い）から右辺の記号列への展開の操作を繰り返し、最終的に入力と一致する終端記号の列が得られるならば解析成功とするのがトップダウン構文解析であり、入力の終端記号の列から始めて右辺の記号列から左辺の非終端記号への還元の操作を繰り返し、最終的にトップレベルの左辺の非終端記号が得られるならば解析成功とするのがボトムアップ構文解析である。
※この「構文解析」の解説は、「トップダウン設計とボトムアップ設計」の解説の一部です。
「構文解析」を含む「トップダウン設計とボトムアップ設計」の記事については、「トップダウン設計とボトムアップ設計」の概要を参照ください。
構文解析
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/14 17:00 UTC 版)
ピーター・ノーヴィグは1991年、構文解析戦略にメモ化を応用し、単純なバックトラッキング式の再帰下降構文解析に自動メモ化を適用することでアーリー法のようなアルゴリズムになることを示した。1995年には Johnson と Dörre も構文解析でのメモ化の応用を提案した。2002年、Ford はこれのパックラット構文解析への応用をかなり詳細に論じた。 ノーヴィグは構文解析器をメモ化によって強化したが、時間計算量はアーリー法と同じであった。つまりこれは、速度的性能の最適化以外にメモ化を応用した例である。Johnson と Dörre も同様に時間短縮以外の応用を示した。それは、言語的制約の解決を必要な情報が構文解析によって十分集まった時点にまで遅延されることにメモ化を利用するものだった。一方、Ford は時間的性能の最適化にメモ化を応用し、パックラット構文解析が最悪ケースのバックトラッキングが必要な形式言語でも線形時間で構文解析できることを示した。 次のような形式文法を考えてみよう。 S → (A c) | (B d) A → X (a|b) B → X b X → x [X] ここで、生成規則 S → (A c) | (B d) の意味は、「S は、A の後に1つの c が続くか、あるいは B の後に1つの d が続くかのどちらかである」となる。また、生成規則 X → x [X] の意味は、「X は、1つの x の後にオプションの X が続く」となる。 この文法が生成する文字列は、xac、xbc、xbd（なお、x は1つ以上の x の連続となりうる）のいずれかである。次にこの文法から構文解析の仕様をトップダウンでかつ左から右に解析するものとしたとき、文字列 xxxxxbd の解析がどうなるかを考える。 トップダウンであるから、まず全体が S に置換可能であるとの前提で、S の規則から、まず全体が (A c) であると仮定する。最後の文字がここで既に違っていることは明らかだが、左から右に構文解析するので、構文解析器にはまだ最後の文字が見えていない。次に A の生成規則を見て、さらに X の生成規則を見ていく。ここで初めて先頭の文字が一致する。そして、x が続いている間は X の規則を再帰的に適用し、次の文字 b も A の規則に一致するが、その次の d と c が一致しない。ここでバックトラックが発生し、S のもう一方の選択肢である B の規則を適用し、同様に X を必要な回数適用して、最終的に最後の文字まで一致する。以上によりこの文字列は、この文法で認識される。 ここで重要となるのは、以上の説明の中で X の繰り返し適用が2回出現することである。このように処理を進めていって失敗し、元に戻って別の選択肢に移って処理を再開することをバックトラッキングと呼ぶ。そして、構文解析におけるバックトラッキングにメモ化を応用する余地があることがわかる。ここで、関数 RuleAcceptsSomeInput(Rule, Position, Input) を考える。引数の意味は次の通りである。 Rule は、検討中の生成規則の名前 Position は、現在検討中の入力上のオフセット位置 Input は、検討中の入力 関数 RuleAcceptsSomeInput のリターン値は Rule が受理した入力の長さとする。その生成規則が指定されたオフセット位置の入力文字を受理しなかった場合は 0 を返す。バックトラッキングとメモ化を使う場合、構文解析は次のようになる。 オフセット 0 で、生成規則 A から生成規則 X へと下降していき、そこでその位置と生成規則 X について長さ 5 をメモ化（記録）する。d の位置で生成規則の適用に失敗すると、生成規則 B が選ばれ、再び X を適用するのではなく、メモ化エンジンに対して位置 0 と生成規則 X についての記録があるかを訊ねる。メモ化エンジンは長さ 5 が記録されているのでそれを返す。これにより実際に X を適用することなく処理を省略でき、前回と同じぶんだけ X を適用したのと同じ効果を得る。 この例では、X は再帰的に何度でも適用可能であるため、xxxxxxxxxxxxxxxxbd のような文字列もありうる。従って S を始点として X まで下降して再帰的に生成規則の適用を繰り返すが、バックトラックして B に移行した後は RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) のリターン値が 16 であることが分かっている（メモ化済みである）ので、実際に X を適用する必要がない。 統語的述語（syntactic predicate）を使った構文解析器でも、述語の構文解析結果をメモ化できる。例えば次のような構文規則があるとする。 S → (A)? A A → /* 何らかの規則 */ これは、入力の先頭で A で受理できるなら A で受理することを表している。述語部分 (A)? の結果をメモ化しておけば、実際の生成規則適用時は省略できる。 構文解析時に構文木を構築する場合、メモ化ではマッチした入力の長さだけでなく、その位置と生成規則によって生成された部分木も記憶しておく必要がある。同様に、生成規則がマッチしたときに外部のコードを呼び出す方式の構文解析器の場合、その呼び出し順序が本来期待されている順序になるよう注意してメモ化する必要がある。 全ての文法でバックトラッキングや統語的述語が必要となるわけではないので、個々の生成規則について結果を記憶しておくことで構文解析の性能が低下する可能性がある。これは、メモ化する生成規則を明示的に選択することで問題を限定することができる。
※この「構文解析」の解説は、「メモ化」の解説の一部です。
「構文解析」を含む「メモ化」の記事については、「メモ化」の概要を参照ください。
「構文解析」の例文・使い方・用例・文例
構文解析と同じ種類の言葉
- 構文解析のページへのリンク
