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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 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.

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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