我经常听到有人说c++是一种上下文敏感的语言。举个例子:

a b(c);

这是变量定义还是函数声明?这取决于符号c的含义。如果c是一个变量,则ab (c);定义一个名为b的类型为a的变量。它直接用c初始化。但如果c是类型,则ab (c);声明一个名为b的函数,该函数接受c并返回a。

如果您查找上下文无关语言的定义,它基本上会告诉您,所有语法规则的左侧必须恰好包含一个非终结符。另一方面,上下文敏感语法允许在左侧使用任意的终结符和非终结符字符串。

浏览“c++程序设计语言”的附录A,我找不到一条语法规则,它的左边除了一个非终结符之外,还有其他任何东西。这意味着c++是上下文无关的。(当然,每一种与上下文无关的语言也是与上下文相关的,因为与上下文无关的语言构成了与上下文相关的语言的一个子集,但这不是重点。)

那么,c++是上下文无关的还是上下文敏感的?


当前回答

c++不是上下文无关的。我以前在编译器课上学过。快速搜索得到了这个链接,其中“语法或语义”部分解释了为什么C和c++不是上下文无关的:

维基百科演讲:上下文无关语法

眼神, Ovanes

其他回答

没有一种类algol语言是与上下文无关的,因为它们有规则约束表达式和语句,标识符可以根据它们的类型出现在这些表达式和语句中,并且因为在声明和使用之间可以出现的语句数量没有限制。

通常的解决方案是编写一个上下文无关的解析器,它实际上接受有效程序的超集,并将上下文敏感的部分放在附加到规则的特殊“语义”代码中。

c++的图灵完备模板系统远远超越了这一点。参见堆栈溢出问题794015。

首先,你正确地观察到c++标准末尾的语法中没有上下文敏感的规则,因此语法与上下文无关。

然而,这种语法并不能精确地描述c++语言,因为它生成的是非c++程序,例如

int m() { m++; }

or

typedef static int int;

c++语言被定义为“一组格式良好的c++程序”,它不是与上下文无关的(可以证明,仅仅要求声明变量就可以做到这一点)。理论上,您可以在模板中编写图灵完备程序,并根据其结果使程序具有病态形式,因此它甚至不是上下文敏感的。

现在,(无知的)人们(通常不是语言理论家,而是解析器设计者)通常在以下一些含义中使用“not context-free”

模棱两可的 不能用Bison解析 而不是LL(k) LR(k) LALR(k)或任何他们选择的解析器定义的语言类

标准后面的语法不满足这些类别(即它是模糊的,不是LL(k)…),所以c++语法对他们来说“不是上下文无关的”。从某种意义上说,他们是对的,要创建一个工作的c++解析器是非常困难的。

注意,这里使用的属性只与上下文无关的语言有微弱的联系——歧义与上下文无关没有任何关系(事实上,上下文敏感的规则通常有助于消除歧义),另外两个只是上下文无关语言的子集。解析与上下文无关的语言不是一个线性过程(尽管解析确定性语言是)。

非上下文无关语法最简单的例子是解析包含模板的表达式。

a<b<c>()

这可以解析为任意一种

template
   |
   a < expr > ()
        |
        <
      /   \
     b     c

Or

 expr
   |
   <
 /   \
a   template
     |
     b < expr > ()
          |
          c

这两个AST只能通过检查'a'的声明来消除歧义——如果'a'是模板,则前者为AST,如果'a'不是模板,则后者为AST。

c++不是上下文无关的。我以前在编译器课上学过。快速搜索得到了这个链接,其中“语法或语义”部分解释了为什么C和c++不是上下文无关的:

维基百科演讲:上下文无关语法

眼神, Ovanes

你可能想看看Bjarne Stroustrup写的《c++的设计与进化》。在这篇文章中,他描述了他在尝试使用yacc(或类似的)来解析早期版本的c++时遇到的问题,并希望他当时使用的是递归下降。