トップダウン解析

コンピュータサイエンスにおけるトップダウン構文解析は、まず構文解析ツリーの最上位レベルを見て、形式文法の書き換え規則を使用して構文解析ツリーを下に向かって解析していく構文解析戦略です。^[1] LLパーサーは、トップダウン構文解析戦略を使用するタイプのパーサーです。

トップダウン解析は、一般的な解析ツリー構造を仮定し、既知の基本構造がその仮説と互換性があるかどうかを検討することによって、未知のデータ関係を解析する戦略です。これは、自然言語とコンピュータ言語の両方の解析で発生します。

トップダウン構文解析は、与えられた形式文法規則をトップダウンに展開して構文木を検索することで、入力ストリームの左端の導出を見つけようとする試みとみなすことができます。包括的選択は、文法規則の右側の選択肢をすべて展開することで、曖昧さに対応するために使用されます。^[2]

トップダウン構文解析の単純な実装は左再帰文法では終了せず、バックトラックを伴うトップダウン構文解析は、曖昧なCFGの入力の長さに対して指数関数的な時間計算量を持つ可能性があります。^[3]しかし、Frost、Hafiz、Callaghanによって、より洗練されたトップダウン構文解析器が作成されました。^{[4] [5]これらは、}多項式時間で曖昧性と左再帰に対応し、潜在的に指数関数的な数の構文解析木の多項式サイズの表現を生成します。

コンパイラは、入力シンボルを生成規則と照合することにより、プログラミング言語からの入力を内部表現に解析します。生成規則は一般にバッカス・ナウア記法を使用して定義されます。LLパーサーは、入力シンボルに各生成規則を適用し、生成規則で生成された最も左のシンボルから作業して、遭遇した各非終端シンボルの次の生成規則に進むことによってトップダウン解析を行うタイプのパーサーです。このように、解析は生成規則の結果側 (右側) の左側から開始し、最初に左側から非終端を評価し、新しい非終端ごとに解析ツリーを下って進み、生成規則の次のシンボルに進みます。

例えば：

• ${\displaystyle A\rightarrow aBC}$
• ${\displaystyle B\rightarrow c\mid cd}$
• ${\displaystyle C\rightarrow df\mid eg}$

文字列A = acdfを生成します。

が一致し、次に一致を試みます。その後、が試されます。予想どおり、一部の言語は他の言語よりも曖昧です。非終端のすべての生成規則が異なる文字列を生成する非曖昧性言語の場合、1つの生成規則によって生成された文字列は、別の生成規則によって生成された文字列と同じ記号で始まることはありません。非曖昧性言語は、LL(1) 文法で解析できます。ここで、(1) は、パーサーが一度に 1 つのトークンを先読みすることを意味します。曖昧な言語を LL パーサーで解析するには、パーサーは 1 つ以上の記号を先読みする必要があります (例: LL(3))。 ${\displaystyle A\rightarrow aBC}$${\displaystyle B\rightarrow c\mid cd}$${\displaystyle C\rightarrow df\mid eg}$

この問題の一般的な解決策は、シフトリデュースパーサーの一種であり、ボトムアップ解析を行うLR パーサーを使用することです。

左再帰を含む形式文法は、弱く等価な右再帰形式に変換されない限り、単純な再帰下降パーサーでは解析できません。ただし、最近の研究では、左再帰文法 (および他のすべての形式の一般的なCFG ) を、削減を使用することで、より洗練されたトップダウン パーサーに組み込むことが可能であることが実証されています。2006 年に Frost と Hafiz は、入力長と現在の入力位置に関する深さ制限を課すことで、あいまいな文法に対応し、増え続ける直接左再帰構文解析を削減する認識アルゴリズムを発表しました^。[6]このアルゴリズムは、間接 (以前に計算されたコンテキストと現在のコンテキストを比較することにより) と直接左再帰を多項式時間で対応し、あいまいさが非常に高い文法の潜在的に指数関数的な数の構文解析ツリーのコンパクトな多項式サイズの表現を生成する完全な構文解析アルゴリズムに拡張されました。 ^{[4]このアルゴリズムはその後、} Haskellプログラミング言語で記述された構文解析コンビネータのセットとして実装されました。これらの新しいコンビネータのセットの実装の詳細は、PADL'08 で発表された著者の論文^[5]に記載されています。X-SAIGA サイトには、アルゴリズムと実装の詳細に関する詳細が記載されています。

さらに、前述の削減に加えてグラフ構造スタック (GSS) を使用することで、共通プレフィックスを持つスタックを「マージ」し、無限再帰を防ぐことで左再帰に対応し、各スタックの数と内容を減らして、パーサーの時間と空間の複雑さを軽減することができます。これにより、一般化 LL 解析と呼ばれるアルゴリズムが生まれ、GSS、左再帰削減、LL(k) パーサーを使用して、指定されたCFG を基準にして入力文字列を解析します。^{[7] [8]}

トップダウンパーサーが曖昧なCFGに関して曖昧な入力を解析しようとすると、すべての可能な解析木を生成するためにCFGのすべての代替を試すために指数関数的なステップ数（入力の長さに関して）が必要になる可能性があり、最終的には指数関数的なメモリスペースが必要になります。相互再帰関数の集合として構築されたトップダウンパーサーの指数関数的な時間計算量の問題は、1991年にNorvigによって解決されました。 ^{[9]彼の手法は、} Earleyのアルゴリズム（1970）での動的計画法と状態セット、およびCocke、Younger、KasamiのCYKアルゴリズムでのテーブルの使用に似ています。

鍵となるアイデアは、パーサを適用した結果を記憶できるp場所に保存し、同じ状況が発生したときに結果を再利用するというものである。Frost、Hafiz、Callaghan ^{[4] [5]}も、冗長な計算を回避して、多項式時間 (左再帰文法の場合はΘ (n ^{4 )、非左再帰文法の場合は}Θ (n ^{3 )) であらゆる形式の CFG に対応するために}メモ化を使用している。彼らのトップダウン構文解析アルゴリズムは、「コンパクトな表現」と「局所的な曖昧さのグループ化」によって、潜在的に指数関数的に曖昧な構文解析木のための多項式空間も必要とする。彼らのコンパクトな表現は、Tomitaのボトムアップ構文解析のコンパクトな表現に匹敵する。^[10]j

文法の別の表現である PEG を使用して、packrat パーサーは洗練された強力な解析アルゴリズムを提供します。式文法の解析を参照してください。

トップダウン解析を使用するパーサーには次のようなものがあります。

• 定節文法パーサー^[11]
• 再帰降下パーサー
• 予測パーサー
• アーリーパーサー

• ボトムアップ解析
• 解析
• 構文解析式の文法

• X-SAIGA - 文法の実行可能な仕様