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

Какой общий способ генерации предложений из грамматики?

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

Пример грамматики:

program   : <imports> NEWLINE? <namespace>
imports   : ("import" <identifier> NEWLINE)* 
namespace : "namespace " <identifier> NEWLINE "{" <classes> "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)*
...

Пример сгенерированной программы:

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

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

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

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