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

StackOverflow https://stackoverflow.com/questions/803515

题

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

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

我有兴趣编写 Packrat解析器，以启动所有嵌套-parenthesis-quirks与regexps相关（对于它的运动，可能更是如此），但不知怎的，我有这样的感觉，我只是走进另一个停止问题 - 类似沼泽。

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

有帮助吗？

解决方案

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

其他提示

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

如果你想制作自己的，我用过 BNFC 用于我最新的编译器项目，它提供了其自身实施中使用的语法。这可能是一个很好的起点...

没有潜伏在阴影中的技术/理论限制。我不能说为什么它们不是更受欢迎，但我知道至少有一个提供这种“在线”的库。解析你寻求的。

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

Pyparsing（ http://pyparsing.wikispaces.com ）内置支持packrat解析和它是纯Python，所以你可以看到实际的实现。

因为完整的无上下文语法令人困惑，因为它们没有一些密码密集且难以理解的语法，使它们更加混乱？

很难知道你在问什么。您是否尝试创建类似正则表达式的内容，但是对于无上下文的语法？比如，使用 $ var =〜/ expr = expr + expr / （在Perl中）并匹配＆quot; 1 + 1＆quot; 或＆quot; 1 + 1 + 1＆quot; 或＆quot; 1 + 1 + 1 + 1 + 1 + ...＆quot; ？我认为其中一个局限就是语法：拥有超过三个规则将使你的“语法表达”成为可能。比任何现代正则表达都更难以理解。

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

一种方法是命名行动，然后制作“行动”。获取要执行的操作的名称以及执行该操作的args的函数。

理论上你可以在C ++中使用 Boost Spirit 来实现它，但它主要用于静态语法。我认为这不常见的原因是CFG并不像正则表达式那样常用。我从来没有使用过语法，除了编译器构造，但我多次使用正则表达式。 CFG通常比正则表达式复杂得多，因此使用YACC或ANTLR等工具静态生成代码是有意义的。

tcllib 有类似的东西，如果你能忍受 Parse Expression Grammars 和TCL。如果Perl是你的事，CPAN已经 Parse :: Earley 。 这里是纯粹的Perl变体，看起来很有前景。 PLY 似乎是Python的合理解决方案

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top