Я пытался портироватьinvRegex.py на реализацию node.js на некоторое время, но яЯ все еще борюсь с этим. У меня уже есть дерево разбора регулярных выражений благодаряret.js tokenizer, и он работает довольно хорошо, но фактическое создание и объединение всех отдельных элементов способом, который эффективно использует память, показалось мне очень сложным. Для простоты, скажем, у меня есть следующее регулярное выражение:

[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

Учитывая, что яm может получить каждый отдельный токен и создать массив всех допустимых отдельных выходных данных:

[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 - к сожалению, я могуне понимаю Хаскелла, а я нетТакже не знаю, как имитировать поведение генератора в 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
                        }
                    ]
                }
            }
        ]
    ]
}

/SETRANGE Тип должен давать 26 различных значений, а родительскийREPETITION type должен принять это предыдущее значение до степени 3, что даст 17576 различных комбинаций. Если бы я должен был сгладитьtokens массив, как я делал раньше дляcartesianProductOfпромежуточные сплюснутые значения заняли бы столько же места, сколько и сам фактический декартов.

Я надеюсь, что этот пример лучше объясняет проблему, с которой я сталкиваюсь.