我经常听到声称C是一种上下文敏感的语言 . 采用以下示例:
a b(c);
这是变量定义还是函数声明?这取决于符号 c
的含义 . 如果 c
是变量,则 a b(c);
定义名为 b
的变量 a
. 它用 c
直接初始化 . 但是如果 c
是一个类型,则 a b(c);
声明一个名为 b
的函数,该函数接受 c
并返回 a
.
如果您查找无上下文语言的定义,它基本上会告诉您所有语法规则必须具有由一个非终端符号组成的左侧 . 另一方面,上下文敏感语法允许左侧的任意字符串的终端和非终端符号 .
浏览“C编程语言”的附录A,我找不到单个语法规则,除了左侧的单个非终端符号之外还有其他任何东西 . 这意味着C是无上下文的 . (当然,在无上下文语言形成上下文敏感语言的子集的意义上,每种无上下文语言也都是上下文敏感的,但这不是重点 . )
那么,C是无上下文还是上下文敏感?
19 回答
你可能想看看Bjarne Stroustrup的The Design & Evolution of C++ . 在其中,他描述了他试图使用yacc(或类似)来解析C的早期版本并希望他使用递归下降的问题 .
要回答您的问题,您需要区分两个不同的问题 .
几乎所有编程语言的语法都是无上下文的 . 通常,它是作为扩展的Backus-Naur形式或无上下文的gramar给出的 .
但是,即使程序符合编程语言定义的无上下文gramar,它也不一定是有效的程序 . 程序必须满足许多非上下文无关的特性才能成为有效的程序 . 例如,最简单的这种属性是变量的范围 .
总而言之,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 . }
最简单的非上下文语法包括解析涉及模板的表达式 .
这可以解析为
要么
这两个AST只能通过检查'a'的声明来消除歧义 - 前者AST如果'a'是模板,或者后者,如果不是 .
首先,您正确地观察到C语言末尾的语法中没有上下文敏感规则,因此语法是无上下文的 .
但是,该语法并没有精确地描述C语言,因为它产生非C程序,如
要么
被定义为“一组格式良好的C程序”的C语言不是无上下文的(可以证明只需要声明的要求变量就是这样) . 理论上,你可以在模板中编写图灵完备程序,并根据结果使程序格式不正确,它甚至不是上下文敏感的 .
现在,(无知)人(通常不是语言理论家,但解析器设计者)通常使用“不具有上下文”的某些含义
含糊不清
无法用Bison解析
不是LL(k),LR(k),LALR(k)或他们选择的任何解析器定义的语言类
标准背面的语法不满足这些类别(即它是模糊的,而不是LL(k)......)因此C语法对它们来说“不是无上下文” . 从某种意义上说,他们是对的,很难生成一个有效的C解析器 .
请注意,此处使用的属性仅与上下文无关语言微弱关联 - 模糊性与上下文敏感性无关(事实上,上下文敏感规则通常有助于消除歧义生成),其他两个仅仅是上下文的子集 - 免费语言 . 解析无上下文语言不是一个线性过程(虽然解析确定性语言) .
正确的链接是parsing enigines
元-S是一家名为Thothic的已解散公司的 property . 我可以向任何感兴趣的人发送Meta-S的免费副本,我在rna解析研究中使用过它 . 请注意,示例文件夹中包含的“pseudoknot语法”是由非生物信息学,不成熟的程序员编写的,基本上不起作用 . 我的语法采用不同的方法,并且工作得很好 .
C标准中的作品是无上下文的,但我们都知道并没有真正定义语言 . 大多数人认为当前语言中含糊不清的一些内容可以(我相信)通过上下文敏感语法明确地解决 .
对于最明显的例子,让我们考虑最令人烦恼的解析:
int f(X);
. 如果X
是一个值,则将f
定义为将使用X
初始化的变量 . 如果X
是一个类型,它将f
定义为采用X
类型的单个参数的函数 .从语法的角度来看,我们可以这样看:
当然,为了完全正确,我们需要添加一些额外的“东西”来说明干预其他类型声明的可能性(即,A和B都应该是“声明包括声明X为......”)或者那个订单上的东西) .
这仍然与典型的CSG有所不同(或者至少我记得它们) . 这取决于正在构造的符号表 - 特别将
X
识别为类型或值的部分,而不仅仅是此前的某种语句类型,而是正确的符号/标识符的正确语句类型 .因此,我必须做一些寻找确定,但我的直接猜测是,这并不真正有资格作为CSG,至少通常使用该术语 .
This answer says C++ is not context-free...那里有's an implication (not by the answerer) that it can'解析,答案提供了一个困难的代码示例,如果某个常量不是素数,则产生无效的C程序 .
正如其他人所观察到的,关于语言是否是上下文敏感/自由的问题与关于特定语法的相同问题不同 .
为了设置关于可解析性的问题,我提供了经验证据,证明C语句有无上下文语法,可以用来为源文本的无上下文解析生成AST,实际上用现有的GLR解析它基于分析器的工具,由显式语法驱动 .
是的,它成功地“接受了太多”;并不是它接受的一切都是有效的C程序,这就是为什么它会跟进额外的检查(类型检查) . 是的,类型检查器可能会遇到可计算性问题 . 在实践中,工具没有这个问题;如果人们写这样的程序,他们都不会编译 . (我认为标准实际上限制了你可以展开模板的计算量,所以实际上计算实际上是有限的,但可能非常大) .
如果你的意思是,确定源程序是否是一组有效的C源程序的成员,那么我将同意这个问题要困难得多 . 但它解析不是问题所在 .
该工具通过将解析与类型检查解析的程序隔离来解决此问题 . (如果在没有上下文的情况下有多种解释,它会在解析树中记录一个含有几个可能的解析的歧义节点;类型检查决定哪一个是正确的并消除了无效的子树) . 您可以在下面的示例中看到(部分)解析树;整棵树太大了,不适合SO答案 . 请注意,无论使用值234797还是234799,您都会获得解析树 .
在AST上运行工具的名称/类型解析器,原始值为234799成功 . 使用值234797,名称解析程序失败(按预期方式),并显示错误消息“typen不是类型” . 因此该版本不是有效的C程序 .
没有类似Algol的语言是无上下文的,因为它们具有限制表达式和语句可以根据其类型出现的规则,并且因为声明和使用之间可能出现的语句数量没有限制 .
通常的解决方案是编写一个无上下文的解析器,它实际上接受有效程序的超集,并将上下文相关的部分放在附加到规则的ad hoc "semantic"代码中 .
由于其图灵完整的模板系统,C远远超出了这个范围 . 见Stack Overflow Question 794015 .
下面是我(当前)最喜欢的解释为什么解析C(可能)Turing-complete的演示,因为它显示了一个语法正确的程序,当且仅当给定的整数是素数时 .
所以我断言 C++ is neither context-free nor context-sensitive .
如果在任何产品的两边允许任意符号序列,则在Chomsky hierarchy中产生一个Type-0语法("unrestricted"),它比上下文敏感语法更强大;不受限制的语法是图灵完备的 . 上下文敏感(Type-1)语法允许在a的左侧有多个上下文符号 生产环境 ,但相同的上下文必须出现在 生产环境 的右侧(因此名称"context-sensitive") . [1]上下文相关语法相当于linear-bounded Turing machines .
在示例程序中,素数计算可以由线性有界图灵机执行,因此它不能完全证明图灵等价,但重要的是解析器需要执行计算才能执行句法分析 . 它可以是任何可表示为模板实例化的计算,并且有充分的理由相信C模板实例化是图灵完备的 . 例如,见Todd L. Veldhuizen's 2003 paper .
无论如何,C可以由计算机解析,因此它当然可以由图灵机解析 . 因此,不受限制的语法可以识别它 . 实际上写这样的语法是不切实际的,这就是为什么标准不试图这样做的原因 . (见下文 . )
某些表达方式的“含糊不清”问题主要是一个红色的鲱鱼 . 首先,歧义是特定语法的一个特征,而不是语言 . 即使一种语言可以证明没有明确的语法,如果它可以通过无上下文语法识别,那么它就是无上下文的 . 类似地,如果无法通过无上下文语法识别它,但它可以被上下文敏感的语法识别,那么它是上下文敏感的 . 歧义是无关紧要的 .
但无论如何,如下面的程序中的第21行(即
auto b = foo<IsPrime<234799>>::typen<1>();
),表达式根本不含糊 . 它们只是根据上下文进行不同的解析 . 在问题的最简单表达中,某些标识符的语法类别取决于它们的声明方式(例如,类型和函数),这意味着形式语言必须识别两个任意长度字符串的事实 . 相同的程序是相同的(声明和使用) . 这可以通过"copy"语法建模,该语法是识别同一个单词的两个连续精确副本的语法 . 用pumping lemma证明这种语言不是无上下文很容易 . 这种语言的上下文敏感语法是可能的,并且在这个问题的答案中提供了Type-0语法:https://math.stackexchange.com/questions/163830/context-sensitive-grammar-for-the-copy-language .如果一个人试图编写一个上下文敏感(或不受限制)的语法来解析C,那么它很可能会用乱涂乱填充整个宇宙 . 编写图灵机来解析C将是一项同样不可能完成的任务 . 即使编写C程序也很困难,据我所知,没有一个被证明是正确的 . 这就是为什么标准不试图提供完整的正式语法,以及为什么它选择用技术英语编写一些解析规则的原因 .
看起来像C标准中的形式语法并不是C语言语法的完整形式定义 . 它甚至不是预处理后语言的完整形式定义,这可能更容易形式化 . (但这不是语言:标准定义的C语言包括预处理器,预处理器的操作是通过算法描述的,因为在任何语法形式中都难以描述 . 它在那部分描述词汇分解的标准,包括必须多次应用的规则 . )
各种语法(用于词法分析的两个重叠语法,一个在预处理之前发生,另一个在必要时,之后发生,加上“句法”语法)收集在附录A中,这个重要说明(重点补充):
最后,这是承诺的计划 . 当且仅当
IsPrime<N>
中的N为素数时,第21行在语法上是正确的 . 否则,typen
是整数,而不是模板,因此typen<1>()
被解析为(typen<1)>()
,这在语法上是不正确的,因为()
不是语法上有效的表达式 .[1]更具技术性,上下文敏感语法中的每个产品必须具有以下形式:
αAβ → αγβ
其中
A
是非终端且α
,β
可能是空语法符号序列,γ
是非空序列 . (语法符号可以是终端或非终端) .只能在
[α, β]
上下文中将其读作A → γ
. 在无上下文(Type 2)语法中,α
和β
必须为空 .事实证明,您还可以使用“单调”限制来限制语法,其中每个制作必须具有以下形式:
α → β
其中|α| ≥ |β| > 0
(|α|
表示“长度α
“)有可能证明单调语法识别的语言集与上下文敏感语法识别的语言集完全相同,并且通常情况下,单调语法上的校对更容易 . 因此,使用“上下文敏感”就好像它意味着“单调”一样 .
它是上下文敏感的,因为
a b(c);
有两个有效的parses-声明和变量 . 当你说“如果c
是一个类型", that's context, right there, and you've described exactly how C++ is sensitive to it. If you didn't have that context of "什么是c
?”你不能毫不含糊地解析这个 .这里,上下文在标记的选择中表示 - 如果标识符命名类型,则解析器将标识符读取为类型名称标记 . 这是最简单的解决方案,并且避免了上下文敏感的大部分复杂性(在这种情况下) .
编辑:当然,有更多关于情境敏感性的问题,我只关注你所展示的问题 . 模板对此尤其讨厌 .
C不是无上下文的 . 不久前我在编译器讲座中学到了它 . 快速搜索给出了这个链接,其中“语法或语义”部分解释了为什么C和C不是无上下文的:
Wikipedia Talk: Context-Free grammar
问候,
Ovanes
C用GLR解析器解析 . 这意味着在解析源代码期间,解析器可能会遇到歧义,但它应该继续并决定稍后使用哪个语法规则 .
看,也
Why C++ cannot be parsed with a LR(1) parser?
请记住,无上下文语法 can not 描述了编程语言语法的规则 . 例如,属性语法用于检查表达式类型的有效性 .
您无法使用无上下文语法描述以下规则: The Right Side of the assignment should be of the same type of the Left Hand side.
显然,如果你逐字逐句地提出问题,几乎所有带标识符的语言都是上下文敏感的 .
需要知道标识符是类型名称(类名,typedef引入的名称,typename模板参数),模板名称还是其他一些名称才能正确使用标识符 . 例如:
如果
name
是函数名称,则name
是类型名称和函数调用 . 另一种情况是所谓的"most vexing parse",它不可能区分变量定义和函数声明(有一条规则说它是一个函数声明) .这种困难引入了
typename
和template
与依赖名称的需要 . 据我所知,C的其余部分不是上下文敏感的(即可以为它编写无上下文语法) .是 . 以下表达式具有不同的操作顺序,具体取决于类型已解析的上下文:
编辑:当实际操作顺序不同时,使用“常规”编译器在解析它(传播类型信息)之前解析为未修饰的AST非常困难 . 与此相比,提到的其他上下文敏感事物“相当容易”(并非模板评估很简单) .
其次是:
是的C是上下文敏感的,非常敏感 . 您无法通过使用上下文无关解析器解析文件来构建语法树,因为在某些情况下您需要知道先前知识中的符号来决定(即在解析时构建符号表) .
第一个例子:
这是一个乘法表达式吗?
要么
这是
B
变量的声明是A
类型的指针吗?如果A是一个变量,那么它就是一个表达式,如果A是一个类型,它就是一个指针声明 .
第二个例子:
这是一个函数原型采用
bar
类型的参数吗?要么
这是
A
类型的声明变量B
并使用bar
常量作为初始值调用A的构造函数吗?您需要再次知道
bar
是变量还是符号表中的类型 .第三个例子:
这是构建符号表时的情况,而解析没有帮助,因为x和y的声明在函数定义之后 . 所以你需要先扫描类定义,然后在第二遍中查看方法定义,告诉x * y是一个表达式,而不是指针声明或其他什么 .
有时情况更糟:What do people mean when they say C++ has "undecidable grammar"?
真的:)
J. Stanley Warford . Computer systems . 第341-346页 .
我感觉在“上下文敏感”的正式定义与“上下文敏感”的非正式使用之间存在一些混淆 . 前者具有明确的含义 . 后者用于说“你需要上下文来解析输入” .
这也是在这里问的:Context-sensitivity vs Ambiguity .
这是一个无上下文的语法:
这是不明确的,所以为了解析输入“x”你需要一些上下文(或者带有模糊性,或发出“警告:E8271 - 第115行的输入不明确”) . 但它肯定不是一个上下文敏感的语法 .