構文解析

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

構文解析構文解析、または構文解析は、形式文法の規則に従って、自然言語コンピューター言語、またはデータ構造のいずれかで一連記号を分析するプロセスです構文解析という用語は、 品詞)を意味するラテン語の構文解析orationis )に由来します。[1]

この用語は、言語学コンピュータサイエンスのさまざまな分野でわずかに異なる意味を持っています。従来の文の構文解析は、文または単語の正確な意味を理解する方法として、場合によっては文の図などのデバイスを使用して実行されることがよくあります通常、主語述語などの文法的な区分の重要性を強調します。

計算言語学では、この用語は、コンピューターによる文またはその他の単語の文字列の構成要素への正式な分析を指すために使用されます。その結果、相互の構文関係を示す解析ツリーが生成されます。これには、意味情報やその他の情報も含まれる場合があります(p値)。[要出典]一部の解析アルゴリズムは、構文的にあいまいな入力に対して解析フォレストまたは解析ツリーのリストを生成する場合があります。[2]

この用語は、言語理解を説明するときに心理言語学でも使用されます。この文脈では、構文解析とは、人間が文または句を(口頭言語またはテキストで)「文法的構成要素、品詞、構文関係などの観点から」分析する方法を指します。[1]この用語は、話者が庭の小道の文 を解釈するのにどの言語的手がかりが役立つかを議論するときに特に一般的です。

コンピュータサイエンスでは、この用語はコンピュータ言語の分析で使用され、コンパイラインタプリタの記述を容易にするために、入力コードをそのコンポーネント部分に構文解析することを指しますこの用語は、分割または分離を説明するために使用することもできます。

人間の言語

従来の方法

構文解析の従来の文法的な演習は、句分析とも呼ばれ、テキストを品詞の形式、機能、および構文上の関係の説明とともに品詞に分解することを含みます。[3]これは主に、言語の活用曲用の研究から決定されます。これは、大きく変化する言語では非常に複雑になる可能性があります。「manbitesdog」などの句を解析するには、単数名詞「man」が文の主語であり、動詞「bites」が現在形の三人称単数であることに注意する必要があります。動詞の「噛む」、単数名詞の「犬」が文の目的語です。文の要素間の関係を示すために 、文の図などの手法が使用されることがあります。

構文解析は、以前は英語圏全体で文法教育の中心であり、書記言語の使用と理解の基本と広く見なされていました。しかし、そのような技術の一般的な教えはもはや最新ではありません。[要出典]

計算方法

一部の機械翻訳および自然言語処理システムでは、人間の言語で書かれたテキストはコンピュータープログラムによって解析されます。[4]人間の文は、プログラムによって簡単に解析されません。人間の言語の構造にはかなりのあいまいさがあり、その使用法は、潜在的に無制限の範囲の可能性の中で意味(または意味論)を伝えることですが、その一部だけが具体的事例。[5]したがって、「人が犬を噛む」と「犬を噛む」という発話は、ある詳細では明確ですが、別の言語では、これら2つの可能性を区別するために、より大きなコンテキストに依存する「人が犬を噛む」と表示される場合があります。気がかりな。いくつかの規則が守られていることは明らかですが、非公式な行動を説明するための正式な規則を準備することは困難です。[要出典]

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

最新のパーサーのほとんどは、少なくとも部分的に統計的です。つまり、すでに注釈が付けられている(手動で解析された)トレーニングデータのコーパスに依存しています。このアプローチにより、システムは、特定のコンテキストでさまざまな構造が発生する頻度に関する情報を収集できます。機械学習を参照してください。)使用されてきたアプローチには、単純なPCFG(確率的文脈自由文法)、[6] 最大エントロピー[7]およびニューラルネットが含まれます。[8]より成功したシステムのほとんどは字句を使用します統計(つまり、関連する単語のIDと、品詞を考慮します)。ただし、このようなシステムは過剰適合に対して脆弱であり、効果を発揮するには何らかの平滑化が必要です。[要出典]

