是C ++的上下文
我经常听到C ++是上下文敏感语言的说法。 以下面的例子：
a b(c);
这是一个变量定义还是函数声明？ 这取决于符号c的含义。 如果c是变量，则ab(c); 定义了一个名为b的变量a 。 它直接用c初始化。 但如果c是一个类型，那么ab(c); 声明一个名为b的函数，它接受一个c并返回一个a 。
如果你查找上下文无关语言的定义，它基本上会告诉你，所有的语法规则都必须有左侧包含一个非终端符号。 另一方面，上下文敏感的语法允许左侧的任意字符串的终端和非终端符号。
通过浏览“C ++编程语言”的附录A，我找不到一个单独的文法规则，它的左侧只有一个非终端符号。 这意味着C ++是上下文无关的。 （当然，上下文无关语言也是上下文敏感的，因为上下文无关语言构成上下文敏感语言的一个子集，但这不是重点。）
那么，C ++上下文无关或上下文敏感？
下面是我的（当前）最喜欢的演示，解释为什么解析C ++是（可能）图灵完整的，因为它显示了一个程序，当且仅当给定的整数是素数时，它在语法上是正确的。
所以我断言C ++既不是上下文自由的，也不是上下文敏感的 。
如果在任何生产的任何一边允许任意符号序列，则在乔姆斯基层次结构中生成一个类型0语法（“无限制”），该语法比上下文敏感语法更强大; 不受限制的语法是图灵完备的。 上下文相关（Type-1）语法允许在产品左侧的多个上下文符号，但是同一个上下文必须出现在产品的右侧（因此名称为“上下文相关”）。 [1]语境敏感的语法相当于线性界限的图灵机。
在示例程序中，主要计算可以由线性有界的图灵机执行，所以它不能很好地证明图灵等价性，但重要的部分是解析器需要执行计算以执行语法分析。 它可能是任何可作为模板实例化表达的计算，并且有充分的理由相信C ++模板实例化是图灵完备的。 例如，参见Todd L. Veldhuizen的2003年论文。
无论如何，C ++可以被计算机解析，所以它肯定可以被图灵机解析。 因此，一个不受限制的语法可以识别它。 实际上写这样的语法是不切实际的，这就是为什么标准没有这样做的原因。 （见下文。）
某些表达方式的“模棱两可”问题大多是红鲱鱼。 首先，歧义是特定语法的一个特征，而不是语言。 即使一种语言可以被证明没有明确的语法，但如果它可以被上下文无关的语法识别，那么它就是上下文无关的。 同样，如果无法通过上下文无关语法识别它，但它可以通过上下文敏感语法识别，则它是上下文敏感的。 歧义不相关。
但无论如何，像下面的程序中的第21行（即auto b = foo<IsPrime<234799>>::typen<1>(); ），表达式根本auto b = foo<IsPrime<234799>>::typen<1>(); ; 根据上下文简单地对它们进行解析。 在这个问题的最简单表达中，某些标识符的语法类别取决于它们是如何被声明的（例如类型和函数），这意味着形式语言必须认识到两个任意长度的字符串相同的程序是相同的（声明和使用）。 这可以通过“复制”语法来模拟，该语法是识别同一单词的两个连续精确副本的语法。 抽象引理证明这种语言不是上下文无关的，这很容易证明。 这种语言的上下文敏感语法是可能的，并且在这个问题的答案中提供了0型语法：https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-the-复制语言。
如果有人试图编写一个上下文敏感的（或不受限制的）语法来解析C ++，它很可能会用涂鸦填充整个宇宙。 编写一个图灵机来解析C ++将是一项同样不可能的任务。 即使编写一个C ++程序也很困难，据我所知，没有一个证明是正确的。 这就是为什么标准没有提供完整的形式语法，以及为什么它选择在技术英语中编写一些解析规则。
看起来像C ++标准中的形式语法不是C ++语言语法的完整正式定义。 它甚至不是预处理后语言的完整正式定义，这可能更容易形式化。 （但这不是语言：由标准定义的C ++语言包括预处理器，并且预处理器的操作在算法上被描述，因为在任何语法形式中描述都是非常困难的，在该部分在描述词法分解的标准中，包括必须多次应用的规则。）
在附录A中收集了各种语法（词法分析中的两个重叠语法，其中一个在预处理之前发生，另一个在必要时发生，然后再加上“语法”语法），附有这个重要注释（强调增加）：
C ++语法的总结旨在帮助理解。 这不是语言的确切说明。 特别是，这里描述的语法接受有效C ++结构的超集。 必须应用消歧规则（6.8,7.1,10.2）来区分表达式和声明。 此外，必须使用访问控制，模糊性和类型规则来清除语法上有效但无意义的构造。
最后，这是承诺的计划。 当且仅当IsPrime<N>中的IsPrime<N>是素数时，第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 → γ A → γ仅在上下文[α, β] 。 在上下文无关的（类型2）语法中， α和β必须是空的。
事实证明，您还可以将语法限制为“单调”限制，每个生产必须具有以下形式：
α → β α → β其中|α| ≥ |β| > 0 |α| ≥ |β| > 0 |α| ≥ |β| > 0 （ |α|表示“ α的长度”）
有可能证明由单调语法识别的语言集合与由语境敏感语法识别的语言集合完全相同，并且通常情况下，在单调语法基础上更容易进行证明。 因此，将“上下文相关”用作“单调”意义相当普遍。
首先，你正确地观察到在C ++标准结尾的语法中没有上下文敏感的规则，所以语法是上下文无关的。
但是，该语法没有精确地描述C ++语言，因为它产生非C ++程序，如
int m() { m++; }
要么
typedef static int int;
被定义为“一组格式良好的C ++程序”的C ++语言不是上下文无关的（可以证明只需要声明要求变量的变量就可以）。 鉴于理论上可以在模板中编写图灵完整程序，并根据其结果制定不合格的程序，它甚至不会对上下文敏感。
现在，（无知的）人（通常不是语言理论家，但是解析器设计者）通常在以下某些含义中使用“不含上下文”
标准后面的语法不符合这些类别（即它不明确，而不是LL（k）...），因此C ++语法对他们来说“没有上下文”。 从某种意义上说，它们是正确的，生成一个可用的C ++解析器非常困难。
请注意，这里使用的属性只与上下文无关语言弱相关 - 模糊与上下文敏感没有任何关系（事实上，上下文敏感的规则通常有助于消除生成歧义），另外两个仅仅是上下文的子集免费语言。 解析上下文无关语言不是一个线性过程（尽管解析确定性语言）。
是。 以下表达式具有不同的操作顺序，具体取决于解析上下文的类型：
编辑：当操作的实际顺序不同时，它使得使用“常规”编译器难以置信地困难，该编译器在对其进行装饰之前解析为未修饰的AST（传播类型信息）。 与此相比，提及的其他上下文相关的事情“相当容易”（不是简单的模板评估）。
#if FIRST_MEANING
template<bool B>
class foo
{ };
#else
static const int foo = 0;
static const int bar = 15;
#endif
其次是：
static int foobar( foo < 2 ? 1 < 1 : 0 > & bar );
上一篇: Is C++ context
下一篇: How to execute a command and get output of command within C++ using POSIX?