grammer_builder.py

import random

def is_terminal(token):
  return token[0] != "_"

def expand(grammer, tokens):
  result = []
  for token in tokens:
    if is_terminal(token):
      result.append(token)
    else:
      replacement = grammer[token]
      if is_terminal(replacement[0]):
        return [random.choice(replacement)]
      else:
        for replace in replacement:
          result = result + expand(grammer, [replace])
  return result

def generate_sentence(grammer):
  return expand(grammer, ["_S"])

generate_sentence({
  "_S": ["_A", "_N", "_V", "_N_thing"],
  "_A": ["big", "scary", "blue", "surprising"],
  "_N": ["cat", "dog", "bear"],
  "_N_thing": ["a hot dog", "a trash can", "all the snacks"],
  "_V": ["ate", "devoured", "ran"],
})