Как мне генерировать предложения из формальной грамматики?
https://stackoverflow.com/questions/603687
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Как обычно формируются предложения из грамматики?
Мне нужен алгоритм, который является своего рода противоположностью синтаксического анализатора.То есть, учитывая формальную контекстно-свободную грамматику (скажем, 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 { ... }
}
Решение
Я не знаю, существует ли «общий» алгоритм для этого.Генерация случайных программ используется в генетическом программировании, поэтому вы можете найти систему 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);
}
}
Это предполагает, что вы прочитали все части некоторой структуры данных.Вам также нужно будет обрабатывать повторения (случайным образом генерировать количество раз, когда они происходят) и дополнительные правила (подбросить монетку, чтобы увидеть, есть они или нет).
Редактировать:Да, и если правило имеет более одного варианта, вы просто выбираете один из вариантов и обрабатываете его таким же образом.Итак, если бы какое-то правило было (Литерал | Переменная), вы бы случайным образом выбрали одно из двух.
Другие советы
Вот пример Python, использующий НЛТК:
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()))
Пример адаптирован из книга.Сгенерированные предложения являются синтаксически правильными, но все же являются полной тарабарщиной.
Ваше решение должно следовать индуктивной структуре грамматики.Как сгенерировать случайное высказывание для каждого из следующих утверждений?
- Символ терминала
- Нетерминальный символ
- Последовательность правых частей
- Выбор правых частей
- Звездообразное замыкание правых сторон
Все станет намного понятнее, если вы запишете структуру данных, которую используете для представления грамматики.Структура вашего набора взаимно рекурсивных функций-генераторов будет очень точно отражать эту структуру данных.
Работа с бесконечной рекурсией немного рискованна.Самый простой способ — создать поток высказываний и сохранить ограничение по глубине.Или, если вы используете ленивый язык, такой как Haskell, вы можете сгенерировать все высказываний и отделяйте столько конечных, сколько захотите (задача сложнее, чем исходный вопрос, но очень занимательная).
С верхней части моей головы:
Я бы работал рекурсивно (по сути, в противоположность хорошему рекурсивному парсеру), используя некоторую эвристику о том, что делать с диапазонами ((...):наверное выберу наугад) опционально (?:видеть [], ниже), повторения('' Распределение Пуассона?).Литералы ("...") просто записываются на выходные данные, а подтокены (`<...>') генерируют рекурсию.
Это не должно быть слишком сложно, если вы не хотите гарантировать какой-то полный охват.Даже тогда, просто генерируя связка данных было бы полезно...
[*] Вам необходимо включать дополнительные параметры менее чем в 50 % случаев, чтобы предотвратить бесконечный регресс при обработке таких правил, как
nonterm: otherstuff <nonterm>?
Хороший улов постамент.
Аналогично с повторениями, создайте сильно сходящееся распределение.
Сначала вам нужно будет проанализировать входную грамматику, если она представлена в форме BNF, как здесь.Проще всего было бы использовать сопоставление (name, string), затем начните с токена самого высокого уровня (который, как вы можете предположить, означает первый...).
Это дает вам:
("программа", "<импорт> NEWLINE?<пространство имен>")
(«импорт», («импорт» <идентификатор> NEWLINE)*)
...
Вы начинаете с «программы», нажимаете «<импорт>», чтобы повторить... по возвращении нажмите «NEWLINE?», так что бросайте кости и пишите или нет, нажмите «<пространство имен>», так что повторите... по возвращении все готово.
Я ловлю себя на подозрении, что это уже делалось раньше.Если вам просто нужен результат, я бы поискал в Интернете...Возможно http://portal.acm.org/citation.cfm?doid=966137.966142, хотя огромное количество генераторов парсеров загромождает пространство поиска...Пытаться Эта бумага, слишком.
Кстати, в вашем местном университете, вероятно, есть онлайн-подписка на эти журналы, поэтому вы можете получить их бесплатно, подключившись к библиотеке.
Проблема, с которой вы столкнетесь, заключается в том, что рекурсивная природа графа такова, что вы можете генерировать правильные грамматики бесконечного размера.Вероятно, вы захотите сделать что-то вроде настройки хэша типов узлов в своей грамматике с указанием количества и ограничений того, сколько раз вы позволяете себе попасть в этот узел.Тогда ищите в глубину, сколько душе угодно.
Мое первое предложение — поиск в ширину.Просто создайте график правил и выполните поиск по ним.Вы начнете выплевывать программы, начиная с самых маленьких и постепенно увеличиваясь.Однако вы, скорее всего, обнаружите, что ваша грамматика будет выдавать экспоненциально больше программ для заданного количества правил, и вы, скорее всего, не превысите 30 или около того токенов в программе, использующей DFS.
Проблема с поиском в глубину заключается в том, что как только у вас появится правило леворекурсивного поиска, ваш поиск застрянет в бесконечном цикле.
Другая большая проблема заключается в том, что синтаксически правильные программы далеки от семантически правильных программ.Генерация последнего типа, вероятно, совершенно неосуществима во всех случаях, кроме самых простых.
Как обычно, я не советую изобретать велосипед.Я написал один из них для ассемблера ARM, но официально сожалею об этом (Программное обеспечение:Практика и опыт апрель 2007 г.):
«Оглядываясь назад, можно сказать, что для генерации случайных инструкций сборки ARM для сравнения следовало использовать готовый генератор выражений.Вместо этого сценарий Perl создавался поэтапно, принимая каждое определение инструкции ARM и генерируя экземпляры.Однако преимущество поэтапного внутреннего подхода заключалось в том, что простые замены выявляли простые ошибки, и поиск ошибок мог продолжаться постепенно».
Боюсь, я не помню, что заставило меня изменить свое мнение, и сомневаюсь, что это будет иметь отношение к вашим конкретным потребностям, но я предлагаю тщательнее поискать уже существующее решение.Самостоятельное написание подобных вещей требует меньше дисциплины, но это всегда занимает больше времени, чем вы ожидаете.
не ответ, но проверьте запись в Википедии о генерации грамматики:http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms
в нем описаны некоторые распространенные используемые алгоритмы.
Хотя идея хороша (я уже много раз думал об этом), реальность такова, что без некоторых выборочных данных и/или множества ограничений/ограничений усилий генератора это довольно большая работа.
Возможно, кому-то будет проще писать образцы вручную.:)
