Информация об изменениях

Сообщение Re[19]: Простой скрипт внутри приложения (в виде строки) от 29.11.2021 10:56

Изменено 29.11.2021 11:02 Pauel

Старый текст
Новый текст
Разница

Re[19]: Простой скрипт внутри приложения (в виде строки)

Здравствуйте, Sinclair, Вы писали:

S>Не знаю, будет ли парсер, основанный на Пратте, более простым.

На счет простоты есть сомнения. Я взял готовый парсер, доработал выбрасывая лишнее и потратил треть от времени на recursive descent, который делал честно с нуля.
Т.е. мне не пришлось тратить время на вещи вида "а как реализовать это правило", "а как надо парсить вот такое", "нужен префикс или инфикс" и тд — собтсвенно самое сложное я взял готовым. Сам алгоритм Пратта на этом фоне можно даже никак не учитывать.
При этом кода вышло чуть больше, чем в recursive descent.
Подозреваю, если вдруг решу сделать такое полностью с нуля, времени уйдет намного больше. В бнф грамматике всё дадено, что и как парсить, а т

Парсер по методу Пратта

Парсер:

function make_parse() {
    let symbol_table = {};
    let currentToken;
    let tokens;
    let token_nr;

    let itself = function () {
        return this;
    };

    let advance = function (id) {
        let type, o, token, value;
        if (id && currentToken.id !== id) {
            currentToken.error(`Expected ${id}`);
        }
        if (token_nr >= tokens.length) {
            currentToken = symbol_table['(end)'];
            return;
        }
        token = tokens[token_nr];
        token_nr += 1;
        value = token.value;
        type = token.type;
        if (type === 'name') {
            o = symbol_table['(name)'];
            type = 'variable';
        } else if (type === 'operator' || type === 'group') {
            o = symbol_table[value];
            if (!o) {
                token.error('Unknown operator.');
            }
        } else if (type ===  'number') {
            o = symbol_table['(literal)'];
            type = 'literal';
        } else {
            token.error('Unexpected token.');
        }
        currentToken = Object.create(o);
        currentToken.type = type;
        // currentToken.line_nr  = token.line_nr;
        // currentToken.column_nr = token.column_nr;
        currentToken.value = value;
        return currentToken;
    };

    let expression = function (rbp) {
        let left;
        let t = currentToken;
        advance();
        left = t.nud();
        while (rbp < currentToken.lbp) {
            t = currentToken;
            advance();
            left = t.led(left);
        }
        return left;
    };

    let original_symbol = {
        nud: function () {
            this.error('Undefined.');
        },
        led: function (left) {
            this.error('Missing operator.');
        }
    };

    let symbol = function (id, bp) {
        let s = symbol_table[id];
        bp = bp || 0;
        if (s) {
            if (bp >= s.lbp) {
                s.lbp = bp;
            }
        } else {
            s = Object.create(original_symbol);
            s.id = s.value = id;
            s.lbp = bp;
            symbol_table[id] = s;
        }
        return s;
    };

    let infix = function (id, bp, led) {
        let s = symbol(id, bp);
        s.led = led || function (left) {
            this.first = left;
            this.second = expression(bp);
            this.type = 'binary';
            return this;
        };
        return s;
    };

    let prefix = function (id, nud) {
        let s = symbol(id);
        s.nud = nud || function () {
            this.first = expression(70);
            this.type = 'unary';
            return this;
        };
        return s;
    };

    symbol('(end)');
    symbol('(name)').nud = itself;
    symbol(')');
    symbol('(literal)').nud = itself;

    infix('+', 50);
    infix('-', 50);

    infix('*', 60);
    infix('/', 60);
    infix('%', 60);

    infix('^', 70);

    prefix('-');
    prefix('(', function () {
        let e = expression(0);
        advance(')');
        return e;
    });

    return function (array_of_tokens) {
        tokens = array_of_tokens;
        token_nr = 0;
        advance();
        let e = expression(0);
        advance('(end)');

        return e;
    };
}

