下面是我(当前)最喜欢的演示为什么解析 C++ 是(可能)图灵完备的,因为它显示了一个程序在语法上是正确的,当且仅当给定整数是素数时。
所以我断言C++ 既不是 context-free 也不是 context-sensitive。
如果在任何产生式的两边都允许任意符号序列,则在Chomsky 层次结构中产生一个 Type-0 语法(“无限制”) ,它比上下文相关语法更强大;不受限制的文法是图灵完备的。上下文相关(Type-1)语法允许在产生式的左侧出现多个上下文符号,但相同的上下文必须出现在产生式的右侧(因此名称为“上下文敏感”)。[1] 上下文相关文法等价于线性有界图灵机。
在示例程序中,素数计算可以由线性有界图灵机执行,因此它并不能完全证明图灵等价,但重要的部分是解析器需要执行计算才能执行句法分析。它可以是任何可表示为模板实例化的计算,并且完全有理由相信 C++ 模板实例化是图灵完备的。例如,参见Todd L. Veldhuizen 2003 年的论文。
无论如何,C++ 可以被计算机解析,所以它当然可以被图灵机解析。因此,不受限制的语法可以识别它。实际上编写这样的语法是不切实际的,这就是标准不尝试这样做的原因。(见下文。)
某些表达的“歧义”问题主要是红鲱鱼。首先,歧义是特定语法的特征,而不是语言。即使可以证明一种语言没有明确的语法,如果它可以被上下文无关语法识别,它就是上下文无关的。同样,如果它不能被上下文无关文法识别,但可以被上下文相关文法识别,则它是上下文相关的。模棱两可无关紧要。
但无论如何,就像auto b = foo<IsPrime<234799>>::typen<1>();
下面程序中的第 21 行(即 )一样,表达式一点也不含糊;它们只是根据上下文进行不同的解析。在这个问题的最简单表达中,某些标识符的句法类别取决于它们的声明方式(例如类型和函数),这意味着形式语言必须认识到两个任意长度的字符串在相同的程序是相同的(声明和使用)。这可以通过“复制”语法来建模,该语法是识别同一单词的两个连续精确副本的语法。用抽水引理很容易证明这种语言不是上下文无关的。该语言的上下文敏感语法是可能的,并且在此问题的答案中提供了 Type-0 语法:https ://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-复制语言。
如果有人试图编写一种上下文相关(或不受限制)的语法来解析 C++,它很可能会用乱七八糟的东西填满整个宇宙。编写图灵机来解析 C++ 将是同样不可能的任务。甚至编写 C++ 程序也很困难,据我所知,没有一个被证明是正确的。这就是为什么该标准不尝试提供完整的形式语法,以及为什么它选择用技术英语编写一些解析规则的原因。
在 C++ 标准中看起来像形式语法的东西并不是 C++ 语言语法的完整形式定义。它甚至不是预处理后语言的完整正式定义,这可能更容易形式化。(不过,这不是语言:标准定义的 C++ 语言包括预处理器,并且预处理器的操作是用算法描述的,因为它很难用任何语法形式来描述。它在那个部分描述词法分解的标准,包括必须多次应用的规则。)
各种文法(用于词法分析的两种重叠文法,一种在预处理之前进行,另一种在必要时在之后进行,加上“句法”文法)收集在附录 A 中,并附有重要说明(添加了重点):
此 C++ 语法摘要旨在帮助理解。这不是语言的准确表述。特别是,此处描述的语法接受有效 C++ 构造的超集。必须应用消歧规则(6.8、7.1、10.2)来区分表达式和声明。此外,必须使用访问控制、歧义和类型规则来清除语法上有效但无意义的结构。
最后,这是承诺的程序。当且仅当 N inIsPrime<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
(|α|
表示“的长度α
”)
可以证明单调文法所识别的语言集与上下文相关文法所识别的语言集完全相同,而且通常更容易将证明建立在单调文法的基础上。因此,将“上下文敏感”视为“单调”的意思是很常见的。