高效的无上下文语法解析器,最好是Python友好的

Question

我需要为我的一个项目解析一小部分英语,描述为具有(1级)特征结构的无上下文语法(示例),我需要有效地完成它.

现在我正在使用NLTK的解析器,它产生正确的输出,但速度非常慢.对于我的约450个相当模糊的非词典规则和50万个词条的语法,解析简单的句子可能需要2到30秒,这取决于所得到的树的数量.词条对性能几乎没有影响.

另一个问题是在开始时加载(25MB)语法+词典可能需要一分钟.

从我在文献中可以找到的,用于解析这种语法(Earley或CKY)的算法的运行时间应该与语法的大小呈线性关系,并且应该与输入令牌列表的大小相关.我对NLTK的体验表明,歧义是最能伤害表现的,而不是语法的绝对大小.

所以现在我正在寻找一个CFG解析器来取代NLTK.我一直在考虑PLY,但我不知道它是否支持CFG中的特征结构,这在我的情况下是必需的,我看到的例子似乎是在进行大量的过程解析,而不仅仅是指定语法.有人能告诉我一个PLY的例子,它既支持功能结构又使用声明性语法？

对于能够有效地完成我需要的任何其他解析器,我也没问题.Python接口是首选,但不是绝对必要的.

Answer 1

一定要看看Pyparsing.这是我遇到的解析最疯狂的实现,从纯粹的学术角度来看,这是一个很棒的设计.

我使用ANTLR和JavaCC在当地大学教授翻译和编译理论.它们既好又成熟,但我不会在Python项目中使用它们.

也就是说,与编程语言不同,自然语言更多地是关于语义而不是语法,所以你可以更好地跳过现有解析工具的学习曲线,与家庭酿造(自上而下,回溯,无限制)前瞻性的词法分析器和解析器,并花费大量时间编写代码,找出解析但含糊不清的自然语句的含义.

令牌化器和解析器的分离是LEX/YACC等工具的随意遗留,而且从计算能力的时代开始,甚至考虑单通道编译器都是疯狂的.如果语法语言足够强大,可以在所有级别定义目标语言,则不需要分离.设计人员长期以来一直使用EBNF来定义编程语言的所有部分,虽然ANTLR提供了分离,但它使用无上下文语法(也不是正则表达式)进行词法分析.Pyparsing也是如此. (2认同)
@Max Shawabkeh Pyparsing 与否，我的 Prolog 时代有一个老技巧，您可以使用任何自上而下的解析工具来获取所有解析树。如果您的语法是 G-> <alpha>，请将其更改为： G' -> G {semantic-clone-parse-tree} <TOKEN-NOT-IN-LANGUAGE> 也就是说，在强制执行之前克隆完整的解析树解析器使解析失败。克隆而不是保存是必要的，因为解析器在寻求不同的解析时会修改树。 (2认同)

Answer 2

我认为 ANTLR 是我所知道的最好的 Java 解析器生成器。我不知道Jython是否能为您提供Python和Java交互的好方法。

感谢您的推荐。然而，据我所知，ANTLR（及其所有亲戚，Lex/Yacc，Bison 等）主要是为了解析确定性编程语言而不是模糊的自然语言而编写的。在我的例子中，一个中等长度的句子可能会产生 20 个解析树，我需要生成它们全部。注意：反对票不是我的。 (2认同)