解析

構文解析と呼ばれる伝統的な文法作業では、テキストを構成要素である品詞に分解し、各部分の形式、機能、および統語関係を説明します。^{[ 3 ]}これは主に言語の活用と格変化の研究から決定され、屈折の多い言語では非常に複雑になることがあります。「man bites dog」のようなフレーズを解析するには、単数名詞「man」が文の主語であり、動詞「bites」が動詞「to bite」の現在形の三人称単数であり、単数名詞「dog」が文の目的語であることに注意する必要があります。文の要素間の関係を示すために、文図などの手法が使用されることがあります。

構文解析はかつて英語圏全体で文法教育の中心であり、書き言葉の使用と理解の基礎として広く認識されていた。

機械翻訳や自然言語処理システムの中には、人間の言語で書かれたテキストをコンピュータ プログラムが解析するものがあります。 ^{[ 4 ]}人間の文は、プログラムで簡単に解析できるものではありません。人間の言語の構造にはかなりの曖昧さがあり、その用途は潜在的に無限の可能性の中から意味（または意味論）を伝えることですが、特定のケースに関連するのはそのうちのいくつかだけです。 ^{[ 5 ]}したがって、「Man bites dog」と「Dog bites man」という発話は、ある点では明確ですが、別の言語では「Man dog bites」と表現され、その違いが問題となる場合、より大きな文脈に依存して両者を区別することになります。非公式な行動を記述するための正式な規則を作成するのは困難ですが、いくつかの規則が守られていることは明らかです。

自然言語データを解析するには、研究者はまず使用する文法について合意する必要があります。構文の選択は、言語学的および計算上の懸念の両方によって影響を受けます。たとえば、一部の構文解析システムは語彙機能文法を使用しますが、一般的に、この種の文法の構文解析はNP完全であることが知られています。ヘッド駆動句構造文法は、構文解析コミュニティで人気のあるもう1つの言語形式ですが、他の研究努力は、ペンツリーバンクで使用されているもののような、より単純な形式に焦点を当てています。浅い構文解析は、名詞句などの主要な構成要素の境界のみを見つけることを目的としています。言語論争を回避するためのもう1つの一般的な戦略は、依存文法構文解析です。

現代の構文解析器のほとんどは、少なくとも部分的には統計的である。つまり、すでに注釈が付けられた（手作業で解析された）訓練データのコーパスに依存している。このアプローチにより、システムはさまざまな構文が特定のコンテキストでどのくらいの頻度で出現するかについての情報を収集できる。（機械学習を参照。）使用されているアプローチには、単純なPCFG（確率的文脈自由文法）^{[ 6 ]} 、最大エントロピー^{[ 7 ]} 、ニューラルネットワーク^{[ 8 ]}などがある。より成功しているシステムのほとんどは、語彙統計を使用している（つまり、関連する単語の識別情報と品詞を考慮する）。しかし、このようなシステムは過学習を起こしやすく、効果を発揮するには何らかの平滑化が必要となる。

自然言語の構文解析アルゴリズムは、プログラミング言語の手動で設計された文法のように、「良い」特性を持つ文法に依存することはできません。前述のように、一部の文法形式は計算的に解析するのが非常に困難です。一般に、目的の構造が文脈自由でない場合でも、文法の何らかの文脈自由近似を使用して最初のパスを実行します。文脈自由文法を使用するアルゴリズムは、多くの場合、 CYK アルゴリズムの何らかのバリアントに依存しており、通常は時間を節約するために、ありそうもない分析を剪定する何らかのヒューリスティックが使用されています。 （チャート解析を参照。）ただし、一部のシステムは、たとえばシフト削減アルゴリズムの線形時間バージョンを使用して、速度と精度をトレードオフしています。比較的最近の開発として、構文解析リランキングがあり、これは、パーサーが多数の分析を提案し、より複雑なシステムが最良のオプションを選択します。自然言語理解アプリケーションでは、意味解析器がテキストをその意味の表現に変換します。^{[ 9 ]}

心理言語学において、構文解析とは、単に単語をカテゴリーに分類すること（存在論的洞察の形成）だけでなく、文中の各単語から推論される構文規則に従って文の意味を評価すること（含意と呼ばれる）も含まれます。これは通常、単語を聞いたり読んだりする際に起こります。

神経言語学では一般的に構文解析はワーキングメモリの機能であると理解されており、構文解析は1つの文の複数の部分を一度に心の中で保持し、必要に応じてすぐに分析できるようにするために使用される。人間のワーキングメモリには限界があるため、文の構文解析の機能にも限界がある。^{[ 10 ]}これは、文の心的構文解析における潜在的な問題を示す、構文的に複雑ないくつかの異なるタイプの文によって証明されている。

