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

23
我需要解析一个小型的英语子集,作为上下文无关文法,具有(1级)特征结构(example),并且我需要高效地完成它。目前我正在使用NLTK的解析器,它可以产生正确的输出,但速度非常慢。对于大约450个相当模糊的非词汇规则和半百万词汇条目的语法,解析简单的句子需要花费2到30秒不等,似乎取决于生成的树木数量。词汇条目对性能几乎没有影响。另一个问题是,在开始加载(25MB)语法和词汇时可能需要一分钟时间。
从我在文献中找到的信息来看,用于解析这种语法(Earley或CKY)的算法的运行时间应该与语法的大小成线性关系,并与输入令牌列表的大小成立方关系。使用NLTK的经验表明,歧义会最大程度地损害性能,而不是语法绝对大小。
所以现在我正在寻找一个替代NLTK的CFG解析器。我一直在考虑PLY,但我不能确定它是否支持CFG中的特征结构,在我的情况下是必需的,而且我看到的例子似乎正在进行很多程序化解析,而不仅仅是指定一个语法。有人可以给我展示一个既支持特征结构又使用声明性语法的PLY示例吗?

我对任何其他可以高效完成我需要的解析器也感到满意,Python接口是可取的但不是绝对必要的。


我只是在寻找Java相关的东西。这是我的相关问题:http://stackoverflow.com/questions/4584684/java-cfg-parser-that-supports-ambiguities。那么你决定使用哪种方法呢?Apalala说我们可以修复ANTLR来处理歧义。然而,我并不理解他所建议的方法。 - hrzafer
到目前为止,我仍然使用NLTK,因为答案中的库或技术都不适用于我。然而,这部分是因为我需要一个统一语法(CFG + 特征结构),根据负责解析器的NLTK开发人员说,我的效率问题源于此。 - Max Shawabkeh
这是Python解析器列表:https://wiki.python.org/moin/LanguageParsing - Pro Q
8个回答

18

务必查看Pyparsing。它是我遇到的最pythonic的解析实现,从纯学术角度来看,它是一个很好的设计。

我在当地一所大学教授翻译和编译器理论时,使用了ANTLRJavaCC,它们都很好且成熟,但我不会在Python项目中使用它们。

话虽如此,与编程语言不同,自然语言更多地涉及语义而非语法,因此您可能会更好地跳过现有解析工具的学习曲线,采用自制(自上而下、回溯、无限向前查看)词汇分析器和解析器,并将大部分时间花在编写代码上,以确定已解析但模棱两可的自然语言句子的含义。


1
IMX pyparsing 添加了相当多不必要的开销。它也并没有真正考虑分离词法分析和语法分析步骤的概念。 - Karl Knechtel
3
分词器和解析器的分离是来自于像LEX/YACC这样的工具的任意遗留物,以及在计算能力不足以考虑单遍编译器的年代。如果语法语言足够强大,可以在所有级别定义目标语言,则不需要分离。设计者们长期以来一直使用EBNF来定义编程语言的所有部分,尽管ANTLR提供了分离功能,但它使用上下文无关文法(而不是正则表达式)进行词法分析。Pyparsing也是如此。 - Apalala
就像ANTLR一样,Pyparsing似乎不能(1)处理CFGs并且(2)无法正确生成所有二义性解析的树。这两者在我的情况下都是必需的。关于您对自然语言的注释,您是正确的。该项目的主要部分是语义分析,并且我已经用自己的代码完成了它。但是,在我可以消除歧义之前,我需要获取解析树。编写自己的代码是一个选择,但总的来说,我宁愿不重复造轮子。 - Max Shawabkeh
2
无论是否使用Pyparsing,从我在Prolog时期的经验中,有一个老技巧可以用于在任何自顶向下的解析工具中获取所有的解析树。如果你的文法是G-> <alpha>,那么将它改为:G' -> G {semantic-clone-parse-tree} <TOKEN-NOT-IN-LANGUAGE>也就是,在强制解析器失败之前克隆完整的解析树。必须使用克隆而不是保存,因为解析器在寻找不同的解析时会修改树。 - Apalala

3

我曾使用pyparsing进行有限词汇命令解析,但这里有一个在pyparsing基础上构建的小框架,可以解决您发布的示例问题:

from pyparsing import *

transVerb, transVerbPlural, transVerbPast, transVerbProg = (Forward() for i in range(4))
intransVerb, intransVerbPlural, intransVerbPast, intransVerbProg = (Forward() for i in range(4))
singNoun,pluralNoun,properNoun = (Forward() for i in range(3))
singArticle,pluralArticle = (Forward() for i in range(2))
verbProg = transVerbProg | intransVerbProg
verbPlural = transVerbPlural | intransVerbPlural

for expr in (transVerb, transVerbPlural, transVerbPast, transVerbProg,
            intransVerb, intransVerbPlural, intransVerbPast, intransVerbProg,
            singNoun, pluralNoun, properNoun, singArticle, pluralArticle):
    expr << MatchFirst([])

def appendExpr(e1, s):
    c1 = s[0]
    e2 = Regex(r"[%s%s]%s\b" % (c1.upper(), c1.lower(), s[1:]))
    e1.expr.exprs.append(e2)

