上下文无关文法和格雷巴赫标准式

快捷方式: 差异，相似，杰卡德相似系数，参考。

上下文无关文法和格雷巴赫标准式之间的区别

上下文无关文法 vs. 格雷巴赫标准式

上下文无关文法（context-free grammar，縮寫為CFG），在计算机科学中，若一个形式文法 G. 在计算机科学中，声称一个上下文无关文法是Greibach 标准式（范式）(GNF)的意味着所有的产生规则都有如下形式： 或 这里的 A 是非终结符，α 是终结符，X 是不包括开始符号的非终结符的（可能为空）的序列，S 是开始符号，而 ε 是空串。 可观察出这种文法没有左递归。 所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法。（某些定义不认可第二种形式的规则，在这种情况下能生成空串的上下文无关文法不能被如此转换。）这可以被用来证明所有上下文无关语言可以被非确定下推自动机所接受。 给定 GNF 的一个文法和长度为 n 的符合这个文法的一个可导出的字符串，任何自顶向下分析器将在深度 n 停机。 Greibach 范式得名于 Sheila Greibach。.

巴科斯范式

巴科斯范式（Backus Normal Form，縮寫為 BNF），又称为巴科斯-诺尔范式（Backus-Naur Form，縮寫同樣為 BNF，也譯为巴科斯-瑙尔范式、巴克斯-诺尔范式），是一种用于表示上下文无关文法的语言，上下文无关文法描述了一类形式语言。它是由约翰·巴科斯（John Backus）和彼得·诺尔（Peter Naur）首先引入的用来描述计算机语言语法的符号集。 尽管巴科斯范式也能表示一部分自然语言的语法，它还是更广泛地使用于程序设计语言、指令集、通信协议的语法表示中。大多数程序设计语言或者形式语义方面的教科书都采用巴科斯范式。在各种文献中还存在巴科斯范式的一些变体，如扩展巴科斯范式 EBNF 或扩充巴科斯范式 ABNF。.

上下文无关文法和巴科斯范式 · 巴科斯范式和格雷巴赫标准式 · 查看更多 »

上下文无关语言

上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。.

上下文无关文法和上下文无关语言 · 上下文无关语言和格雷巴赫标准式 · 查看更多 »

乔姆斯基范式

在计算机科学中，一个形式文法是 Chomsky 范式的，当且仅当所有产生规则都有如下形式： 这里的 A, B 和 C 是非终结符，α 是终结符（表示常量值的符号），S 是开始符号，而 ε 是空串。还有，B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。 Chomsky 范式得名于诺姆·乔姆斯基，他是发明乔姆斯基层级的美国语言学家。.

上下文无关文法和乔姆斯基范式 · 乔姆斯基范式和格雷巴赫标准式 · 查看更多 »

计算机科学

计算机科学用于解决信息与计算的理论基础，以及实现和应用它们的实用技术。 计算机科学（computer science，有时缩写为CS）是系统性研究信息与计算的理论基础以及它们在计算机系统中如何与应用的实用技术的学科。 它通常被形容为对那些创造、描述以及转换信息的算法处理的系统研究。计算机科学包含很多分支领域；有些强调特定结果的计算，比如计算机图形学；而有些是探討计算问题的性质，比如计算复杂性理论；还有一些领域專注于怎样实现计算，比如程式語言理論是研究描述计算的方法，而程式设计是应用特定的程式語言解决特定的计算问题，人机交互则是專注于怎样使计算机和计算变得有用、好用，以及随时随地为人所用。 有时公众会误以为计算机科学就是解决计算机问题的事业（比如信息技术），或者只是与使用计算机的经验有关，如玩游戏、上网或者文字处理。其实计算机科学所关注的，不仅仅是去理解实现类似游戏、浏览器这些软件的程序的性质，更要通过现有的知识创造新的程序或者改进已有的程序。 尽管计算机科学（computer science）的名字里包含计算机这几个字，但实际上计算机科学相当数量的领域都不涉及计算机本身的研究。因此，一些新的名字被提议出来。某些重点大学的院系倾向于术语计算科学（computing science），以精确强调两者之间的不同。丹麦科学家Peter Naur建议使用术语"datalogy"，以反映这一事实，即科学学科是围绕着数据和数据处理，而不一定要涉及计算机。第一个使用这个术语的科学机构是哥本哈根大学Datalogy学院，该学院成立于1969年，Peter Naur便是第一任教授。这个术语主要被用于北欧国家。同时，在计算技术发展初期，《ACM通讯》建议了一些针对计算领域从业人员的术语：turingineer，turologist，flow-charts-man，applied meta-mathematician及applied epistemologist。 三个月后在同样的期刊上，comptologist被提出，第二年又变成了hypologist。 术语computics也曾经被提议过。在欧洲大陆，起源于信息（information）和数学或者自动（automatic）的名字比起源于计算机或者计算（computation）更常见，如informatique（法语），Informatik（德语），informatika（斯拉夫语族）。 著名计算机科学家Edsger Dijkstra曾经指出：“计算机科学并不只是关于计算机，就像天文学并不只是关于望远镜一样。”（"Computer science is no more about computers than astronomy is about telescopes."）设计、部署计算机和计算机系统通常被认为是非计算机科学学科的领域。例如，研究计算机硬件被看作是计算机工程的一部分，而对于商业计算机系统的研究和部署被称为信息技术或者信息系统。然而，现如今也越来越多地融合了各类计算机相关学科的思想。计算机科学研究也经常与其它学科交叉，比如心理学，认知科学，语言学，数学，物理学，统计学和经济学。 计算机科学被认为比其它科学学科与数学的联系更加密切，一些观察者说计算就是一门数学科学。 早期计算机科学受数学研究成果的影响很大，如Kurt Gödel和Alan Turing，这两个领域在某些学科，例如数理逻辑、范畴论、域理论和代数，也不断有有益的思想交流。.

上下文无关文法和计算机科学 · 格雷巴赫标准式和计算机科学 · 查看更多 »