module.exports = {make_parse};

Токенизатор:

const rx_crlf = /\n|\r\n?/;

function tokenize(source) {
    const lines = (Array.isArray(source))
        ? source
        : source.split(rx_crlf);
    const result = [];

    lines.forEach(function (line, line_nr) {
        const rx_token = /(\u0020+)|([a-zA-Z][a-zA-Z_0-9]*)|(\d+(?:\.\d+)?(?:[eE][+\-]?\d+)?)|(\(|\))|([\+\-\/*\%\^])/y;

// Capture Group
// [1]  Whitespace
// [2]  Name
// [3]  Number
// [4]  Punctuator

        let column_nr = 0;
        let make = function (type, value) {

// Make a token object and append it to the result.

            result.push({
                type,
                value,
                line_nr,
                column_nr
            });
        };

        while (column_nr < line.length) {
            let captives = rx_token.exec(line);
            if (!captives) {
                throw new SyntaxError(
                    "line "
                    + line_nr
                    + " column "
                    + column_nr
                );
            } else if (captives[1]) {
                // ignore
            } else if (captives[2]) {
                make("name", captives[2]);
            } else if (captives[3]) {
                make("number", captives[3]);
            } else if (captives[4]) {
                make("group", captives[4]);
            } else if (captives[5]) {
                make("operator", captives[5]);
            }
            column_nr = rx_token.lastIndex;
        }
    });
    return result;
}

module.exports = {tokenize};

const {tokenize} = require('./tokenize');
const {make_parse} = require('./pratt');
const parse = make_parse();

const tokens = tokenize('2 * (-2.9*k - 8)');
const x = parse(tokens);

console.log(JSON.stringify(x, null, 2));

Вот хороший пример — по фрагменту кода догадаться, это что именно оно парсит

infix("(", 80, function (left) {
        let a = [];
        if (left.id === "." || left.id === "[") {
            this.arity = "ternary";
            this.first = left.first;
            this.second = left.second;
            this.third = a;
        } else {
            this.arity = "binary";
            this.first = left;
            this.second = a;
            if ((left.arity !== "unary" || left.id !== "function") &&
                    left.arity !== "name" && left.id !== "(" &&
                    left.id !== "&&" && left.id !== "||" && left.id !== "?") {
                left.error("Expected a variable name.");
            }
        }
        if (token.id !== ")") {
            while (true) {
                a.push(expression(0));
                if (token.id !== ",") {
                    break;
                }
                advance(",");
            }
        }
        advance(")");
        return this;
    });

Re[19]: Простой скрипт внутри приложения (в виде строки)

Парсер по методу Пратта

Парсер:

function make_parse() {
    let symbol_table = {};
    let currentToken;
    let tokens;
    let token_nr;

    let itself = function () {
        return this;
    };

    let advance = function (id) {
        let type, o, token, value;
        if (id && currentToken.id !== id) {
            currentToken.error(`Expected ${id}`);
        }
        if (token_nr >= tokens.length) {
            currentToken = symbol_table['(end)'];
            return;
        }
        token = tokens[token_nr];
        token_nr += 1;
        value = token.value;
        type = token.type;
        if (type === 'name') {
            o = symbol_table['(name)'];
            type = 'variable';
        } else if (type === 'operator' || type === 'group') {
            o = symbol_table[value];
            if (!o) {
                token.error('Unknown operator.');
            }
        } else if (type ===  'number') {
            o = symbol_table['(literal)'];
            type = 'literal';
        } else {
            token.error('Unexpected token.');
        }
        currentToken = Object.create(o);
        currentToken.type = type;
        // currentToken.line_nr  = token.line_nr;
        // currentToken.column_nr = token.column_nr;
        currentToken.value = value;
        return currentToken;
    };

    let expression = function (rbp) {
        let left;
        let t = currentToken;
        advance();
        left = t.nud();
        while (rbp < currentToken.lbp) {
            t = currentToken;
            advance();
            left = t.led(left);
        }
        return left;
    };

    let original_symbol = {
        nud: function () {
            this.error('Undefined.');
        },
        led: function (left) {
            this.error('Missing operator.');
        }
    };

    let symbol = function (id, bp) {
        let s = symbol_table[id];
        bp = bp || 0;
        if (s) {
            if (bp >= s.lbp) {
                s.lbp = bp;
            }
        } else {
            s = Object.create(original_symbol);
            s.id = s.value = id;
            s.lbp = bp;
            symbol_table[id] = s;
        }
        return s;
    };

    let infix = function (id, bp, led) {
        let s = symbol(id, bp);
        s.led = led || function (left) {
            this.first = left;
            this.second = expression(bp);
            this.type = 'binary';
            return this;
        };
        return s;
    };

    let prefix = function (id, nud) {
        let s = symbol(id);
        s.nud = nud || function () {
            this.first = expression(70);
            this.type = 'unary';
            return this;
        };
        return s;
    };

    symbol('(end)');
    symbol('(name)').nud = itself;
    symbol(')');
    symbol('(literal)').nud = itself;

    infix('+', 50);
    infix('-', 50);

    infix('*', 60);
    infix('/', 60);
    infix('%', 60);

    infix('^', 70);

    prefix('-');
    prefix('(', function () {
        let e = expression(0);
        advance(')');
        return e;
    });

    return function (array_of_tokens) {
        tokens = array_of_tokens;
        token_nr = 0;
        advance();
        let e = expression(0);
        advance('(end)');

        return e;
    };
}

module.exports = {make_parse};

Токенизатор:

const rx_crlf = /\n|\r\n?/;

function tokenize(source) {
    const lines = (Array.isArray(source))
        ? source
        : source.split(rx_crlf);
    const result = [];

    lines.forEach(function (line, line_nr) {
        const rx_token = /(\u0020+)|([a-zA-Z][a-zA-Z_0-9]*)|(\d+(?:\.\d+)?(?:[eE][+\-]?\d+)?)|(\(|\))|([\+\-\/*\%\^])/y;

// Capture Group
// [1]  Whitespace
// [2]  Name
// [3]  Number
// [4]  Punctuator

        let column_nr = 0;
        let make = function (type, value) {

// Make a token object and append it to the result.

            result.push({
                type,
                value,
                line_nr,
                column_nr
            });
        };

        while (column_nr < line.length) {
            let captives = rx_token.exec(line);
            if (!captives) {
                throw new SyntaxError(
                    "line "
                    + line_nr
                    + " column "
                    + column_nr
                );
            } else if (captives[1]) {
                // ignore
            } else if (captives[2]) {
                make("name", captives[2]);
            } else if (captives[3]) {
                make("number", captives[3]);
            } else if (captives[4]) {
                make("group", captives[4]);
            } else if (captives[5]) {
                make("operator", captives[5]);
            }
            column_nr = rx_token.lastIndex;
        }
    });
    return result;
}

module.exports = {tokenize};

const {tokenize} = require('./tokenize');
const {make_parse} = require('./pratt');
const parse = make_parse();

const tokens = tokenize('2 * (-2.9*k - 8)');
const x = parse(tokens);

console.log(JSON.stringify(x, null, 2));

Вот хороший пример — по фрагменту кода догадаться, что же именно оно парсит

infix("(", 80, function (left) {
        let a = [];
        if (left.id === "." || left.id === "[") {
            this.arity = "ternary";
            this.first = left.first;
            this.second = left.second;
            this.third = a;
        } else {
            this.arity = "binary";
            this.first = left;
            this.second = a;
            if ((left.arity !== "unary" || left.id !== "function") &&
                    left.arity !== "name" && left.id !== "(" &&
                    left.id !== "&&" && left.id !== "||" && left.id !== "?") {
                left.error("Expected a variable name.");
            }
        }
        if (token.id !== ")") {
            while (true) {
                a.push(expression(0));
                if (token.id !== ",") {
                    break;
                }
                advance(",");
            }
        }
        advance(")");
        return this;
    });