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:

• <A>{n} - Repeat rule A n times.
• <A>{n,m} - Repeat rule A a random number of times between n and m (uniformly, inclusive).
• <A>? - Produce rule A ½ of the time, and nothing ½ of the time.
• <A>* - Produce nothing ½ of the time, <A> ¼ of the time, <A><A> ⅛ of the time, and so on.
• <A>+ - Produce <A> ½ of the time, <A><A> ¼ of the time, <A><A><A> ⅛ of the time, and so on.

Repetition patterns can also be specified with a space after the rule name, e.g. <A >+. In this case, the repetitions have spaces between them, e.g. <A> <A>.

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>', '<Term> + <Term>', '<Term> - <Term>'],
    Term: ['<Fact>', '<Fact> * <Fact>', '<Fact> / <Fact>'],
    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: { '<Number>': 1, '<Sign>(<Expr>)': 0.4 },

    // A numeral may not begin with a 0.
    Number: ['<Sign><digit><digit0>*'],
    digit: '123456789',
    digit0: '1234567890'

}, '<Expr>'); // 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('<Expr>')
// => '-9 * 3512 + (-(-51 - -9 / 6) / -6278 + -4 * 30321) / 21940'

grammar.generate('Solve: <Expr>');
// => 'Solve: 7 + (255 * (4 / 18))'

grammar.generate("Today's numbers are <Number> and <Number>.");
// => '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 <Fact> <op> <Fact> (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: { '<foo>": 0.8, "<foo><A>": 0.2 } }

will contain one <foo> 80% of the time, two 16% of the time, three 3.2% of the time, etc.