プログラミング言語に関連するチョムスキー階層のいくつかの側面を学ぼうとしていますが、まだドラゴンブックを読まなければなりません。
ほとんどのプログラミング言語は文脈自由文法 (CFG) として解析できると読みました。計算能力に関しては、プッシュダウン型の非決定性オートマトンに匹敵します。私は正しいですか？
それが本当なら、チューリングが完了している無制限文法 (UG) を CFG がどのように保持できるのでしょうか? プログラミング言語がCFGで記述されていても、実際にはチューリングマシンを記述するために使用されているため、UGを介して質問しています。
それは、少なくとも 2 つの異なるレベルのコンピューティングによるものだと思います。1 つ目は CFG の解析であり、言語の構造 (表現?) に関連する構文に焦点を当て、もう 1 つはセマンティック (意味、解釈) に焦点を当てています。チューリングが完了しているプログラミング言語の機能に関連しています。繰り返しますが、これらの仮定は正しいですか?
ほとんどのプログラミング言語は文脈自由文法 (CFG) として解析できると読みました。計算能力に関しては、プッシュダウン型の非決定性オートマトンに匹敵します。私は正しいですか？
技術的にはい。いいえ。
これらの質問について考えるには、少なくとも 2 つの有用な方法があります。
問題は、ほとんどのプログラミング言語が文脈自由文法 (Tcl は興味深い例外です) によって簡単に記述できる基本構造を持っている一方で、文脈自由文法 によって記述される多くの文は実際には「言語内」にないことです。ここで、「その言語で」とは、「問題の言語で有効なプログラム」を意味します。これらの余分な文は、通常、何らかの形式の静的セマンティクスによって除外されます。たとえば、次の発話は C プログラムの文脈自由文法の文ですが、それ自体は有効な C プログラムのセットには含まれていません。
int f(void) { return n + 1; }
ここでの問題は、それnが範囲外であることです。C では「使用前の宣言」が必要であり、そのプロパティは文脈自由文法を使用して表現することはできません。
実際のプログラミング言語の典型的な決定手順は、コンパイラまたはインタープリターのフロント エンドの一部であり、少なくとも2 つの部分があります。しかし、2 つ目は、多くの発話を無効として除外する追加のチェックを行います。これらのチェックが何らかの種類の使用前定義プロパティを必要とする場合、プッシュダウン オートマトンまたは文脈自由文法では実行できません。
それが本当なら、チューリングが完了している無制限文法 (UG) を CFG がどのように保持できるのでしょうか?
CFG は何も「保持」しません。単に言語を記述します。
...プログラミング言語がCFGによって記述されていても、実際にはチューリングマシンを記述するために使用されているため、UGを介して.
ここでは、いくつかの重要なレベルの間接化をスキップしています。
それは、少なくとも 2 つの異なるレベルのコンピューティングによるものだと思います。1 つ目は CFG の解析であり、言語の構造 (表現?) に関連する構文に焦点を当て、もう 1 つはセマンティック (意味、解釈) に焦点を当てています。チューリングが完了しているプログラミング言語の機能に関連しています。繰り返しますが、これらの仮定は正しいですか?
彼らは私には少し混乱しているように見えますが、あなたは正しい道を進んでいます. 重要な質問は、「言語とプログラミング言語の違いは何ですか?」です。その答えは、プログラミング言語には計算解釈があるということです。計算による解釈にはさまざまな種類がありますが、そのすべてがチューリング完全であるとは限りません。しかし、魔法は構文ではなく解釈にあるため、ここではチョムスキー階層はあまり関係ありません。
私の主張を証明するために、極端な例を挙げましょう。正規言語[1-9][0-9]*は、次の解釈の下でチューリング完全です。
したがって、整数リテラルの言語はチューリング完全です。
今頭が痛くないなら、そうすべきです。
これは絶対に真実ではありません。ほとんどのプログラミング言語には、CFG または BNG で記述できる構文がありますが、構文に準拠していても正当なプログラムが保証されるわけではありません。「使用する前に変数を宣言する必要がある」または「この式の型を合法的な方法で組み合わせる必要がある」など、文法でカバーされていないあらゆる種類の追加条件があり、それが言語を非文脈にするものです。 -自由。(これは、形式的に検証可能な定義を持つ XML に少し似ていますが、通常、パーサーが検証できない追加の制約も備えています。)
構文に CFG がない言語の非常に良い例は C++ です。あなたはUGを正確に理解していないようです。普遍文法とは、チューリング マシンのコードとそのチューリング マシンによって受け入れられる単語を含む単語の言語として記述される解釈の問題です。したがって、言語自体 (単語のセット) をエンコードするのではなく、そのためのチューリング マシンをエンコードします。ここでポイントになります。無限の単語の言語を持つことはできますが、無限の記号の単語を持つことはできません。つまり、UG にも有限の単語が含まれているため、チューリング マシンのすべての記述は有限です。したがって、チューリング マシン (プログラミング言語によるプログラム) の記述には有限数の記号 (ステートメント) が含まれるため、記述言語 (プログラミング言語の構文文法) は規則的でさえあります。たとえば、バイナリ組み合わせロジック。