Как писать парсеры на JavaScript

    … а именно как писать LL парсеры для не очень сложных структур при помощи конструирования сложного парсера из более простых. Изредка возникает необходимость распарсить что то несложное, скажем некую XML-подобную структуру или какой нибудь data URL, и тогда обычно возникает либо простыня хитрого трудно читаемого кода либо зависимость от какой то ещё более сложной и хитрой библиотеки для парсинга. Здесь я собираюсь совместить несколько известных идей (какие то из них попадались на Хабре) и показать как можно просто и лаконично написать довольно сложные парсеры уложившись при этом в совсем немного строчек кода. Для примера я буду писать парсер XML-подобной структуры. И да, я не буду вставлять сюда картинку для привлечения внимания. В статье вообще картинок нет, поэтому читать будет трудно.



    Основная идея



    Она в том, что каждый кусочек входного текста парсится отдельной функцией (назовём её «паттерном») и комбинируя эти функции можно получать более сложные функции которые смогут парсить более сложные тексты. Итак, паттерн — это такой объект у которого есть метод exec который и осуществляет парсинг. Этой функции указывают что и откуда парсить и она возвращает распарсенное и то место где парсинг закончился:

    var digit = {
        exec: function (str, pos) {
            var chr = str.charAt(pos);
            if (chr >= "0" && chr <= "9") 
                return { res: +chr, end: pos + 1};
        }
    };
    


    Теперь digit это паттерн парсящий цифры и его можно использовать так:

    assert.deepEqual(digit.exec("5", 0), { res: 5, end: 1 });
    assert.deepEqual(digit.exec("Q", 0), void 0);
    


    Почему именно такой интерфейс? Потому что в JS есть встроенный класс RegExp с очень похожим интерфейсом. Для удобства введём класс Pattern (смотрите на него как на аналог RegExp) экземпляры которого и будут представлять собой эти паттерны:

    function Pattern(exec) {
        this.exec = exec;
    }
    


    Затем введём несколько простых паттернов которые пригодятся практически в людом более-менее сложном парсере.

    Простые паттерны



    Самый простой паттерн это txt — он парсит фиксированную наперёд заданную строку текста:

    function txt(text) {
        return new Pattern(function (str, pos) {
            if (str.substr(pos, text.length) == text)
                return { res: text, end: pos + text.length };
        });
    }
    


    Применяется он так:

    assert.deepEqual(txt("abc").exec("abc", 0), { res: "abc", end: 3 });
    assert.deepEqual(txt("abc").exec("def", 0), void 0);
    


    Если бы в JS были конструкторы-по-умолчанию (как в C++), то запись txt(«abc») можно было бы сократить до «abc» в контексте конструирования более сложного паттерна.

    Затем введём его аналог для регулярных выражений и назовём его rgx:

    function rgx(regexp) {
        return new Pattern(function (str, pos) {
            var m = regexp.exec(str.slice(pos));
            if (m && m.index === 0)
                return { res: m[0], end: pos + m[0].length };
        });
    }
    


    Применяют его так:

    assert.deepEqual(rgx(/\d+/).exec("123", 0), { res: "123", end: 3 });
    assert.deepEqual(rgx(/\d+/).exec("abc", 0), void 0);
    


    Опять же, если бы в JS были конструторы-по-умолчанию, то запись rgx(/abc/) можно было сократить до /abc/.

    Паттерны-комбинаторы



    Теперь нужно ввести несколько паттернов которые комбинируют уже имеющиеся паттерны. Самый простой из таких «комбинаторов» это opt — он делает любой паттерн не обязательным, т.е. если исходный паттерн p не может распарсить текст, то opt(p) на этом же тексте скажет, что всё распарсилось, только результат парсинга пуст:

    function opt(pattern) {
        return new Pattern(function (str, pos) {
            return pattern.exec(str, pos) || { res: void 0, end: pos };
        });
    }
    


    Пример использования:

    assert.deepEqual(opt(txt("abc")).exec("abc"), { res: "abc", end: 3 });
    assert.deepEqual(opt(txt("abc")).exec("123"), { res: void 0, end: 0 });
    


    Если бы в JS была возможна перегрузка операторов и конструкторы-по-умолчанию, то запись opt(p) можно было бы сократить до p || void 0 (это хорошо видно из того как реализован opt).

    Следующий по сложности паттерн-комбинатор это exc — он парсит только то, что может распарсить первый паттерн и не может распарсить второй:

    function exc(pattern, except) {
        return new Pattern(function (str, pos) {
            return !except.exec(str, pos) && pattern.exec(str, pos);
        });
    }
    


    Если W(p) это множество текстов которые парсит паттерн p, то W(exc(p, q)) = W(p) \ W(q). Это удобно например когда нужно распарсить все большие буквы кроме буквы H:

    var p = exc(rgx(/[A-Z]/), txt("H"));
    
    assert.deepEqual(p.exec("R", 0), { res: "R", end: 1 });
    assert.deepEqual(p.exec("H", 0), void 0);
    


    Если бы в JS была перегрузка операторов, то exc(p1, p2) можно было бы сократить до p1 — p2 или до !p2 && p1 (для этого, правда, потребуется ввести паттерн-комбинатор all/and который будет работать как оператор &&).

    Затем идёт паттерн-комбинатор any — он берёт несколько паттернов и конструирует новый, который парсит то, что парсит первый из данных паттернов. Можно сказать, что W(any(p1, p2, p3, ...)) = W(p1) v W(p2) v W(p3) v…

    function any(...patterns) {
        return new Pattern(function (str, pos) {
            for (var r, i = 0; i < patterns.length; i++)
                if (r = patterns[i].exec(str, pos))
                    return r;
        });
    }
    


    Я воспользовался конструкцией ...patterns (harmony:rest_parameters), чтобы избежать корявого кода вроде [].slice.call(arguments, 0). Пример использования any:

    var p = any(txt("abc"), txt("def"));
    
    assert.deepEqual(p.exec("abc", 0), { res: "abc", end: 3 });
    assert.deepEqual(p.exec("def", 0), { res: "def", end: 3 });
    assert.deepEqual(p.exec("ABC", 0), void 0);
    


    Если бы в JS была перегрузка операторов, то any(p1, p2) можно было бы сократить до p1 || p2.

    Следующий паттерн-комбинатор это seq — он последовательно парсит текст данной ему последовательностью паттернов и выдаёт массив результатов:

    function seq(...patterns) {
        return new Pattern(function (str, pos) {
            var i, r, end = pos, res = [];
    
            for (i = 0; i < patterns.length; i++) {
                r = patterns[i].exec(str, end);
                if (!r) return;
                res.push(r.res);
                end = r.end;
            }
    
            return { res: res, end: end };
        });
    }
    


    Применяется он так:

    var p = seq(txt("abc"), txt("def"));
    
    assert.deepEqual(p.exec("abcdef"), { res: ["abc", "def"], end: 6 });
    assert.deepEqual(p.exec("abcde7"), void 0);
    


    Если бы в JS была перегрузка операторов, то seq(p1, p2) можно было бы сократить до p1, p2 (перегружен оператор «запятая»).

    Ну и наконец паттерн-комбинатор rep — он много раз применяет известный паттерн к тексту и выдаёт массив результатов. Как правило это применяется для парсинга неких однотипных конструкций разделённых скажем запятыми, поэтому rep принимает два аргумента: основной паттерн результаты которого нам интересны и разделяющий паттерн результаты которого отбрасываются:

    function rep(pattern, separator) {
        var separated = !separator ? pattern :
            seq(separator, pattern).then(r => r[1]);
    
        return new Pattern(function (str, pos) {
            var res = [], end = pos, r = pattern.exec(str, end);
    
            while (r && r.end > end) {
                res.push(r.res);
                end = r.end;
                r = separated.exec(str, end);
            }
    
            return { res: res, end: end };
        });
    }
    


    Можно добавить ещё пару параметров min и max которые будут контролировать сколько повторений допустимо. Здесь я воспользовался стрелочной функцией r => r[1] (harmony:arrow_functions), чтобы не писать function (z) { return z[1] }. Обратите внимание на то как rep сводится к seq при помощи Pattern#then (идея взята у Promise#then):

    function Pattern(exec) {
        ...
    
        this.then = function (transform) {
            return new Pattern(function (str, pos) {
                var r = exec(str, pos);
                return r && { res: transform(r.res), end: r.end };
            });
        };
    }
    


    Этот метод позволяет выводить из одного паттерна другой при помощи применения произвольного преобразования к результатам первого. Кстати, знатоки хаскеля, можно ли сказать что этот Pattern#then делает из паттерна монаду?

    Ну а rep применяется таким образом:

    var p = rep(rgx(/\d+/), txt(","));
    
    assert.deepEqual(p.exec("1,23,456", 0), { res: ["1", "23", "456"], end: 8 });
    assert.deepEqual(p.exec("123ABC", 0), { res: ["123"], end: 3 });
    assert.deepEqual(p.exec("ABC", 0), void 0);
    


    Какой либо внятной аналогии с перегрузкой операторов для rep мне в голову не приходит.

    В итоге получается около 70 строчек на все эти rep/seq/any. На этом список паттернов-комбинаторов заканчивается и можно переходить собственно к конструированию паттерна распознающего XML-подобный текст.

    Парсер XML-подобных текстов



    Ограничимся вот такими XML-подобными текстами:

    <?xml version="1.0" encoding="utf-8"?>
    <book title="Book 1">
      <chapter title="Chapter 1">
        <paragraph>123</paragraph>
        <paragraph>456</paragraph>
      </chapter>
      <chapter title="Chapter 2">
        <paragraph>123</paragraph>
        <paragraph>456</paragraph>
        <paragraph>789</paragraph>
      </chapter>
      <chapter title="Chapter 3">
        ...
      </chapter>
    </book>
    


    Для начала напишем паттерн распознающий именованный атрибут вида name=«value» — он, очевидно, часто встречается в XML:

    var name = rgx(/[a-z]+/i).then(s => s.toLowerCase());
    var char = rgx(/[^"&]/i);
    var quoted = seq(txt('"'), rep(char), txt('"')).then(r => r[1].join(''));
    var attr = seq(name, txt('='), quoted).then(r => ({ name: r[0], value: r[2] }));
    


    Здесь attr парсит именованный атрибут со значением в виде строки, quoted — парсит строку в кавычках, char — парсит одну букву в строке (зачем это писать в виде отдельного паттерна? затем, что потом «научить» этот char парсить т.н. xml entities), ну а name парсит имя атрибута (обратите внимание что парсит он как большие так и малые буквы, но возвращает распарсенное имя где все буквы малые). Применение attr выглядит так:

    assert.deepEqual(
        attr.exec('title="Chapter 1"', 0), 
        { res: { name: "title", value: "Chapter 1" }, end: 17 });
    


    Далее сконструируем паттерн умеющий парсить заголовок вида <?xml… ?>:

    var wsp = rgx(/\s+/);
    
    var attrs = rep(attr, wsp).then(r => {
        var m = {}; 
        r.forEach(a => (m[a.name] = a.value));
        return m;
    });
    
    var header = seq(txt('<?xml'), wsp, attrs, txt('?>')).then(r => r[2]);
    


    Здесь wsp парсит один или несколько пробелов, attrs парсит один или несколько именованных атрибутов и возвращает распарсенное в виде словаря (rep возвратил бы массив пар имя-значение, но словарь удобнее, поэтому массив преобразуется в словарь внутри then), а header парсит собственно заголовок и возвращает только атрибуты заголовка в виде того самого словаря:

    assert.deepEqual(
        header.exec('<?xml version="1.0" encoding="utf-8"?>', 0),
        { res: { version: "1.0", encoding: "utf-8" }, end: ... });
    


    Теперь перейдём к распарсиванию конструкций вида <node...>...:

    var text = rep(char).then(r => r.join(''));
    var subnode = new Pattern((str, pos) => node.exec(str, pos));
    
    var node = seq(
        txt('<'), name, wsp, attrs, txt('>'),
        rep(any(text, subnode), opt(wsp)),
        txt('</'), name, txt('>'))
        .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] }));
    


    Здесь text парсит текст внутри узла (node) и использует паттерн char который может быть научен распознавать xml entities, subnode парсит внутренний узел (фактически subnode = node) и node парсит узел с атрибутами и внутренними узлами. Зачем такое хитрое определение subnode? Если в определении node сослаться на node напрямую (как то так: node = seq(..., node, ...)) то окажется, что на момент определения node эта переменная ещё пуста. Трюк с subnode позволяет убрать эту циклическую зависимость.

    Осталось определить паттерн распознающий весь файл с заголовком:

    var xml = seq(header, node).then(r => ({ root: r[1], attrs: r[0] }));
    


    Применение соответственно такое:

    assert.deepEqual(
        xml.exec(src), {
            attrs: { version: '1.0', encoding: 'utf-8' },
            root: {
                name: 'book',
                attrs: { title: 'Book 1' },
                nodes: [
                    {
                        name: 'chapter',
                        attrs: { title: 'Chapter 1' },
                        nodes: [...]
                    },
                    ...
                ]
            }
        });
    


    Здесь я вызываю Pattern#exec с одним аргументом и смысл этого в том, что я хочу распарсить строку с самого начала и убедиться, что она распарсилась до конца, ну а поскольку она распарсилась до конца, то вернуть достаточно только распарсенное без указателя на то место где парсер остановился (я и так знаю, что это конец строки):

    function Pattern(name, exec) {
        ...
    
        this.exec = function (str, pos) {
            var r = exec(str, pos || 0);
            return pos >= 0 ? r : !r ? null : r.end != str.length ? null : r.res;
        };
    }
    


    Собственно весь парсер в 20 строчек (не забываем про те 70 которые реализуют rep, seq, any и пр.):

    var name = rgx(/[a-z]+/i).then(s => s.toLowerCase());
    var char = rgx(/[^"&]/i);
    var quoted = seq(txt('"'), rep(char), txt('"')).then(r => r[1].join(''));
    var attr = seq(name, txt('='), quoted).then(r => ({ name: r[0], value: r[2] }));
    
    var wsp = rgx(/\s+/);
    
    var attrs = rep(attr, wsp).then(r => {
        var m = {}; 
        r.forEach(a => (m[a.name] = a.value));
        return m;
    });
    
    var header = seq(txt('<?xml'), wsp, attrs, txt('?>')).then(r => r[2]);
    
    var text = rep(char).then(r => r.join(''));
    var subnode = new Pattern((str, pos) => node.exec(str, pos));
    
    var node = seq(
        txt('<'), name, wsp, attrs, txt('>'),
        rep(any(text, subnode), opt(wsp)),
        txt('</'), name, txt('>'))
        .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] }));
    
    var xml = seq(header, node).then(r => ({ root: r[1], attrs: r[0] }));
    


    С перегрузкой операторов в JS (или в C++) это выглядело бы как то так:

    var name = rgx(/[a-z]+/i).then(s => s.toLowerCase());
    var char = rgx(/[^"&]/i);
    var quoted = ('"' + rep(char) + '"').then(r => r[1].join(''));
    var attr = (name + '=' + quoted).then(r => ({ name: r[0], value: r[2] }));
    
    var wsp = rgx(/\s+/);
    
    var attrs = rep(attr, wsp).then(r => {
        var m = {}; 
        r.forEach(a => (m[a.name] = a.value));
        return m;
    });
    
    var header = ('<?xml' + wsp + attrs + '?>').then(r => r[2]);
    
    var text = rep(char).then(r => r.join(''));
    var subnode = new Pattern((str, pos) => node.exec(str, pos));
    
    var node = ('<' + name + wsp + attrs + '>' + rep(text | subnode) + (wsp | null) + '</' + name + '>')
        .then(r => ({ name: r[1], attrs: r[3], nodes: r[5] }));
    
    var xml = (header + node).then(r => ({ root: r[1], attrs: r[0] }));
    


    Стоит отметить, что каждый var здесь строго соответствует одному правилу ABNF и потому если надо что то распарсить по описанию в RFC (а там любят ABNF), то перенос тех правил — дело механическое. Более того, поскольку сами правила ABNF (а также EBNF и PEG) строго формальны, то можно написать парсер этих правил и затем, вместо вызовов rep, seq и пр. писать что то такое:

    var dataurl = new ABNF('"data:" mime ";" attrs, "," data', {
        mime: /[a-z]+\/[a-z]+/i,
        attrs: ...,
        data: /.*/
    }).then(r => ({ mime: r[1], attrs: r[3], data: r[5] }));
    


    И применять как обычно:

    assert.deepEqual(
        dataurl.exec('data:text/plain;charset="utf-8",how+are+you%3f'),
        { mime: "text/plain", attrs: { charset: "utf-8" }, data: "how are you?" });
    


    Ещё немного буков



    Почему Pattern#exec возвращает null/undefined если распарсить ничего не удалось? Почему бы не бросать исключение? Если использовать исключения таким образом, то парсер станет медленнее раз в двадцать. Исключения хороши для исключительных случаев.

    Описанный способ позволяет писать LL парсеры которые подходят не для всех целей. Например если надо распарсить XML вида

    <book attr1="..." attr2="..." очень много атрибутов ???
    


    То в том месте где стоит ??? может оказаться как /> так и просто >. Теперь если LL парсер пытался всё это распарсить как <book ...> а на месте ??? оказался />, то парсер отбросит всё то что он так долго парсил и начнёт заново в предположении, что это <book .../>. LR парсеры лишены этого недостатка, но писать их трудно.

    Также LL парсеры плохо подходят для разбора разнообразных синтаксических/математических выражений где есть операторы с разным приоритетом и т.п. LL парсер конечно можно написать, но он будет несколько запутан и будет работать медленно. LR парсер будет запутан сам по себе, но будет быстр. Поэтому такие выражения удобно парсить т.н. алгоритмом Пратта который неплохо объяснил Крокфорд (если эта ссылка у вас фиолетовая, то в парсерах вы наверно разбираетесь лучше меня и вам наверно было очень скучно читать всё это).

    Надеюсь кому нибудь это пригодится. В своё время я писал парсеры разной степени корявости и описанный выше способ был для меня открытием.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 53

      0
      Не совсем понял один момент. То, что вы называете «XML-подобным» текстом, есть самый что ни на есть обычный XML-документ. Какова была задача, что не было возможности воспользоваться встроенными средствами и пришлось реализовывать парсер самостоятельно?
        +4
        «XML-подобный» потому что в нём нет конструкций вроде <a:b ...>, нет xml entities, не учитываются теги вида <abc .../> и т.п. А задача была показать применение описанного метода на примере XML как хорошо известного формата. А на практике полезнее писать парсер для, скажем, заголовка WWW-Authenticate, но если бы я привёл пример такого парсера, то мало бы кто понял, что там вообще парсится.
        +4
        Если вам просто нужен парсер и нет желания упражняться в его написании, то лучше воспользоваться генератором. Тем более, что часто можно найти готовую грамматику. Ссылка на один из генераторов. Кстати, я им пользовался не совсем по прямому назначению. Обычно парсеры используют для чтения неких документов. У меня же было формализованное описание некого API, описав грамматику я получил сначала парсер для описания, а при помощи парсера получил генератор кода для работы с API.
          0
          Автоматические сгенерированные парсеры весьма объёмны. Так например упомянутый вами PEG показывает пример как из простейшей грамматики из 5-ти правил генерируется парсер на 400 строк. Если встроить такое в свой код (например в свою библиотеку) — не проблема, то наверно это и вправду рабочее решение. Генераторы парсеров имеют и другую проблему: однажды сгенерировав код парсера, поменять его сложно — нужно будет взять оригинальное описание грамматики, изменить её, применить оригинальный генератор и заменить сгенерированное. Оба этих ограничения наводят меня на мысль, что генераторы парсеров уместны на серверах Node.
            0
            Если в цикле развертывания есть этап компиляции (что довольно часто встречается для JS и не только для серверного), то генерация парсера из грамматики вообще не проблема. Считаем исходником грамматику и все.
              +3
              А по скорости не пробовали сравнить? Объём кода всё-таки не главное.
                +1
                Если скорость важнее всего, то генератор лучше. Если важнее объём кода — то генераторы не подойдут.
                +3
                Автоматические сгенерированные парсеры весьма объёмны.

                ваша статья тоже не маленькая. :) серьезно, классно, что вы так подробно объясняете причины выбора тех или иных решений и иллюстрируете суть простыми примерами реализации. практически, академичная статья. единственное, что на практике это использовать вряд-ли получится. для «промышленного» применения, при генерации js-парсеров, нужно учитывать еще ряд крайне важных «потребительских» характеристик, без которых, как говорят в народе, такая «простота хуже воровства».

                во-первых, парсер обязан генерировать адекватные сообщения об ошибках, с классификацией проблем и четкой локализацией мест и причин их возникновения. обычное дело, когда код, связанный с анализом ошибок во входных данных и выводом соответствующих сообщений, занимает в объеме больше, нежели собственно код парсинга, как такового. важность момента может быть не очевидной на начальных этапах, но опыт будет дорого стоить. например, можно вспомнить как из стека BEM, после нескольких человеко-лет вложений в разработку и внедрение, был выкинут пресловутый bemhtml, вместе с его умопомрачительным DSL.

                во вторых, парсер должен быть алгоритмически простым (в смысле «O») и быстрым. пусть char — парсит одну букву в строке. это универсально. но когда парсинг каждой буквы приводит к созданию объектов и вызову пачки методов, я сомневаюсь, что такая архитектура позволит достичь производительности сколь-нибудь выше плинтуса. именно поэтому «академические» реализации встречаются только в учебниках, а на практике грамматика компиляется в хитросплетенную, развесистую и только машине понятную «лапшу». это не прихоть. x4 в объеме кода приятнее, нежели x4 по потребляемой памяти или процессору.

                в третьих, нужна возможность парсить асинхронно. в js, вы очень быстро с этим столкнетесь, поскольку асинхронность очень распространена в js, а асинхронный код обладает «вирусным» эффектом (если на низком уровне появляется асинхронный код, то и весь высокоуровневый код должен быть асинхронным). ничего страшного, просто решение этой задачи усложняет решение двух предыдущих на порядок.
                  0
                  Вы пытаетесь применить моё решение для написания простых парсеров в рамках маленьких js библиотек размером в несколько тысяч строк для решения больших и сложных задач распарсивания очень сложных и больших текстов где важна производительность и сообщения об ошибках и потому неизбежно обнаруживаете указанные вами недостатки. Однако всё это верно лишь для больших и сложных парсеров.

                  Моя же цель была показать как можно распарсить что то простое малым количеством простого кода. Вот допустим вы пишете js библиотеку которая должна оставаться в рамках 5-6 тысяч строк и эта библиотека должна парсить что то небольшое из HTTP ответов, скажем те же WWW-Authenticate заголовки. Тут есть два варианта: написать парсер самому или использовать хороший генератор парсеров. Во втором случае вы получаете кучу сложностей в виде проблем с лицензионным соглашением (можно ли использовать тот генератор в рамках вашей библиотеки?), тысячми строк нечитаемого сгенерированного кода, невозможностью исправить этот код добавив что то новое в парсер (нужно ведь заново генерить весь парсер), и такие сомнительные плюсы как скорость (какая разница будет этот парсер работать за 1 мс или за 10 мс если HTTP запрос идёт 100 мс и возникает редко?) и хорошие сообщения об ошибках (их всё равно никто не будет читать в описанном случае). Самописный же парсер лишён этих недостатков (ибо занимает меньше 100 строчек), хотя и не обладает ненужной скоростью и ненужными сообщениями об ошибках.

                    0
                    > в третьих, нужна возможность парсить асинхронно
                    Очень интересно, как из синхронного решения вы планируете получить асинхронное. Очень крутая фраза :)

                    > можно вспомнить как из стека BEM, после нескольких человеко-лет вложений в разработку и внедрение, был выкинут пресловутый bemhtml
                    Оо, чего только не узнаешь. А bemhtml@2 наверное возник из ниоткуда? А bemtree?
                      0
                      Про асинхронность он наверно имел ввиду когда держится вторичный поток куда посылают запрос на парсинг чего нибудь большого, а потом в ответ получают распарсенное.
                  0
                  Есть еще JS/CC, но он мне не особенно понравился. Там генерируется множество таблиц переходов от чего код разбухает значительно. PEG понравился в разы больше и для разбора небольших простых правил самое оно.
                    0
                    Таблицы переходов? Это наверное LR парсер.
                  +1
                  Очень интересует тема грамматик, если на хабре впредь будут подобные посты, то я с интересом их буду читать.

                  У меня есть простой парсер, основанный на идее комбинаторов. На гитхабе, в виде npm-пакета: StreetStrider/str-reader. Если у кого-то есть интерес поревьюить/покритиковать, то это можно сделать (на гитхабе или здесь в лс).
                    +2
                    Я думал о том, чтобы написать генератор ассемблеро-подобных (очень быстрых, но нечитаемых, возможно с использованием «use asm») парсеров который бы парсил описание грамматики на ABNF/EBNF/PEG и выдавал ассемблеро-подобный код на JS — этакий компилятор ABNF, но пока ничего толкового не придумал. Как придумаю — напишу. Возможно придётся утащить пару идей у peg.js :)
                    +4
                    Использовал Jison. Шикарнейшая вещь.
                      0
                      Для не очень сложных грамматик (no-backtrack-PEG, соответственно это что-то вроде LL(1)), (и не в продакшене, если что) лично мне нравится вот эта штука: www.bayfronttechnologies.com/mc_workshop.html.
                        0
                        > Как писать парсеры на JavaScript
                        Не писать :)

                        То что у вас получилось, кстати, похоже на красивый синтаксический сахар для метода рекурсивного спуска.

                        Я похожий интерфейс в своё время пилил на Lua для packrat-парсера. Там получилось особенно хорошо, потому что в Lua можно не писать скобки при вызове функции с литералом в качестве параметра, из-за чего код получается примерно таким:
                        local digit = peg.R"09"
                        


                        Полный код примера использования:
                        --- калькулятор
                        local function accum(u,op,v)
                            if op=="+" then return u+v
                            elseif op=="-" then return u-v
                            elseif op=="*" then return u*v
                            elseif op=="/" then return u/v
                            end
                        end
                        
                        local space = peg.S" \n\t":star()
                        local digit = peg.R"09"
                        local sign = peg.S"+-"
                        local unsigned = digit:plus()
                        local number = (sign^{0,1}*unsigned*("."*unsigned)^{0,1}):C()/tonumber*space
                        local Open = "(" * space
                        local Close = ")" * space
                        local mulop = peg.S"/*":C() * space
                        local sumop = peg.S"-+":C() * space
                        
                        -- необходимо сделать Fake(), т.к. тут рекурсия value -> sum -> mul -> value
                        -- реальная формула для value доопределяется тремя строками ниже
                        local value = peg.Fake()
                        local mul = (value * (mulop*value):Cg():star()):Cf(accum)
                        local sum = (mul * (sumop*mul):Cg():star()):Cf(accum)
                        
                        value:define(number + Open*sum*Close)
                        
                        local expression = sum * peg.eof
                        
                        --print(expression"3 + 5*9 / (1+1) - 12 + 0.012")
                        
                        print(expression(io.read()))
                        
                          0
                          То что у вас получилось, кстати, похоже на красивый синтаксический сахар для метода рекурсивного спуска.


                          Так и есть. Эту статью можно было бы назвать «как написать парсер для XML/dataURL/… и уложиться в 100 строк,» что весьма актуально для либ запускаемых в браузере где размер имеет значение. Во всех остальных случаях лучше наверно будет держать описание грамматики в отдельном файле и во время билда автоматически генерить парсер известной и проверенной тулзой. Впрочем даже здесь есть исключения — GCC вон перешёл на самопальный парсер и уж их то уличить в незнании основ парсинга точно нельзя.
                          0
                          Не OMeta ли то, что вы описываете?
                            0
                            Не, мой парсер самопальный :)
                            +1
                            Уж слишком часто встречается фраза «Если бы в JS была перегрузка операторов» — fake-operator-overloading
                              0
                              Любопытный трюк, но как там сами пишут — в продакшене лучше не использовать из за обилия хаков.
                                0
                                Спасибо за ссылку =) Очень интересная статья =)
                                0
                                Я JS только учусь и статья сложная для меня, поэтому прошу объяснить, кому несложно: чем вышенаписанная простыня лучше DOMParser, который справляется с XML и HTML?
                                  –3
                                  Ответ на вопрос. Если стоит вопрос почему стоит писать парсеры? То любой инструмент вроде Bem, Jade, React.JS, Emmet не обходится без парсинга. Поэтому парсить надо уметь, чтобы при случае применить свое знание.
                                  Впрочем, все стоит помнить простое правило: Пользуйтесь уже проверенными, готовыми, покрытых тестами парсерами.
                                    0
                                    DOMParser лучше для XML. Самопальные парсеры хороши только когда надо распарсить что то очень необычное.
                                      0
                                      Хотя и тут есть подводный камень: DOMParser не поддерживается в IE 8.
                                        0
                                        Ну для необычного я использую RegExp. Мне кажется оно проще.
                                        Ну да ладно, я просто до этого не дорос. Не буду больше лезть во взрослую песочницу )

                                        Спасибо!
                                          0
                                          Для совсем простых текстов сойдёт и RegExp. Так, например, чтобы распарсить URI на составляющие его части (scheme, user, host, port, path, query, hash) достаточно регулярки. Но что то с повторяющимися структурами (например Data URL) уже не выйдет распарсить регуляркой. Попробуйте написать регулярку для data URL вида:

                                          data:text/plain;charset=«utf-8»;sometag=123;anothertag=abc,qwerty

                                          Хочется написать что то такое:

                                          ^data:(\w+/\w+)(;\w+=\w+)*,.*$

                                          Однако вы обнаружите, что (;\w+=\w+)* запоминает лишь последний атрибут вида abc=def, а вовсе не массив атрибутов, как хотелось бы. И эта проблема нерешаема в RegExp. В таких случаях нужен парсер.

                                          Ещё один типичный случай это когда надо распарсить XML-подобную стркутуру где есть вложенные самоподобные структуры. Скажем как распарсить вот такое выражение со скобками:

                                          (1, 2, (4, 5, (6), 7, (8), 9), 0)

                                          Регулярки здесь не помогут, а вот LL парсер с этим легко справится.
                                            0
                                            Ясно. Спасибо!
                                              +1
                                              Регулярки здесь не помогут
                                              Ну, это смотря какие регулярки! Не знаю что умеет RegExp на Javascript, а на Perl это делается например так:
                                              use Data::Dumper;
                                              "(1, 2, (4, 5, (6), 7, (8), 9), 0)" =~ 
                                                /(?{@s=();$r=[]})(\((?{local @s=(@s,$r);local $r=[];push @{$s[-1]},$r})(?:(\d), (?{push $r,$^N})|(?1), )*(\d)(?{push $r,$^N;$r=pop @s})\))/ms;
                                              print Dumper @{$r};
                                              
                                              результат:
                                              $VAR1 = [
                                                        '1',
                                                        '2',
                                                        [
                                                          '4',
                                                          '5',
                                                          [
                                                            '6'
                                                          ],
                                                          '7',
                                                          [
                                                            '8'
                                                          ],
                                                          '9'
                                                        ],
                                                        '0'
                                                      ];
                                              
                                              При желании это регулярное выражение можно записать более читабельно:
                                              "(1, 2, (4, 5, (6), 7, (8), 9), 0)" =~ /
                                                  (?{ @s=(); $r=[]; })
                                                  (
                                                      \(  (?{
                                                          local @s = (@s, $r);
                                                          local $r = [];
                                                          push $s[-1], $r;
                                                          })
                                                      (?:
                                                          (\d),\s     (?{ push $r, $^N })
                                                        | (?1),\s
                                                      )*
                                                      (\d)    (?{ push $r, $^N })
                                                      \)      (?{ $r = pop @s })
                                                  )
                                                  /xms;
                                              

                                                +3
                                                Это не регулярка, а смесь перла и регулярок. Впрочем топик не о перле, а о JS и там такое сделать не получится.
                                                  0
                                                  Да нет, должно получиться, только синтаксис немного другой, вообще в JS regexp перлоподобный.
                                                  Тут другой вопрос, что стоило бы подсчитать, как правильно кто-то упомянул выше, что эффективнее по скорости, т.к. некоторые regexp очень нагружают процессор при неправильном использовании.
                                                    0
                                                    Буду очень удивлён если обнаружится, что в JS можно делать что то подобное., а с этим JS я уже лет десять знаком. По сравнению с методом парсинга который я описал любая регулярка работает за пренебрежимо малое время.

                                                    Про то что некоторые регулярки нагружают процессор хорошо написано тут: swtch.com/~rsc/regexp/regexp1.html Но это проблема не регулярок, а их реализации, причём в перле, как отмечает автор указанной статьи, они (были) реализованы как раз медленно.
                                                0
                                                И эта проблема нерешаема в RegExp. В таких случаях нужен парсер.

                                                Одна регулярка не поможет. А две — вполне.
                                                  0
                                                  Думаю, что даже двух не хватит. Атрибуты могут быть вида charset=«utf-8» и в кавычках могут быть запятые, знаки равенства, точки с запятой и прочие неприятные штуки. Регулярки будут очень запутанными и кода будет в разs больше чем в случае аналогичного LL парсера.
                                          0
                                          Если бы в JS были конструкторы-по-умолчанию (как в C++), то запись txt(«abc») можно было бы сократить до «abc» в контексте конструирования более сложного паттерна.


                                          А что мешает опционально расширять прототип String/RegExp etc? Раз уж извращаться, то по полной ;)
                                          Например:
                                            String.prototype.parse = function (str, pos) {
                                                  if (str.substr(pos, this.length) == this)
                                                      return { res: this, end: pos + this.length };
                                            };
                                            RegExp.prototype.parse = function(str, pos) {
                                                  var m = this.exec(str.substr(pos));
                                                  if (m && m.index === pos)
                                                      return { res: m[0], end: pos + m[0].length };
                                            };
                                          
                                            assert.deepEqual("abc".parse("abc", 0), { res: "abc", end: 3 });
                                            assert.deepEqual(/\d+/.parse("123", 0), { res: "123", end: 3 });
                                          
                                            0
                                            Такой способ не позволит комбинировать парсеры и получать более сложные парсеры. Например из «abc» и /\d+/ я могу получить rep(rgx(/\d+/), txt(«abc»)) — парсер который распознаёт чередование «abc» и цифр. Если же у меня есть методы parse которые вы написали, то они никак не помогут сконструировать аналог этого rep.
                                              0
                                              Почему же? Просто вместо exec везде используйте parse (или другой метод, так как exec занят у RegExp).
                                                0
                                                А, я понял. Вы хотите переименовать exec в parse и вмонтировать этот parse прямо в String и RegExp чтобы они стали очень похожи на Pattern. У этого подхода есть небольшая проблема. Что если я захочу иметь два режима работы parse/exec:

                                                p.exec(str, pos) возвращает (res, end)
                                                p.exec(str) возвращает (res) и полагает, что pos = 0, а также проверяет что end = str.length

                                                Если exec/parse вмонтирован в String и RegExp, то придётся дописать этот второй режим к каждому.
                                                  0
                                                  Да, верно, это я и предлагал :)
                                                  Описанная проблема тоже решаема, можно сделать фабрику parse, как то так:
                                                  var createParse = function(fn){
                                                    return function(str, pos){
                                                      if (arguments.length == 1)
                                                        pos = 0;
                                                      var res = fn.call(this, str, pos);
                                                      if (res && arguments.length == 1)
                                                          res = res.res.length == res.end ? res.res : undefined;
                                                      return res;
                                                    };
                                                  };
                                                  
                                                  String.prototype.parse = createParse(function (str, pos) {
                                                          if (str.substr(pos, this.length) == this)
                                                              return { res: this, end: pos + this.length };
                                                  });
                                                  
                                                    0
                                                    Ух ты ж ё моё. Вы знаете толк. Ладно, поставил плюс :) Вообщем parse и вправду помогает решить проблему, но решение какое то чрезмерно хитрое.
                                            0
                                            Интересная статья, интересные комментарии. Спасибо!
                                              0
                                              Кстати, можно использовать существующие инструменты для создания парсеров, например JavaCC, и скомпилировать полученный Java код в JavaScript с помощью GWT. Последние версии JavaCC поддерживают компиляцию себя в JavaScript.
                                                0
                                                Так, и сколько места будет занимать этот сгенерированный парсер? Хотя бы 10к строк поместится? :) Такой парсер будет в разы больше всего остального кода (я рассматриваю случай браузерного js кода).
                                                  0
                                                  ну от 40Кбайт будет занимать конечно. Это цена за все навороты JavaCC.
                                                0
                                                regexp.exec(str.slice(pos))
                                                

                                                а в данном случае не произойдет копирование части строки?
                                                в принципе строки менять нельзя, так что теоретически возможна работа slice без копирования…
                                                  0
                                                  а за чем вы делаете так
                                                  var char = rgx(/[^"&]/i);
                                                  rep(char).then(r => r.join(''))
                                                  

                                                  а не так
                                                  rgx(/^[^"&]*/i)
                                                  

                                                  ?

                                                  И еще надо не забывать регекспы начинать писать с ^

                                                  спасибо за статью, метод then очень понравился
                                                    0
                                                    Можно было ужать до одной строчки. Скорее всего я просто хотел записать это ABNF-подобным способом где обычно есть отдельное правило «char».
                                                    0
                                                    <book attr1="..." attr2="..." очень много атрибутов ???
                                                    

                                                    То в том месте где стоит ??? может оказаться как /> так и просто >. Теперь если LL парсер пытался всё это распарсить как <book ...> а на месте ??? оказался />, то парсер отбросит всё то что он так долго парсил и начнёт заново в предположении, что это <book .../>
                                                    В этом случае можно парсить в 2 прохода: на первом генерировать массив токенов, которыми будут текст и теги (открывающий, закрывающий, самозакрывающийся), а на втором строить дерево.
                                                    При чем на втором проходе можно применять те же Pattern, opt, exc, any, seq, rep, изменятся только терминальные методы
                                                      0
                                                      Действительно. Однако в этом случае все эти opt/exc/any надо будет переписать в обобщённом виде.
                                                      0
                                                      Может кому-то пригодится. Сделал на основе идей из этой статьи библиотеку парсер-комбинаторов: nano parser. В ней есть возможность кеширования и парсинга масива строк (что актуально для использования с шаблонными литералами из ES 2015)
                                                      Успешно применил библиотеку для создания строкового jsx: es6x

                                                      Only users with full accounts can post comments. Log in, please.