c++ - C++ 是上下文无关的还是上下文敏感的？

Question

我经常听到声称 C++ 是一种上下文敏感的语言。以下面的例子为例:

a b(c);

这是变量定义还是函数声明？这取决于符号 c 的含义.如 c是一个变量，那么 a b(c);定义了一个名为 b 的变量类型 a .直接用c初始化.但如果 c是一个类型，那么 a b(c);声明一个名为 b 的函数这需要一个 c并返回 a .

如果您查看上下文无关语言的定义，它基本上会告诉您所有语法规则的左侧都必须由一个非终结符组成。另一方面，上下文相关文法允许在左侧使用任意的终结符和非终结符字符串。

浏览“C++ 编程语言”的附录 A，我找不到一条语法规则除了左侧的单个非终结符之外还有其他任何内容。这意味着 C++ 是上下文无关的。 (当然，每个上下文无关语言也是上下文敏感的，因为上下文无关语言构成上下文敏感语言的子集，但这不是重点。)

那么，C++ 是上下文无关的还是上下文敏感的？

Answer 1

下面是我(当前)最喜欢的为什么解析 C++ 的演示(可能)Turing-complete ，因为它显示了一个语法正确的程序，当且仅当给定的整数是素数。

所以我断言 C++ 既不是上下文无关的，也不是上下文敏感的 .

如果在任何产生式的两边都允许任意符号序列，则在 Chomsky hierarchy 中产生一个 Type-0 文法(“无限制”)。 ，它比上下文敏感的语法更强大；无限制语法是图灵完备的。上下文敏感(Type-1)语法允许在产生式的左侧出现多个上下文符号，但相同的上下文必须出现在产生式的右侧(因此名称为“上下文敏感”)。 [1] 上下文相关文法等价于 linear-bounded Turing machines .

在示例程序中，素数计算可以由线性有界图灵机进行，因此并不能完全证明图灵等价，但重要的是解析器需要进行计算才能进行句法分析。它可以是任何可表示为模板实例化的计算，并且有充分的理由相信 C++ 模板实例化是图灵完备的。例如，参见 Todd L. Veldhuizen's 2003 paper .

无论如何，C++可以被计算机解析，所以它当然可以被图灵机解析。因此，不受限制的语法可以识别它。实际上编写这样的语法是不切实际的，这就是标准不尝试这样做的原因。 (见下文。)

某些表达的“歧义”问题主要是一个红鲱鱼。首先，歧义是特定语法的特征，而不是语言。即使一种语言可以被证明没有明确的语法，如果它可以被上下文无关的语法识别，它就是上下文无关的。同样，如果它不能被上下文无关文法识别但可以被上下文敏感文法识别，则它是上下文敏感的。歧义是不相关的。

但无论如何，就像下面程序中的第 21 行(即 auto b = foo<IsPrime<234799>>::typen<1>(); )一样，这些表达式完全没有歧义；它们只是根据上下文进行不同的解析。在这个问题的最简单表达中，某些标识符的句法类别取决于它们的声明方式(例如类型和函数)，这意味着形式语言必须认识到以下事实:两个任意长度的字符串在相同的程序是相同的(声明和使用)。这可以通过“复制”语法建模，该语法识别同一个单词的两个连续的精确拷贝。用 pumping lemma 很容易证明这种语言不是上下文无关的。该语言的上下文相关语法是可能的，并且在此问题的答案中提供了 Type-0 语法:https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .

如果有人试图编写一种上下文敏感(或不受限制)的语法来解析 C++，它很可能会用涂鸦填满整个宇宙。编写一个图灵机来解析 C++ 将是一项同样不可能的任务。即使编写 C++ 程序也很困难，据我所知，没有一个被证明是正确的。这就是为什么该标准不尝试提供完整的形式语法，以及为什么它选择用技术英语编写一些解析规则的原因。

在 C++ 标准中看起来像正式语法的东西并不是 C++ 语言语法的完整正式定义。它甚至不是预处理后语言的完整正式定义，这可能更容易形式化。 (不过，这不是语言:标准定义的 C++ 语言包括预处理器，并且预处理器的操作是通过算法描述的，因为在任何语法形式主义中都很难描述。它在该部分描述词法分解的标准，包括必须多次应用的规则。)

附录 A 中收集了各种语法(用于词法分析的两种重叠语法，一种发生在预处理之前，另一种在必要时在处理之后加上“句法”语法)，并附有以下重要说明(强调):

This summary of C++ syntax is intended to be an aid to comprehension. It is not an exact statement of the language. In particular, the grammar described here accepts a superset of valid C++ constructs. Disambiguation rules (6.8, 7.1, 10.2) must be applied to distinguish expressions from declarations. Further, access control, ambiguity, and type rules must be used to weed out syntactically valid but meaningless constructs.

最后，这是 promise 的程序。当且仅当 IsPrime<N> 中的 N 时，第 21 行在语法上是正确的是素数。否则，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)文法中，α和 β必须是空的。

事实证明，您还可以使用“单调”限制来限制语法，其中每个产生式都必须采用以下形式:
α → β哪里|α| ≥ |β| > 0 ( |α| 表示“α 的长度”)

可以证明单调文法识别的语言集与上下文相关文法识别的语言集完全相同，并且通常情况下，更容易基于单调文法进行证明。因此，经常会看到“上下文敏感”被用作“单调”的意思。