Matthew Bellantoni

Panini: A Way to Generate Sentences From A Context Free Grammar

panini, ruby

One of the coolest things I ever learned about were Context Free Grammars (also known as a CFG.) I'll leave the description of CFGs to Wikipedia.

I've always had an interest in using CFGs to generate sentences that could be used to seed data sets, or to create a series of certain actions within a bounded set (e.g. to drive a GUI for testing purposes.)

I was never able to do that because I didn't have the tools. So, a couple of months ago I started creating a toolkit in Ruby called Panini that would allow me to do this.

Getting Started

The gem can be installed via:

  gem install panini

You can also find the code on GitHub.

Usage

Defining a grammar is easy. Create a grammar object, add some nonterminals and then add the productions to those nonterminals.

Here’s how a grammar to create sequences of the letters "a" and "b" is defined:

1
2
3
4
5
6
7
8
9
10
11
  
  grammar = Panini::Grammar.new
  
  nt_s = grammar.add_nonterminal
  nt_a = grammar.add_nonterminal
  nt_b = grammar.add_nonterminal
  
  n_s.add_production([n_a, n_b])        # S -> AB
  n_s.add_production([n_a, n_s, n_b])   # S -> ASB
  n_a.add_production(['a'])             # A -> 'a'
  n_b.add_production(['b'])             # A -> 'b'

Sentences are created from Grammars using a Derivator. Creating the sentences from the grammar can be tricky, and certain derivation strategies may be better for some grammars.

  derivator = Panini::DerivationStrategy::RandomDampened.new(grammar)

To generate a sentence, call the derivator's sentence method like thus:

  derivator.sentence -> ['a', 'a', 'b', 'b']

You will get a new sentence (depending on the grammar) with every call:

  derivator.sentence -> ['a', 'a', 'a', 'a', 'b', 'b', 'b', 'b']

Check out the README at GitHub to learn more!