def makeVerb(s, transitive):
    v_pl, v_sg, v_past, v_prog = s.split()
    if transitive:
        appendExpr(transVerb, v_sg)
        appendExpr(transVerbPlural, v_pl)
        appendExpr(transVerbPast, v_past)
        appendExpr(transVerbProg, v_prog)
    else:
        appendExpr(intransVerb, v_sg)
        appendExpr(intransVerbPlural, v_pl)
        appendExpr(intransVerbPast, v_past)
        appendExpr(intransVerbProg, v_prog)

def makeNoun(s, proper=False):
    if proper:
        appendExpr(properNoun, s)
    else:
        n_sg,n_pl = (s.split() + [s+"s"])[:2]
        appendExpr(singNoun, n_sg)
        appendExpr(pluralNoun, n_pl)

def makeArticle(s, plural=False):
    for ss in s.split():
        if not plural:
            appendExpr(singArticle, ss)
        else:
            appendExpr(pluralArticle, ss)

makeVerb("disappear disappears disappeared disappearing", transitive=False)
makeVerb("walk walks walked walking", transitive=False)
makeVerb("see sees saw seeing", transitive=True)
makeVerb("like likes liked liking", transitive=True)

makeNoun("dog")
makeNoun("girl")
makeNoun("car")
makeNoun("child children")
makeNoun("Kim", proper=True)
makeNoun("Jody", proper=True)

makeArticle("a the")
makeArticle("this every")
makeArticle("the these all some several", plural=True)

transObject = (singArticle + singNoun | properNoun | Optional(pluralArticle) + pluralNoun | verbProg | "to" + verbPlural)
sgSentence = (singArticle + singNoun | properNoun) + (intransVerb | intransVerbPast | (transVerb | transVerbPast) + transObject)
plSentence = (Optional(pluralArticle) + pluralNoun) + (intransVerbPlural | intransVerbPast | (transVerbPlural |transVerbPast) + transObject)

sentence = sgSentence | plSentence


def test(s):
    print s
    try:
        print sentence.parseString(s).asList()
    except ParseException, pe:
        print pe

test("Kim likes cars")
test("The girl saw the dog")
test("The dog saw Jody")
test("Kim likes walking")
test("Every girl likes dogs")
test("All dogs like children")
test("Jody likes to walk")
test("Dogs like walking")
test("All dogs like walking")
test("Every child likes Jody")

输出:

Kim likes cars
['Kim', 'likes', 'cars']
The girl saw the dog
['The', 'girl', 'saw', 'the', 'dog']
The dog saw Jody
['The', 'dog', 'saw', 'Jody']
Kim likes walking
['Kim', 'likes', 'walking']
Every girl likes dogs
['Every', 'girl', 'likes', 'dogs']
All dogs like children
['All', 'dogs', 'like', 'children']
Jody likes to walk
['Jody', 'likes', 'to', 'walk']
Dogs like walking
['Dogs', 'like', 'walking']
All dogs like walking
['All', 'dogs', 'like', 'walking']
Every child likes Jody
['Every', 'child', 'likes', 'Jody']

随着词汇量的扩大,这很可能会变得缓慢。50万个词条?我认为一个合理的功能性词汇量大约是5-6千个单词。而且你将受到限制,只能处理有限的句子结构——自然语言正是NLTK的用途。


谢谢提供这么大的示例,但是它使用了一种过程化的方法,在有如此多规则的情况下会显得非常笨重。我更愿意使用能理解EBNF的解析器。至于词汇表,你说得对,5万个单词应该足够了。然而,添加词汇表条目并不会真正影响性能——使用自底向上的解析器,终结符只需要进行一次字典查找,即使我们假设它的时间复杂度是O(log n),实际上并不是这样,词汇量增加一个数量级也是微不足道的。问题在于那些有歧义的非终结符规则。 - Max Shawabkeh

3

撇开工具不谈...

你可能还记得理论上存在着无数定义同一语言的文法。有一些标准可用于分类文法并确定哪个是给定语言的“规范”或“最小化”的文法,但最终,“最佳”文法是更方便完成任务和使用工具的那个(还记得将CFG转换为LL和LR文法吗?)。

然后,你可能不需要一个庞大的词汇表来解析英语句子。在像德语、拉丁语(甚至是西班牙语)这样的语言中,对于单词的了解要多得多,但在许多时候任意和模棱两可的英语中却不是这样。你应该能够通过一个只包含到达句子结构所必需的关键词的小型词汇表来完成。无论如何,你选择的文法,无论其大小,都可以以一种方式缓存,使工具能够直接使用它(即,你可以跳过文法解析)。

鉴于这一点,查看别人已经研究过的更简单的解析器可能是个好主意。文献中可能有成千上万个这样的解析器。研究不同的方法将让你评估自己的方法,并可能导致你采用别人的方法。

最后,正如我之前提到的,解释自然语言更多地涉及人工智能而不是解析。因为结构决定意义,意义决定结构,所以你必须同时处理两者。自80年代以来,文献中出现了一种方法,即让不同的专业代理针对"blackboard"解决问题。采用这种方法,句法和语义分析同时进行。

