term.js

   1 (function (exports) {
   2     /*global require */
   3     var rrr = exports.rrr || require('./rrr');
   4
   5     var grammar = new rrr.Grammar({
   6         // Canonical expression/term/factor grammar.
   7         Expr: ['<Term>', '<Term> + <Term>', '<Term> - <Term>'],
   8         Term: ['<Fact>', '<Fact> * <Fact>', '<Fact> / <Fact>'],
   9         Sign: ['-', ''],
  10
  11         // If a parenthesized expression is as likely as a number, the
  12         // expansion explodes and overflows the stack. You can prove
  13         // this by multiplying out the probabilities: On average, Expr
  14         // produces 5/3 Terms, Terms produce 5/3 Facts, and Fact
  15         // produces 1/2 Exprs.
  16         //
  17         // So with equal weights Expr produces, on average,
  18         // (5/3)*(5/3)*(1/2) ~= 1.4 Exprs.
  19         //
  20         // That means Expr must be weighed at _most_ 1/1.4 ~= 0.72
  21         // relative to the other option to produce one Expr, and in
  22         // practice should be even less to avoid "lucky" stack
  23         // overflows.
  24         Fact: { '<Number>': 1, '<Sign>(<Expr>)': 0.4 },
  25
  26         // A numeral may not begin with a 0.
  27         Number: ['<Sign><digit><digit0>*'],
  28         digit: '123456789',
  29         digit0: '1234567890'
  30     }, '<Expr>');
  31
  32     exports.randomEquation = grammar.expand.bind(grammar);
  33 })(typeof module !== 'undefined' ? module.exports : this);