Как генерировать предложения из формальной грамматики?

Ответ 1

Я не знаю, что для этого существует "общий" алгоритм. Генерация случайной программы используется в генетическом программировании, поэтому вы можете искать грамматическую систему GP и посмотреть, как они обрабатывают генерацию программ. Я бы сделал алгоритм генерации рекурсивного правила, такой как псевдокод:

void GenerateRule(someRule)
{
  foreach (part in someRule.Parts)
  {
    if (part.IsLiteral) OutputLiteral(part);
    if (part.IsIdentifier) Output(GenerateIdentifier(part)));
    if (part.IsRule) GenerateRule(part.Rule);
  }
}

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

Изменить: О, и если правило имеет более одного параметра, вы просто выберите один из вариантов, с которым нужно пойти, и обработайте его таким же образом. Поэтому, если какое-то правило было (Literal | Variable), вы случайно выбрали бы между ними.

Ответ 2

Вот пример Python с помощью NLTK:

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

Пример адаптирован из book. Сгенерированные предложения являются синтаксически правильными, но все же общей тарабарщиной.

Ответ 3

Сверху моей головы:

Я бы работал рекурсивно (в основном, против рекурсивного приличного парсера), используя некоторую эвристику о том, что делать с диапазонами ((...): возможно, выбирайте случайным образом) (?: см. [] ниже), повторения ('' распределение Пуассона?). Литералы ("...") просто записываются на выход, а subtokens (`<... > ') генерируют рекурсию.

Это не должно быть слишком сложно, если вы не хотите гарантировать какой-то полный охват. Даже тогда просто создание группы данных было бы полезным...

[*] Вам нужно включить дополнительные опции менее 50% времени, чтобы предотвратить бесконечный регресс при обработке правил, таких как

 nonterm:  otherstuff <nonterm>?

Хорошая уловка плинтуса.

Аналогично с повторениями, бросьте распределения, которые сильно сходятся.

Сначала вам нужно проанализировать входную грамматику, если она представлена ​​в форме BNF, как здесь. Проще всего было бы использовать сопоставление (name, string), а затем начать с токена наивысшего уровня (который вы можете считать первым)...

Это дает вам:

( "program", "<import> NEWLINE <namespace> " )

( "import", ( "import" < идентификатор > NEWLINE) *)

...

Вы начинаете с "программы", нажимаете "<import> "; так что вы возвращаетесь... вернувшись назад, запустите "NEWLINE?", поэтому бросьте кости и напишите или нет, нажмите "<namespace> ". так что возвращайтесь... по возвращении вы закончили.

Я считаю, что сам подозреваю, что это было сделано раньше. Если вам просто нужен выход, я бы поискал в Интернете... Возможно, http://portal.acm.org/citation.cfm?doid=966137.966142, хотя огромное количество генераторов парсера там загромождайте пространство поиска... Попробуйте эту статью.

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

Ответ 4

Ваше решение должно следовать индуктивной структуре грамматики. Как вы производите произвольное высказывание для каждого из следующих?

• Символ терминала
• Нетерминальный символ
• Последовательность правых частей
• Выбор правых сторон
• Закрытие звезды правых частей

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

Работа с бесконечной рекурсией - это немного рискованно. Самый простой способ - создать поток высказываний и сохранить отсечку глубины. Или, если вы используете ленивый язык, такой как Haskell, вы можете генерировать все высказывания и снимать с них столько конечных, сколько хотите (более сложная проблема, чем исходный вопрос, но очень интересная).

Ответ 5

Мое первое предложение было бы первым поиском. Просто настройте график правил и выполните поиск через них. Вы начнете выплевывать программы, начиная с самых маленьких, и постепенно увеличиваясь. Вы, скорее всего, обнаружите, что ваша грамматика будет выставлять экспоненциально больше программ для определенного количества правил, и вы, вероятно, не получите более 30 или около того токенов в программе с использованием DFS.

Проблема с первым поиском глубины заключается в том, что во втором у вас есть леворекурсивное правило, ваш поиск застрянет в бесконечном цикле.

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

Ответ 6

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

Ответ 7

Как обычно, я собираюсь посоветовать не изобретать колесо. Ive написал один из них для ARM-ассемблера, но Im записывает его как сожаление (Software: Practice and Experience April 2007):

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

Я боюсь, что не помню, что заставило меня передумать, и я сомневаюсь, что это будет иметь отношение к вашим конкретным потребностям, но я предлагаю вам усложнить существовавшее ранее решение. Это требует меньше дисциплины, чтобы писать подобные вещи самостоятельно, но это всегда занимает больше времени, чем вы ожидаете.

Ответ 8

не ответ, но проверьте запись в википедии о генерации грамматики: http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

описал некоторые распространенные алгоритмы.

Ответ 9

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

Можно просто найти записи образцов вручную.:)