<script>

function randInt(low_bound_inclusive, high_bound_inclusive) {
    var range = high_bound_inclusive - low_bound_inclusive;
    var r = Math.random();
    r = r * range;
    r = r + low_bound_inclusive;
    r = Math.round(r);
    return r;
}



proper_nouns = [
    'John',
    'Mary'
];

nominals = [
    'fish',
    'cat',
    'dog',
    'zebra',
    'horse',
    'donkey',
    'giraffe',
    'walrus',
];

determiners = [
    'the',
    'a',
];

past_tense_verbs = [
    'ate',
    'dragged in',
    'befriended',
    'saluted',
];

// cfg maps between a non-terminal symbol and the list of expansions it can have
cfg = {
    'S': ['NP VP'],
    'NP': ['DN', 'PN'],
    'DN': ['DET N', 'DET N that NP V'],
    'PN': proper_nouns,
    'VP': ['V NP'],
    'V': past_tense_verbs,
    'DET': determiners,
    'N': nominals,
}
var nonterminals = [
    'S',
    'PN',
    'VP',
    'V',
    'NP',
    'DET',
    'N',
    'DN',
];


function generate(g) {
    var tokens = g.split(' ');
    for (var i = 0; i < tokens.length; i++) { var token = tokens[i];
        for (var j = 0; j < nonterminals.length; j++) {
            var nonterminal = nonterminals[j];
            if (token === nonterminal) {
                // select one of the possible expansions of token to use
                var expansions = cfg[nonterminal];
                var expansion = expansions[randInt(0, expansions.length-1)];

                // now replace this instance of token with a recursive expansion of its expansion
                g = g.replace(token, generate(expansion));
                break;
            }
        }
        // if no nonterminal matched, then token was a terminal symbol
    }
    // all nonterminal symbols have been replaced by terminal ones
    return g;
}

document.writeln('<ul>');
for (var i = 0; i < 5; i++) {
  var sentence = generate('S');
  document.writeln('<li>' + sentence + '</li>');
}
document.writeln('</ul>');
</script>