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

a b(c);

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

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

浏览“c++程序设计语言”的附录A,我找不到一条语法规则,它的左边除了一个非终结符之外,还有其他任何东西。这意味着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解析研究中使用了它。请注意,示例文件夹中包含的“伪结语法”是由一个非生物信息学的、成熟的程序员编写的,基本上不起作用。我的语法采用了一种不同的方法,而且效果很好。

其他回答

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

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

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

有时情况更糟:当人们说c++具有“不可判定语法”时,他们的意思是什么?

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

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

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

你可能想看看Bjarne Stroustrup写的《c++的设计与进化》。在这篇文章中,他描述了他在尝试使用yacc(或类似的)来解析早期版本的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,至少从通常使用的术语来看是这样的。