Эффективный контекстно-свободный анализатор грамматики, предпочтительно дружественный к Python

Обязательно взгляните на Pyparsing. Это самая питоническая реализация синтаксического анализа, с которой я сталкивался, и это отличный дизайн с чисто академической точки зрения.

Я использовал как ANTLR, так и JavaCC для преподавания теории транслятора и компилятора в местном университете. Они оба хороши и зрелы, но я бы не стал использовать их в проекте Python.

Тем не менее, в отличие от языков программирования, естественные языки гораздо больше связаны с семантикой, чем с синтаксисом, поэтому вам было бы гораздо лучше пропустить кривые обучения существующим инструментам синтаксического анализа, используя самодельные (сверху вниз, откат, неограниченный) вперед) лексический анализатор и синтаксический анализатор, и тратить большую часть своего времени на написание кода, который выясняет, что означает проанализированное, но неоднозначное предложение на естественном языке.

Я использовал 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.

Инструменты в сторону...

Возможно, вы помните из теории, что существует бесконечное количество грамматик, определяющих один и тот же язык. Существуют критерии для категоризации грамматик и определения того, какая из них является «канонической» или «минимальной» для данного языка, но, в конце концов, «лучшая» грамматика — это та, которая более удобна для задачи и имеющихся инструментов (помните преобразования CFG в LL и LR грамматики?).

Тогда вам, вероятно, не понадобится огромный словарный запас, чтобы разобрать предложение на английском языке. О слове в таких языках, как немецкий или латинский (или даже испанский), можно многое узнать, но не во многих случаях произвольном и двусмысленном английском. Вам может сойти с рук небольшой лексикон, который содержит только ключевые слова, необходимые для построения структуры предложения. В любом случае, выбранная вами грамматика, независимо от ее размера, может быть кэширована таким образом, что ваш инструментарий сможет использовать ее напрямую (т. е. вы можете пропустить синтаксический анализ грамматики).

Учитывая это, было бы неплохо взглянуть на более простой синтаксический анализатор, над которым уже работал кто-то другой. Таких в литературе должны быть тысячи. Изучение различных подходов позволит вам оценить свои собственные и может привести к принятию чужих.

Наконец, как я уже упоминал, интерпретация естественных языков гораздо больше связана с искусственным интеллектом, чем синтаксическим анализом. Поскольку структура определяет смысл, а смысл определяет структуру, вы должны играть с ними одновременно. Подход, который я видел в литературе с 80-х годов, заключается в том, чтобы позволить различным специализированным агентам попытаться решить проблему с помощью «доска". При таком подходе синтаксический и семантический анализ происходят одновременно.

Я бы рекомендовал использовать bitpar, очень эффективный анализатор PCFG, написанный на C++. Я написал для него оболочку Python на основе оболочки, см. https://github.com/andreasvc/eodop/blob/master/bitpar.py

Я думаю, что ANTLR — лучший из известных мне генераторов синтаксических анализаторов для Java. Я не знаю, предоставит ли Jython хороший способ взаимодействия Python и Java.

Несколько поздно, но вот еще два варианта для вас:

Spark — это анализатор Earley, написанный на Python.

Elkhound — парсер GLR, написанный на C++. Elkhound использует синтаксис, подобный Bison.

Если это можно выразить как язык PEG (я не думаю, все CFG могут, но предположительно могут многие), тогда вы можете использовать pyPEG, который должен быть линейным при использовании реализации синтаксического анализа packrat (хотя это потенциально запрещает использование памяти).

У меня нет никакого опыта с этим, так как я только начинаю снова исследовать синтаксический анализ и компиляцию после долгого перерыва в этом, но я читаю хорошие слухи об этой относительно современной технике. YMMV.

Попробуйте запустить его на PyPy, это может быть намного быстрее.