Портирование invRegex.py в Javascript (Node.js)
Я пытался портировать 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 type должен принять это предыдущее значение до степени 3, что даст 17576 различных комбинаций. Если бы я должен был сгладить tokens массив, как я делал раньше для cartesianProductOfпромежуточные сплюснутые значения заняли бы столько же места, сколько и сам фактический декартов.
Я надеюсь, что этот пример лучше объясняет проблему, с которой я сталкиваюсь.
6 ответов
Я советую вам писать классы итераторов. Их легко реализовать (в основном это конечные автоматы), они занимают мало памяти, их можно комбинировать для создания все более сложных выражений (прокрутите вниз, чтобы увидеть конечный результат), и полученный итератор можно обернуть в переписчик.
Каждый класс итератора имеет следующие методы:
- первый: инициализирует конечный автомат (первое совпадение)
- следующее: переходит в следующее состояние (следующий матч)
- ОК: изначально верно, но становится ложным, как только "следующий" выходит за пределы последнего матча
- get: возвращает текущее совпадение (в виде строки)
- клон: клонирует объект; важно для повторения, потому что каждый экземпляр нуждается в своем собственном состоянии
Начните с самого тривиального случая: последовательность из одного или нескольких символов, которые должны совпадать буквально (например, / 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(); }));
};
Другой способ объединить итераторы - это выбор (альтернативы), например, 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) или страдает от плохого ООП. Я просто надеюсь, что это проясняет концепцию.
РЕДАКТИРОВАТЬ: для полноты и по инициативе 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.
Вот версия, которая создает функцию для каждой части входных данных и объединяет их все для создания функции, которая будет генерировать каждый результат регулярного выражения и передавать его в этот аргумент:
//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, "");
};
}
Модифицировано для работы с деревом разбора ( отсюда скопирован небольшой код):
//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;
}
Если вы в порядке с менее функциональным, более C-esque решением:
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: вы действительно хотите получить декартово произведение, но не хотите заранее вычислять их все (и использовать всю эту память). Иными словами, вы хотите перебрать декартово произведение.
Если это так, вы проверили реализацию Javascript формулы X(n)? При этом вы можете либо перебирать их в естественном порядке <<0,0,0>, <0,0,1>, <0,1,0>, ...> или выбирать произвольную позицию для расчета.
Кажется, что вы можете просто сделать:
// 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 код, образец массива токенов и вызов lazyProduct с этими tokens,
Когда вы запустите код без изменений, вы увидите, что он генерирует 0@aи т. д. ожидаемый выход из выборки tokens массив. Я думаю, что ссылка объясняет логику довольно хорошо, но в итоге... если вы раскомментируете инструментарий в lazyProductвы заметите, что есть две ключевые переменные lens а также p, lens является предварительным вычислением длины каждого массива (в массиве массивов), переданного в. p является стеком, который содержит текущий путь до того места, где вы находитесь (например, если вы "1-й массив 3-й индекс, 2-й массив 2-й индекс и 3-й массив 1-й индекс" p представляет это), и это то, что передается в вашу функцию обратного вызова.
Моя функция обратного вызова просто выполняет объединение аргументов (согласно вашему примеру с OP), но опять-таки это просто соответствующие значения в p, сопоставленные с исходным массивом массивов.
Если вы профилируете это дальше, вы увидите, что площадь, необходимая для построения декартового произведения, ограничена только тем, что вам нужно для вызова функции обратного вызова. Попробуйте это на одном из ваших наихудших жетонов, чтобы увидеть.
Обновление 2
Я написал около 75% подхода, основанного на декартовом произведении. Мой API взял дерево разбора ret.js, преобразовал его в RPN, затем сгенерировал наборы наборов для передачи в калькулятор X(n). Используя пример @ruud ([ab]{2}){1,2}|[cd](f|ef{0,2}e), это будет сгенерировано:
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']))
])
])
Сложными частями были вложенные параметры (с ошибками) и обратные классы символов и обратные ссылки (не поддерживаются).
Этот подход становился хрупким, и действительно решение Iterator превосходит его. Преобразование из вашего дерева разбора в это должно быть довольно простым. Спасибо за интересную проблему!
Здесь уже есть много хороших ответов, но я специально хотел, чтобы генераторная часть работала, что не для вас. Похоже, вы пытались сделать это:
//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
Вы можете использовать это для декартовых произведений, необходимых при сопоставлении регулярных выражений.
Просто хочу поделиться тем, что я придумал, используя генераторы и основанные на 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 Тип токена еще не сгенерирован в лексикографическом порядке, но кроме этого он работает.