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

a b(c);

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

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

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

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


当前回答

首先,你正确地观察到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++解析器是非常困难的。

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

其他回答

显然,如果逐字逐句地回答这个问题,几乎所有带有标识符的语言都是上下文敏感的。

一个人需要知道一个标识符是一个类型名(一个类名,一个由typedef引入的名字,一个typename模板参数),一个模板名还是其他一些名称,以便能够正确地使用标识符。例如:

x = (name)(expression);

如果name是类型名,则为类型转换;如果name是函数名,则为函数调用。另一种情况是所谓的“最恼人的解析”,其中不可能区分变量定义和函数声明(有一个规则说它是函数声明)。

这个困难引入了对typename和具有依赖名称的模板的需求。据我所知,c++的其余部分不是上下文敏感的(也就是说,可以为它编写上下文无关的语法)。

真正的:)

斯坦利·沃福德。计算机系统。页341 - 346。

它是上下文敏感的,如a b(c);有两个有效的解析-声明和变量。当你说“If c是一个类型”时,这就是上下文,就在那里,你已经准确地描述了c++对它的敏感程度。如果没有“c是什么?”的上下文,就无法明确地解析它。

在这里,上下文通过标记的选择来表示——如果标识符指定了类型,解析器将其读取为typename标记。这是最简单的解决方案,避免了上下文敏感的复杂性(在本例中)。

编辑:当然,还有更多的上下文敏感性问题,我只是关注你展示的那个。模板在这方面尤其糟糕。

要回答你的问题,你需要区分两个不同的问题。

几乎每一种编程语言的语法都与上下文无关。通常,它是作为扩展的Backus-Naur形式或上下文无关语法给出的。 然而,即使一个程序符合编程语言定义的上下文无关语法,它也不一定是一个有效的程序。为了成为一个有效的程序,程序必须满足许多与上下文无关的属性。例如,最简单的属性是变量的作用域。

综上所述,c++是否与上下文无关取决于你问的问题。

是的。下面的表达式根据解析的上下文类型有不同的操作顺序:

编辑:当实际操作顺序发生变化时,使用“常规”编译器在修饰AST(传播类型信息)之前解析未修饰的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 );