C++是无上下文还是上下文敏感？

Question

我经常听到C++是一种上下文敏感语言的说法.请看以下示例:

a b(c);

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

如果您查找无上下文语言的定义,它基本上会告诉您所有语法规则必须具有仅由一个非终端符号组成的左侧.另一方面,上下文敏感语法允许左侧的任意字符串的终端和非终端符号.

浏览"C++编程语言"的附录A,除了左侧的单个非终端符号之外,我找不到单个语法规则.这意味着C++是无上下文的.(当然,在无上下文语言形成上下文敏感语言的子集的意义上,每种无上下文语言也都是上下文敏感的,但这不是重点.)

那么,C++是无上下文还是上下文敏感？

Answer 1

下面是我(当前)最喜欢的解释为什么解析C++(可能)Turing-complete,因为它显示了一个语法正确的程序,当且仅当给定的整数是素数时.

所以我断言C++既不是上下文也不是上下文敏感的.

如果在任何作品的两边允许任意符号序列,则在Chomsky层次结构中生成Type-0语法("unrestricted"),这比语境敏感语法更强大; 不受限制的语法是图灵完备的.上下文敏感(Type-1)语法允许生产左侧的多个上下文符号,但相同的上下文必须出现在生产的右侧(因此名称为"上下文相关").[1]上下文相关语法相当于线性有界图灵机.

在示例程序中,素数计算可以由线性有界图灵机执行,因此它不能完全证明图灵等价,但重要的是解析器需要执行计算才能执行句法分析.它可以是任何可表示为模板实例化的计算,并且有充分的理由相信C++模板实例化是图灵完备的.例如,参见Todd L. Veldhuizen的2003年论文.

无论如何,C++可以被计算机解析,因此它可以被图灵机解析.因此,不受限制的语法可以识别它.实际上写这样的语法是不切实际的,这就是为什么标准不试图这样做的原因.(见下文.)

某些表达方式的"含糊不清"问题主要是一个红色的鲱鱼.首先,歧义是特定语法的一个特征,而不是语言.即使一种语言可以证明没有明确的语法,如果它可以通过无上下文语法识别,那么它就是无上下文的.类似地,如果无法通过无上下文语法识别它,但它可以被上下文敏感语法识别,则它是上下文敏感的.歧义是无关紧要的.

但无论如何,如auto b = foo<IsPrime<234799>>::typen<1>();下面的程序中的第21行(即),表达式根本不含糊; 它们只是根据上下文进行不同的解析.在问题的最简单表达中,某些标识符的语法类别取决于它们的声明方式(例如,类型和函数),这意味着形式语言必须识别两个任意长度的字符串相同的程序是相同的(声明和使用).这可以通过"复制"语法建模,该语法是识别同一个单词的两个连续精确副本的语法.用抽象引理证明这种语言不是无上下文的.这种语言的上下文敏感语法是可能的,在这个问题的答案中提供了一个0型语法:https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-复制语言.

如果一个人试图编写一个上下文敏感(或不受限制)的语法来解析C++,它很可能会填满整个世界的涂鸦.编写图灵机来解析C++也是一项同样不可能完成的任务.即使编写C++程序也很困难,据我所知,没有一个被证明是正确的.这就是为什么标准不试图提供完整的正式语法,以及为什么它选择用技术英语编写一些解析规则的原因.

看起来像C++标准中的形式语法并不是C++语言语法的完整形式定义.它甚至不是预处理后语言的完整形式定义,这可能更容易形式化.(但这不是语言:标准定义的C++语言包括预处理器,预处理器的操作是通过算法描述的,因为在任何语法形式中都难以描述.它在那个部分描述词汇分解的标准,包括必须多次应用的规则.)

各种语法(用于词法分析的两个重叠语法,一个在预处理之前发生,另一个在必要时,之后发生,加上"句法"语法)收集在附录A中,这个重要说明(重点补充):

