ETOOBUSY 🚀 minimal blogging for the impatient
Fantasy Name Generator - a grammar
I stumbled upon a grammar for a “system” for generating fantasy names.
Sifting through some of my links, I (re-)discovered an interesting blog: null program. Among a lot of stuff there, I was intrigued by Fantasy Name Generator: Request for Patterns, from about eleven years ago.
In a nutshell, the author re-created the Fantasy Name Generator by Samuel Stoddard at RinkWorks, implementing a parser for the generator sequences and then using them to do the actual generator.
It’s interesting that at the time the author was still using Perl and leveraged Parse::RecDescent to use a grammar he came up with to do the parsing. I don’t know why, the result was slooooowwwww, maybe due to a combination of an older version of the module and probably a grammar that can be improved.
The code is online at FantasyName.pm, which is interesting for a few reasons:
- Parse::RecDescent allows to pre-generate a parser and save it as a module. This saves doing this over and over;
- I usually separate the parsing phase from the usage phase, so that I have to do the parsing once and reuse it over and over. I noticed that the actual generation of the result is interspersed in the parsing, so that any new name requires going through the grammar every time.
The supported language is described in the Fantasy Name Generator instructions. The grammar is the following:
LITERAL ::= /[^|()<>]+/ TEMPLATE ::= /[-svVcBCimMDd']/ literal_set ::= LITERAL | group template_set ::= TEMPLATE | group literal_exp ::= literal_set literal_exp | literal_set template_exp ::= template_set template_exp | template_set literal_list ::= literal_exp "|" literal_list | literal_exp "|" | literal_exp template_list ::= template_exp "|" template_list | template_exp "|" | template_exp group ::= "<" template_list ">" | "(" literal_list ")" name ::= template_list | group
I reshaped it to take advantage of the star operator, among other things:
LITERAL ::= /[^|()<>]+/ TEMPLATE ::= /[-svVcBCimMDd']+/ literal_set ::= LITERAL | group literal_exp ::= literal_set* literal_list ::= literal_exp ("|" literal_exp)* template_set ::= TEMPLATE | group template_exp ::= template_set* template_list ::= template_exp ("|" template_exp)* group ::= "<" template_list ">" | "(" literal_list ")" name ::= template_list | group
TEMPLATEtakes multiple template characters at once. I can then divide them afterwards;
- the two
_expdefinitions are actually just a sequence of the corresponding
_setdefinitions, so we’re using the start operator;
- the two
_listexpressions are actually the correponding expression, followed by a sequence of zero or more alternation separators (i.e.
|) followed by another expression.
The grammar is sound and compact, although it’s somehow strange that it’s been designed to be fully compatible with the original - because the original is not open source and its pre-defined expressions are not available.
I would have probably gone for something more refactored, using escape characters for templates and only one grouping symbol.