[解決済み】C++は文脈自由か文脈依存か？

質問

C++は文脈依存型言語であるという主張をよく耳にします。次のような例を見てみましょう。

a b(c);

これは変数定義でしょうか、それとも関数宣言でしょうか？それは、この記号の意味による c . もし c は 変数 であれば a b(c); という名前の変数を定義しています。 b 型の a . で直接初期化されます。 c . しかし、もし c は タイプ であれば a b(c); という名前の関数を宣言しています。 b を受け取り、それを c を返し a .

文脈自由言語の定義を調べると、基本的には、すべての文法規則は、正確に1つの非終端記号からなる左辺を持たなければならないと書いてある。一方、文脈依存文法は、左辺に任意の終端記号と非終端記号の文字列を許容する。

C++プログラミング言語』の付録Aを見ても、左辺に非終端記号を1つだけ持つ文法規則は1つもない。これは、C++が文脈自由であることを意味する。(もちろん、文脈自由言語は文脈依存言語の部分集合を形成するという意味で、すべての文脈自由言語は文脈依存言語でもあるのだが、それは重要なことではない。）

では、C++は文脈自由なのか、文脈依存なのか？

どのように解決するのか？

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

そこで、私は次のように主張します。 C++は文脈自由でも文脈依存でもない .

任意の記号列を生成の両側で許容すると、以下のような Type-0 文法 ("unrestricted") が生成されます。 チョムスキー階層 この文法は文脈依存文法よりも強力であり、無制限文法はチューリング完全である。文脈依存文法（Type-1）は、文法の左辺に複数の文脈の記号を置くことができるが、同じ文脈が文法の右辺になければならない（そのため、文脈依存という名前がついている）。[1]文脈依存文法は次のものと等価である。 線形結合チューリング機械 .

例のプログラムでは、素数計算は線形結合チューリング機械で実行できたので、チューリング等価性の証明にはなっていませんが、重要なのはパーサーが構文解析を行うために計算を行う必要があるという点です。しかし、重要なのは、構文解析を行うためにパーサーが計算を行う必要があるということです。これは、テンプレートのインスタンス化として表現できる任意の計算である可能性があり、C++テンプレートのインスタンス化がチューリング完全であると信じるに足る十分な根拠があります。例えば、以下をご覧ください。 Todd L. Veldhuizenの2003年の論文 .

それはともかく、C++はコンピュータで解析できるので、チューリング機械で解析できるのは確かです。その結果、無制限の文法がそれを認識することができるのです。実際にそのような文法を書くのは非現実的なので、この規格ではそうしようとはしていないのです。(後述）。

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

しかし、いずれにせよ、21行目のように（つまり auto b = foo<IsPrime<234799>>::typen<1>(); のように、文脈によって解析が異なるだけで、曖昧な表現ではありません。この問題の最も単純な表現としては、ある識別子の構文上のカテゴリは、それがどのように宣言されたかに依存する（例えば、型や関数）、つまり、同じプログラム内の二つの任意長の文字列が同一（宣言と使用）であることを形式言語が認識しなければならないだろう、ということである。これは、"copy"という文法でモデル化することができ、これは、同じ単語の正確なコピーが2つ連続していることを認識する文法である。を使えば簡単に証明できる。 ポンピングレマ この言語が文脈自由でないこと。この言語に対して文脈を考慮した文法は可能であり，Type-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行目が構文的に正しいのは 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;
}

[1] より技術的に言うと、文脈依存文法におけるすべての生成は、その形式でなければならない。

αAβ → αγβ

ここで A は非終端記号であり α , β は空の可能性がある文法記号の列であり γ は空でないシーケンスである。(文法記号は終端でも非終端でもよい）。

これは次のように読むことができます。 A → γ のみで、コンテキスト [α, β] . 文脈自由文法（タイプ2）では α と β は空でなければならない。

また、文法にはquot;monotonic"という制限があり、すべてのプロダクションがこの形でなければならないことが分かっています。

α → β ここで |α| ≥ |β| > 0   ( |α| の長さを意味します。 α となります。）

単調文法で認識される言語の集合と文脈依存文法で認識される言語の集合は全く同じであることを証明することが可能であり、単調文法に基づく証明の方が簡単であることが多いのです。そのため、quot;context-sensitive"があたかもquot;monotonic"を意味するように使われているのをよく見かけるようになった。