C++ はコンテキストフリーですか、それともコンテキスト依存ですか? 質問する

以下は、C++のパースが（おそらく）なぜ難しいのかを示す、私の（現在の）お気に入りのデモンストレーションです。チューリング完全これは、与えられた整数が素数である場合にのみ、構文的に正しいプログラムを示しているためです。

したがって、私はC++ はコンテキストフリーでもコンテキスト依存でもないと主張します。

任意の生成規則の両側に任意の記号列を許可すると、タイプ0文法（「制限なし」）が生成されます。チョムスキー階層は文脈依存文法よりも強力である。制限のない文法はチューリング完全である。文脈依存（タイプ1）文法では、生成規則の左側に複数の文脈記号を記述できるが、生成規則の右側に同じ文脈が記述されなければならない（そのため「文脈依存」という名前が付けられている）。[1] 文脈依存文法は、線形制限チューリングマシン。

サンプルプログラムでは、素数の計算は線形制限チューリングマシンで実行できるため、チューリング等価性を完全に証明しているわけではありませんが、重要なのは、構文解析を実行するためにパーサーが計算を実行する必要があることです。これはテンプレートのインスタンス化として表現できる任意の計算である可能性があり、C++ テンプレートのインスタンス化がチューリング完全であると信じる理由は十分にあります。たとえば、トッド・L・ベルドハイゼンの2003年の論文。

いずれにしても、C++ はコンピューターで解析できるので、チューリング マシンで解析できるのは間違いありません。したがって、制限のない文法で認識できます。実際にそのような文法を記述するのは非現実的であるため、標準ではそのような文法を記述しようとしません。(以下を参照)

特定の表現の「曖昧さ」に関する問題は、ほとんどが誤解を招くものです。まず、曖昧さは特定の文法の特徴であり、言語の特徴ではありません。言語に明確な文法がないことが証明されたとしても、文脈自由文法で認識できる場合は、文脈自由です。同様に、文脈自由文法では認識できないが、文脈依存文法では認識できる場合は、文脈依存です。曖昧さは関係ありません。

しかし、いずれにしても、auto b = foo<IsPrime<234799>>::typen<1>();以下のプログラムの 21 行目 (つまり ) のように、式はまったく曖昧ではありません。単にコンテキストに応じて異なる方法で解析されるだけです。この問題の最も単純な表現では、特定の識別子の構文カテゴリは、それらの宣言方法 (たとえば、型と関数) に依存します。つまり、形式言語は、同じプログラム内の 2 つの任意の長さの文字列が同一であるという事実 (宣言と使用) を認識する必要があります。これは、「コピー」文法によってモデル化できます。これは、同じ単語の 2 つの連続した正確なコピーを認識する文法です。次の式で簡単に証明できます。ポンピング補題この言語は文脈自由ではない。この言語の文脈依存文法は可能であり、この質問の回答ではタイプ 0 文法が提供されています。https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language。

C++ を解析するための文脈依存型 (または制限なし) の文法を書こうとすると、おそらく宇宙が落書きで埋め尽くされるでしょう。C++ を解析するためのチューリング マシンを書くのも同様に不可能な仕事です。C++ プログラムを書くのも難しく、私が知る限り、正しいことが証明されたプログラムはありません。これが、標準が完全な形式文法を提供しようとせず、一部の解析ルールを技術英語で書くことを選択した理由です。

C++ 標準の形式文法のように見えるものは、C++ 言語の構文の完全な形式定義ではありません。前処理後の言語の完全な形式定義でもありません。前処理後の言語の完全な形式定義は形式化が容易かもしれません。(ただし、それは言語ではありません。標準で定義されている C++ 言語にはプリプロセッサが含まれており、プリプロセッサの動作は、文法形式で記述するのが非常に難しいため、アルゴリズムで記述されています。標準のそのセクションでは、語彙分解が記述されており、複数回適用する必要があるルールも含まれています。)

さまざまな文法 (語彙分析用の重複する 2 つの文法。1 つは前処理の前に実行され、もう 1 つは必要に応じて後から実行される文法、および「構文」文法) が付録 A にまとめられていますが、次の重要な注記があります (強調追加):

この C++ 構文の要約は、理解を助けることを目的としています。言語の正確な記述ではありません。特に、ここで説明する文法は、有効な C++ 構文のスーパーセットを受け入れます。式と宣言を区別するには、曖昧さ回避ルール (6.8、7.1、10.2) を適用する必要があります。さらに、アクセス制御、曖昧性、および型ルールを使用して、構文的には有効だが意味のない構文を排除する必要があります。

最後に、約束のプログラムを示します。 21 行目は、 の N が素数である場合にのみ構文的に正しいですIsPrime<N>。 それ以外の場合は、typenはテンプレートではなく整数であるため、typen<1>()として解析されますが、 は構文的に有効な式ではない(typen<1)>()ため、構文的に誤りです。()

template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};

template<bool no, bool yes, int f, int p> struct IsPrimeHelper
  : IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };

template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; }; 

template<typename A> struct foo;
template<>struct foo<answer<true>>{
  template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
  static const int typen = 0;
};

int main() {
  auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
  return 0;
}