Próbowałem portowaćinvRegex.py do implementacji node.js przez jakiś czas, ale wciąż z tym walczę. Mam już drzewo analizujące wyrażenie regularne dziękiret.js tokenizer i działa całkiem nieźle, ale faktyczne generowanie i łączenie wszystkich odrębnych elementów w sposób, który jest wydajny pod względem pamięci, jest dla mnie bardzo trudne. Aby to było proste, powiedzmy, że mam następujące wyrażenie regularne:

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

Podając toinvRegex.py produkuje następujące dane wyjściowe (tabbified zajmować mniej miejsca):

 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

Biorąc pod uwagę, że jestem w stanie uzyskać każdy indywidualny token i utworzyć tablicę wszystkich ważnych indywidualnych wyników:

[01]{1,2} = function () {
    return ['0', '00', '01', '1', '10', '11'];
};

@ = function () {
    return ['@'];
};

[a-f] = function () {
    return ['a', 'b', 'c', 'd', 'e', 'f'];
};

Mogę obliczyćprodukt kartezjański wszystkich tablic i uzyskaj taką samą oczekiwaną wydajność:

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

Problem polega na tym, że zawiera wszystkie 36 wartości w pamięci, jeśli miałbym nieco bardziej skomplikowane wyrażenie regularne, takie jak[a-z]{0,10} to się utrzyma146813779479511 wartości w pamięci, co jest całkowicie niewykonalne. Chciałbym przetworzyć tę ogromną listę w sposób asynchroniczny, przekazując każdą wygenerowaną kombinację do wywołania zwrotnego i pozwalając mi przerwać proces w dowolnym sensownym punkcie, który uważam za odpowiedni, podobnie jak invRegex.py lubten pakiet Haskell - niestety nie rozumiem Haskella i nie wiem jak naśladować zachowanie generatora w Pythonie na Javascript.

Próbowałem uruchomić kilka prostych eksperymentów generatora w węźle 0.11.9 (z--harmony) jak ten:

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

Nie trzeba dodawać, że powyższe nie działa. = /

Uderzając głową o ścianę tutaj, każda pomoc w rozwiązaniu tego problemu byłaby bardzo ceniona.

AKTUALIZACJA: Oto przykładowe drzewo analizowania ret.js dlab[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
                        }
                    ]
                }
            }
        ]
    ]
}

TheSET / RANGE typ powinien dawać 26 różnych wartości, a rodzicaREPETITION typ powinien przyjąć tę poprzednią wartość do potęgi 3, dając 17576 różnych kombinacji. Gdybym miał wygenerować spłaszczonetokens tablica jak wcześniejcartesianProductOf, pośrednie spłaszczone wartości zajęłyby tyle miejsca, co sam produkt kartezjański.

Mam nadzieję, że ten przykład lepiej wyjaśnia problem, przed którym stoję.