= panini

Panini is a flexible toolkit that enables you to generate sentences from a context-free grammar, also known as a CFG.

== CFG Background

Informally, a context-free grammar consists of a set of productions rules where a _nonterminal_ on the right
hand side of the produces a string of terminals and nonterminals on the right hand side.  Like this:

  S -> AB
  A -> a
  B -> b

I the above example, _S_, _A_, and _B_ are all nonterminals.  _a_ and _b_ are terminals.  Furthermore, the nonterminal _S_ is the _start_ _symbol_ for this CFG.  By applying the productions as follows:

  S     (start symbol)
  AB    (apply S -> AB)
  aB    (apply A -> a)
  ab    (apply B -> b)

The sentence _ab_ is generated.  In fact, this is the only sentence this grammar can produce!  By adding one additional production to the grammar:

  S -> ASB

The grammar may now potentially create an infinite number of sentences.  They will all have the form of _a_<sup>i</sup>_b_<sup>i</sup> where _i_ > 1. Here is one more example derivation:

  S      (start symbol)
  ASB    (apply S -> ASB)
  aSB    (apply A -> a)
  aSb    (apply B -> b)
  aaSbb  (apply S -> ASB)
  aaABbb (apply S -> AB)
  aaaBbb (apply A -> a)
  aaabbb (apply B -> b)

You learn more about CFGs, you can reference the CFG article[http://en.wikipedia.org/wiki/Context-free_grammar] on Wikipedia</a>.

== Getting Started With Panini

=== Defining a Grammar

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

Here's how the grammar from above 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'

=== Derivators

Derivators are objects that take a Panini::Grammar and then apply the rules to generate a sentence.  Creating the sentences
from the grammar can be tricky, and certain derivation strategies may be better for some grammars.
Currently, the main derivator is the Panini::DerivationStrategy::RandomDampened derivator.

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

=== Generating a Sentence

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']


== Example

In this example, we create a grammar that generates mathematical expressions.

  # ================
  # = Nonterminals =
  # ================
  expression = grammar.add_nonterminal("EXPR")
  term = grammar.add_nonterminal("TERM")
  factor = grammar.add_nonterminal("FACT")
  identifier = grammar.add_nonterminal("ID")
  number = grammar.add_nonterminal("NUM")


  # =============
  # = Terminals =
  # =============
  expression.add_production([term, '+', term])
  expression.add_production([term, '-', term])
  expression.add_production([term])

  term.add_production([factor, '*', term])
  term.add_production([factor, '/', term])
  term.add_production([factor])

  factor.add_production([identifier])
  factor.add_production([number])
  factor.add_production(['(', expression, ')'])

  ('a'..'z').each do |v|
    identifier.add_production([v])
  end

  (0..100).each do |n|
    number.add_production([n])
  end

  # ===============================================
  # = Choose a strategy and create some sentences =
  # ===============================================
  deriver = Panini::DerivationStrategy::RandomDampened.new(grammar)
  10.times do
    puts "#{deriver.sentence.join(' ')}"
  end

== Contributing to panini
* Check out the latest master to make sure the feature hasn't been implemented or the bug hasn't been fixed yet
* Check out the issue tracker to make sure someone already hasn't requested it and/or contributed it
* Fork the project
* Start a feature/bugfix branch
* Commit and push until you are happy with your contribution
* Make sure to add tests for it. This is important so I don't break it in a future version unintentionally.
* Please try not to mess with the Rakefile, version, or history. If you want to have your own version, or is otherwise necessary, that is fine, but please isolate to its own commit so I can cherry-pick around it.

== To Do

=== Features
* Detect invalid grammars
* Weighted productions.
* Arbitrary start symbol.
* Support Enumerator?
* DSL?
* Purdom Derivator?

=== Examples
* Natural language
* XML
* JSON
* Address
* Tree/Flower (PS?)
* Simulated user actions

== Copyright

Copyright (c) 2011 Matthew Bellantoni. See LICENSE.txt for further details.