Loading article…
GLRパーサ（一般化左から右への右端導出パーサ）は、 LRパーサアルゴリズムを拡張したもので、非決定性で曖昧な文法を処理できる。[1]理論的基礎は、1974年の論文[2]でBernard Lang（GLLなどの他の一般的な文脈自由パーサとともに）によって提供された。この論文では、このようなアルゴリズムを作成する体系的な方法が説明されており、正しさの証明、文法クラスに関する複雑さ、最適化手法に関する統一的な結果が示されている。GLRの最初の実際の実装は、1984年の論文で富田勝によって説明され、「並列パーサ」とも呼ばれている。富田はオリジナルの研究で5つの段階を提示したが[3]、実際にはGLRパーサとして認識されているのは2番目の段階である。
アルゴリズムは元の形式から進化していますが、原理はそのまま残っています。以前の出版物[4]に示されているように、ラングは主に、拡張可能なプログラミング言語のための、より使いやすく柔軟なパーサーに興味を持っていました。富田の目標は、自然言語テキストを徹底的かつ効率的に解析することでした。標準的なLRパーサーは、自然言語の非決定性と曖昧さに対応できませんが、GLRアルゴリズムは対応できます。
アルゴリズム
簡単に言うと、GLR アルゴリズムはLR パーサーアルゴリズムと同様に機能しますが、特定の文法が与えられると、GLR パーサーは幅優先探索で与えられた入力のすべての可能な解釈を処理するという点が異なります。フロントエンドでは、GLRパーサー ジェネレーターがLR ジェネレーターと同様の方法で入力文法をパーサー テーブルに変換します。ただし、LR 解析テーブルでは状態遷移が1 つしか許可されないのに対し(状態と入力トークンが与えられると)、GLR 解析テーブルでは複数の遷移が許可されます。実際、GLR ではシフト/削減と削減/削減の競合が許可されます。
矛盾する遷移が発生すると、解析スタックは 2 つ以上の並列解析スタックに分岐します。各遷移に対応する状態は最上位になります。次に、次の入力トークンが読み取られ、各「最上位」状態の次の遷移を決定するために使用されます。さらに分岐が発生する場合があります。特定の最上位状態と入力トークンが少なくとも 1 つの遷移をもたらさない場合、解析テーブルを介したその「パス」は無効であり、破棄できます。
グラフ構造スタックと呼ばれる重要な最適化により、これらのスタックの共通のプレフィックスとサフィックスを共有できるようになり、入力テキストの解析に必要な全体的な検索スペースとメモリ使用量が制限されます。この改善によって生じる複雑な構造により、検索グラフはツリーではなく、有向非巡回グラフになります(さまざまなノードの「深さ」に対する追加の制限があります)。
利点
GLRアルゴリズムを使用した認識は、CYKアルゴリズムやEarleyアルゴリズムと同じ最悪の場合の時間計算量O ( n3 )となる。[要出典]しかし、GLRにはさらに2つの利点がある。
- アルゴリズムの実行に必要な時間は、文法の非決定性の度合いに比例します。決定性文法では、GLRアルゴリズムはO ( n )時間で実行されます（これはEarley [要出典]およびCYKアルゴリズムには当てはまりませんが、元のEarleyアルゴリズムはこれを保証するために変更できます）。
- GLR アルゴリズムは「オンライン」です。つまり、入力トークンを特定の順序で消費し、各トークンを消費した後に可能な限り多くの作業を実行します (Earley の場合も同様です)。
実際には、ほとんどのプログラミング言語の文法は決定論的または「ほぼ決定論的」であり、非決定性は通常、少数の（ただし無制限の可能性がある）トークン内で解決されることを意味します[引用が必要]。文脈自由文法の完全なクラスを処理できる他のアルゴリズム（Earley パーサーやCYK アルゴリズムなど）と比較して、GLR アルゴリズムは、解析プロセスの大部分で単一のスタックのみがアクティブになるため、これらの「ほぼ決定論的」文法でより優れたパフォーマンスを発揮します。
GLRはLALR（1）アルゴリズムとハイブリッドパーサーで組み合わせることができ、さらに高いパフォーマンスを実現します。 [5]
参照
- パーサージェネレータの比較
- DMS ソフトウェア リエンジニアリング ツールキット
- GNU Bison、LALR および GLR パーサーを作成できるパーサー ジェネレーター
- Packratパーサー、曖昧で非決定的な言語を解析できる別のパーサー
参考文献
- ^富田勝（2012年12月6日）。一般化されたLR構文解析 。Springer Science & Business Media。ISBN 978-1-4615-4034-2。
- ^ Lang, Bernard (1974)。「効率的な非決定論的パーサーのための決定論的手法」。Loeckx, J. (編)。オートマトン、言語、プログラミング。コンピュータサイエンスの講義ノート。第 14 巻。ザールブリュッケン: Springer。pp. 255–269。doi : 10.1007 /3-540-06841-4_65。ISBN 978-3-540-06841-9. ISSN 0302-9743.
- ^ 富田勝. 自然言語の効率的な構文解析. Kluwer Academic Publishers, ボストン, 1986.
- ^ Lang , Bernard (1971 年 12 月)。「並列非決定性ボトムアップ構文解析」。ACM SIGPLAN 通知。拡張可能言語に関する国際シンポジウムの議事録。6 (12): 56–57。doi : 10.1145 /942582.807982。
- ^ 「Elkhound、Elsa、Cqual++: C++ 向けのオープンソースの静的解析」。YouTube。2021年12月21日時点のオリジナルよりアーカイブ。
さらに読む
- グルーネ、ディック、ジェイコブス、セリエル JH (2008)。解析テクニック。シュプリンガー サイエンス+ビジネス メディア。ISBN 978-0-387-20248-8。
- 富田勝 (1984) 「自然言語のための LR パーサー」COLING . 第 10 回国際計算言語学会議 pp. 354–357。
- 富田勝 (1985) 「自然言語のための効率的な文脈自由構文解析アルゴリズム」IJCAI。人工知能に関する国際合同会議。pp. 756–764。