構文解析能力を試す最初の、そしておそらく最もよく知られているタイプの文は、ガーデンパス文です。これらの文は、最も一般的な解釈が文法的に誤りであるように見えるように設計されていますが、さらに詳しく調べると、これらの文は文法的に正しいことがわかります。ガーデンパス文は、複数の意味を持つ句や単語が含まれているため、構文解析が困難です。多くの場合、それらの最も一般的な意味は、別の品詞です。^{[ 11 ]}例えば、「the horse raced past the barn fell」という文では、raced は最初は過去形の動詞として解釈されますが、この文では形容詞句の一部として機能しています。^{[ 12 ]}構文解析は品詞を識別するために使用されるため、これらの文は読者の構文解析能力を試します。

解析が難しいもう 1 つのタイプの文は、付加曖昧性です。これは、文の異なる部分を修飾する可能性のある句を含み、したがって構文関係の特定に課題をもたらします (たとえば、「少年は望遠鏡を持った女性を見た」という文では、曖昧な句「望遠鏡を持った」が「少年は見た」または「女性」を修飾する可能性があります)。^{[ 11 ]}

構文解析能力を阻害する3つ目のタイプの文は、中心埋め込みです。これは、フレーズが他の同様の形式のフレーズの中心に配置されるものです（例：「男が叩いた猫を追いかけたネズミは罠に飛び込んだ」）。2つ、あるいは最も極端な場合には3つの中心埋め込みを持つ文は、構文関係の曖昧さのために、やはり精神的な構文解析を困難にします。^{[ 13 ]}

神経言語学には、脳内で構文解析がどのように行われるかを説明することを目的とした複数の理論が存在する。そのようなモデルの1つは、より伝統的な生成文処理モデルであり、脳内には文構文解析専用のモジュールがあり、その前に語彙認識と検索が行われ、その後、構文解析の単一の構文結果を考慮した構文処理が行われ、潜在的な問題が検出された場合にのみその構文解釈を修正するという理論である。^{[ 14 ]}反対の、より現代的なモデルでは、心の中では文の処理はモジュール化されておらず、厳密な順序で行われるわけではないと理論づけている。むしろ、語彙アクセス、構文処理、意味の決定が脳内で並行して行われるため、複数の異なる構文の可能性を同時に考慮できるとしている。このようにして、これらのプロセスは統合される。^{[ 15 ]}

構文解析の神経学についてはまだ解明されていない点が多いものの、いくつかの脳領域が構文解析に関与している可能性を示す証拠が研究によって示されている。これらの領域には、左前側頭極、左下前頭回、左上側頭回、左上前頭回、右後帯状皮質、左角回などが含まれる。完全に証明されたわけではないが、これらの異なる構造が句構造構文解析または依存構造構文解析のいずれかを優先する可能性があり、つまり、異なるタイプの構文解析がまだ解明されていない異なる方法で処理される可能性があると示唆されている。^{[ 16 ]}

談話分析は、言語使用や記号論的事象を分析する方法を研究する。説得力のある言語は修辞学と呼ばれることもある。

パーサーは、入力データ（通常はテキスト）を受け取り、データ構造（多くの場合、構文解析ツリー、抽象構文木、またはその他の階層構造）を構築して、入力の構造的表現を与え、正しい構文をチェックするソフトウェアコンポーネントです。構文解析は、他のステップの前後に実行される場合もあれば、単一のステップにまとめられる場合もあります。パーサーの前には、入力文字のシーケンスからトークンを作成する別の字句解析器が配置されることがよくあります。あるいは、スキャナレス構文解析ではこれらを組み合わせることもできます。パーサーは手動でプログラミングすることも、パーサージェネレータによって自動または半自動的に生成することもできます。構文解析は、フォーマットされた出力を生成するテンプレート化と相補的です。これらは異なるドメインに適用できますが、多くの場合、scanf / printf のペアや、コンパイラの入力（フロントエンド構文解析）と出力（バックエンドコード生成）ステージのように一緒に現れます。

パーサーへの入力は通常、何らかのコンピュータ言語のテキストですが、自然言語のテキストや構造化されていないテキストデータの場合もあります。後者の場合、一般的には構文木が構築されるのではなく、テキストの特定の部分のみが抽出されます。パーサーは、scanfのような非常に単純な関数から、 C++ コンパイラのフロントエンドやWeb ブラウザのHTMLパーサーのような複雑なプログラムまで多岐にわたります。単純な構文解析の重要なクラスは正規表現を使用して行われます。正規表現のグループが正規言語を定義し、正規表現エンジンがその言語のパーサーを自動的に生成することで、パターンマッチングとテキストの抽出が可能になります。他のコンテキストでは、正規表現は構文解析の前に字句解析ステップとして使用され、その出力がパーサーによって使用されます。

