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

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

a b(c);

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

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

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

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

当前回答

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

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

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

其他回答

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>()

这可以解析为任意一种

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

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

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

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

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

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

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

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

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

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

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

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

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

推荐文章