为什么在线解析器似乎停在正则表达式处？

Question

我一直想知道为什么似乎没有任何解析器，例如 BNF，其行为类似于各种库中的正则表达式。

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

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

这些解析器是否存在技术/理论限制，或者我只是错过了一些东西？

Answer 1

我认为这更多是一种文化问题。 上下文无关语法的使用主要限于编译器，编译器通常具有与每个产生规则相关联的代码。 在某些语言中，输出代码比模拟回调更容易。 在其他情况下，您将看到解析器库：例如 Haskell 中的解析器组合器。 另一方面，正则表达式在 grep 等工具中得到广泛使用，每次用户给出新的正则表达式时都运行 C 编译器很不方便。

Answer 2

Boost.Spirit 看起来就像你所追求的。

如果您想自己制作，我使用了 BNFC< /a> 对于我最新的编译器项目，它提供 在其自己的实现中使用的语法。 这可能是一个很好的起点......

Answer 3

不存在隐藏在阴影中的技术/理论限制。 我不能说为什么它们不更受欢迎，但我知道至少有一个库可以提供您所寻求的这种“在线”解析。

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 的解析器组合器库还允许您在使用它的同一代码块中表达解析器的语法。 但是，您不能让用户在运行时输入语法（这可能只有制作软件来帮助人们理解语法的人感兴趣）。

Answer 4

Pyparsing (http://pyparsing.wikispaces.com) 内置了对 Packrat 解析的支持，而且它是纯粹的Python，这样你就可以看到实际的实现。

Answer 5

因为成熟的上下文无关语法已经足够令人困惑了，因为它们没有一些神秘而密集且难以理解的语法来使它们更加令人困惑？

很难知道你在问什么。 您是否正在尝试创建类似于正则表达式的东西，但用于上下文无关语法？ 例如，使用 $var =~ /expr = expr + expr/ （在 Perl 中）并匹配 "1 + 1" 或 "1 + 1 + 1” 或 “1 + 1 + 1 + 1 + 1 + ...”？ 我认为这样做的局限性之一是语法：拥有超过三个规则将使您的“语法表达式”比任何现代正则表达式更难读。

Answer 6

副作用是我看到的唯一能让你受益的东西。 大多数解析器生成器都包含用于处理的嵌入式代码，您需要一个 eval 才能使其工作。

解决这个问题的一种方法是命名操作，然后创建一个“操作”函数，该函数采用要执行的操作的名称和执行该操作的参数。

Answer 7

理论上你可以用 C++ 中的 Boost Spirit 来做到这一点，但它主要是为静态语法而设计的。 我认为这种情况不常见的原因是 CFG 不像正则表达式那样常用。 除了编译器构造之外，我从未使用过语法，但我多次使用过正则表达式。 CFG 通常比正则表达式复杂得多，因此使用 YACC 或 ANTLR 等工具静态生成代码是有意义的。

Answer 8

tcllib 有类似的东西，如果你能忍受 解析表达式语法 以及 TCL。 如果你喜欢 Perl，CPAN 有 Parse::Earley 。 这里是一个看起来很有前途的纯 Perl 变体。 PLY 似乎是 Python 的一个可行的解决方案