C ++上下文无关或上下文无关文法?

  • 回答 (2)
  • 关注 (0)
  • 查看 (580)

我经常听到C ++是一种上下文敏感语言的说法。以下面的例子:

a b(c);

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

如果你查找上下文无关语言的定义,它将基本上告诉你,所有的语法规则都必须包含一个只包含一个非终结符号的左边。另一方面,上下文敏感的语法允许在左侧的任意字符串的终端和非终端符号。

通过浏览“C ++编程语言”的附录A,我找不到一个单独的文法规则,除了左边的一个非终端符号之外,还有其他的东西。这意味着C ++是上下文无关的。(当然,上下文无关语言也是上下文敏感的,上下文无关语言构成上下文敏感语言的一个子集,但这不是重点。)

那么,C ++是上下文无关的还是上下文有关文法?

Lonely永夜Lonely永夜提问于
无心道人道可道 非常道 名可名 非常名回答于

对C++不是很熟悉,所以后面的讨论会局限在C语言的范畴内。后面提到的东西放到C++里估计就会错一堆了。首先,C语言的文法中确实存在上下文相关的部分。我照着文法看了半天,只找到了typedef会带来上下文相关的问题,不知道还有没有别的地方也有……如果有的话欢迎补充。回归正题。首先题主说的函数先声明再使用,这个不是语法层面上的上下文相关。语法的作用是看句子是否符合某些给定的规则。语法层面的上下文相关是指,在判断一个句子是否符合某个规则时,需要这个句子之外的额外信息来进行判断。不考虑typedef的话,给一个函数声明的句子,我们总是能根据规则和输入的句子本身是不是一个合法的函数声明而不需要知道额外的信息,那么这样就算是上下文无关。题主所认为的上下文相关实际上是语义的上下文相关。再说说C文法里上下文相关的事。再次强调,这里的上下文相关是语法上的上下文相关,即判断一个句子是否符合某规则时需要额外的信息。有了typedef的话,c的类型和标识符就可能一样了,这就是冲突的根源。比如,a*b这个,在上文是typedef struct {} a的情况下,这个句子就会符合指针定义的规则。如果上文是int a, b,那么这个句子就是一个语句了。最后放上一个不太确定的猜测,欢迎讨论:如果去除了typedef,那么C的文法应该是上下文无关的

人生的旅途辣鸡前端回答于

首先,你正确地观察到在C ++标准结尾的语法中没有上下文敏感的规则,所以语法是上下文无关的。

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

int m() { m++; }

要么

typedef static int int;

被定义为“一组格式良好的C ++程序”的C ++语言不是上下文无关的(可以证明只需要声明要求的变量就可以)。考虑到理论上你可以在模板中编写图灵完整的程序,并根据其结果编写一个不合格的程序,它甚至不是上下文敏感的。

现在,(无知的)人(通常不是语言理论家,但是解析器设计者)通常在下面的一些含义中使用“没有上下文的”

而不是LL(k),LR(k),LALR(k)或他们选择的任何语法分析器定义的语言类

在标准背后的语法不符合这些类别(即不明确,而不是LL(k)...),所以C ++语法对于他们来说“没有上下文”。从某种意义上说,它们是正确的,生成一个可用的C ++解析器是非常困难的。

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

扫码关注云+社区

领取腾讯云代金券