Генерация случайных имен из грамматики

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

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

Грамматики

Грамматика – это просто формальный набор правил, описывающих все возможные элементы набора. Например, если у нас есть набор строк, имеющих вид «a», «b», «ab», «aab», «aabb», «aaab», «abbb» и т. д., одна грамматика, описывающая эти строки могут быть такими:

S := A B
A := ‘’ | ‘a’ A
B := ‘’ | ‘b’ B

Каждая из этих строк называется производственным правилом. Первый символ в первой строке (по соглашению) является начальным символом и указывает, где начинается грамматика. Вот это S. Грамматика говорит нам, что S можно заменить на A, за которым следует B.

Таким образом, расширяя S, у нас теперь есть AB, и мы можем приступить к расширению этих символов по очереди. Начнем с A, который (согласно правилу) может быть заменен либо пустой строкой, либо буквой «a», за которой следует другая A. B расширяется аналогичным образом. (Эти строки в кавычках называются терминалами, потому что их нельзя заменить ничем другим.) Мы повторяем этот процесс до тех пор, пока результат не будет полностью состоять из терминальных символов.

Создание контента из грамматики

Вот самое интересное! Мы можем генерировать контент из грамматики с помощью рекурсии. Если мы определим функцию для каждого нетерминального символа (S, A, и B в приведенной выше грамматике), мы можем скомпоновать эти функции таким образом, что вызов S вернет случайную строку, как в реализации Ruby ниже:

def S
  A + B
end
def A
  if rand(10) < 5
    ""
  else
    "a" + A
  end
end
def B
  if rand(10) < 5
    ""
  else
    "b" + B
  end
end

Разве это не круто? Я упоминал, что люблю играть с грамматиками?

Еженедельное соревнование по программированию #2

Итак, все это подводит нас к нашему еженедельному вызову. Мы собираемся написать программу, которая случайным образом генерирует синдаринские имена из простой грамматики. Но я не буду давать вам грамматику. О нет. Это часть удовольствия. :) Вместо этого вам нужно будет придумать грамматику, проанализировав самого Толкина. (Я рекомендую этот список составных синдаринских имен, но используйте любой источник, который вы предпочитаете.)

Однако я дам вам подсказку — не пытайтесь определять грамматику посимвольно. Вместо этого определите слоги и постройте грамматику вокруг них.

Итак, задача:

Обычный режим: реализация генератора имен. Ваше решение должно:

  1. Отображение списка из десяти случайно сгенерированных имен в синдаринском стиле.
  2. Составьте имена не менее чем из двух слогов и не более чем из пяти.
  3. Быть основанным на грамматике, как описано выше. Грамматика НЕ ​​должна быть в состоянии генерировать все возможные синдаринские имена — достаточно, чтобы быть убедительной.
  4. Включите используемую грамматику — хотя бы просто как комментарий к коду.

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

Жесткий режим: ваша программа должна принимать в качестве аргумента файл, содержащий определение грамматики, и случайным образом генерировать десять строк из этой грамматики. Грамматика может быть в любом формате, который вам легче всего разобрать (но вы получаете серьезные бонусные баллы за умение читать расширенную форму Бэкуса-Наура (EBNF)). Ваша заявка должна включать файл с грамматикой синдаринских имен, а также хотя бы одну другую грамматику по вашему выбору.

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

Идти! Крайний срок подачи заявок — 12:00 MDT (18:00 UTC) в субботу, 13 августа.

Это задание завершено, но, пожалуйста, не стесняйтесь публиковать свои решения! Мне всегда нравится смотреть, как люди подходят к таким проблемам.