我建议你编写迭代器类。它们易于实现(基本上它们是状态机),具有较低的内存占用,可以组合使用以构建越来越复杂的表达式(请向下滚动以查看最终结果),并且生成的迭代器可以包装在枚举器中。
每个迭代器类都有以下方法:
- first:初始化状态机(第一个匹配项)
- next:继续到下一个状态(下一个匹配项)
- ok:最初为真,但一旦“next”超过最后一个匹配项,就变为假
- get:返回当前匹配项(作为字符串)
- clone:克隆对象;对于重复很重要,因为每个实例都需要自己的状态
从最简单的情况开始:应该按字面意义匹配的一个或多个字符序列(例如
/foo/)。不用说,这只有一个匹配项,因此在第一次调用“next”时,“ok”将变为假。
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); };
现在我们需要迭代器来组合其他迭代器以形成更复杂的正则表达式。一个序列只是两个或多个连续的模式(例如
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(); }));
};
另一种组合迭代器的方式是选择(也称为替代),例如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(); }));
};
通过组合现有的类可以实现其他正则表达式功能。类继承是一种很好的方法。例如,可选模式 (x?) 只是在空字符串和 x 之间进行选择。
function Optional(iterator) {
if (arguments.length > 0) {
Choice.call(this, [new Literal(''), iterator]);
}
}
Optional.prototype = new Choice();
重复(x{n,m})是序列和可选项的组合。由于我必须继承其中之一,因此我的实现由两个相互依赖的类组成。
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());
}
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());
}
};
}
现在是把所有东西放在一起的时候了。让我们来看一些愚蠢的正则表达式:
([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等)选取早先捕获组的当前匹配项(即括号中的任何内容)。它的实现与文字类型非常相似,因为它只有一个匹配项。
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])
]);
在构建迭代器类的树时,可以指定捕获组。我现在仍然以手动方式执行此操作,但最终您希望将其自动化。这只是将解析树映射到类似的迭代器类树的问题。
编辑2: 这里有一个相对简单的递归函数,它将由ret.js生成的解析树转换为迭代器。
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[a-n]{3}';
var parseTree = ret(regex);
var iterator = new ParseTreeMapper().mapToIterator(parseTree);
我在这个演示中将所有组件放在一起:
http://jsfiddle.net/Pmnwk/3/
注意:许多正则表达式语法结构不受支持(锚点、前瞻、后顾、递归),但我想它已经与invRegex.py相当了。
yield*
就像 Python 中的yield from
。另外,“我也不知道如何在 JavaScript 中模仿生成器行为。”具体是指哪种行为? - Benjamin Gruenbaumyield *
能帮助澄清它是如何工作的?要使您的字母数字组合正常工作,您需要分配yield
的结果,然后进行连接。例如:var x,y; x = yield* alpha(); y = yield* numeric(); return x + y;
- bishopyield*
绑定:yield (yield* alpha()) + (yield* numeric());
- bishop