这个C++语法的摘要旨在帮助理解.它不是语言的确切陈述.特别是,这里描述的语法接受有效C++构造的超集.必须应用消歧规则(6.8,7.1,10.2)来区分表达式和声明.此外,必须使用访问控制,歧义和类型规则来清除语法上有效但无意义的结构.

最后,这是承诺的计划.当且仅当N in IsPrime<N>是素数时,第21行在语法上是正确的.否则,typen是整数,而不是模板,因此typen<1>()解析为(typen<1)>()语法不正确,因为()它不是语法上有效的表达式.

template<bool V> struct answer { answer(int) {} bool operator()(){return V;}};

template<bool no, bool yes, int f, int p> struct IsPrimeHelper
  : IsPrimeHelper<p % f == 0, f * f >= p, f + 2, p> {};
template<bool yes, int f, int p> struct IsPrimeHelper<true, yes, f, p> { using type = answer<false>; };
template<int f, int p> struct IsPrimeHelper<false, true, f, p> { using type = answer<true>; };

template<int I> using IsPrime = typename IsPrimeHelper<!(I&1), false, 3, I>::type;
template<int I>
struct X { static const int i = I; int a[i]; }; 

template<typename A> struct foo;
template<>struct foo<answer<true>>{
  template<int I> using typen = X<I>;
};
template<> struct foo<answer<false>>{
  static const int typen = 0;
};

int main() {
  auto b = foo<IsPrime<234799>>::typen<1>(); // Syntax error if not prime
  return 0;
}

[1]更具技术性,上下文敏感语法中的每个产品必须具有以下形式:

αAβ → αγβ

其中A是非终端的α,β并且可能是空的语法符号序列,并且γ是非空序列.(语法符号可以是终端或非终端).

这A → γ只能在上下文中阅读[α, β].在上下文无关(类型2)的语法,α并且β必须是空的.

事实证明,您还可以使用"单调"限制来限制语法,其中每个制作必须采用以下形式:

α → βwhere |α| ≥ |β| > 0  (|α|表示"长度α")

有可能证明单调语法识别的语言集与上下文敏感语法识别的语言集完全相同,并且通常情况下,单调语法的校对更容易.因此,使用"上下文敏感"就好像它意味着"单调"一样.

Answer 2

首先,您正确地观察到C++标准末尾的语法中没有上下文敏感规则,因此语法是无上下文的.

但是,该语法并没有精确地描述C++语言,因为它产生非C++程序,如

int m() { m++; }

要么

typedef static int int;

定义为"一组结构良好的C++程序"的C++语言不是无上下文的(可以证明只需要声明要求的变量就可以了).鉴于理论上你可以在模板中编写图灵完备程序,并根据结果使程序格式不正确,它甚至不是上下文敏感的.

现在,(无知)人(通常不是语言理论家,但解析器设计者)通常使用"不具有上下文"的某些含义

• 暧昧
• 无法用Bison解析
• 不是LL(k),LR(k),LALR(k)或他们选择的任何解析器定义的语言类

标准背面的语法不满足这些类别(即它是模棱两可的,而不是LL(k)......)因此C++语法对它们来说"不具有上下文".从某种意义上说,他们是对的,很难生成一个可用的C++解析器.

请注意,这里使用的属性只是弱连接上下文无关语言 - 模棱两可没有任何与上下文相关做(其实,上下文相关的规则通常有助于区分作品),其他两个仅仅是背景的子集 - 免费语言.解析无上下文语言不是一个线性过程(虽然解析确定性语言).

Answer 3

是.以下表达式具有不同的操作顺序,具体取决于类型已解析的上下文:

编辑:当实际的操作顺序不同时,使用"常规"编译器在解析它(传播类型信息)之前解析为未修饰的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 );

Answer 4

要回答您的问题,您需要区分两个不同的问题.

1. 几乎所有编程语言的语法都是无上下文的.通常,它是作为扩展的Backus-Naur形式或无上下文的gramar给出的.

