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

a b(c);

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

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

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

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


当前回答

c++模板已经被证明是图灵强大的。虽然不是正式的参考资料,但从这方面来看,我们可以从以下几个方面入手:

http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html

我大胆地猜测一下(古老的民间和简明的CACM证明表明,60年代的ALGOL不能用CFG表示),并说c++因此不能仅用CFG正确地解析。cfg与各种TP机制结合在一起,无论是在树通道还是在减少事件中——这是另一个故事。一般来说,由于停止问题,存在一些c++程序不能被证明是正确的/不正确的,但仍然是正确的/不正确的。

{PS-作为Meta-S的作者(上面有几个人提到过),我可以很肯定地说Thothic并没有消失,也不是免费的软件。也许我这样回答是为了不被删除或被投票降至-3。

其他回答

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

a<b<c>()

这可以解析为任意一种

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

Or

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

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

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

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

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

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

x = (name)(expression);

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

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

c++模板已经被证明是图灵强大的。虽然不是正式的参考资料,但从这方面来看,我们可以从以下几个方面入手:

http://cpptruths.blogspot.com/2005/11/c-templates-are-turing-complete.html

我大胆地猜测一下(古老的民间和简明的CACM证明表明,60年代的ALGOL不能用CFG表示),并说c++因此不能仅用CFG正确地解析。cfg与各种TP机制结合在一起,无论是在树通道还是在减少事件中——这是另一个故事。一般来说,由于停止问题,存在一些c++程序不能被证明是正确的/不正确的,但仍然是正确的/不正确的。

{PS-作为Meta-S的作者(上面有几个人提到过),我可以很肯定地说Thothic并没有消失,也不是免费的软件。也许我这样回答是为了不被删除或被投票降至-3。

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

正确的环节是解析谜题

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