Generative Grammar

Updated April 24, 2019

Generative grammars let you build generative systems that produce variety, and structure.

A generative grammar describes a set of rules for constructing meaningful sentences from individual words. "Sentence" and "word" are meant loosely — really, grammars can be used to build many kinds of structures from smaller component parts. Textile designs, automatic poetry creators, and procedural level builders are all places where grammars could be used.

Grammars are DNA for your generator

DNA is a generative grammar with 4 "words" — GATC. Evolution is the process by which those words are expanded into a wide variety of "sentences", including you.

Taking a cue from nature, we can use generative grammars to construct "DNA" for generative programs:

  • Generate a series of drawing commands using a grammar.
  • Design game levels and rooms using a grammar.
  • Describe cathedrals, mandalas, rose windows, city plans, or haikus using a grammar.

What does a grammar look like?

Grammars are often defined using named lists of templates:

<story>:
- Once upon a time, there was a <hero> who lived in a <location>...
- A long time ago, in a <location> far, far away, there was a <hero>...

Each template variable references another list of templates, which may reference other templates, and so on... describing a graph of relationships between templates.

<location>:
- <adjective> wood
- hut at the edge of a <landmark>
- castle far away

A template variable can be replaced with any item from the corresponding list of templates, and the resulting sentence will be valid. Structural correctness is encoded within the grammar itself.

By walking this graph of relationships, and making choices at each branch, we can expand the grammar into sentences:

Once upon a time, there was a kind old fisherman
who lived in a hut at the edge of a quiet river.

The choices we make at each branch might be random, weighted, or determined by some other factor. The graph of relationships defines the structure, the choices produce variety.

Lenses

  • When you see something that exhibits structure and variety, ask "can I describe this as a grammar?". Now, you have a recipe for generating that thing.
  • Some grammars result in evolution. Others don't. What would it look like to introduce mutation, heredity, or selection to your grammar?

Resources