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++可以由计算机解析，因此可以肯定地可以由Turing机器解析。因此，无限制的语法可以识别它。实际上编写这样的语法是不切实际的，这就是为什么该标准不尝试这样做的原因。 (见下文。)

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

但是无论如何，就像下面程序中的第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( |α|表示“ α的长度”)

有可能证明单调语法可以识别的语言集与上下文敏感语法可以识别的语言集完全相同，并且通常情况下，更容易将证明基于单调语法。因此，看到“上下文敏感”似乎意味着“单调”是很常见的。