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

Question

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

Сейчас я использую парсер NLTK , который выдает правильный вывод, но очень медленный. Для моей грамматики ~ 450 довольно неоднозначных нелексиконных правил и полумиллиона лексических записей, анализ простых предложений может занять от 2 до 30 секунд, в зависимости от количества результирующих деревьев. Лексические записи практически не влияют на производительность.

Другая проблема заключается в том, что загрузка (25 МБ) грамматики + лексики в начале может занять до минуты.

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

Так что теперь я ищу синтаксический анализатор CFG для замены NLTK. Я рассматривал PLY , но я не могу сказать, поддерживает ли он структурные особенности в CFG, которые требуются в моем случае, и примеры, которые я видел, похоже, делают довольно много процедурного анализа чем просто указание грамматики. Кто-нибудь может показать мне пример PLY как с поддержкой структур функций, так и с использованием декларативной грамматики?

Я также в порядке с любым другим парсером, который может делать то, что мне нужно, эффективно. Интерфейс Python предпочтителен, но не абсолютно необходим.

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

С некоторым опозданием, но вот еще два варианта:

Spark - это парсер Earley, написанный на Python.

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

Answer 5

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

Answer 6

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

Answer 7

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

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

Answer 8

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