python - 高效的上下文无关语法解析器，最好是 Python 友好的

Question

我需要为我的一个项目解析一小部分英语，描述为具有（1级）特征结构（示例）的无上下文语法，我需要有效地做到这一点。

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

另一个问题是，在开头加载（25MB）语法+词典可能需要一分钟。

从我在文献中可以找到的，用于解析这种语法（Earley 或 CKY）的算法的运行时间应该与语法的大小成线性关系，并与输入标记列表的大小成三次关系。我对 NLTK 的经验表明，歧义是最损害性能的因素，而不是语法的绝对大小。

所以现在我正在寻找一个 CFG 解析器来替换 NLTK。我一直在考虑PLY，但我不知道它是否支持 CFG 中的特征结构，这在我的情况下是必需的，而且我看到的示例似乎做了很多程序解析，而不仅仅是指定语法。任何人都可以向我展示一个支持功能结构和使用声明性语法的 PLY 示例吗？

我也可以使用任何其他可以有效地完成我需要的解析器。Python 接口是可取的，但不是绝对必要的。

score 15 · Accepted Answer

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

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

也就是说，与编程语言不同，自然语言更多的是关于语义而不是语法，所以你最好跳过现有解析工具的学习曲线，使用自制的（自上而下、回溯、无限制） lookahead) 词法分析器和解析器，并花费大量时间编写代码来确定已解析但模棱两可的自然语言句子的含义。

score 2 · Accepted Answer

我建议使用 bitpar，这是一个用 C++ 编写的非常高效的 PCFG 解析器。我已经为它编写了一个基于 shell 的 Python 包装器，请参阅https://github.com/andreasvc/eodop/blob/master/bitpar.py

score 2 · Accepted Answer

我已经将 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']

随着您扩大词汇量，这可能会变慢。一百万个条目？我认为一个合理的功能词汇量在 5-6 千词左右。而且您可以处理的句子结构非常有限 - 自然语言是 NLTK 的用途。

score 2 · Accepted Answer

抛开工具...

你可能记得理论上存在定义相同语言的无限语法。对语法进行分类并确定给定语言的“规范”或“最小”语法是有标准的，但最终，“最佳”语法是对手头的任务和工具更方便的语法（记住将 CFG 转换为 LL 和 LR 语法？）。

然后，您可能不需要庞大的词典来解析英语句子。在德语或拉丁语（甚至西班牙语）等语言中，有很多关于一个词的知识，但在很多时候是武断和模棱两可的英语中却没有。您应该能够使用仅包含到达句子结构所需的关键词的小型词典。无论如何，您选择的语法，无论其大小，都可以以您的工具可以直接使用它的方式进行缓存（即，您可以跳过语法分析）。

鉴于此，看看其他人已经在使用的更简单的解析器可能是个好主意。文学中一定有成千上万的人。学习不同的方法可以让你评估自己的方法，并可能导致你采用别人的方法。

最后，正如我已经提到的，解释自然语言更多的是关于人工智能而不是解析。因为结构决定意义，意义决定结构，所以你必须同时使用两者。自 80 年代以来，我在文献中看到的一种方法是让不同的专业代理针对“黑板”解决问题。使用这种方法，句法和语义分析同时发生。

score 1 · Accepted Answer

这有点晚了，但这里还有两个选择：

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

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

score 1 · Accepted Answer

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

score 0 · Accepted Answer

如果它可以表示为PEG语言（我认为并非所有 CFG 都可以，但据说很多都可以），那么您可以使用pyPEG，这在使用 Packrat 解析实现时应该是线性时间的（尽管可能禁止内存使用情况）。

我没有任何经验，因为我刚刚开始研究解析和编译很长时间后再次开始研究，但我正在阅读一些关于这种相对最新技术的好消息。YMMV。

score 0 · Accepted Answer

0

尝试在 PyPy 上运行它，它可能会快很多。

于 2010-12-28T02:46:29.437 回答

python - 高效的上下文无关语法解析器，最好是 Python 友好的

8 回答 8

Related

Reference