我一直想知道为什么似乎没有任何解析器，比如BNF，它们的行为就像各种库中的正则表达式。
当然，有像ANTLR、Yacc和许多其他生成代码的东西，这些代码反过来可以解析CFG，但似乎没有一个库可以在没有中间步骤的情况下做到这一点。
我有兴趣编写一个Packrat 解析器，以启动所有与正则表达式相关的嵌套括号怪癖（也许更重要的是，为了它的运动），但不知何故，我有一种感觉，我只是走进另一个停止问题 - 类似沼泽的一类。
这些解析器是否存在技术/理论限制，或者我只是遗漏了什么？
问问题
315 次
8 回答
4
我认为这更像是一种文化。上下文无关文法的使用主要限于编译器，它们通常具有与每个生产规则相关联的代码。在某些语言中，输出代码比模拟回调更容易。在其他地方，您会看到解析器库：例如 Haskell 中的解析器组合器。另一方面，正则表达式在 grep 等工具中得到广泛使用，每次用户提供新的正则表达式时运行 C 编译器很不方便。
于 2009-04-29T18:08:20.560 回答
2
Boost.Spirit看起来像你所追求的。
如果你想自己做，我在我最新的编译器项目中使用了 BNFC，它提供了在它自己的实现中使用的语法。这可能是一个很好的起点...
于 2009-04-29T18:27:57.143 回答
2
没有潜伏在阴影中的技术/理论限制。我不能说为什么它们没有更受欢迎，但我知道至少有一个库可以提供您所寻求的这种“在线”解析。
SimpleParse是一个 python 库，可以让您简单地将毛茸茸的 EBNF 语法粘贴到您的程序中，并使用它立即解析事物，无需中间步骤。我已经将它用于几个我想要自定义输入语言但真的不想提交任何正式构建过程的项目。
这是我脑海中的一个小例子：
decl = r"""
root := expr
expr := term, ("|", term)*
term := factor+
factor := ("(" expr ")") / [a-z]
"""
parser = Parser(decl)
success, trees, next = parser.parse("(a(b|def)|c)def")
Haskell 和 Scala 的解析器组合库还可以让您在使用它的同一块代码中表达您的解析器的语法。但是，您不能让用户在运行时输入语法（这可能只对制作软件以帮助人们理解语法的人感兴趣）。
于 2009-04-30T07:13:51.997 回答
1
Pyparsing ( http://pyparsing.wikispaces.com ) 内置了对 Packrat 解析的支持，它是纯 Python，所以你可以看到实际的实现。
于 2009-09-11T03:00:31.780 回答
0
因为成熟的上下文无关语法已经足够令人困惑了，因为它们没有一些神秘的密集和难以理解的语法使它们更加混乱？
很难知道你在问什么。您是否正在尝试创建类似于正则表达式的东西，但用于上下文无关的语法？就像，使用$var =~ /expr = expr + expr/（在 Perl 中）并进行匹配"1 + 1"or "1 + 1 + 1"or "1 + 1 + 1 + 1 + 1 + ..."？我认为其中一个限制将是语法：拥有超过三个规则将使您的“语法表达式”比任何现代正则表达式都更难以阅读。
于 2009-04-29T18:08:11.900 回答
0
副作用是我看到的唯一能让你受益的东西。大多数解析器生成器都包含用于处理的嵌入式代码，您需要一个 eval 才能使其工作。
解决此问题的一种方法是命名动作，然后创建一个“动作”函数，该函数采用要执行的动作的名称和要使用的参数。
于 2009-04-29T18:12:30.377 回答
0
理论上，您可以在 C++ 中使用Boost Spirit来实现，但它主要用于静态语法。我认为这不常见的原因是 CFG 不像正则表达式那样常用。除了编译器构造之外，我从未使用过语法，但我已经多次使用正则表达式。CFG 通常比正则表达式复杂得多，因此使用 YACC 或 ANTLR 等工具静态生成代码是有意义的。
于 2009-04-29T18:17:46.683 回答
0
tcllib有类似的东西，如果你能忍受Parse Expression Grammars和 TCL。如果你喜欢 Perl，CPAN 就有Parse::Earley。 这是一个看起来很有希望的纯 Perl 变体。 PLY似乎是 Python 的一个合理的解决方案
于 2009-04-29T18:26:22.077 回答