问题标签 [context-free-grammar]

我正在查看我的理论计算机科学课程的教学大纲，并在上下文无关语法的标题中列出了“闭包属性”。我翻阅了关于这个主题的教科书，发现很少。目前它所拥有的东西有点超出我的想象（我还没有上过这门课程），但我了解一点。

我想知道上下文无关语法中的闭包概念是否与函数式编程中的闭包概念相同或相关。据我所知，它谈到了结合语法和解决重叠问题。书中的部分有很多部分我还不明白，所以我不确定这些想法是否相同。

（更多背景信息：我正在给教授写一封电子邮件，询问是否可以将课程从 Perl 切换到 Ruby 或 Python。如果这些概念相关，那可能是我们应该使用 Ruby 而不是 Perl 的另一个原因。）

我正在为我的计算语言测试而学习，并且有一个想法是我遇到了问题。

我明白常规语法更简单，不能包含歧义，但不能完成编程语言所需的大量任务。我还理解上下文无关语法允许歧义，但允许一些编程语言所必需的东西（如回文）。

我遇到的问题是通过知道常规语法非终结符可以映射到终结符或非终结符后跟终结符或上下文无关的非终结符映射到终结符和非终结符的任何组合来了解我如何推导出上述所有内容.

有人可以帮我把所有这些放在一起吗？

多年来，“正则表达式”模式匹配变得越来越强大，以至于我想知道：它真的只是上下文敏感的语法匹配吗？它是上下文无关语法匹配的变体/扩展吗？它现在在哪里，为什么我们不直接称它为旧的、限制性的“正则表达式”？

谁能告诉我是否有任何软件可以将乔姆斯基范式转换为巴科斯-瑙尔范式，反之亦然？

我为大学做了一份工作，基本上说：

“证明非正则语言 L={0^n 1^n : n natural} 没有无限的正则子语言。”

我通过矛盾证明了这一点。我基本上说有一种语言 S 是 L 的子语言，它是一种常规语言。因为 S 可能的正则表达式是 0*、1*、(1+0)* 和 (0o1)*。我检查每个语法并证明它们都不是语言 L 的一部分。

但是，我如何证明任何非常规上下文无关语言都不能包含任何常规无限子语言？

我不想要证明本身，我只想指出正确的方向。

我正在尝试在字母表Σ = {a,b}上为所有以相同数量的 's 开头和结尾的单词写一个 CFG，中间a至少有一个b。

现在我了解了 CFG、变量、生产规则等的基本概念。不幸的是，我已经没有编写上述 CFG 的想法了。到目前为止我所拥有的是

我认为生产规则会给我一个字符串，两边都有两个 ** S** ，中间有尽可能多的 ** **。但是，我不确定如何在 ** ** 的两侧放置尽可能多的** **，同时确保每侧的 ** ** 数量完全相同。Xababa

任何建议，解决方案将不胜感激。谢谢。

我一直想知道为什么似乎没有任何解析器，比如BNF，它们的行为就像各种库中的正则表达式。

当然，有像ANTLR、Yacc和许多其他生成代码的东西，这些代码反过来可以解析CFG，但似乎没有一个库可以在没有中间步骤的情况下做到这一点。

我有兴趣编写一个Packrat 解析器，以启动所有与正则表达式相关的嵌套括号怪癖（也许更重要的是，为了它的运动），但不知何故，我有一种感觉，我只是走进另一个停止问题 - 类似沼泽的一类。

这些解析器是否存在技术/理论限制，或者我只是遗漏了什么？

有谁知道如何在考虑到其转义序列的情况下拆分字符上的字符串？

例如，如果字符是 ':'，则“a:b”被分成两部分（“a”和“b”），而“a:b”根本不被分割。

我认为这很难（不可能？）与正则表达式有关。

先感谢您，

凯达

我想要一个实用程序，我可以提供一段文本（在文本框中）并尝试解析器语法（通过编辑类似的 BNF）和令牌结构，同时我可以看到解析树的外观（如果它是无法使用我当前的语法解析文本，我会看到它在哪里停止）。

关键词是交互性。例如，我可以使用 flex 和 bison 来做到这一点，但我必须不断地重新创建我的词法分析器和解析器。

外面有这样的东西吗？我还没有找到。理想情况下，它应该在 Linux 中工作并且是免费的，如果这不是一个选项，它仍然很有趣。

或者，更准确一点：哪些编程语言是由上下文无关文法定义的？

据我所知，由于宏和模板之类的原因，C++ 不是上下文无关的。我的直觉告诉我，函数式语言可能是上下文无关的，但我没有任何硬数据来支持它。

简洁示例的额外代表:-)