高效的上下文无关文法解析器，最好支持Python
我需要在我的一个项目中解析一小部分英语，这个部分用了一种叫做上下文无关文法的方式来描述，并且包含了一些特征结构（可以理解为一种数据结构，用来表示句子的不同部分）。我希望这个过程能高效一些。
目前我在使用 NLTK 的解析器，它能输出正确的结果，但速度非常慢。我的文法大约有450条相当模糊的非词典规则和50万个词汇条目，解析简单的句子可能需要2到30秒不等，似乎是根据生成的树的数量来决定的。词汇条目对性能几乎没有影响。
另一个问题是，加载这个25MB的文法和词典一开始可能需要花费一分钟的时间。
根据我查到的资料，用来解析这种文法的算法（比如Earley或CKY）的运行时间应该是与文法的大小成线性关系，而与输入的标记列表的大小成立方关系。但我在使用NLTK的经验表明，模糊性是影响性能的主要原因，而不是文法的绝对大小。
所以现在我在寻找一个可以替代NLTK的CFG解析器。我考虑过 PLY，但我不确定它是否支持我需要的特征结构，而且我看到的例子似乎更多是在进行过程式解析，而不是单纯地指定文法。有没有人能给我一个例子，展示PLY如何支持特征结构并使用声明式文法？
我也愿意尝试其他任何能高效完成我需求的解析器。最好是有Python接口，但这不是绝对必要的。
7 个回答
工具不谈了……
你可能还记得，从理论上讲，有无数种语法可以定义同一种语言。虽然有一些标准可以用来分类语法，判断哪一种是某种语言的“标准”或“最简”语法，但最终，最“好”的语法是最适合当前任务和工具的那种（还记得把上下文无关文法（CFG）转换成LL和LR语法的过程吗？）。
那么，解析一句英语句子其实不需要一个庞大的词汇表。像德语、拉丁语（甚至西班牙语）中，一个词的含义可能涉及很多内容，但英语往往是任意且模糊的。你应该可以只用一个包含关键字的小词汇表，就能理解句子的结构。无论你选择什么样的语法，不管它有多大，都可以以一种方式缓存起来，让工具直接使用（也就是说，你可以跳过解析语法这一步）。
考虑到这一点，看看别人已经做好的简单解析器可能是个好主意。文献中肯定有成千上万这样的例子。研究不同的方法可以帮助你评估自己的方法，甚至可能让你采用别人的方法。
最后，正如我之前提到的，理解自然语言更多的是关于人工智能，而不是单纯的解析。因为结构决定了意义，而意义又决定了结构，所以你必须同时处理这两者。我在80年代的文献中看到过一种方法，就是让不同的专业代理人同时尝试解决问题，利用一个“黑板系统”。通过这种方法，句法分析和语义分析是同时进行的。
我之前用过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']
随着词汇量的增加，这个可能会变得很慢。比如说有五十万条词汇？我觉得一个合理的功能性词汇量大概在五六千个单词左右。而且你能处理的句子结构会非常有限——自然语言的处理是NLTK的专长。