description | Recursive Random Rewrites |

owner | Yukkuri Games (Git) |

last change | Fri, 10 Oct 2014 10:21:08 +0000 (12:21 +0200) |

URL | http://git.yukkurigames.com/rrr.git |

readme

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.

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.

`expand`

return?`RangeError: Maximum call stack size exceeded`

?Your grammar contains infinitely recursive rules. This is not currently handled.

`foo{4}`

, `foo+`

, etc. working?Repetition modifiers only apply to rules, not literals.

`+`

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.

2014-10-10 |
Joe Wreschnig | Fix old project name. master | commit | commitdiff | tree |

2014-10-10 |
Joe Wreschnig | Remove nonstandard Markdown hints. | commit | commitdiff | tree |

2014-10-09 |
Joe Wreschnig | Initial import. | commit | commitdiff | tree |

8 years ago |
master | shortlog | log | tree |