Loading article…
形式文法理論では、決定性文脈自由文法( DCFG )は文脈自由文法の適切なサブセットです。これらは、決定性プッシュダウンオートマトンから導出できる文脈自由文法のサブセットであり、決定性文脈自由言語を生成します。DCFG は常に一義的であり、一義的な CFG の重要なサブクラスです。ただし、非決定性の一義的な CFG も存在します。
DCFG は線形時間で解析でき、実際にパーサー ジェネレーターによって文法からパーサーを自動的に生成できるため、実用上非常に興味深いものです。そのため、コンピューター サイエンスの分野で広く使用されています。さまざまな制限付きの DCFG 形式は、より単純でリソースをあまり消費しないパーサーで解析できるため、よく使用されます。これらの文法クラスは、解析するパーサーの種類によって参照され、重要な例としては、LALR、SLR、LL などがあります。
歴史
1960年代、正規表現と有限オートマトンに関する計算機科学の理論的研究により、文脈自由文法が非決定性プッシュダウンオートマトンと同等であることが発見された。[1] [2] [3]これらの文法は、計算機プログラミング言語の構文を捉えていると考えられていた。当時は最初の高水準計算機プログラミング言語が開発中であり（プログラミング言語の歴史を参照）、コンパイラを書くのは困難だった。しかし、文脈自由文法を使ってコンパイラの構文解析部分を自動化することで、作業が簡素化された。決定性文脈自由文法は、計算機のメモリ制約により必須であった決定性プッシュダウンオートマトンによって順次解析できるため、特に有用であった。 [4] 1965年、ドナルド・クヌースがLR(k)パーサーを発明し、あらゆる決定性文脈自由言語に対してLR(k)文法が存在することを証明した。[5]このパーサーはまだ大量のメモリを必要とした。 1969年、フランク・デレマーはLALRパーサーとシンプルLRパーサーを発明した。どちらもLRパーサーをベースにしており、言語認識能力は劣るもののメモリ要件を大幅に削減していた。LALRパーサーの方が強力な選択肢だった。[6] これら2つのパーサーは、それ以来、多くのコンピュータ言語のコンパイラーで広く使用されている。最近の研究では、クヌースのテーブル構築アルゴリズムよりも大幅にテーブル要件を削減した標準的なLRパーサーを実装する方法が特定されている。[7]
参照
参考文献
- ^ チョムスキー、ノーム(1962)。「文脈自由文法とプッシュダウンストレージ」。四半期進捗報告書、MIT電子工学研究所。65 : 187–194。
- ^ Evey, RJ (1963)。「プッシュダウンストアマシンの応用」。1963 AFIPS Proceedings of the Fall Joint Computer Conference : 215–227。
- ^ Schützenberger, Marcel Paul (1963). 「文脈自由言語とプッシュダウンオートマトンについて」.情報と制御. 6 (3): 246–264. doi : 10.1016/s0019-9958(63)90306-1 .
- ^ A. Salomaa ; D. Wood; S. Yu編 (2001)。オートマトン理論の半世紀。ワールドサイエンティフィックパブリッシング。pp. 38–39。
- ^ Knuth, DE (1965年7月). 「左から右への言語の翻訳について」.情報と制御. 8 (6): 607–639. doi : 10.1016/S0019-9958(65)90426-2 .
- ^ Franklin L. DeRemer (1969). 「LR(k) 言語の実用的な翻訳者」(PDF) 。MIT、博士論文。2012-04-05 のオリジナル(PDF)からアーカイブ。
- ^ X. Chen、「LR(1)構文解析の測定と拡張」、ハワイ大学博士論文、2009年。