1 # Recursive Random Rewrites

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][].

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.

14 The `Grammar`'s `expand` method then randomly expands an input string

15 based on the grammar specified.

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:

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.

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>`.

34 Production rules are case-sensitive. By convention, terminals start

35 with a lowercase letter.

37 ## Example

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.

43 (This example is also available as a loadable module in the included

44 `term.js` file.)

46 var grammar = new rrr.Grammar({

47 // Canonical expression/term/factor grammar.

49 Expr: ['<Term>', '<Term> + <Term>', '<Term> - <Term>'],

50 Term: ['<Fact>', '<Fact> * <Fact>', '<Fact> / <Fact>'],

51 Sign: ['-', ''],

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 },

68 // A numeral may not begin with a 0.

69 Number: ['<Sign><digit><digit0>*'],

70 digit: '123456789',

71 digit0: '1234567890'

73 }, '<Expr>'); // This is the default start token.

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.

79 grammar.generate(); // Equivalent to grammar.generate('<Expr>')

80 // => '-9 * 3512 + (-(-51 - -9 / 6) / -6278 + -4 * 30321) / 21940'

82 grammar.generate('Solve: <Expr>');

83 // => 'Solve: 7 + (255 * (4 / 18))'

85 grammar.generate("Today's numbers are <Number> and <Number>.");

86 // => 'Today\'s numbers are 94 and -142.'

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.

94 ## FAQ

96 ### Why doesn't `expand` return?

97 ### Why do I get `RangeError: Maximum call stack size exceeded`?

99 Your grammar contains infinitely recursive rules. This is not

100 currently handled.

102 ### Why aren't `foo{4}`, `foo+`, etc. working?

104 Repetition modifiers only apply to rules, not literals.

106 ### Can I use `+` but with a chance other than ½?

108 If you need probabilities other than 50% you can use weighted rules, e.g.

110 { A: { '<foo>": 0.8, "<foo><A>": 0.2 } }

112 will contain one `<foo>` 80% of the time, two 16% of the time, three

113 3.2% of the time, etc.

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