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

a b(c);

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

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

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

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


当前回答

这里的一个大问题是术语“上下文无关”和“上下文敏感”在计算机科学中有点不直观。对于c++,上下文敏感性看起来很像歧义,但在一般情况下不一定是这样。

在C/ c++中,if语句只允许在函数体中使用。这似乎是上下文敏感的,对吧?嗯,没有。与上下文无关的语法实际上不需要这样的属性,即您可以提取某一行代码并确定它是否有效。这实际上并不是context-free的意思。它实际上只是一个标签,模糊地暗示了一些与它的发音相关的东西。

现在,如果函数体中的语句根据直接语法祖先之外的定义而被不同地解析(例如,标识符是描述类型还是变量),如a * b;大小写,那么它实际上是上下文敏感的。这里没有实际的歧义;如果a是类型,则解析为指针声明,否则解析为乘法声明。

Being context-sensitive does not necessarily mean "hard to parse". C is actually not that hard because the infamous a * b; "ambiguity" can be resolved with a symbol table containing typedefs encountered previously. It doesn't require any arbitrary template instantiations (which have been proven to be Turing Complete) to resolve that case like C++ does on occasion. It's not actually possible to write a C program that will not compile in a finite amount of time even though it has the same context-sensitivity that C++ does.

Python (and other whitespace-sensitive languages) is also context-dependent, as it requires state in the lexer to generate indent and dedent tokens, but that doesn't make it any harder to parse than a typical LL-1 grammar. It actually uses a parser-generator, which is part of why Python has such uninformative syntax error messages. It's also important to note here that there is no "ambiguity" like the a * b; problem in Python, giving a good concrete example of a context-sensitive language without "ambiguous" grammar (as mentioned in the first paragraph).

其他回答

这里的一个大问题是术语“上下文无关”和“上下文敏感”在计算机科学中有点不直观。对于c++,上下文敏感性看起来很像歧义,但在一般情况下不一定是这样。

在C/ c++中,if语句只允许在函数体中使用。这似乎是上下文敏感的,对吧?嗯,没有。与上下文无关的语法实际上不需要这样的属性,即您可以提取某一行代码并确定它是否有效。这实际上并不是context-free的意思。它实际上只是一个标签,模糊地暗示了一些与它的发音相关的东西。

现在,如果函数体中的语句根据直接语法祖先之外的定义而被不同地解析(例如,标识符是描述类型还是变量),如a * b;大小写,那么它实际上是上下文敏感的。这里没有实际的歧义;如果a是类型,则解析为指针声明,否则解析为乘法声明。

Being context-sensitive does not necessarily mean "hard to parse". C is actually not that hard because the infamous a * b; "ambiguity" can be resolved with a symbol table containing typedefs encountered previously. It doesn't require any arbitrary template instantiations (which have been proven to be Turing Complete) to resolve that case like C++ does on occasion. It's not actually possible to write a C program that will not compile in a finite amount of time even though it has the same context-sensitivity that C++ does.

Python (and other whitespace-sensitive languages) is also context-dependent, as it requires state in the lexer to generate indent and dedent tokens, but that doesn't make it any harder to parse than a typical LL-1 grammar. It actually uses a parser-generator, which is part of why Python has such uninformative syntax error messages. It's also important to note here that there is no "ambiguity" like the a * b; problem in Python, giving a good concrete example of a context-sensitive language without "ambiguous" grammar (as mentioned in the first paragraph).

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

编辑:当实际操作顺序发生变化时,使用“常规”编译器在修饰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 );

有时情况更糟:当人们说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是一个表达式,而不是指针声明或其他东西。

我感觉在“上下文敏感”的正式定义和“上下文敏感”的非正式使用之间存在一些混淆。前者有明确的含义。后者用于表示“为了解析输入,您需要上下文”。

这里也有一个问题: 上下文敏感性vs模糊性。

这是一个与上下文无关的语法:

<a> ::= <b> | <c>
<b> ::= "x"
<c> ::= "x"

它是模棱两可的,所以为了解析输入“x”,你需要一些上下文(或者忍受这种模棱两可,或者发出“警告:E8271 - input is ambiguous in line 115”)。但它肯定不是上下文敏感的语法。