将invRegex.py移植到Javascript(Node.js)

我建议你编写迭代器类.它们易于实现(基本上它们是状态机),它们具有较低的内存占用,它们可以组合起来构建越来越复杂的表达式(请向下滚动以查看最终结果),并且生成的迭代器可以包含在枚举.

每个迭代器类都有以下方法:

第一:初始化状态机(第一场比赛)

下一个:进入下一个状态(下一场比赛)

ok:最初为true,但是一旦'next'超出最后一场比赛就会变为false

get:返回当前匹配(作为字符串)

克隆:克隆对象; 重复是必不可少的,因为每个实例都需要自己的状态

从最简单的案例开始:一个或多个应按字面匹配的字符序列(例如/ foo /).不用说这只有一个匹配,所以'ok'在第一次调用'next'时会变为false.

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})是Sequence和Optional的组合.因为我必须继承一个或另一个,所以我的实现包含两个相互依赖的类.

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());
      }
   };
}

是时候把它们放在一起了.让我们采取一些愚蠢的正则表达式:

([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])
]);

在构建迭代器类树时指定捕获组.我仍在这里手动执行此操作,但最终您希望自动执行此操作.这只是将您的解析树映射到类似的迭代器类树的问题.

编辑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);    // requires ret.js
var iterator = new ParseTreeMapper().mapToIterator(parseTree);

我在这个演示中将所有组件放在一起:http://jsfiddle.net/Pmnwk/3/

注意:不支持许多正则表达式语法结构(锚点,前瞻,后瞻,递归),但我想它已经与invRegex.py相当.