README.md

   1 # Recursive Random Rewrites
   2
   3 RRR is a JavaScript library which repeatedly applies replacements to a
   4 string. This can be used to generate a wide variety of random text. It
   5 is sort of like, but is not, an [L-system][], a [Markov machine][], or
   6 a [stochastic grammar][].
   7
   8 RRR works by specifying a grammar using [BNF][]-like rules (easily
   9 specified with JSON). An object providing the production rules,
  10 mapping the names to possible expansions, is provided to the `Grammar`
  11 constructor. Possible productions are specified as an object mapping a
  12 production to a numeric weight.
  13
  14 The `Grammar`'s `expand` method then randomly expands an input string
  15 based on the grammar specified.
  16
  17 For convenience, possible productions may also be provided as a list
  18 or string, in which case each item has equal weight. RRR also provides
  19 some syntactic sugar for repetition:
  20
  21 * `<A>{n}` - Repeat rule `A` `n` times.
  22 * `<A>{n,m}` - Repeat rule `A` a random number of times between `n`
  23   and `m` (uniformly, inclusive).
  24 * `<A>?` - Produce rule `A` ½ of the time, and nothing ½ of the time.
  25 * `<A>*` - Produce nothing ½ of the time, `<A>` ¼ of the time,
  26   `<A><A>` ⅛ of the time, and so on.
  27 * `<A>+` - Produce `<A>` ½ of the time, `<A><A>` ¼ of the time,
  28   `<A><A><A>` ⅛ of the time, and so on.
  29
  30 Repetition patterns can also be specified with a space after the rule
  31 name, e.g. `<A >+`. In this case, the repetitions have spaces between
  32 them, e.g. `<A> <A>`.
  33
  34 Production rules are case-sensitive. By convention, terminals start
  35 with a lowercase letter.
  36
  37 ## Example
  38
  39 The following is the term/expression/factor grammar you might
  40 encounter in a textbook about parsing. However, instead
  41 of _parsing_ equations, RRR will generate random ones.
  42
  43 (This example is also available as a loadable module in the included
  44 `term.js` file.)
  45
  46     ::javascript
  47     var grammar = new rrr.Grammar({
  48         // Canonical expression/term/factor grammar.
  49
  50         Expr: ['<Term>', '<Term> + <Term>', '<Term> - <Term>'],
  51         Term: ['<Fact>', '<Fact> * <Fact>', '<Fact> / <Fact>'],
  52         Sign: ['-', ''],
  53
  54         // If a parenthesized expression is as likely as a number, the
  55         // expansion explodes and overflows the stack. You can prove
  56         // this by multiplying out the probabilities: On average, Expr
  57         // produces 5/3 Terms, Terms produce 5/3 Facts, and Fact
  58         // produces 1/2 Exprs.
  59         //
  60         // So with equal weights Expr produces, on average,
  61         // (5/3)*(5/3)*(1/2) ~= 1.4 Exprs.
  62         //
  63         // That means Expr must be weighed at _most_ 1/1.4 ~= 0.72
  64         // relative to the other option to produce one Expr, and in
  65         // practice should be even less to avoid "lucky" stack
  66         // overflows.
  67         Fact: { '<Number>': 1, '<Sign>(<Expr>)': 0.4 },
  68
  69         // A numeral may not begin with a 0.
  70         Number: ['<Sign><digit><digit0>*'],
  71         digit: '123456789',
  72         digit0: '1234567890'
  73
  74     }, '<Expr>'); // This is the default start token.
  75
  76 To generate a random equation, call `grammar.generate()`. If you want
  77 a start expression other than the default, you can provide a different
  78 initial string.
  79
  80     ::javascript
  81     grammar.generate(); // Equivalent to grammar.generate('<Expr>')
  82     // => '-9 * 3512 + (-(-51 - -9 / 6) / -6278 + -4 * 30321) / 21940'
  83
  84     grammar.generate('Solve: <Expr>');
  85     // => 'Solve: 7 + (255 * (4 / 18))'
  86
  87     grammar.generate("Today's numbers are <Number> and <Number>.");
  88     // => 'Today\'s numbers are 94 and -142.'
  89
  90 Because RRR is not parsing and unconcerned with ambiguity, some of the
  91 standard rules could be simplified. For example, `Expr` could be
  92 written as `<Fact> <op> <Fact>` (with `op` defined as `+-*/`),
  93 removing the need for `Term`. Such a grammar would still generate only
  94 valid expressions, but with slightly different probabilities.
  95
  96 ## FAQ
  97
  98 ### Why doesn't `expand` return?
  99 ### Why do I get `RangeError: Maximum call stack size exceeded`?
 100
 101 Your grammar contains infinitely recursive rules. This is not
 102 currently handled.
 103
 104 ### Why aren't `foo{4}`, `foo+`, etc. working?
 105
 106 Repetition modifiers only apply to rules, not literals.
 107
 108 ### Can I use `+` but with a chance other than ½?
 109
 110 If you need probabilities other than 50% you can use weighted rules, e.g.
 111
 112     { A: { '<foo>": 0.8, "<foo><A>": 0.2 } }
 113
 114 will contain one `<foo>` 80% of the time, two 16% of the time, three
 115 3.2% of the time, etc.
 116
 117
 118 [L-system]: http://en.wikipedia.org/wiki/L-system
 119 [Markov machine]: http://en.wikipedia.org/wiki/Markov_algorithm
 120 [stochastic grammar]: http://en.wikipedia.org/wiki/Stochastic_grammar
 121 [BNF]: http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form