xff.cz - mapa webu - novinky

Generátor parserů pro JavaScript

Občas se hodí vytvořit si specializovaný jazyk (DSL) pro popis nějakého problému či procesu. Sice je tato potřeba v dynamických jazycích jako je JavaScript menší, než např. v jazyce C, ale i tak se to může občas hodit.

Problém tvorby DSL pro JS je v nepohodlnos­ti použití generátorů parserů. Je třeba se nejprve naučit jazyk pro zápis definice lexeru, pak parseru a kód parseru je třeba předem vygenerovat a začlenit do aplikace. Navíc vzniká závislost na nástrojích třetích stran.

Jak to tedy zjednodušit? Co není potřeba:

Myšlenka je maximálně využít vlastností JavaScriptu a nesnažit se vymýšlet věci navíc.

Princip fungování

Parsovací funkce je rozdělená na dvě části. Ta první, lexikální analýza, rozdělí vstupní řetězec na lexikální jednotky – tokeny. Ta druhá na základě seznamu syntaktických pravidel jazyka zpracuje pole tokenů vrácených první funkcí a pokusí se najít ve vstupu strukturu popsanou pravidly syntaxe.

Předpokládám, že již máte zkušenosti s tvorbou podobných parserů, naříklad za pomoci nástrojů typu lemon.

Příklad použití

Například parser pro výpočet matematických výrazů by vypadal takto:

var calc = parser([{
        match: /\s+/
}, {
        literals: ['(', ')', '+', '-', '/', '*']
}, {
        name: 'Int',
        match: /\d+/
}, {
        name: 'Id',
        match: /[a-zA-Z_][a-zA-Z0-9_]*/
}], {
        primary: [{
                match: ['Id'],
                action: function(r) {
                        return r[0];
                }
        }, {
                match: ['Int'],
                action: function(r) {
                        return Number(r[0]);
                }
        }, {
                match: ['(', 'expr', ')'],
                action: function(r) {
                        return r[1];
                }
        }],
        expr_mult: [{
                match: ['primary', '*', 'expr_mult'],
                action: function(r) {
                        return r[0] * r[2];
                }
        }, {
                match: ['primary', '/', 'expr_mult'],
                action: function(r) {
                        return r[0] / r[2];
                }
        }, {
                match: ['primary'],
                action: function(r) {
                        return r[0];
                }
        }],
        expr_add: [{
                match: ['expr_mult', '+', 'expr_add'],
                action: function(r) {
                        return r[0] + r[2];
                }
        }, {
                match: ['expr_mult', '-', 'expr_add'],
                action: function(r) {
                        return r[0] - r[2];
                }
        }, {
                match: ['expr_mult'],
                action: function(r) {
                        return r[0];
                }
        }],
        expr: [{
                match: ['expr_add'],
                action: function(r) {
                        return r[0];
                }
        }],
        start: [{
                match: ['expr'],
                action: function(r) {
                        return r[0];
                }
        }]
});

Zdrojový kód samotného generátoru parserů

function parser(termsDef, nonTermsDef) {
        var re = new RegExp(termsDef.map(function(d) {
                if (d.literals) {
                        return '(' + d.literals.map(function(l) {
                                return l.replace(/[|()\[\]{}.+*?^$\\\/-]/g, "\\$&");
                        }).join('|') + ')';
                } else if (d.match) {
                        return '(' + d.match.source + ')';
                } else {
                        throw new Error('Missing match or literals in token definition');
                }
        }).join('|') + '|[^]', 'g');

        function lex(input) {
                var tokens = [], m, pos = 0, i, found, d;

                re.lastIndex = 0;
                while ((m = re.exec(input)) !== null) {
                        found = false;
                        for (i = 1; i <= termsDef.length; i++) {
                                d = termsDef[i - 1];
                                if (typeof m[i] != 'undefined') {
                                        if (d.name) {
                                                tokens.push([d.name, m[i], pos]);
                                        } else if (d.literals) {
                                                tokens.push([m[i], m[i], pos]);
                                        }

                                        found = true;
                                        break;
                                }
                        }

                        if (!found) {
                                throw new Error('Unknown token detected at offset ' +
                                        pos + ': ' + input.substr(pos, 1));
                        }

                        pos = re.lastIndex;
                }

                tokens.push(['EOF', 'EOF', input.length]);

                return tokens;
        }

        return function(input) {
                var tokens = lex(input);
                var lastTried = -1, lastExpected;

                function eatNonTerminal(pos, nt) {
                        var defs = nonTermsDef[nt], i, j, match, def, capture, prevCapture, res;

                        if (pos > lastTried) {
                                lastTried = pos;
                                lastExpected = nt;
                        }

                        for (i = 0; i < defs.length; i++) {
                                def = defs[i];
                                prevCapture = capture;
                                capture = [];
                                capture.pos = pos;
                                capture.size = 0;
                                capture.def = def;
                                capture.name = nt;

                                for (j = 0; j < def.match.length; j++) {
                                        match = def.match[j];

                                        if (nonTermsDef[match]) {
                                                if (prevCapture && prevCapture[j] &&
                                                        prevCapture[j].name == match) {
                                                        res = prevCapture[j];
                                                } else {
                                                        res = eatNonTerminal(pos +
                                                                capture.size, match);
                                                }

                                                if (res) {
                                                        capture.push(res);
                                                        capture.size += res.size;
                                                } else {
                                                        break;
                                                }
                                        } else {
                                                if (tokens[pos + capture.size] &&
                                                        match == tokens[pos + capture.size][0]) {
                                                        capture.push(tokens[pos + capture.size]);
                                                        capture.size++;
                                                } else {
                                                        break;
                                                }
                                        }
                                }

                                if (capture.length == def.match.length) {
                                        return capture;
                                }
                        }
                }

                function invokeAction(capture) {
                        var i, res = [];

                        for (i = 0; i < capture.length; i++) {
                                res.push(capture[i].def ? invokeAction(capture[i]) : capture[i][1]);
                        }

                        return capture.def.action(res);
                }

                var captureStart = eatNonTerminal(0, 'start');

                if (!captureStart || captureStart.size < tokens.length - 1) {
                        var expectations = nonTermsDef[lastExpected].map(nt => '"' +
                                (nt.match[0] || '') + '"').reduce(function(l, name) {
                                return l.indexOf(name) >= 0 ? l : l.concat([name]);
                        }, []);

                        throw new Error('Parsing failed near offset ' + tokens[lastTried][2] +
                                ', expecting ' + expectations.join(' or ') + ', got: "' +
                                input.substr(tokens[lastTried][2], 50) + '"');
                }

                return invokeAction(captureStart);
        };
}

Licence AGPL v3

Copyright © 2017 xff.cz authors <=@xff.cz>

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABI­LITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.

Click here for the complete Affero GPL license text.

Historie změn

15.7.2018 18:17První sestavení webu