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

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

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

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

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

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

Первое, что пришло на ум:

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

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

[*] необходимо включать optionals меньше чем 50% времени для предотвращения бесконечного регресса когда правила обработки как

 nonterm:  otherstuff <nonterm>?

Хорошая выгода постаментом.

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

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

Это дает Вам:

("программа", "<импорт> НОВАЯ СТРОКА? <пространство имен>")

("импорт", ("импорт" <идентификатор> НОВАЯ СТРОКА) *)

...

Вы запускаются с "программы", совершают нападки" <импортирует>", таким образом, Вы повторяетесь... на возвращении, тсс "НОВАЯ СТРОКА?", так бросьте игру в кости и запись или нет, совершите нападки" <пространство имен>", так повторитесь... по возврату, Вы сделаны.

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

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

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

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

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

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

это описало некоторые используемые общие алгоритмы.

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

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

As usual, I’m going to advise against reinventing the wheel. I’ve written one of these for ARM assembler, but I’m on record as regretting it (Software: Practice and Experience April 2007):

“In retrospect, an off-the-shelf expression generator should have been used to generate random ARM assembly instructions for comparison. Instead a Perl script was built incrementally, taking each ARM instruction definition and generating instances. An advantage, however, of the incremental in-house approach was that simple substitutions detected simple bugs, and bug hunting could proceed incrementally.”

I’m afraid I don’t recall what made me change my mind, and I doubt it would be relevant to your specific needs, but I do suggest looking harder for a preexisting solution. It requires less discipline to write stuff like this yourself, but it always takes longer than you expect.

Вот пример 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()))

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