# Recursive Random Rewrites
RRR is a JavaScript library which repeatedly applies replacements to a
string. This can be used to generate a wide variety of random text. It
is sort of like, but is not, an [L-system][], a [Markov machine][], or
a [stochastic grammar][].
RRR works by specifying a grammar using [BNF][]-like rules (easily
specified with JSON). An object providing the production rules,
mapping the names to possible expansions, is provided to the `Grammar`
constructor. Possible productions are specified as an object mapping a
production to a numeric weight.
The `Grammar`'s `expand` method then randomly expands an input string
based on the grammar specified.
For convenience, possible productions may also be provided as a list
or string, in which case each item has equal weight. RRR also provides
some syntactic sugar for repetition:
* `{n}` - Repeat rule `A` `n` times.
* `{n,m}` - Repeat rule `A` a random number of times between `n`
and `m` (uniformly, inclusive).
* `?` - Produce rule `A` ½ of the time, and nothing ½ of the time.
* `*` - Produce nothing ½ of the time, `` ¼ of the time,
`` ⅛ of the time, and so on.
* `+` - Produce `` ½ of the time, `` ¼ of the time,
`` ⅛ of the time, and so on.
Repetition patterns can also be specified with a space after the rule
name, e.g. `+`. In this case, the repetitions have spaces between
them, e.g. ` `.
Production rules are case-sensitive. By convention, terminals start
with a lowercase letter.
## Example
The following is the term/expression/factor grammar you might
encounter in a textbook about parsing. However, instead
of _parsing_ equations, RRR will generate random ones.
(This example is also available as a loadable module in the included
`term.js` file.)
var grammar = new rrr.Grammar({
// Canonical expression/term/factor grammar.
Expr: ['', ' + ', ' - '],
Term: ['', ' * ', ' / '],
Sign: ['-', ''],
// If a parenthesized expression is as likely as a number, the
// expansion explodes and overflows the stack. You can prove
// this by multiplying out the probabilities: On average, Expr
// produces 5/3 Terms, Terms produce 5/3 Facts, and Fact
// produces 1/2 Exprs.
//
// So with equal weights Expr produces, on average,
// (5/3)*(5/3)*(1/2) ~= 1.4 Exprs.
//
// That means Expr must be weighed at _most_ 1/1.4 ~= 0.72
// relative to the other option to produce one Expr, and in
// practice should be even less to avoid "lucky" stack
// overflows.
Fact: { '': 1, '()': 0.4 },
// A numeral may not begin with a 0.
Number: ['*'],
digit: '123456789',
digit0: '1234567890'
}, ''); // This is the default start token.
To generate a random equation, call `grammar.generate()`. If you want
a start expression other than the default, you can provide a different
initial string.
grammar.generate(); // Equivalent to grammar.generate('')
// => '-9 * 3512 + (-(-51 - -9 / 6) / -6278 + -4 * 30321) / 21940'
grammar.generate('Solve: ');
// => 'Solve: 7 + (255 * (4 / 18))'
grammar.generate("Today's numbers are and .");
// => 'Today\'s numbers are 94 and -142.'
Because RRR is not parsing and unconcerned with ambiguity, some of the
standard rules could be simplified. For example, `Expr` could be
written as ` ` (with `op` defined as `+-*/`),
removing the need for `Term`. Such a grammar would still generate only
valid expressions, but with slightly different probabilities.
## FAQ
### Why doesn't `expand` return?
### Why do I get `RangeError: Maximum call stack size exceeded`?
Your grammar contains infinitely recursive rules. This is not
currently handled.
### Why aren't `foo{4}`, `foo+`, etc. working?
Repetition modifiers only apply to rules, not literals.
### Can I use `+` but with a chance other than ½?
If you need probabilities other than 50% you can use weighted rules, e.g.
{ A: { '": 0.8, "": 0.2 } }
will contain one `` 80% of the time, two 16% of the time, three
3.2% of the time, etc.
[L-system]: http://en.wikipedia.org/wiki/L-system
[Markov machine]: http://en.wikipedia.org/wiki/Markov_algorithm
[stochastic grammar]: http://en.wikipedia.org/wiki/Stochastic_grammar
[BNF]: http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form