自然言語の構文解析アルゴリズムは、プログラミング言語用に手動で設計された文法のように、「優れた」プロパティを持つ文法に依存することはできません。先に述べたように、いくつかの文法形式は計算で解析するのが非常に困難です。一般に、目的の構造が文脈自由でない場合でも、文法に対するある種の文脈自由近似を使用して最初のパスを実行します。文脈自由文法を使用するアルゴリズムは、多くの場合、 CYKアルゴリズムのいくつかの変形に依存します。通常、時間を節約するために、ありそうもない分析を取り除くためのヒューリスティックがあります。チャートの解析を参照してください。)ただし、一部のシステムでは、たとえば、shift-reduceの線形時間バージョンを使用して速度と精度を交換します。アルゴリズム。やや最近の開発は、パーサーがいくつかの多数の分析を提案し、より複雑なシステムが最良のオプションを選択する解析再ランク付けです。[要出典] セマンティックパーサーは、テキストをその意味の表現に変換します。[9]

心理言語学

心理言語学では、構文解析には、カテゴリへの単語の割り当て(オントロジーの洞察の形成)だけでなく、文の各単語から作成された推論によって描かれた構文規則に従った文の意味の評価(含意として知られています)が含まれますこれは通常、単語が聞こえたり読んだりしているときに発生します。その結果、構文解析の心理言語学的モデルは必然的にインクリメンタルになります。つまり、文が処理されるときに解釈が構築されます。これは通常、部分的な構文構造で表されます。ガーデンパス文を解釈するときに、最初は間違った構造が作成されます。

談話分析

談話分析は、言語の使用と記号論的イベントを分析する方法を調べます。説得力のある言葉はレトリックと呼ばれることがあります。

コンピュータ言語

パーサー

パーサーは、入力データ(多くの場合テキスト)を取得してデータ構造を構築するソフトウェアコンポーネントです。多くの場合、ある種の解析ツリー抽象構文ツリー、またはその他の階層構造で、正しい構文をチェックしながら入力の構造表現を提供します。解析は、他のステップの前または後に行うことができます。あるいは、これらを組み合わせて1つのステップにすることもできます。多くの場合、パーサーの前には、入力文字のシーケンスからトークンを作成する別の字句アナライザーがあります。あるいは、これらをスキャナーレス解析で組み合わせることができますパーサーは手動でプログラムすることも、パーサージェネレーターによって自動または半自動で生成することもできます。解析は、フォーマットされた出力を生成するテンプレートを補完します。これらは異なるドメインに適用できますが、scanf / printfペア、またはコンパイラの入力(フロントエンド解析)ステージと出力(バックエンドコード生成)ステージなど、一緒に表示されることがよくあります。

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

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

ワンパスコンパイラの暗黙の欠点は、修正を追加することで大幅に克服できます。修正は、フォワードパス中にコードの再配置が行われ、現在のプログラムセグメントが認識されたときに修正が逆方向に適用されます。完了しました。このような修正メカニズムが役立つ例は、プログラムセグメントが完了するまでGOTOのターゲットが不明なフォワードGOTOステートメントです。この場合、修正の適用は、GOTOのターゲットが認識されるまで延期されます。逆に、後方GOTOは、場所がすでにわかっているため、修正は必要ありません。

文脈自由文法は、言語のすべての要件を表現できる範囲に制限があります。非公式に、その理由はそのような言語の記憶が限られているということです。文法は、任意の長さの入力に対する構成の存在を思い出せません。これは、たとえば、名前を参照する前に名前を宣言する必要がある言語で必要です。ただし、この制約を表現できるより強力な文法は、効率的に解析できません。したがって、目的の言語構造のスーパーセットを受け入れる(つまり、いくつかの無効な構造を受け入れる)文脈自由文法用のリラックスしたパーサーを作成するのが一般的な戦略です。後で、不要な構成は、セマンティック分析(コンテキスト分析)ステップ でフィルターで除外できます。

たとえば、Pythonでは、構文的に有効なコードは次のとおりです。

x  =  1
印刷x 

ただし、次のコードは、文脈自由文法の観点から構文的に有効であり、前と同じ構造の構文ツリーを生成しますが、使用前に変数を初期化する必要があるセマンティックルールに違反します。

x  =  1
印刷y 

プロセスの概要

典型的なパーサーでのデータの流れ

次の例は、2つのレベルの文法(字句と構文)を使用してコンピューター言語を構文解析する一般的なケースを示しています。

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

次の段階は、トークンが許容可能な式を形成していることを確認する構文解析または構文解析です。これは通常、式を構成できるコンポーネントとそれらが表示される順序を再帰的に定義する文脈自由文法を参照して行われます。ただし、プログラミング言語を定義するすべてのルールが、型の妥当性や識別子の適切な宣言など、文脈自由文法だけで表現できるわけではありません。これらのルールは、属性文法を使用して正式に表現できます

