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

a b(c);

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

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

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

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


当前回答

是的,c++是上下文敏感的,非常上下文敏感。您不能通过使用上下文无关的解析器简单地解析文件来构建语法树,因为在某些情况下,您需要从以前的知识中了解符号来决定(例如。在解析时构建一个符号表)。

第一个例子:

A*B;

这是一个乘法表达式吗?

OR

这是B变量作为a类型指针的声明吗?

如果A是一个变量,那么它就是一个表达式,如果A是类型,它就是一个指针声明。

第二个例子:

A B(bar);

这是一个函数原型接受一个条形参数吗?

OR

这是声明A类型的变量B,并调用A的构造函数和bar常量作为初始化式吗?

您需要再次了解bar是符号表中的变量还是类型。

第三个例子:

class Foo
{
public:
    void fn(){x*y;}
    int x, y;
};

当解析时构建符号表没有帮助时,就是这种情况,因为x和y的声明在函数定义之后。因此,您需要首先浏览类定义,然后在第二步查看方法定义,以确定x*y是一个表达式,而不是指针声明或其他东西。

其他回答

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

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

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

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

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

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

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

a<b<c>()

这可以解析为任意一种

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

Or

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

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

c++标准中的结果是与上下文无关的,但正如我们所知,它并没有真正精确地定义语言。大多数人认为当前语言中的一些歧义可以(我相信)用上下文敏感的语法明确地解决。

对于最明显的例子,让我们考虑最恼人的解析:int f(X);。如果X是一个值,那么它将f定义为一个将用X初始化的变量。如果X是一个类型,它将f定义为一个接受单个类型X形参的函数。

从语法的角度来看,我们可以这样看:

A variable_decl ::= <type> <identifier> '(' initializer ')' ';'

B function_decl ::= <type> <identifier> '(' param_decl ')' ';'

A ::= [declaration of X as value]
B ::= [declaration of X as type]

当然,为了完全正确,我们需要添加一些额外的“东西”来解释其他类型的介入声明的可能性(即,A和B都应该是“声明,包括将X声明为…”,或者类似的顺序)。

这与典型的CSG还是有很大不同的(至少在我印象中是这样)。这取决于正在构造的符号表——即专门将X识别为类型或值的部分,而不仅仅是前面的某些语句类型,而是正确的符号/标识符的正确语句类型。

因此,我必须做一些研究来确定,但我的直接猜测是,这并不是真正的CSG,至少从通常使用的术语来看是这样的。

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

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

x = (name)(expression);

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

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