2. 但是,即使程序符合编程语言定义的无上下文gramar,它也不一定是有效的程序.程序必须满足许多非上下文无关的特性才能成为有效的程序.例如,最简单的这种属性是变量的范围.

总而言之,C++是否无上下文取决于您提出的问题.

Answer 5

您可能想看看Bjarne Stroustrup撰写的C++设计与演变.在其中,他描述了他试图使用yacc(或类似)来解析早期版本的C++并希望他使用递归下降的问题.

Answer 6

是的C++是上下文敏感的,非常上下文敏感.您无法通过使用上下文无关解析器解析文件来构建语法树,因为在某些情况下,您需要知道先前知识中的符号来决定(即在解析时构建符号表).

第一个例子:

A*B;

这是一个乘法表达式吗？

要么

这是B变量的声明是一个类型的指针A吗？

如果A是变量,那么它是一个表达式,如果A是类型,它是一个指针声明.

第二个例子:

A B(bar);

这是一个采用bar类型参数的函数原型吗？

要么

这是声明B类型的变量,A并使用bar常量作为初始化器调用A的构造函数吗？

您需要再次知道bar符号表中的变量还是类型.

第三个例子:

class Foo
{
public:
    void fn(){x*y;}
    int x, y;
};

这是构建符号表时的情况,而解析没有帮助,因为x和y的声明在函数定义之后.所以你需要首先扫描类定义,然后在第二遍中查看方法定义,告诉x*y是一个表达式,而不是指针声明或其他什么.

Answer 7

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

看,也

为什么C++无法使用LR(1)解析器进行解析？

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

int x;
x = 9 + 1.0;

您无法使用无上下文语法描述以下规则: 分配的右侧应与左手侧的类型相同.

Answer 8

我感觉在"上下文敏感"的正式定义与"上下文敏感"的非正式使用之间存在一些混淆.前者具有明确的含义.后者用于说"你需要上下文来解析输入".

这里也会问: 上下文敏感度与歧义.

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

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

它是模糊的,所以为了解析输入"x"你需要一些上下文(或者带有模糊性,或者发出"警告:E8271 - 输入在第115行中是模糊的").但它肯定不是一个上下文敏感的语法.

Answer 9

没有类似Algol的语言是无上下文的,因为它们具有限制表达式和语句可以根据其类型出现的规则,并且因为声明和使用之间可能出现的语句数量没有限制.

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

由于其图灵完整的模板系统,C++远远超出了这个范围.请参阅堆栈溢出问题794015.

Answer 10

是的:)

斯坦利·沃福德（J. Stanley Warford）。计算机系统。341-346页。

Answer 11

有时更糟：人们说 C++ 有“不可判定的语法”是什么意思？

Answer 12

它是上下文敏感的，因为它a b(c);具有两个有效的解析器-声明和变量。当您说“ If cis a type”时，就在上下文中，并且您已经准确地描述了C ++对它的敏感程度。如果您没有“什么是c？”的上下文，您无法明确地对此进行解析。

在这里，上下文以令牌的选择表示-解析器读取一个标识符，如果它为类型命名，则作为类型名令牌。这是最简单的解决方案，并且避免了上下文相关的大部分复杂性（在这种情况下）。

编辑：当然，还有更多的上下文敏感性问题，我只关注您所展示的问题。模板对此尤其讨厌。

Answer 13

C ++标准中的产品是在没有上下文的情况下编写的，但是众所周知，实际上并没有精确定义该语言。大多数人认为当前语言中的歧义可以通过上下文相关的语法得到明确解决。

对于最明显的示例，让我们考虑“最令人烦恼的解析”：int f(X);。如果X为，则将其定义f为将使用初始化的变量X。如果X为type，则将其定义f为采用type的单个参数的函数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。

Answer 14

最简单的非上下文语法包括解析涉及模板的表达式.

a<b<c>()

这可以解析为

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

要么

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

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