最後のフェーズは、セマンティック解析または分析です。これは、検証されたばかりの式の影響を解明し、適切なアクションを実行します。[10]電卓またはインタプリタの場合、アクションは式またはプログラムを評価することです。一方、コンパイラはある種のコードを生成します。属性文法を使用して、これらのアクションを定義することもできます。

パーサーの種類

パーサーのタスクは、基本的に、文法の開始記号から入力を導出できるかどうか、およびどのように導出できるかを判別することです。これは、基本的に2つの方法で実行できます。

LLパーサー再帰下降パーサーは、左再帰 生成ルールに 対応できないトップダウンパーサーの例ですトップダウン構文解析の単純な実装では、直接および間接の左再帰に対応できず、あいまいな文脈自由文法を解析する際に指数関数的な時間とスペースの複雑さが必要になる可能性があると考えられていましたが、トップダウン構文解析のより高度なアルゴリズムがFrostによって作成されました。 、Hafiz、およびCallaghan [13] [14]は、あいまいさ左再帰に対応します。多項式時間で、潜在的に指数関数的な数の解析ツリーの多項式サイズの表現を生成します。彼らのアルゴリズムは、与えられた文脈自由文法に関して、入力の左端と右端の両方の派生を生成することができます

パーサーに関する重要な違いは、パーサーが左端の派生を生成するか、右端の派生を生成するかです(文脈自由文法を参照)。LLパーサーは左端の派生を生成し、LRパーサーは右端の派生を生成します(通常は逆ですが)。[11]

いくつかグラフィカル解析アルゴリズムは、ビジュアルプログラミング言語[15] [16]視覚言語のパーサーは、グラフ文法に基づいている場合があります。[17]

適応型解析アルゴリズムは、「自己拡張型」の自然言語ユーザーインターフェイスを構築するために使用されてきました。[18]

実装

最も単純なパーサーAPIは、入力ファイル全体を読み取り、中間計算を実行してから、出力ファイル全体を書き込みます。(メモリ内マルチパスコンパイラなど)。

これらの単純なパーサーは、入力ファイル全体または出力ファイル全体を格納するのに十分なメモリーがない場合は機能しません。また、現実世界からの終わりのないデータストリームに対しては機能しません。

そのようなデータを解析するためのいくつかの代替APIアプローチ:

  • パーサーが入力ストリーム( Expatなど)で関連するトークンを検出するとすぐに、登録されたハンドラー(コールバック)を呼び出すプッシュパーサー
  • パーサーをプルする
  • ファイルのテキストがユーザーによって編集されるときに、ファイル全体を完全に再解析する必要がないインクリメンタルパーサー(インクリメンタルチャートパーサーなど)。
  • アクティブパーサーとパッシブパーサー[19] [20]

パーサー開発ソフトウェア

よく知られているパーサー開発ツールには、次のものがあります。

先読み