パーサーの使用方法は入力によって異なります。データ言語の場合、パーサーはプログラムのファイル読み込み機能としてよく使用され、HTMLやXMLテキストの読み込みなどに用いられます。これらはマークアップ言語の例です。プログラミング言語の場合、パーサーはコンパイラまたはインタプリタの構成要素であり、コンピュータプログラミング言語のソースコードを解析して何らかの内部表現を作成します。パーサーはコンパイラのフロントエンドにおける重要なステップです。プログラミング言語は、高速かつ効率的なパーサーを作成できるため、決定論的な文脈自由文法で規定される傾向があります。コンパイラの場合、解析自体は1回のパスまたは複数回のパスで実行できます（ 1パスコンパイラとマルチパスコンパイラを参照）。

1パスコンパイラの潜在的な欠点は、修正機能を追加することで大部分が克服できます。修正機能とは、順方向パス中にコードの再配置を考慮に入れ、現在のプログラムセグメントが完了したと認識された時点で逆方向パスに修正を適用する機能です。このような修正メカニズムが役立つ例としては、順方向GOTO文が挙げられます。この場合、GOTOのターゲットはプログラムセグメントが完了するまで不明です。修正の適用は、GOTOのターゲットが認識されるまで遅延されます。逆に、逆方向GOTOでは、位置が既にわかっているため、修正は必要ありません。

文脈自由文法は、言語のすべての要件を表現できる範囲が限られています。非公式に言えば、その理由は、そのような言語の記憶容量が限られているためです。文法は、任意の長さの入力にわたって構造の存在を記憶することができません。これは、例えば、名前が参照される前に宣言されなければならない言語では必要不可欠です。しかし、この制約を表現できるより強力な文法は、効率的に解析することができません。そのため、文脈自由文法に対して、望ましい言語構造のスーパーセットを受け入れる（つまり、一部の無効な構造を受け入れる）緩和されたパーサーを作成するのが一般的な戦略です。その後、意味解析（文脈解析）の段階で、不要な構造をフィルタリングすることができます。

例えば、Pythonでは以下のコードは構文的に有効です。

x : int = 1 print ( x )

しかし、以下のコードは文脈自由文法の観点からは構文的に有効であり、前のコードと同じ構造の構文木を生成しますが、変数を使用する前に初期化する必要があるという意味規則に違反しています。

x : int = 1 print ( y )

以下の例は、語彙レベルと構文レベルの2つの文法レベルを持つコンピュータ言語の構文解析という一般的なケースを示しています。

最初の段階はトークン生成、つまり字句解析です。この段階では、入力された文字ストリームが正規表現の文法によって定義された意味のある記号に分割されます。たとえば、電卓プログラムは「12 * (3 + 4)^2」のような入力を見て、それをトークン12、*、(、3、+、4、)、に分割します^。これらのトークンはそれぞれ算術式の文脈において意味のある記号です。字句解析器には、文字、、、が新しいトークンの開始を示す2ことを示すルールが含まれているため、「 」や「 」のような意味のないトークンは生成されません。*+^()12*(3

次の段階は構文解析、つまりトークンが許容される式を形成しているかどうかのチェックです。これは通常、式を構成する要素とその出現順序を再帰的に定義する文脈自由文法を参照して行われます。しかし、プログラミング言語を定義するすべての規則が文脈自由文法だけで表現できるわけではありません。例えば、型の妥当性や識別子の適切な宣言などが挙げられます。これらの規則は属性文法を用いて形式的に表現できます。

最終段階は意味解析または分析であり、これは検証された式の意味を解明し、適切なアクションを実行することです。^{[ 17 ]}電卓やインタプリタの場合、アクションは式またはプログラムを評価することです。一方、コンパイラは何らかのコードを生成します。属性文法を使用してこれらのアクションを定義することもできます。

単純なパーサーの実装では、入力ファイル全体を読み込み、中間的な計算または変換を実行し、出力ファイル全体を書き込みます。これは、インメモリマルチパスコンパイラなどです。

代替のパーサー実装アプローチ：

• プッシュパーサーは、入力ストリーム内で関連するトークンを検出するとすぐに、登録済みのハンドラー（コールバック）を呼び出します。プッシュパーサーは、無関係な入力部分をスキップする場合があります（Expatはその一例です）。
• 入力テキストを「プル」することでコンパイラのフロントエンドなどで一般的に使用されるパーサーなど、プルパーサー。
• インクリメンタルパーサー（インクリメンタルチャートパーサーなど）は、ユーザーがファイルのテキストを編集しても、ファイル全体を完全に再解析する必要がありません。
• アクティブパーサーとパッシブパーサー^{[ 26 ] [ 27 ]}