正如我在评论Paul的帖子中提到的,词汇表与性能无关。缓存语法是显而易见的,我已经在做了,因此加载时间是次要问题。然而,应该指出,将一个NLTK解析器pickle到磁盘并重新加载比从语法创建一个新的解析器加载要慢。关于使用现有的解析器,我正在使用的语义分析方法(Montague语法/DRT的变体)的问题在于它要求我为每个句法规则编写一个语义处理步骤... - Max Shawabkeh
......规则必须以特定方式制定。我见过的大多数广泛覆盖的语法都是通过从树库中经验性地提取大量长规则并为其分配概率来解决这个问题的。这种方法对某些用途是有效的,但不适用于我的情况。 - Max Shawabkeh
我想我的观点是,对于自然语言来说,在句法分析期间没有足够的信息进行语义分析,而且没有足够的语义信息可以通过典型的解析器准确地把握句法结构。"玛丽读了简读得好。玛丽也读了简读的东西。" - Apalala
这就是模棱两可的地方。我可以几乎不需要语义知识(除了编码在词汇中的部分)就可以句法地解析一句话,一旦我拥有所有可能的解析树,我会进行一步语义分析,并找出哪些树是可接受的。 - Max Shawabkeh
@Max Shawabkeh。你的方法是有效的,但它是暴力破解,所以应该预料到资源(内存/时间)方面的问题(我想起了排序算法的动画)。为了处理资源问题,你可以至少在发现树时立即使用并发语义分析器进行丢弃。理论时间将是相同的,但计算机时间可能会急剧下降,因为你将使用更少的内存。如果解析器构建中间树,则最好将博弈论(http://en.wikipedia.org/wiki/A_star)纳入其中。 - Apalala
我的消歧方法没有完整的树来分析就不起作用。事实上,任何分析不完整树的消歧器都会冒着丢弃有效树的风险,因为任何可能在语义上不一致的子树都可以在放入条件或否定时产生一个完全有效的树。无论如何,(1)即使我只得到<10棵树,速度问题仍然存在,所以丢弃任何一个都没有帮助,(2)使用的CKY/Earley解析算法不是暴力搜索,并且不会呈指数增长。CKY的运行时间为O(g*n^3),其中g是语法大小,n是输入大小。 - Max Shawabkeh

2

1

我认为ANTLR是我所知道的最好的Java解析器生成器。我不知道Jython是否会为Python和Java提供良好的互动方式。


1
ANTLR实际上支持Python,还支持其他几种语言:http://www.antlr.org/wiki/display/ANTLR3/Code+Generation+Targets - Fabian Steeg
没想到,我只是用它来写Java。谢谢你的更新。 - duffymo
2
谢谢推荐。然而,从我所看到的,ANTLR(以及它的所有相关工具,比如Lex/Yacc、Bison等)主要是用于解析确定性编程语言而不是歧义自然语言。在我的情况下,一句中等长度的句子可能会产生20个分析树,我需要生成这些树。注意:我没有给它点踩。 - Max Shawabkeh
1
是的,大多数自然语言(包括英语)并不是上下文无关的,但是它的一个大而非常有用的子集可以用足够复杂的歧义CFG表达,然后可以在语义上消除歧义。 - Max Shawabkeh
@Max - "can be disambiguated semantically" 可能并不容易。我所知道的唯一一个尝试这样做的项目是Doug Lenat的Cyc(http://www.cyc.com/cyc/opencyc),这是一个超过十年的巨大工程。 - duffymo
显示剩余3条评论

1

虽然有点晚了,但这里还有两个选项供您选择:

Spark 是用 Python 编写的 Earley 解析器。

Elkhound 是用 C++ 编写的 GLR 解析器。Elkhound 使用类似 Bison 的语法。


0

尝试在PyPy上运行它,可能会更快。


我正在使用的解析器似乎过多地使用内省并且在对象处理方面有些繁琐,因此无法从PyPy中获得太多性能提升,而将其正确移植可能与从头编写一个解析器一样困难。 - Max Shawabkeh
移植?只需从pypy.org/download.html下载PyPy,然后将“time python yourscript.py data.txt”更改为“time pypy yourscript.py data.txt”即可。 - TryPyPy
此外,如果您能提供更多细节(如何使用示例语法解析器在哪些数据上运行相关基准测试等),我们可以尝试其他加速方法(例如在热点上使用Cythonize或Shed Skin)。 - TryPyPy

0

如果它可以表示为PEG语言(我认为并非所有CFG都可以,但据说许多可以),那么您可以使用pyPEG,该技术在使用packrat解析实现时应该是线性时间(尽管可能会占用大量内存)。

我没有任何经验,因为我刚开始重新研究解析和编译,离开已经很长时间了,但我正在阅读一些关于这种相对较新的技术的好消息。 个人经验可能有所不同。


据我所知,该方法是通过优先级等方式解决EBNF语法中的歧义,这当然很有用,但在我的情况下却是适得其反,因为我实际上希望保留歧义。 - Max Shawabkeh
是的,它确实说它不适用于依赖于歧义的语言。 - Binary Phile

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接