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     var grammar = new rrr.Grammar({
  47         // Canonical expression/term/factor grammar.
  48
  49         Expr: ['<Term>', '<Term> + <Term>', '<Term> - <Term>'],
  50         Term: ['<Fact>', '<Fact> * <Fact>', '<Fact> / <Fact>'],
  51         Sign: ['-', ''],
  52
  53         // If a parenthesized expression is as likely as a number, the
  54         // expansion explodes and overflows the stack. You can prove
  55         // this by multiplying out the probabilities: On average, Expr
  56         // produces 5/3 Terms, Terms produce 5/3 Facts, and Fact
  57         // produces 1/2 Exprs.
  58         //
  59         // So with equal weights Expr produces, on average,
  60         // (5/3)*(5/3)*(1/2) ~= 1.4 Exprs.
  61         //
  62         // That means Expr must be weighed at _most_ 1/1.4 ~= 0.72
  63         // relative to the other option to produce one Expr, and in
  64         // practice should be even less to avoid "lucky" stack
  65         // overflows.
  66         Fact: { '<Number>': 1, '<Sign>(<Expr>)': 0.4 },
  67
  68         // A numeral may not begin with a 0.
  69         Number: ['<Sign><digit><digit0>*'],
  70         digit: '123456789',
  71         digit0: '1234567890'
  72
  73     }, '<Expr>'); // This is the default start token.
  74
  75 To generate a random equation, call `grammar.generate()`. If you want
  76 a start expression other than the default, you can provide a different
  77 initial string.
  78
  79     grammar.generate(); // Equivalent to grammar.generate('<Expr>')
  80     // => '-9 * 3512 + (-(-51 - -9 / 6) / -6278 + -4 * 30321) / 21940'
  81
  82     grammar.generate('Solve: <Expr>');
  83     // => 'Solve: 7 + (255 * (4 / 18))'
  84
  85     grammar.generate("Today's numbers are <Number> and <Number>.");
  86     // => 'Today\'s numbers are 94 and -142.'
  87
  88 Because RRR is not parsing and unconcerned with ambiguity, some of the
  89 standard rules could be simplified. For example, `Expr` could be
  90 written as `<Fact> <op> <Fact>` (with `op` defined as `+-*/`),
  91 removing the need for `Term`. Such a grammar would still generate only
  92 valid expressions, but with slightly different probabilities.
  93
  94 ## FAQ
  95
  96 ### Why doesn't `expand` return?
  97 ### Why do I get `RangeError: Maximum call stack size exceeded`?
  98
  99 Your grammar contains infinitely recursive rules. This is not
 100 currently handled.
 101
 102 ### Why aren't `foo{4}`, `foo+`, etc. working?
 103
 104 Repetition modifiers only apply to rules, not literals.
 105
 106 ### Can I use `+` but with a chance other than ½?
 107
 108 If you need probabilities other than 50% you can use weighted rules, e.g.
 109
 110     { A: { '<foo>": 0.8, "<foo><A>": 0.2 } }
 111
 112 will contain one `<foo>` 80% of the time, two 16% of the time, three
 113 3.2% of the time, etc.
 114
 115
 116 [L-system]: http://en.wikipedia.org/wiki/L-system
 117 [Markov machine]: http://en.wikipedia.org/wiki/Markov_algorithm
 118 [stochastic grammar]: http://en.wikipedia.org/wiki/Stochastic_grammar
 119 [BNF]: http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form