文脈自由言語とプッシュダウンオートマトン

文脈自由文法は、入れ子になった再帰的な構造を持つ言語を生成し、プッシュダウンオートマトンは、有限制御装置に無制限のスタックを追加することで、これらの言語を正確に認識します。

Definition

文脈自由言語は、単一の非終端記号を文脈に依存せずに書き換える規則を持つ文法によって生成され、プッシュダウンオートマトンによって認識されます。プッシュダウンオートマトンは、無制限の深さのLIFO（後入れ先出し）メモリを提供するスタックを備えた有限オートマトンです。

Scope

このトピックでは、文脈自由文法と導出、構文解析木と曖昧性、文脈自由文法とプッシュダウンオートマトンの等価性、チョムスキー標準形などの標準形、文脈自由言語のポンピング補題、およびこのクラスを正規言語と区別する閉包特性と決定特性について扱います。

Core questions

• どのような種類の入れ子または再帰的なパターンが、有限メモリではなくスタックを必要としますか？
• なぜ文脈自由文法とプッシュダウンオートマトンは能力において等価なのでしょうか？
• 文法が曖昧であるのはどのような場合で、なぜ曖昧性は構文解析にとって重要なのでしょうか？
• 文脈自由言語に関するどの決定問題が解決可能で、どれが解決不可能ですか？

Key theories

文法とオートマトンの等価性

ある言語が文脈自由であるのは、それが何らかのプッシュダウンオートマトンによって受理される場合のみであり、したがって生成文法による見方とスタックマシンによる見方は同じ言語クラスを記述します。

チョムスキー標準形

すべての文脈自由文法は、各規則が2つの非終端記号または1つの終端記号のいずれかを生成するように書き換えることができ、これは構文解析アルゴリズムやこのクラスに関する帰納的証明の基礎となる標準形です。

文脈自由言語のポンピング補題

文脈自由言語内の十分に長いすべての文字列は、その2つの部分が一緒にポンピングされるように分割できます。この特性は、スタックメモリ以上のものを必要とする言語には当てはまらず、したがってそれらの言語が文脈自由ではないことを証明します。

Clinical relevance

文脈自由文法は、ほとんどすべてのプログラミング言語と多くのデータ形式の構文を規定しており、プッシュダウン方式の構文解析アルゴリズムは、これらの文法をコンパイラやインタプリタの中核となる構文アナライザに変換します。これにより、このトピックはプログラミング言語処理の理論的基盤となっています。

History

チョムスキーは1950年代後半に自身の階層の一部として文脈自由文法を導入し、バックアップとナウアによってALGOLプログラミング言語の構文を定義するために独立して使用されました。プッシュダウンオートマトンとの等価性およびこのクラスの構造理論は、1960年代を通じて研究されました。

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

プログラミング言語の構文解析になぜスタックが必要なのですか？

プログラムには、括弧、ブロック、関数呼び出しなど、入れ子になった構造が含まれており、その対応する深さは無制限です。スタックは、未完了の各構造を記録し、閉じられたときにそれをポップします。これは、プッシュダウンオートマトンが提供し、有限オートマトンが欠いているメモリ管理そのものです。

文法が曖昧であるとはどういう意味ですか？

文法が曖昧であるとは、ある文字列が複数の構文解析木を持つことを意味し、つまり、本質的に異なる構造で導出され得るということです。曖昧性は、コードの意味を不明瞭にするため、プログラミング言語にとって望ましくありません。そのため、言語設計者は曖昧さのない文法を追求するか、曖昧性解消規則を追加します。