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

Question

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

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

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

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

Пример сгенерированного program :

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

Answer 1

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

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

Answer 2

Я не знаю, что есть «общий» алгоритм для этого. Генерация случайных программ используется в генетическом программировании, поэтому вы можете найти основанную на грамматике систему 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);
  }
}

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

---

Редактировать: Да, и если в правиле есть несколько вариантов, вы просто выберите один из вариантов и обработаете его таким же образом. Так что если какое-то правило было (Литерал | Переменная), вы бы случайно выбрали между ними.

Answer 3

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

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

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

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

Answer 4

с макушки головы:

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

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

---

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

 nonterm:  otherstuff <nonterm>?

Хороший улов по плинтусу .

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

---

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

Это дает вам:

("программа", " NEWLINE? ")

(«импорт», («импорт» NEWLINE) *)

...

Когда вы начинаете с "program", нажимаете "", поэтому вы возвращаетесь ... при возвращении, история "NEWLINE?", Поэтому бросьте кубик и напишите или нет, нажмите "", чтобы повториться ... по возвращении все готово.

---

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

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

Answer 5

Как обычно, я собираюсь посоветовать не изобретать велосипед. Я написал одну из них для ассемблера ARM, но я сожалею об этом ( Программное обеспечение: практика и опыт апрель 2007 г.):

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

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

Answer 6

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

Answer 7

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

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

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

Answer 8

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

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

Answer 9

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

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