问题标签 [context-free-grammar]

我正在尝试编写一个正则表达式引擎。我想手动编写一个递归下降解析器。对于正则表达式的语言（不是正则表达式可以描述的语言），没有左递归的上下文无关语法会是什么样子？重新分解语法糖是否最容易，即更改a+为aa*？提前致谢！

我正在编写一个模拟器，并想通过调用模拟器的许多实例，使用不同的命令行参数集来运行研究。我已经阅读了这个问题和其他几个问题，它们看起来很接近，但我实际上并不是在寻找满足特定正则表达式的随机数据，我想要与正则表达式匹配的所有字符串的集合。示例输入文件如下所示：

或者：

并会产生：

我想像这样的东西已经存在，我只是不知道要搜索的正确术语。任何帮助将非常感激。如果需要，我可以自己实现一种抽象技术或算法，但如果它是一个预先存在的工具，我希望它是免费的（至少像啤酒一样）并在 Linux 上运行。

我知道我可能会遗漏一些细节，如果有必要，可以更具体地说明适当的事情，而不是预先用大量细节淹没人们。我完全有可能以错误的方式解决这个问题，我欢迎所有解决方案，即使它们以不同的方式解决我的问题。

最重要的是，如果我想向我生成的字符串的“叉积”添加更多参数选项，此解决方案不应该要求我编写任何额外的解析代码。我已经有一个 Perl 脚本，它在每个“变量”上使用一组嵌套for循环来执行此操作，每次我更改变量的数量或性质时，这些“变量”都必须更改。

我正在学习有限自动机和语法测试，但我遇到了这个问题：

我相信我的作品应该遵循以下原则：

我的 C 产品如何记住 m 和 n 的数字？我猜这一定是一个上下文无关的语法，如果是这样，它应该是怎样的？

http://www.cs.chalmers.se/Cs/Research/Language-technology/BNFC/

我应该如何编写带标签的 BNF 来让 BNFC 为我生成 INI 解析器？

我只到了这么远o__O！

o__O我被困住了......

我最近试图自学解析器（用于语言/上下文无关语法）是如何工作的，除了一件事之外，其中大部分似乎都是有意义的。我特别关注LL(k) 语法，其中两个主要算法似乎是LL 解析器（使用堆栈/解析表）和递归下降解析器（仅使用递归）。

据我所知，递归下降算法适用于所有 LL(k) 语法，甚至可能更多，而 LL 解析器适用于所有 LL(k) 语法。然而，递归下降解析器显然比 LL 解析器要简单得多（就像 LL 解析器比 LR 解析器更简单一样）。

所以我的问题是，使用任何一种算法时可能会遇到哪些优势/问题？为什么有人会选择 LL 而不是递归下降，因为它适用于同一组语法并且实现起来更棘手？

这是语法，它应该描述一种用逗号作为分隔符的嵌套大括号的语言：

我希望语法接受和拒绝的字符串的更多示例：

接受：

拒绝：

我想解析一个类似于 Gmail 使用 Perl 提供的搜索字符串。一个示例输入是“tag:thing by:{user1 user2} {-tag:a by:user3}”。我想把它放到一个树形结构中，比如

一般规则是：

1. 以空格分隔的标记默认为 AND 运算符。
2. 大括号中的标记是替代选项 (OR)。大括号可以放在字段说明符之前或之后。即“by:{user1 user2}”和“{by:user1 by:user2}”是等价的。
3. 以连字符为前缀的标记被排除在外。

这些元素也可以组合和嵌套：例如“{by:user5 -{tag:k by:user3}} 等”。

我正在考虑编写一个上下文无关的语法来表示这些规则，然后将其解析到树中。这是不必要的吗？（这可能使用简单的正则表达式吗？）

推荐使用哪些模块来解析上下文无关语法？

（最终这将用于生成带有 DBIx::Class 的数据库查询。）

我的问题是：

令 L = { x in {a,b}* | x 具有相同数量的 a 和 b}

我知道这是一种上下文无关语言，因为我可以为它创建一个语法（e 是 epsilon）：

您还可以通过使用与常规语言相交的上下文无关语言是上下文无关的事实来证明它是上下文无关的。

由于它是一种上下文无关语言，根据 CFL 的抽运引理，任何长于抽运长度 p 的字符串都应该能够被抽运。但是，如果我选择字符串 s = a^pb^pa^pb^p，则无法抽出该字符串，因此该语言不应该是上下文无关的。

我哪里错了？

我从任意 IL 构建 CFG，并希望将该 CFG 转换回 IL。CFG中的顶点顺序当然不等于原始IL指令的顺序。

这很好，但会使一些事情过于复杂。想象：

这将导致这样的流程图： (Jump B) -> (Jump C) -> (Return) 这当然是一个简化的示例，但它显示了转换出 CFG 时的问题。

学术界有没有关于这个话题的信息？我认为自下而上遍历图表会非常优雅，但这在更复杂的情况下不起作用。

一个解决方案可能是自上而下搜索 CF 合并，但在这种情况下，我将无法正确处理循环。因此，获得此权利的唯一方法似乎是搜索可能的 CF 合并（如果发生）。如果没有，我们必须有一个循环，这意味着循环是首选的，并且随后会评估持续的路径。这听起来像是一个可以解决的问题，但它也非常昂贵，并且可能存在更优雅的问题解决方案。此外，在考虑“break”语句时，循环也可能导致 CF 合并。

我正在考虑使用基于 W3C 的XML 1.1规范的编译器生成器来实现 XML 转换器的想法，该规范包括完整的 EBNF 语法。

更准确地说，我打算使用Qi-YACC，因为我想学习这个工具。这将是我第一次尝试使用任何编译器-编译器。

我计划实现的第一种翻译非常简单： XML 到S-EXPRs。之后，我打算概括我的翻译，但这不是我问题的重点。

您预计此类项目有什么重大缺陷吗？我读过使用它的 EBNF 翻译 XML 是一个坏主意。我想知道为什么。而且 Qi 语言并不是已经有了 XML 解析器，所以我绝对不想在这里重新发明轮子。