2トークン未満の先読みで解析できないCプログラム。上: C文法の抜粋。[21] 下:パーサーがトークン ""をダイジェストし、Stmtを導出するためのルールを選択しようとしています最初の先読みトークン ""だけを見ると、 Stmtの両方の選択肢のどちらを選択するかを決定できません。後者では、2番目のトークンを確認する必要があります。int v;main(){v

先読みは、パーサーが使用するルールを決定するために使用できる最大の着信トークンを確立します。先読みは、LLLR、およびLALRパーサーに特に関係があり、LALR(1)などの括弧内のアルゴリズム名に先読みを付加することで明示的に示されることがよくあります。

パーサーの主なターゲットであるほとんどのプログラミング言語は、先読みが制限されたパーサーの方が効率的であることが多いため、先読みが制限されたパーサー(通常は1つ)がそれらを解析できるように注意深く定義されています。この傾向に対する重要な変更の1つは、1990年にテレンスパー博士号を取得するためにANTLRを作成したときに発生しました。論文、効率的なLL(k)パーサー用のパーサージェネレーター。ここで、 kは任意の固定値です。

LRパーサーは通常、各トークンを確認した後、わずかなアクションしか実行しません。それらは、shift(後で削減するためにこのトークンをスタックに追加する)、reduce(スタックからトークンをポップして構文構造を形成する)、end、error(既知のルールは適用されない)、または競合(ShiftまたはReduceのどちらかがわからない)です。 。

先読みには2つの利点があります。[説明が必要]

  • これは、競合が発生した場合にパーサーが正しいアクションを実行するのに役立ちます。たとえば、else句の場合のifステートメントの解析。
  • 多くの重複状態を排除し、余分なスタックの負担を軽減します。AC言語の非先読みパーサーには、約10,000の状態があります。先読みパーサーには約300の状態があります。

例:式の解析 1 + 2 * 3 [疑わしい ]

式の解析ルール(文法と呼ばれる)のセットは次のとおりです。
ルール1: E→E + E 式は、2つの式の合計です。
ルール2: E→E * E 式は2つの式の積です。
ルール3: E→番号 式は単純な数です
Rule4: +は*よりも優先順位が低くなります

ほとんどのプログラミング言語(APLやSmalltalkなどのいくつかを除く)と代数式は、加算よりも乗算を優先します。この場合、上記の例の正しい解釈は1 +(2 * 3)です。上記のRule4はセマンティックルールであることに注意してください。文法を書き直して、これを構文に組み込むことができます。ただし、そのようなルールのすべてを構文に変換できるわけではありません。

単純な非先読みパーサーアクション

最初に入力= [1、+、2、*、3]

  1. 「1」を入力からスタックにシフトします(ルール3を見越して)。入力= [+、2、*、3]スタック= [1]
  2. rule3に基づいて、「1」を式「E」に変換します。スタック= [E]
  3. 「+」を入力からスタックにシフトします(ルール1を見越して)。入力= [2、*、3]スタック= [E、+]
  4. 「2」を入力からスタックにシフトします(ルール3を見越して)。入力= [*、3]スタック= [E、+、2]
  5. rule3に基づいて、スタック要素「2」を式「E」に減らします。スタック= [E、+、E]
  6. rule1に基づいて、スタックアイテム[E、+、E]と新しい入力「E」を「E」に減らします。スタック= [E]
  7. 「*」を入力からスタックにシフトします(ルール2を見越して)。入力= [3]スタック= [E、*]
  8. 「3」を入力からスタックにシフトします(ルール3を見越して)。入力= [](空)スタック= [E、*、3]
  9. rule3に基づいて、スタック要素「3」を式「E」に減らします。スタック= [E、*、E]
  10. rule2に基づいて、スタックアイテム[E、*、E]と新しい入力「E」を「E」に減らします。スタック= [E]

解析ツリーとそれから得られるコードは、言語のセマンティクスによれば正しくありません。

先読みなしで正しく解析するには、次の3つの解決策があります。

  • ユーザーは式を括弧で囲む必要があります。これは多くの場合、実行可能な解決策ではありません。
  • パーサーは、ルールに違反したり、ルールが完了していない場合はいつでも、バックトラックして再試行するためのロジックを増やす必要があります。LLパーサーでも同様の方法が使用されます。
  • あるいは、パーサーまたは文法には、削減を遅らせ、最初に削減するルールが完全に確実な場合にのみ削減するための追加のロジックが必要です。このメソッドは、LRパーサーで使用されます。これにより、式が正しく解析されますが、状態が多くなり、スタックの深さが増します。
先読みパーサーアクション[説明が必要]
  1. rule3を見越して、入力1のスタックに1をシフトします。すぐには減りません。
  2. ルール3に基づいて、スタック項目1を入力+の単純な式に減らします。先読みは+であるため、E +へのパス上にあるため、スタックをEに減らすことができます。
  3. rule1を見越して、+を入力+のスタックにシフトします。
  4. ルール3を見越して、入力2のスタックに2をシフトします。
  5. rule3に基づいて、スタック項目2を入力時の式*に減らします。先読み*は、その前にEのみを期待します。
  6. これでスタックはE + Eになり、入力は*になります。現在、rule2に基づいてシフトするか、rule1に基づいて縮小するかの2つの選択肢があります。*はrule4に基づいて+よりも優先順位が高いため、rule2を見越して*をスタックにシフトします。
  7. rule3を見越して、入力3のスタックに3をシフトします。
  8. rule3に基づいて入力の終わりを確認した後、スタック項目3を式に減らします。
  9. ルール2に基づいてスタックアイテムE * EをEに減らします。
  10. rule1に基づいて、スタックアイテムE + EをEに減らします。

生成された解析ツリーは正しく、先読みのないパーサーよりも単純に効率的です[明確化] [要出典] 。これは、LALRパーサーで採用されている戦略です。

も参照してください

参考文献

  1. ^ a b "解析"dictionary.reference.com 2010年11月27日取得
  2. ^ 冨田勝(2012年12月6日)。一般化されたLR構文解析シュプリンガーサイエンス&ビジネスメディア。ISBN 978-1-4615-4034-2
  3. ^ 「文法と作文」
  4. ^ クリストファーD ..マニング; クリストファー・D・マニング; HinrichSchütze(1999)。統計的自然言語処理の基礎MITプレス。ISBN 978-0-262-13360-9
  5. ^ ジュラフスキー、ダニエル(1996)。「語彙および構文アクセスと曖昧性解消の確率モデル」。認知科学20(2):137–194。CiteSeerX10.1.1.150.5711_ 土井10.1207 / s15516709cog2002_1 
  6. ^ クライン、ダン、クリストファーD.マニング。正確な非字句解析。」計算言語学会第41回年次総会の議事録-第1巻。計算言語学会、2003年。
  7. ^ チャニアック、ユージン。最大エントロピーに触発されたパーサー。」計算言語学会の第1回北米支部の議事録。計算言語学会、2000年。
  8. ^ チェン、ダンキ、クリストファー・マニング。ニューラルネットワークを使用した高速で正確な依存関係パーサー。」自然言語処理(EMNLP)の経験的方法に関する2014年の会議の議事録。2014年。
  9. ^ ジア、ロビン; リャン、パーシー(2016-06-11)。「ニューラルセマンティック解析のためのデータ再結合」。arXiv1606.03622 [ cs.CL ]。
  10. ^ ベラント、ジョナサン、パーシーリャン。言い換えによる意味構文解析。」計算言語学会第52回年次総会の議事録(第1巻:ロングペーパー)。2014年。
  11. ^ a b Aho、AV、Sethi、R。and Ullman、JD(1986)「コンパイラ:原理、技術、およびツール」Addison-Wesley Longman Publishing Co.、Inc。米国マサチューセッツ州ボストン。
  12. ^ Sikkel、Klaas、1954-(1997)。構文解析スキーマ:構文解析アルゴリズムの仕様と分析のためのフレームワークベルリン:スプリンガー。ISBN 9783642605413OCLC606012644 _{{cite book}}: CS1 maint: multiple names: authors list (link)
  13. ^ Frost、R.、Hafiz、R。およびCallaghan、P。(2007)「あいまいな左再帰文法のためのモジュール式で効率的なトップダウン構文解析」。解析技術に関する第10回国際ワークショップ(IWPT)、ACL-SIGPARSE、ページ:109-120、2007年6月、プラハ。
  14. ^ Frost、R.、Hafiz、R。and Callaghan、P。(2008)「あいまいな左再帰文法のためのパーサーコンビネーター宣言型言語の実用的側面に関する第10回国際シンポジウム(PADL)、ACM-SIGPLAN、第4902/2008巻、ページ:167-181、2008年1月、サンフランシスコ。
  15. ^ Rekers、Jan、およびAndySchürr。階層化されたグラフ文法を使用した視覚言語の定義と解析。」Journal of Visual Languages&Computing 8.1(1997):27-55。
  16. ^ Rekers、Jan、およびA.Schurr。グラフィカルな構文解析へのグラフ文法アプローチ。」視覚言語、議事録、第11回IEEE国際シンポジウム。IEEE、1995年。
  17. ^ 張、大千、張張、およびJiannongCao。視覚言語の仕様のための文脈依存グラフ文法形式。」The Computer Journal 44.3(2001):186-200。
  18. ^ ジル・フェイン・リーマン(2012年12月6日)。アダプティブ解析:自己拡張型自然言語インターフェースシュプリンガーサイエンス&ビジネスメディア。ISBN 978-1-4615-3622-2
  19. ^ パトリック・ブラックバーンとクリスティーナ・ストリーニッツ。 「プロローグにおける自然言語処理技術」
  20. ^ 朱松純。 「古典的な構文解析アルゴリズム」
  21. ^ Brian W.KernighanとDennisM。Ritchie(1988年4月)からCプログラミング言語プレンティスホールソフトウェアシリーズ(第2版)。イングルウッドクリフ/ニュージャージー:プレンティスホール。ISBN 0131103628(付録A.13「文法」、p.193以降)

さらに読む

外部リンク