Перенос invRegex.py в Javascript (Node.js)

Ответ 1

Я советую вам писать классы итераторов. Их легко реализовать (в основном они являются государственными машинами), они имеют низкую площадь памяти, их можно комбинировать для создания все более сложных выражений (прокрутите вниз до конечного результата), и полученный итератор может быть завернут в переписчик.

Каждый класс итератора имеет следующие методы:

• сначала: инициализирует конечный автомат (первое совпадение)
• next: переходит в следующее состояние (следующее совпадение)
• ok: изначально верно, но становится ложным, как только "next" выходит за пределы последнего совпадения
• get: возвращает текущее соответствие (в виде строки)
• clone: ​​ клонирует объект; необходимо для повторения, поскольку каждый экземпляр нуждается в собственном состоянии.

Начните с самого тривиального случая: последовательность из одного или нескольких символов, которые должны быть сопоставлены буквально (например,/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); };

Теперь нам нужны итераторы, которые объединяют другие итераторы для формирования более сложных регулярных выражений. Последовательность - это всего два или более шаблона в строке (например, 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(); }));
};

Другим способом объединения итераторов является выбор (альтернативы a.k.a.), например. Foo |. бар

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

Другие функции regex могут быть реализованы путем объединения существующих классов. Наследование классов - отличный способ сделать это. Например, необязательный шаблон (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());   // 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) или страдает от плохого ООП. Я просто надеюсь, что это делает концепцию понятной.

EDIT: для полноты и после инициативы 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/

Примечание. Многие синтаксические конструкции регулярных выражений не поддерживаются (привязки, поиск вперед, внешний вид, рекурсия), но я думаю, что это уже почти до уровня с invRegex.py.

Ответ 2

Здесь версия, которая выполняет функцию для каждой части ввода и составляет все из них, создает функцию, которая будет генерировать каждый результат регулярного выражения и передает его в этот аргумент:

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

Ответ 3

Как насчет этого:

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

Ответ 4

Похоже, вы просите 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.

Когда вы запускаете код без изменений, вы увидите, что он генерирует вывод [email protected] и т.д., ожидаемый из массива sample 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 превосходит. Преобразование из дерева разбора в это должно быть довольно простым. Спасибо за интересную проблему!

Ответ 5

Просто хочу поделиться тем, с чем я столкнулся, используя генераторы и на основе 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, еще не создаются в лексикографическом порядке, но кроме этого он работает.

Ответ 6

Здесь уже много хороших ответов, но я специально хотел, чтобы часть генератора работала, что не для вас. Кажется, вы пытались это сделать:

//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

Вы можете использовать это для декартового продукта, необходимого для соответствия регулярному выражению.