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

a b(c);

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

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

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

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


当前回答

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,至少从通常使用的术语来看是这样的。

其他回答

是的,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是一个表达式,而不是指针声明或其他东西。

使用GLR解析器解析c++。这意味着在解析源代码期间,解析器可能会遇到歧义,但它应该继续并决定稍后使用哪个语法规则。

还看,

为什么c++不能用LR(1)解析器解析?


请记住,上下文无关语法不能描述编程语言语法的所有规则。例如,属性语法用于检查表达式类型的有效性。

int x;
x = 9 + 1.0;

你不能用上下文无关的语法描述下面的规则: 作业的右侧应与左侧的类型相同。

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

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

Meta-S”是Quinn Tyler Jackson开发的上下文敏感解析引擎。我没有用过,但他讲了一个令人印象深刻的故事。在comp.compilers中查看他的评论,并查看rnaparse.com/MetaS%20defined.htm - Ira Baxter 7月25日10:42

正确的环节是解析谜题

Meta-S是一家已经倒闭的tho栖公司的财产。我可以将Meta-S的免费副本发送给任何感兴趣的人,我已经在rna解析研究中使用了它。请注意,示例文件夹中包含的“伪结语法”是由一个非生物信息学的、成熟的程序员编写的,基本上不起作用。我的语法采用了一种不同的方法,而且效果很好。

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

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