将invRegex.py移植到Javascript（Node.js）
我一直试图将invRegex.py移植到node.js实现一段时间，但我仍然在努力。 我已经有了正则expression式分析树，这要归功于ret.js标记器，它工作得很好，但是所有不同元素的实际生成和连接都是以内存效率的方式展现给我的。 为了简单起见，可以说我有以下的正则expression式：
[01]{1,2}@[af] invRegex.py会产生下面的输出（ tabbified占用更less的空间）：
0@a 0@b 0@c 0@d 0@e 0@f 00@a 00@b 00@c 00@d 00@e 00@f 01@a 01@b 01@c 01@d 01@e 01@f 1@a 1@b 1@c 1@d 1@e 1@f 10@a 10@b 10@c 10@d 10@e 10@f 11@a 11@b 11@c 11@d 11@e 11@f
考虑到我能够获得每个单独的令牌并生成一个包含所有有效的单个输出的数组：
[01]{1,2} = function () { return ['0', '00', '01', '1', '10', '11']; }; @ = function () { return ['@']; }; [af] = function () { return ['a', 'b', 'c', 'd', 'e', 'f']; };
我可以计算所有数组的笛卡尔乘积 ，并得到相同的期望输出：
var _ = require('underscore'); function cartesianProductOf() { return _.reduce(arguments, function(a, b) { return _.flatten(_.map(a, function(x) { return _.map(b, function(y) { return x.concat([y]); }); }), true); }, [ [] ]); }; var tokens = [ ['0', '00', '01', '1', '10', '11'], ['@'], ['a', 'b', 'c', 'd', 'e', 'f'], ]; var result = cartesianProductOf(tokens[0], tokens[1], tokens[2]); _.each(result, function (value, key) { console.log(value.join('')); });
这个问题就是它把所有的36个值都保存在内存中，如果我有一个稍微复杂一点的正则expression式，例如[az]{0,10}它会在内存中保存146813779479511值，这是完全不可行的。 我想以asynchronous的方式处理这个庞大的列表，将每个生成的组合传递给一个callback函数，并允许我在任何合理的地方中断进程，就像invRegex.py或者这个Haskell包 – 不幸的是我不能理解Haskell，我不知道如何模仿Python到JavaScript的生成器行为。
我尝试了在节点0.11.9（与–harmony）中运行几个简单的发生器实验，就像这样：
function* alpha() { yield 'a'; yield 'b'; yield 'c'; } function* numeric() { yield '0'; yield '1'; } function* alphanumeric() { yield* alpha() + numeric(); // what's the diff between yield and yield*? } for (var i of alphanumeric()) { console.log(i); }
不用说上述不起作用。 = /
我的头靠在墙上，所以任何帮助解决这个问题，将不胜感激。
更新 ：这是一个样本ret.jsparsing树b[az]{3} ：
{ "type": ret.types.ROOT, "stack": [ { "type": ret.types.CHAR, "value": 98 // b }, { "type": ret.types.REPETITION, "max": 3, "min": 3, "value": { "type": ret.types.SET, "not": false, "set": [ { "type": ret.types.RANGE, "from": 97, // a "to": 122 // z } ] } } ] ] }
SET / RANGEtypes应该产生26个不同的值，并且父REPETITIONtypes应该取前面的值为3的幂，产生17576个不同的组合。 如果我要像cartesianProductOf那样生成一个扁平的tokens数组，那么中间扁平化的值将占用与实际的笛卡尔积本身一样多的空间。
我希望这个例子更好地解释我面临的问题。
我build议你编写迭代器类。 它们很容易实现（基本上它们是状态机），它们占用的内存很小，可以组合起来构build越来越复杂的expression式（请向下滚动以查看最终结果），并将得到的迭代器包装成枚举。
每个迭代器类都有以下方法：
- 第一：初始化状态机（第一次匹配）
- 下一步：进入下一个状态（下一场比赛）
- 确定：最初是正确的，但是一旦“下一步”超过了最后一场比赛，就变成了错误
- get：返回当前匹配（作为string）
- 克隆：克隆对象; 因为每个实例都需要自己的状态
从最微不足道的情况开始：一个或多个字符序列，应该逐字匹配（例如/ foo / ）。 不用说，这只有一个匹配，所以'OK'会在'next'的第一个呼叫时变成错误的。
function Literal(literal) { this.literal = literal; } Literal.prototype.first = function() { this.i = 0; }; Literal.prototype.next = function() { this.i++; }; Literal.prototype.ok = function() { return this.i == 0; }; Literal.prototype.get = function() { return this.literal; }; Literal.prototype.clone = function() { return new Literal(this.literal); };
字符类（ [abc] ）也是微不足道的。 构造函数接受一串字符; 如果你喜欢数组，这很容易解决。
function CharacterClass(chars) { this.chars = chars; } CharacterClass.prototype.first = function() { this.i = 0; }; CharacterClass.prototype.next = function() { this.i++; }; CharacterClass.prototype.ok = function() { return this.i < this.chars.length; }; CharacterClass.prototype.get = function() { return this.chars.charAt(this.i); }; CharacterClass.prototype.clone = function() { return new CharacterClass(this.chars); };
现在我们需要结合其他迭代器的迭代器来形成更复杂的正则expression式。 一个序列就是连续两个或更多的模式（如foo [abc] ）。
function Sequence(iterators) { if (arguments.length > 0) { this.iterators = iterators.length ? iterators : [new Literal('')]; } } Sequence.prototype.first = function() { for (var i in this.iterators) this.iterators[i].first(); }; Sequence.prototype.next = function() { if (this.ok()) { var i = this.iterators.length; while (this.iterators[--i].next(), i > 0 && !this.iterators[i].ok()) { this.iterators[i].first(); } } }; Sequence.prototype.ok = function() { return this.iterators[0].ok(); }; Sequence.prototype.get = function() { var retval = ''; for (var i in this.iterators) { retval += this.iterators[i].get(); } return retval; }; Sequence.prototype.clone = function() { return new Sequence(this.iterators.map(function(it) { return it.clone(); })); };
另一种组合迭代器的方法是select（也可以是其他select），例如foo | bar 。
function Choice(iterators) { this.iterators = iterators; } Choice.prototype.first = function() { this.count = 0; for (var i in this.iterators) this.iterators[i].first(); }; Choice.prototype.next = function() { if (this.ok()) { this.iterators[this.count].next(); while (this.ok() && !this.iterators[this.count].ok()) this.count++; } }; Choice.prototype.ok = function() { return this.count < this.iterators.length; }; Choice.prototype.get = function() { return this.iterators[this.count].get(); }; Choice.prototype.clone = function() { return new Choice(this.iterators.map(function(it) { return it.clone(); })); };
其他的正则expression式可以通过结合现有的类来实现。 inheritance类是一个很好的方法来做到这一点。 例如，一个可选的模式（ x？ ）只是空string和x之间的一个select。
function Optional(iterator) { if (arguments.length > 0) { Choice.call(this, [new Literal(''), iterator]); } } Optional.prototype = new Choice();
重复（ x {n，m} ）是Sequence和Optional的组合。 因为我必须inheritance其中一个，所以我的实现由两个相互依赖的类组成。
function RepeatFromZero(maxTimes, iterator) { if (arguments.length > 0) { Optional.call(this, new Repeat(1, maxTimes, iterator)); } } RepeatFromZero.prototype = new Optional(); function Repeat(minTimes, maxTimes, iterator) { if (arguments.length > 0) { var sequence = []; for (var i = 0; i < minTimes; i++) { sequence.push(iterator.clone()); // need to clone the iterator } if (minTimes < maxTimes) { sequence.push(new RepeatFromZero(maxTimes - minTimes, iterator)); } Sequence.call(this, sequence); } } Repeat.prototype = new Sequence();
正如我前面所说，一个迭代器可以被包装成一个枚举器。 这只是一个循环，你可以随时打破。
function Enumerator(iterator) { this.iterator = iterator; this.each = function(callback) { for (this.iterator.first(); this.iterator.ok(); this.iterator.next()) { callback(this.iterator.get()); } }; }
把时间放在一起。 让我们来看一些愚蠢的正则expression式：
([ab]{2}){1,2}|[cd](f|ef{0,2}e)
编写迭代器对象非常简单：
function GetIterationsAsHtml() { var iterator = new Choice([ new Repeat(1, 2, new Repeat(2, 2, new CharacterClass('ab'))), new Sequence([ new CharacterClass('cd'), new Choice([ new Literal('f'), new Sequence([ new Literal('e'), new RepeatFromZero(2, new Literal('f')), new Literal('e') ]) ]) ]) ]); var iterations = '<ol>\n'; var enumerator = new Enumerator(iterator); enumerator.each(function(iteration) { iterations += '<li>' + iteration + '</li>\n'; }); return iterations + '</ol>'; }
这产生了28场比赛，但是我会把你输出。
我的道歉，如果我的代码不符合软件模式，不兼容浏览器（在Chrome和Firefox工作正常）或遭受糟糕的OOP。 我只希望这个概念清楚。
编辑：为了完整性，并遵循OP的倡议，我实现了一个更多的迭代器类： 参考 。
一个引用（\ 1 \ 2等）拿起一个早期的捕获组（即括号中的任何内容）的当前匹配。 它的实现与Literal非常相似，因为它只有一个匹配。
function Reference(iterator) { this.iterator = iterator; } Reference.prototype.first = function() { this.i = 0; }; Reference.prototype.next = function() { this.i++; }; Reference.prototype.ok = function() { return this.i == 0; }; Reference.prototype.get = function() { return this.iterator.get(); }; Reference.prototype.clone = function() { return new Reference(this.iterator); };
给构造函数一个代表引用的子模式的迭代器。 以(foo|bar)([xy])\2\1为例）（产生fooxxfoo，fooyyfoo，barxxbar，baryybar ）
var groups = new Array(); var iterator = new Sequence([ groups[1] = new Choice([new Literal('foo'), new Literal('bar')]), groups[2] = new CharacterClass('xy'), new Reference(groups[2]), new Reference(groups[1]) ]);
在构build迭代器类树时指定捕获组。 我仍然在这里手动做，但最终你希望这是自动的。 这只是将分析树映射到类似的迭代器类树的问题。
编辑2：这是一个相对简单的recursion函数，将由ret.js产生的parsing树转换为迭代器。
function ParseTreeMapper() { this.capturingGroups = []; } ParseTreeMapper.prototype.mapToIterator = function(parseTree) { switch (parseTree.type) { case ret.types.ROOT: case ret.types.GROUP: var me = this; var mapToSequence = function(parseTrees) { return new Sequence(parseTrees.map(function(t) { return me.mapToIterator(t); })); }; var group = parseTree.options ? new Choice(parseTree.options.map(mapToSequence)) : mapToSequence(parseTree.stack); if (parseTree.remember) { this.capturingGroups.push(group); } return group; case ret.types.SET: return new CharacterClass(this.mapToCharacterClass(parseTree.set)); case ret.types.REPETITION: return new Repeat(parseInt(parseTree.min), parseInt(parseTree.max), this.mapToIterator(parseTree.value)); case ret.types.REFERENCE: var ref = parseInt(parseTree.value) - 1; return ref in this.capturingGroups ? new Reference(this.capturingGroups[ref]) : new Literal('<ReferenceOutOfRange>'); case ret.types.CHAR: return new Literal(String.fromCharCode(parseTree.value)); default: return new Literal('<UnsupportedType>'); } }; ParseTreeMapper.prototype.mapToCharacterClass = function(parseTrees) { var chars = ''; for (var i in parseTrees) { var tree = parseTrees[i]; switch (tree.type) { case ret.types.CHAR: chars += String.fromCharCode(tree.value); break; case ret.types.RANGE: for (var code = tree.from; code <= tree.to; code++) { chars += String.fromCharCode(code); } break; } } return chars; };
用法：
var regex = 'b[an]{3}'; var parseTree = ret(regex); // requires ret.js var iterator = new ParseTreeMapper().mapToIterator(parseTree);
我在这个演示中把所有的组件放在一起： http : //jsfiddle.net/Pmnwk/3/
注意：许多正则expression式的语法结构不被支持（锚点，预见，后退，recursion），但是我想这已经和invRegex.py差不多了。
下面是一个为input的每个部分生成函数的版本，并将所有这些函数组合起来，生成一个函数，该函数将生成每个正则expression式结果并将其input到该参数中：
//Takes in a list of things, returns a function that takes a function and applies it to // each Cartesian product. then composes all of the functions to create an // inverse regex generator. function CartesianProductOf() { var args = arguments; return function(callback) { Array.prototype.map.call(args, function(vals) { return function(c, val) { vals.forEach(function(v) { c(val + v); }); }; }).reduce(function(prev, cur) { return function(c, val) { prev(function(v){cur(c, v)}, val); }; })(callback, ""); }; }
修改以处理一个分析树（从这里复制一个litte代码）：
//Takes in a list of things, returns a function that takes a function and applies it to // each Cartesian product. function CartesianProductOf(tree) { var args = (tree.type == ret.types.ROOT)? tree.stack : ((tree.type == ret.types.SET)? tree.set : []); return function(callback) { var funs = args.map(function(vals) { switch(vals.type) { case ret.types.CHAR: return function(c, val) { c(val + vals.value); }; case ret.types.RANGE: return function(c, val) { for(var i=vals.from; i<=vals.to; i++) { c(val+String.fromCharCode(i)); } }; case ret.types.SET: return function(c, val) { CartesianProductOf(vals)(function(i) {c(val+i)}); }; /* return function(c, val) { vals.set.forEach(function(v) { c(val + v); }); }; */ case ret.types.REPETITION: var tmp = CartesianProductOf(vals.value); if(vals.max == vals.min) { return fillArray(function(c, val) { tmp(function(i){c(val+i);}); //Probably works? }, vals.max); } else { return fillArray(function(c, val) { tmp(function(i){c(val+i);}); }, vals.min).concat(fillArray(function(c, val) { c(val); tmp(function(i){c(val+i);}); }, vals.max-vals.min)); } default: return function(c, val) { c(val); }; } }).reduce(function(prev, cur) { //Flatten array. return prev.concat(cur); }, []); if(tree.type == rets.type.ROOT) //If it's a full tree combine all the functions. funs.reduce(function(prev, cur) { //Compose! return function(c, val) { prev(function(v){cur(c, v)}, val); }; })(callback, ""); else //If it's a set call each function. funs.forEach(function(f) {f(callback, "")}); }; } function fillArray(value, len) { var arr = []; for (var i = 0; i < len; i++) { arr.push(value); } return arr; }
如果你没有一个function更强大，更C的解决scheme：
function helper(callme, cur, stuff, pos) { if(pos == stuff.length) { callme(cur); } else for(var i=0; i<stuff[pos].length; i++) { helper(callme, cur+stuff[pos][i], stuff, pos+1); } } function CartesianProductOf(callback) { helper(callback, "", Array.prototype.slice.call(arguments, 1), 0); }
这个怎么样：
var tokens = [ ['0', '00', '01', '1', '10', '11'], ['@'], ['a', 'b', 'c', 'd', 'e', 'f'], ]; function cartesianProductOf(arr, callback) { var cur = []; var f = function(i) { if (i >= arr.length) { callback(cur.join('')); return } for (var j=0; j<arr[i].length; j++) { cur[i] = arr[i][j]; f(i+1); } }; f(0); } cartesianProductOf(tokens, function(str) { console.log(str); });
这听起来像是你在问Lazy Cartesian Product：你确实需要Cartesian产品，但是你不想预先计算它们（并且消耗所有的内存）。 换句话说，你想通过笛卡尔积迭代。
如果这是正确的，你检查了X（n）公式的Javascript实现吗？ 这样，你可以按照自然顺序<< 0,0,0>，<0,0,1>，<0,1,0>，…>迭代它们，或者select一个任意的位置来计算。
看来你可以这样做：
// move through them in natural order, without precomputation lazyProduct(tokens, function (token) { console.log(token); }); // or... // pick ones out at random var LP = new LazyProduct(tokens); console.log(LP.item(7)); // the 7th from the list, without precompute console.log(LP.item(242)); // the 242nd from the list, again without precompute
我肯定会错过一些东西…？ 给定X（n）公式，发电机只是矫枉过正。
更新
在一个JSFiddle中，我已经放置了一个lazyProduct代码的testing版本，一个数组示例标记数组，以及使用这些tokens对lazyProduct的调用。
当你不修改地运行代码时，你会发现它会生成样本tokens数组所期望的0@a等输出。 我认为这个链接很好地解释了这个逻辑，但是lazyProduct …如果你在lazyProduct取消注释，你会注意到有两个关键的variableslens和p 。 lens是预先计算每个数组（在数组数组中）传入的数组的长度p是一个堆栈，将当前path保存到您所在的位置（例如，如果您是“1st array 3rd index，2nd数组第二个索引，第三个数组第一个索引“ p表示），这是什么传递到您的callback函数。
我的callback函数只是在参数上进行连接（根据您的OP示例），但是这些也只是p中映射到原始数组数组的对应值。
如果你进一步分析，你将会看到构build笛卡尔产品所需的脚印仅限于你需要调用callback函数的地方。 尝试一下你最糟糕的情况来看看。
更新2
我编写了基于笛卡尔积的75％的方法。 我的API采用了一个ret.jsparsing树，将其转换为RPN，然后生成一组集以传入X（n）计算器。 使用([ab]{2}){1,2}|[cd](f|ef{0,2}e) @ruud示例，将生成以下代码：
new Option([ new Set([ new Set(new Set(['a','b']), new Set['a','b'])), new Set(new Set(['a','b']), new Set['a','b'])) ]), new Set( ['c', 'd'], new Option([ new Set(['f']), new Set(['e']]), new Set(['e','f']), new Set(new Set(['e','f']), new Set(['e', 'f'])) ]) ])
棘手的部分是嵌套选项（越野车）和反向字符类和后退引用（不支持）。
这种方法变得越来越脆弱，实际上迭代器解决scheme是优越的。 从你的分析树转换到这应该是非常简单的。 感谢有趣的问题！
这里已经有很多好的答案，但我特别想要发电机部分工作，这不适合你。 看来你正在试图做到这一点：
//the alphanumeric part for (x of alpha()) for (y of numeric()) console.log(x + y); //or as generator itself like you wanted function* alphanumeric() { for (x of alpha()) for (y of numeric()) yield(x + y); } //iterating over it for (var i of alphanumeric()) { console.log(i); }
输出：
a0 a1 b0 b1 c0 c1
您可以将此用于正则expression式匹配中所需的笛卡尔积。
只是想分享我想出来的，使用生成器和基于invRegex.py ：
var ret = require('ret'); var tokens = ret('([ab]) ([cd]) \\1 \\2 z'); var references = []; capture(tokens); // console.log(references); for (string of generate(tokens)) { console.log(string); } function capture(token) { if (Array.isArray(token)) { for (var i = 0; i < token.length; ++i) { capture(token[i]); } } else { if ((token.type === ret.types.ROOT) || (token.type === ret.types.GROUP)) { if ((token.type === ret.types.GROUP) && (token.remember === true)) { var group = []; if (token.hasOwnProperty('stack') === true) { references.push(function* () { yield* generate(token.stack); }); } else if (token.hasOwnProperty('options') === true) { for (var generated of generate(token)) { group.push(generated); } references.push(group); } } if (token.hasOwnProperty('stack') === true) { capture(token.stack); } else if (token.hasOwnProperty('options') === true) { for (var i = 0; i < token.options.length; ++i) { capture(token.options[i]); } } return true; } else if (token.type === ret.types.REPETITION) { capture(token.value); } } } function* generate(token) { if (Array.isArray(token)) { if (token.length > 1) { for (var prefix of generate(token[0])) { for (var suffix of generate(token.slice(1))) { yield prefix + suffix; } } } else { yield* generate(token[0]); } } else { if ((token.type === ret.types.ROOT) || (token.type === ret.types.GROUP)) { if (token.hasOwnProperty('stack') === true) { token.options = [token.stack]; } for (var i = 0; i < token.options.length; ++i) { yield* generate(token.options[i]); } } else if (token.type === ret.types.POSITION) { yield ''; } else if (token.type === ret.types.SET) { for (var i = 0; i < token.set.length; ++i) { var node = token.set[i]; if (token.not === true) { if ((node.type === ret.types.CHAR) && (node.value === 10)) { } } yield* generate(node); } } else if (token.type === ret.types.RANGE) { for (var i = token.from; i <= token.to; ++i) { yield String.fromCharCode(i); } } else if (token.type === ret.types.REPETITION) { if (token.min === 0) { yield ''; } for (var i = token.min; i <= token.max; ++i) { var stack = []; for (var j = 0; j < i; ++j) { stack.push(token.value); } if (stack.length > 0) { yield* generate(stack); } } } else if (token.type === ret.types.REFERENCE) { console.log(references); if (references.hasOwnProperty(token.value - 1)) { yield* references[token.value - 1](); // yield references[token.value - 1]().next().value; } else { yield ''; } } else if (token.type === ret.types.CHAR) { yield String.fromCharCode(token.value); } } }
我还没有想出如何实现捕获组/引用，并且REPETITION标记types中产生的值不是按照字典顺序生成的，但除此之外，它的工作原理。