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.
The gem can be installed via:
gem install panini
You can also find the code on GitHub.
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:
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!