将invRegex.py移植到Javascript（Node.js）

孙星鹏

2023-03-14

问题内容：

我已经尝试将invRegex.py移植到node.js实现了一段时间，但是我仍然在努力。多亏了ret.js标记生成器，我已经有了正则表达式分析树，并且运行良好，但是以内存高效的方式实际生成和连接所有不同元素对我来说是非常具有挑战性的。为简单起见，可以说我有以下正则表达式：

[01]{1,2}@[a-f]

喂养到invRegex.py产生下列输出（ tabbified 取更小的空间）：

 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 ['@'];
};

[a-f] = 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个值保存在内存中，例如将[a-z]{0,10}其保存146813779479511在内存中，这是完全不可行的。我想以异步方式处理这个庞大的列表，将每个生成的组合传递给回调，并允许我在我认为合适的任何合理点中断该过程，就像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.js解析树b[a-z]{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/RANGE类型应该收率26倍不同的值，并且父REPETITION类型应该采取先前值至3的动力，得到17576种不同组合。如果要tokens像以前一样生成一个展平的数组cartesianProductOf，则中间展平的值将占用实际笛卡尔乘积本身的空间。

我希望这个例子可以更好地解释我面临的问题。

问题答案：

我建议您编写迭代器类。它们易于实现（基本上是状态机），内存占用少，可以组合起来以构建越来越复杂的表达式（请向下滚动以查看最终结果），并将生成的迭代器包装在枚举器。

每个迭代器类具有以下方法：

first： 初始化状态机（第一个匹配项）
下一个： 进入下一个状态（下一场比赛）
ok： 最初为true，但是一旦“ next”超过了最后一场比赛，就变为false
get： 以字符串形式返回当前匹配项
clone： 克隆对象；重复是必不可少的，因为每个实例都需要有自己的状态

从最简单的情况开始：一个或多个应按字面值匹配的字符的序列（例如 / foo /
）。不用说这只有一个匹配项，因此在第一次调用“下一个”时，“确定”将变为错误。

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

组合迭代器的另一种方法是选择（aka替代项），例如 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的倡议，我实现了另一个迭代器类： reference 。

引用（\ 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/

注意：不支持许多regex语法构造（锚定，先行，后退，递归），但是我想它已经可以与invRegex.py媲美了。

将invRegex.py移植到Javascript（Node.js）

相关阅读

相关文章

相关问答

相关工具

相关文档