c# - C# は文脈自由言語と見なされますか?

Question

私はこれを探していましたが、この質問に対するさまざまな回答がMSDN フォーラムにあります。

「すべてのコンピューター言語の文法は文脈自由である」と言う人もいれば、空白に敏感な構文を持つ言語は文脈依存である可能性が高く、したがって文脈自由ではない(F# と Python) と言う人もいます。

決定的な答えとおそらくいくつかの証拠があればいいでしょう。

Answer 1

C# は文脈自由文法を備えていると説明しますが、この言語には、文法では表現されていない文脈依存の規則があります。

ウィキペディアから (正式な文法):

文脈自由文法は、各生成規則の左側が単一の非終端記号のみで構成される文法です。

C# 4.0 仕様のセクション 2.2.1 (文法表記) から:

字句文法と構文文法は、文法生成を使用して提示されます。各文法生成は、非終端記号と、非終端記号または終端記号のシーケンスへのその非終端記号の可能な展開を定義します。

私が読んだ限りでは、これは C# 言語を定義するプロダクション ルールがコンテキスト フリーであることを意味します。各生産規則の左側は、単一の非終端記号です。対照的に、文脈依存文法では、生成規則の左側に複数の終端記号と非終端記号がある場合があります。

ただし、仕様には状況依存のルールが多数あります。たとえば、「ローカル変数は、その値が取得される各場所で確実に割り当てられる必要があります (§5.3)」。また、「メソッドのシグネチャは、メソッドが宣言されているクラス内で一意でなければなりません。」これらはどちらも、特定のフラグメントの有効性が、それが表示されるコンテキストに依存する場合です。

もちろん、C を含む多くのプログラミング言語にも同様の要件があります。ほとんどの人が C を状況依存言語と見なすとは思えません。この答えはそれをうまく要約していると思います：

構文的に正しいプログラムのセットは、ほとんどすべての言語で文脈自由です。コンパイルされるプログラムのセットは、ほとんどすべての言語でコンテキスト フリーではありません。

Python と F# については、私のコメントで述べたように、これらの言語は通常、文脈に依存しないセマンティック (または場合によっては構文) の空白を持っていると説明されています。