From: Joe Wreschnig Date: Thu, 9 Oct 2014 23:38:08 +0000 (+0200) Subject: Initial import. X-Git-Url: https://git.yukkurigames.com/?p=rrr.git;a=commitdiff_plain;h=bebb8a0982e0a55a060556df5d6ba6aa512d5dbc Initial import. --- bebb8a0982e0a55a060556df5d6ba6aa512d5dbc diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..c169afd --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +build +node_modules +*.min.js diff --git a/COPYING.txt b/COPYING.txt new file mode 100644 index 0000000..d159169 --- /dev/null +++ b/COPYING.txt @@ -0,0 +1,339 @@ + GNU GENERAL PUBLIC LICENSE + Version 2, June 1991 + + Copyright (C) 1989, 1991 Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +License is intended to guarantee your freedom to share and change free +software--to make sure the software is free for all its users. This +General Public License applies to most of the Free Software +Foundation's software and to any other program whose authors commit to +using it. (Some other Free Software Foundation software is covered by +the GNU Lesser General Public License instead.) You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it +if you want it, that you can change the software or use pieces of it +in new free programs; and that you know you can do these things. + + To protect your rights, we need to make restrictions that forbid +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if you +distribute copies of the software, or if you modify it. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must give the recipients all the rights that +you have. You must make sure that they, too, receive or can get the +source code. And you must show them these terms so they know their +rights. + + We protect your rights with two steps: (1) copyright the software, and +(2) offer you this license which gives you legal permission to copy, +distribute and/or modify the software. + + Also, for each author's protection and ours, we want to make certain +that everyone understands that there is no warranty for this free +software. If the software is modified by someone else and passed on, we +want its recipients to know that what they have is not the original, so +that any problems introduced by others will not reflect on the original +authors' reputations. + + Finally, any free program is threatened constantly by software +patents. We wish to avoid the danger that redistributors of a free +program will individually obtain patent licenses, in effect making the +program proprietary. To prevent this, we have made it clear that any +patent must be licensed for everyone's free use or not licensed at all. + + The precise terms and conditions for copying, distribution and +modification follow. + + GNU GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License applies to any program or other work which contains +a notice placed by the copyright holder saying it may be distributed +under the terms of this General Public License. The "Program", below, +refers to any such program or work, and a "work based on the Program" +means either the Program or any derivative work under copyright law: +that is to say, a work containing the Program or a portion of it, +either verbatim or with modifications and/or translated into another +language. (Hereinafter, translation is included without limitation in +the term "modification".) Each licensee is addressed as "you". + +Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running the Program is not restricted, and the output from the Program +is covered only if its contents constitute a work based on the +Program (independent of having been made by running the Program). +Whether that is true depends on what the Program does. + + 1. You may copy and distribute verbatim copies of the Program's +source code as you receive it, in any medium, provided that you +conspicuously and appropriately publish on each copy an appropriate +copyright notice and disclaimer of warranty; keep intact all the +notices that refer to this License and to the absence of any warranty; +and give any other recipients of the Program a copy of this License +along with the Program. + +You may charge a fee for the physical act of transferring a copy, and +you may at your option offer warranty protection in exchange for a fee. + + 2. You may modify your copy or copies of the Program or any portion +of it, thus forming a work based on the Program, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) You must cause the modified files to carry prominent notices + stating that you changed the files and the date of any change. + + b) You must cause any work that you distribute or publish, that in + whole or in part contains or is derived from the Program or any + part thereof, to be licensed as a whole at no charge to all third + parties under the terms of this License. + + c) If the modified program normally reads commands interactively + when run, you must cause it, when started running for such + interactive use in the most ordinary way, to print or display an + announcement including an appropriate copyright notice and a + notice that there is no warranty (or else, saying that you provide + a warranty) and that users may redistribute the program under + these conditions, and telling the user how to view a copy of this + License. (Exception: if the Program itself is interactive but + does not normally print such an announcement, your work based on + the Program is not required to print an announcement.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Program, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Program, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Program. + +In addition, mere aggregation of another work not based on the Program +with the Program (or with a work based on the Program) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may copy and distribute the Program (or a work based on it, +under Section 2) in object code or executable form under the terms of +Sections 1 and 2 above provided that you also do one of the following: + + a) Accompany it with the complete corresponding machine-readable + source code, which must be distributed under the terms of Sections + 1 and 2 above on a medium customarily used for software interchange; or, + + b) Accompany it with a written offer, valid for at least three + years, to give any third party, for a charge no more than your + cost of physically performing source distribution, a complete + machine-readable copy of the corresponding source code, to be + distributed under the terms of Sections 1 and 2 above on a medium + customarily used for software interchange; or, + + c) Accompany it with the information you received as to the offer + to distribute corresponding source code. (This alternative is + allowed only for noncommercial distribution and only if you + received the program in object code or executable form with such + an offer, in accord with Subsection b above.) + +The source code for a work means the preferred form of the work for +making modifications to it. For an executable work, complete source +code means all the source code for all modules it contains, plus any +associated interface definition files, plus the scripts used to +control compilation and installation of the executable. However, as a +special exception, the source code distributed need not include +anything that is normally distributed (in either source or binary +form) with the major components (compiler, kernel, and so on) of the +operating system on which the executable runs, unless that component +itself accompanies the executable. + +If distribution of executable or object code is made by offering +access to copy from a designated place, then offering equivalent +access to copy the source code from the same place counts as +distribution of the source code, even though third parties are not +compelled to copy the source along with the object code. + + 4. You may not copy, modify, sublicense, or distribute the Program +except as expressly provided under this License. Any attempt +otherwise to copy, modify, sublicense or distribute the Program is +void, and will automatically terminate your rights under this License. +However, parties who have received copies, or rights, from you under +this License will not have their licenses terminated so long as such +parties remain in full compliance. + + 5. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Program or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Program (or any work based on the +Program), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Program or works based on it. + + 6. Each time you redistribute the Program (or any work based on the +Program), the recipient automatically receives a license from the +original licensor to copy, distribute or modify the Program subject to +these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties to +this License. + + 7. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Program at all. For example, if a patent +license would not permit royalty-free redistribution of the Program by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Program. + +If any portion of this section is held invalid or unenforceable under +any particular circumstance, the balance of the section is intended to +apply and the section as a whole is intended to apply in other +circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system, which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 8. If the distribution and/or use of the Program is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Program under this License +may add an explicit geographical distribution limitation excluding +those countries, so that distribution is permitted only in or among +countries not thus excluded. In such case, this License incorporates +the limitation as if written in the body of this License. + + 9. The Free Software Foundation may publish revised and/or new versions +of the General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies a version number of this License which applies to it and "any +later version", you have the option of following the terms and conditions +either of that version or of any later version published by the Free +Software Foundation. If the Program does not specify a version number of +this License, you may choose any version ever published by the Free Software +Foundation. + + 10. If you wish to incorporate parts of the Program into other free +programs whose distribution conditions are different, write to the author +to ask for permission. For software which is copyrighted by the Free +Software Foundation, write to the Free Software Foundation; we sometimes +make exceptions for this. Our decision will be guided by the two goals +of preserving the free status of all derivatives of our free software and +of promoting the sharing and reuse of software generally. + + NO WARRANTY + + 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY +FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN +OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES +PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED +OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS +TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE +PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, +REPAIR OR CORRECTION. + + 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR +REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, +INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING +OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED +TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY +YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER +PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE +POSSIBILITY OF SUCH DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + +Also add information on how to contact you by electronic and paper mail. + +If the program is interactive, make it output a short notice like this +when it starts in an interactive mode: + + Gnomovision version 69, Copyright (C) year name of author + Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, the commands you use may +be called something other than `show w' and `show c'; they could even be +mouse-clicks or menu items--whatever suits your program. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the program, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the program + `Gnomovision' (which makes passes at compilers) written by James Hacker. + + , 1 April 1989 + Ty Coon, President of Vice + +This General Public License does not permit incorporating your program into +proprietary programs. If your program is a subroutine library, you may +consider it more useful to permit linking proprietary applications with the +library. If this is what you want to do, use the GNU Lesser General +Public License instead of this License. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..4084442 --- /dev/null +++ b/Makefile @@ -0,0 +1,61 @@ +#!/usr/bin/make -f + +PKGNAME := rrr + +all: + $(info Interesting targets:) + $(info lint - validate source (with jshint)) + $(info test - run tests (with jstest)) + $(info ugly - generate minified source files) + $(info dist - generate redistributables (if git tagged)) + $(info ) + $(info (Running these may download packages from npm.)) + $(info ) + @: + + +SOURCES := rrr.js term.js +JSTEST_SOURCES += $(SOURCES) + +include javascript.mk + +GIT ?= git +git-describe = $(shell $(GIT) describe --tags --always $1) + +UGLIFIED := $(call uglify-stampify,$(SOURCES)) + +JSHINTCONFIG := tests/jshint.config +JSSTAMPDIR := build/stamp + +TESTS := $(wildcard tests/*.js) +LINTS := $(call jshint-stampify,$(SOURCES) $(TESTS)) +TEST_TARGETS = $(patsubst %.js,build/stamp/tests/%.js.test,$(SOURCES)) + +.DELETE_ON_ERROR: +.PHONY: all check lint test ugly dist clean distclean install + +check: lint test + +lint: $(LINTS) + +test: $(TEST_TARGETS) + +ugly: check $(UGLIFIED) + +dist: check + +clean: + $(RM) -r build + $(RM) $(UGLIFIED) + +distclean: clean + $(RM) -r node_modules + +install: check + $(NPM) install -g . + +dist: check build/dist/$(PKGNAME)-$(call git-describe).tar.gz + +$(PKGNAME)-%.tar.gz: | .git + @mkdir -p $(@D) + $(GIT) archive --prefix=$(PKGNAME)-$(*F)/ --output=$@ $(*F) diff --git a/README.md b/README.md new file mode 100644 index 0000000..eaf26ff --- /dev/null +++ b/README.md @@ -0,0 +1,121 @@ +# 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: + +* `{n}` - Repeat rule `A` `n` times. +* `{n,m}` - Repeat rule `A` a random number of times between `n` + and `m` (uniformly, inclusive). +* `?` - Produce rule `A` ½ of the time, and nothing ½ of the time. +* `*` - Produce nothing ½ of the time, `` ¼ of the time, + `` ⅛ of the time, and so on. +* `+` - Produce `` ½ of the time, `` ¼ of the time, + `` ⅛ of the time, and so on. + +Repetition patterns can also be specified with a space after the rule +name, e.g. `+`. In this case, the repetitions have spaces between +them, e.g. ` `. + +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.) + + ::javascript + var grammar = new rrr.Grammar({ + // Canonical expression/term/factor grammar. + + Expr: ['', ' + ', ' - '], + Term: ['', ' * ', ' / '], + 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: { '': 1, '()': 0.4 }, + + // A numeral may not begin with a 0. + Number: ['*'], + digit: '123456789', + digit0: '1234567890' + + }, ''); // 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. + + ::javascript + grammar.generate(); // Equivalent to grammar.generate('') + // => '-9 * 3512 + (-(-51 - -9 / 6) / -6278 + -4 * 30321) / 21940' + + grammar.generate('Solve: '); + // => 'Solve: 7 + (255 * (4 / 18))' + + grammar.generate("Today's numbers are and ."); + // => '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 ` ` (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: { '": 0.8, "": 0.2 } } + +will contain one `` 80% of the time, two 16% of the time, three +3.2% of the time, etc. + + +[L-system]: http://en.wikipedia.org/wiki/L-system +[Markov machine]: http://en.wikipedia.org/wiki/Markov_algorithm +[stochastic grammar]: http://en.wikipedia.org/wiki/Stochastic_grammar +[BNF]: http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form diff --git a/javascript.mk b/javascript.mk new file mode 100644 index 0000000..0e6a180 --- /dev/null +++ b/javascript.mk @@ -0,0 +1,59 @@ +# This is free and unencumbered software released into the public +# domain. To the extent possible under law, the author of this file +# waives all copyright and related or neighboring rights to it. + +.DELETE_ON_ERROR: + +javascript>fallback = $(firstword $(shell command -v $1) $2 $1) + +NPM ?= npm +NPMROOT ?= . + +npmbindir = $(NPMROOT)/node_modules/.bin +.PRECIOUS: $(npmbindir)/% + +from-npm = $(call javascript>fallback,$1,$(npmbindir)/$1) + +JSTEST ?= $(npmbindir)/jstest +JSHINT ?= $(call from-npm,jshint) + +uglifyjs_npm_package := uglify-js + +UGLIFY ?= $(call from-npm,uglifyjs) +UGLIFYFLAGS ?= --comments \ + --compress $(UGLIFYCOMPRESSFLAGS) \ + --mangle $(UGLIFYMANGLEFLAGS) + +JSSTAMPDIR ?= build/stamp +JSHINTDIR ?= $(JSSTAMPDIR) +JSTESTDIR ?= $(JSSTAMPDIR) +JSUGLYDIR ?= . + +JSHINTFLAGS += $(if $(JSHINTCONFIG),--config $(JSHINTCONFIG)) +JSTESTFLAGS += $(if $(JSTESTFORMAT),--format $(JSTESTFORMAT)) +JSTESTFORMAT ?= spec + +jshint-stampify = $(patsubst %.js,$(JSHINTDIR)/%.js.lint,$1) +uglify-stampify = $(patsubst %.js,$(JSUGLYDIR)/%.min.js,$1) + +javascript>capture-to-target = @echo "$1" && $1 > $@ || (cat $@ && exit 1) + +UGLIFY.js = $(UGLIFY) $(UGLIFYFLAGS) +LINT.js = $(JSHINT) $(JSHINTFLAGS) +TEST.js = $(JSTEST) $(JSTESTFLAGS) + +$(JSUGLYDIR)/%.min.js: %.js | $(UGLIFY) + @mkdir -p $(@D) + $(UGLIFY.js) < $< > $@ + +$(JSHINTDIR)/%.js.lint: %.js | $(JSHINT) + @mkdir -p $(@D) + $(LINT.js) $< + @touch $@ + +$(JSTESTDIR)/%.js.test: %.js $(JSTEST_SOURCES) | $(JSTEST) + @mkdir -p $(@D) + $(call javascript>capture-to-target,$(TEST.js) $<) + +$(npmbindir)/%: + $(NPM) install $(firstword $(value $(@F)_npm_package) $(@F)) diff --git a/package.json b/package.json new file mode 100644 index 0000000..6842060 --- /dev/null +++ b/package.json @@ -0,0 +1,27 @@ +{ + "name": "rrr", + "version": "1.0.0", + "author": "Joe Wreschnig", + "description": "recursive random rewrites", + "keywords": ["random", "text"], + + "license": "GPL-2.0+", + + "main": "./rrr.js", + + "scripts": { + "test": "make check" + }, + + "homepage": "https://yukkurigames.com/rrr", + "repository": { + "type": "git", + "url": "http://git.yukkurigames.com/rrr.git" + }, + + "devDependencies": { + "jstest": "*", + "jshint": "*", + "uglify-js": "*" + } +} diff --git a/rrr.js b/rrr.js new file mode 100644 index 0000000..2b76474 --- /dev/null +++ b/rrr.js @@ -0,0 +1,104 @@ +/* rrr - recursive random rewrites + Copyright 2014 Joe Wreschnig + Licensed under the terms of the GNU GPL v2 or later + @license https://www.gnu.org/licenses/gpl-2.0.html + @source: https://yukkurigames.com/rrr/ +*//* + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + As additional permission, you may distribute the program or works + based on it without the copy of the GNU GPL normally required, + provided you include this license notice and a URL through which + recipients can access the corresponding source code. +*/ + +(function (exports) { + "use strict"; + + function randfloat (hi) { return Math.random() * hi; } + function randint (hi) { return randfloat(hi) | 0; } + function randchoice (seq) { return seq[randint(seq.length)]; } + function randrange (lo, hi) { return lo + randint(hi - lo); } + + function Productions (dfn) { + this.__total = 0; + if (Array.isArray(dfn) || dfn.toString() === dfn) { + this.__rules = Array.prototype.slice.call(dfn); + } else if (typeof dfn === "function") { + this.__rules = dfn; + } else { + this.__rules = {}; + Object.keys(dfn).forEach(function (key) { + var value = dfn[key]; + this.__total += value; + this.__rules[key] = value; + }, this); + } + } + + Productions.prototype.randproduction = function () { + if (Array.isArray(this.__rules)) + return randchoice(this.__rules); + + else if (typeof this.__rules === "function") + return this.__rules(); + + var x = randfloat(this.__total); + for (var k in this.__rules) { + x -= this.__rules[k]; + if (x < 0) + return k; + } + return null; + }; + + function Grammar (productions, start) { + this.start = start || ""; + this.productions = {}; + for (var k in productions) + this.productions[k] = new Productions(productions[k]); + } + + function randcount (lo, hi, rep) { + var n = hi ? randrange(+lo, +hi + 1) + : lo ? +lo + : 1; + + var m = 1; + switch (rep) { + case '*': m = 0; while (Math.random() < 0.5) ++m; break; + case '+': while (Math.random() < 0.5) ++m; break; + case '?': m = +(Math.random() < 0.5); break; + } + return n * m; + } + + function repeat (n, f) { + var r = []; + while (n-- > 0) + r.push(f()); + return r; + } + + var R = /<([^> ]+)( ?)>(?:{([0-9]+)(?:,([0-9]+))?}|(\*|\+|\?))?/g; + Grammar.prototype.expand = function (start) { + var g = this; + start = start || this.start; + return start.replace(R, function _ (match, p, w, lo, hi, rep) { + var prod = g.productions[p]; + return repeat(randcount(lo, hi, rep), function () { + return prod.randproduction().replace(R, _); + }).join(w); + }); + }; + + exports.Grammar = Grammar; +})(typeof module !== "undefined" ? module.exports : this.gengram = {}); diff --git a/term.js b/term.js new file mode 100644 index 0000000..b779f8c --- /dev/null +++ b/term.js @@ -0,0 +1,33 @@ +(function (exports) { + /*global require */ + var rrr = exports.rrr || require('./rrr'); + + var grammar = new rrr.Grammar({ + // Canonical expression/term/factor grammar. + Expr: ['', ' + ', ' - '], + Term: ['', ' * ', ' / '], + 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: { '': 1, '()': 0.4 }, + + // A numeral may not begin with a 0. + Number: ['*'], + digit: '123456789', + digit0: '1234567890' + }, ''); + + exports.randomEquation = grammar.expand.bind(grammar); +})(typeof module !== 'undefined' ? module.exports : this); diff --git a/tests/jshint.config b/tests/jshint.config new file mode 100644 index 0000000..fdc8a7d --- /dev/null +++ b/tests/jshint.config @@ -0,0 +1,13 @@ +{ + "camelcase": true, + "eqeqeq": true, + "indent": 4, + "latedef": true, + "nonew": true, + "trailing": true, + "undef": true, + "evil": true, + "globals": { + "module": false + } +} diff --git a/tests/rrr.js b/tests/rrr.js new file mode 100644 index 0000000..679e055 --- /dev/null +++ b/tests/rrr.js @@ -0,0 +1,68 @@ +/*global require, it, assert, assertEqual, assertNot */ +/*jshint -W085 */ // "Don't use 'with'." + +var JS = this.JS || require('jstest'); +var rrr = require('../rrr'); + +var AB = new rrr.Grammar({ + A: ["A"], + B: ["B"], + AB: [" "], +}, "+"); + +var DIGITS = new rrr.Grammar({ + Digits: ["+"], + digit: "0123456789" +}); + +JS.Test.describe('rrr AB', function () { with (this) { + it("simply expands", function () { with (this) { + assertEqual("A", AB.expand("")); + assertEqual("B", AB.expand("")); + assertEqual("A B", AB.expand("")); + }}); + it("expands multiple tokens", function () { with (this) { + assertEqual("A B A", AB.expand(" ")); + }}); + it("expands multiple times", function () { with (this) { + assertEqual("AAAAA", AB.expand("{5}")); + }}); + it("expands random times", function () { with (this) { + var r = []; + for (var i = 0; i < 1000; ++i) + r.push(AB.expand("{1,10}")); + assert(r.indexOf("") < 0); + assert(r.indexOf("A") >= 0); + assert(r.indexOf("AA") >= 0); + assert(r.indexOf("AAA") >= 0); + assert(r.indexOf("AAAA") >= 0); + assert(r.indexOf("AAAAA") >= 0); + assert(r.indexOf("AAAAAA") >= 0); + assert(r.indexOf("AAAAAAA") >= 0); + assert(r.indexOf("AAAAAAAA") >= 0); + assert(r.indexOf("AAAAAAAAA") >= 0); + assert(r.indexOf("AAAAAAAAAA") >= 0); + assert(r.indexOf("AAAAAAAAAAA") < 0); + }}); + it("expands repeatedly", function () { with (this) { + var r = []; + for (var i = 0; i < 100; ++i) + r.push(AB.expand()); + assert(r.indexOf("") < 0); + assert(r.indexOf("A B") >= 0); + assert(r.indexOf("A B A B") >= 0); + }}); + it("expands repetitions differently", function () { with (this) { + var r = DIGITS.expand("{500}"); + assert(~r.indexOf("0")); + assert(~r.indexOf("1")); + assert(~r.indexOf("2")); + assert(~r.indexOf("3")); + assert(~r.indexOf("4")); + assert(~r.indexOf("5")); + assert(~r.indexOf("6")); + assert(~r.indexOf("7")); + assert(~r.indexOf("8")); + assert(~r.indexOf("9")); + }}); +}}); diff --git a/tests/term.js b/tests/term.js new file mode 100644 index 0000000..732fa5a --- /dev/null +++ b/tests/term.js @@ -0,0 +1,15 @@ +/*global require, it, assert, assertEqual, assertNot */ +/*jshint -W085 */ // "Don't use 'with'." + +var JS = this.JS || require('jstest'); +var rrr = require('../rrr'); +var term = require('../term'); + +JS.Test.describe('rrr term test', function () { with (this) { + it("loads and makes expressions", function () { with (this) { + for (var i = 0; i < 1000; ++i) { + var n = eval(term.randomEquation()); + assert(n === +n); + } + }}); +}});