Wizard Parser, v4.4

LL(*)-парсер на C++ с поддержкой DSL для описания грамматики в EBNF непосредственно в коде программы.

Small refactoring of the general code and significantly reducing and simplifying of the example.

Change Log

• Rename types:
  • lexer::exception_group:
    • rename it to type_group;
    • update the example;
  • parser::optional_offset:
    • rename it to offset_optional.
• In the parser module:
  • Add the list parser:
    • implement it;
    • cover it with tests;
    • use it in the example.
  • Remove the empty_parser class:
    • remove it;
    • remove its tests.
  • Unifying header for all parsers:
    • implement it;
    • use it in the example.
  • In the tests:
    • Improve tests:
      • of the repetition_parser class;
      • of the parse() function;
      • of the parse_all() function.
    • Refactor tests:
      • of the repetition_parser class;
      • of the parse_all() function.
• In the transformers module:
  • Add the default_ast_node_handlers constant:
    • implement it;
    • use it:
      • in the parser::parse() function;
      • in the parser::parse_all() function.
  • Add the transform() function for few handlers:
    • implement it;
    • cover it with tests;
    • use it in the parser::parse() function.
• In the example:
  • Refactor:
    • reduce a list of included headers;
    • remove types:
      • constant_group;
      • function_group;
    • lexemes:
      • fix a code style;
    • built-in functions:
      • use the std::fmod() function for computing a division remainder;
      • fix a code style;
      • fix the explanatory comment;
    • evaluate_ast_node() function:
      • make some functions local for it:
        • inspect_sequence() function;
      • fix a code style;
    • main() function:
      • make some functions local for it:
        • stop() function;
        • enrich_exception() function;
      • fix a code style.
  • Extend tests of errors:
    • check unexpected entities:
      • constants;
      • functions;
    • split tests to short and verbose:
      • mark existing tests as a short version;
      • add a verbose version of tests.

Возможности

• лексинг ASCII-текста:
  • задание лексем посредством регулярных выражений;
  • возможность исключения токенов из результирующего списка;
• парсинг ASCII-текста:
  • описание грамматики на EBNF непосредственно в коде программы (посредством DSL);
• результат:
  • представление в виде:
    • CST;
    • AST;
  • задание имени ноды в дереве;
• парсеры:
  • терминальные:
    • определённые:
      • текст;
      • лексема;
  • комбинаторы:
    • альтернатива (упорядоченная);
    • объединяющие:
      • следование;
      • повторение:
        • 0 или 1 раз (опциональность);
        • 0 или больше раз;
        • 1 или больше раз;
        • любое число раз в указанном диапазоне;
      • список с разделителем;
    • проверяющие:
      • исключение;
      • просмотр вперёд:
        • позитивный;
        • негативный.

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

#define THEWIZARDPLUSPLUS_WIZARD_PARSER_PARSER_MACROSES

#include "vendor/better-enums/enum_strict.hpp"
#include "vendor/docopt/docopt.hpp"
#include "vendor/fmt/format.hpp"
#include "vendor/range/v3/all.hpp"

#include <thewizardplusplus/wizard_parser/exceptions/unexpected_entity_exception.hpp>
#include <thewizardplusplus/wizard_parser/lexer/tokenize.hpp>
#include <thewizardplusplus/wizard_parser/parser/parse.hpp>
#include <thewizardplusplus/wizard_parser/parser/parsers.hpp>

#include <iomanip>
#include <iostream>

using namespace thewizardplusplus::wizard_parser;
using namespace thewizardplusplus::wizard_parser::parser::operators;
using namespace std::literals::string_literals;

struct function final {
    const std::size_t arity;
    const std::function<double(const std::vector<double>&)> handler;
};

BETTER_ENUM(entity_type, std::uint8_t,
    node = exceptions::entity_type::_size(),
    constant,
    function
)

template<entity_type::_integral type>
using unexpected_entity_exception =
    exceptions::base_unexpected_entity_exception<entity_type, type>;

const auto usage =
R"(Usage:
  ./example [options] [--] [<expression>]

Options:
  -h, --help                           - show this message;
  -t TARGET, --target TARGET           - preliminary target of processing
                                       (allowed: tokens, cst);
  -p PRECISION, --precision PRECISION  - precision of a result;
  -s, --stdin                          - read an expression from stdin;
  -V, --verbose                        - mark an error.)";
const auto lexemes = lexer::lexeme_group{
    {std::regex{R"(\+)"}, "plus"},
    {std::regex{R"(-)"}, "minus"},
    {std::regex{R"(\*)"}, "star"},
    {std::regex{R"(/)"}, "slash"},
    {std::regex{R"(%)"}, "percent"},
    {std::regex{R"(\()"}, "opening_parenthesis"},
    {std::regex{R"(\))"}, "closing_parenthesis"},
    {std::regex{R"(,)"}, "comma"},
    {std::regex{R"(\d+(\.\d+)?(e-?\d+)?)"}, "number"},
    {std::regex{R"([A-Za-z_]\w*)"}, "identifier"},
    {std::regex{R"(\s+)"}, "whitespace"}
};
const auto lexemes_exceptions = lexer::type_group{"whitespace"};
// precision is taken from Boost 1.70.0, Math Toolkit 2.9.0
const auto constants = std::unordered_map<std::string, double>{
    {"pi", 3.141592653589793238462643383279502884},
    {"e", 2.718281828459045235360287471352662497}
};
const auto functions = std::unordered_map<std::string, function>{
    {"+", {2, [] (const auto& args) { return args[0] + args[1]; }}},
    {"-", {2, [] (const auto& args) { return args[0] - args[1]; }}},
    {"*", {2, [] (const auto& args) { return args[0] * args[1]; }}},
    {"/", {2, [] (const auto& args) { return args[0] / args[1]; }}},
    {"%", {2, [] (const auto& args) { return std::fmod(args[0], args[1]); }}},
    {"floor", {1, [] (const auto& args) { return std::floor(args[0]); }}},
    {"ceil", {1, [] (const auto& args) { return std::ceil(args[0]); }}},
    {"trunc", {1, [] (const auto& args) { return std::trunc(args[0]); }}},
    {"round", {1, [] (const auto& args) { return std::round(args[0]); }}},
    {"sin", {1, [] (const auto& args) { return std::sin(args[0]); }}},
    {"cos", {1, [] (const auto& args) { return std::cos(args[0]); }}},
    {"tn", {1, [] (const auto& args) { return std::tan(args[0]); }}},
    {"arcsin", {1, [] (const auto& args) { return std::asin(args[0]); }}},
    {"arccos", {1, [] (const auto& args) { return std::acos(args[0]); }}},
    {"arctn", {1, [] (const auto& args) { return std::atan(args[0]); }}},
    {"angle", {2, [] (const auto& args) { return std::atan2(args[1], args[0]); }}},
    {"pow", {2, [] (const auto& args) { return std::pow(args[0], args[1]); }}},
    {"sqrt", {1, [] (const auto& args) { return std::sqrt(args[0]); }}},
    {"exp", {1, [] (const auto& args) { return std::exp(args[0]); }}},
    {"ln", {1, [] (const auto& args) { return std::log(args[0]); }}},
    {"lg", {1, [] (const auto& args) { return std::log10(args[0]); }}},
    {"abs", {1, [] (const auto& args) { return std::abs(args[0]); }}},
};

parser::rule_parser::pointer make_parser() {
    const auto expression_dummy = parser::dummy();
    RULE(function_call) = "identifier"_t >> &"("_v >>
        -(expression_dummy % &","_v)
    >> &")"_v;
    RULE(atom) = "number"_t
        | function_call
        | "identifier"_t
        | (&"("_v >> expression_dummy >> &")"_v);
    RULE(unary) = *("-"_v) >> atom;
    RULE(product) = unary % ("*"_v | "/"_v | "%"_v);
    RULE(sum) = product % ("+"_v | "-"_v);
    expression_dummy->set_parser(sum);

    return sum;
}

double evaluate_ast_node(
    const parser::ast_node& ast,
    const std::unordered_map<std::string, double>& constants,
    const std::unordered_map<std::string, function>& functions
) {
    const auto inspect_sequence = [] (const auto& ast) -> const auto& {
        return ast.children[0].children;
    };
    const auto evaluate_with_context = [&] (const auto& ast) {
        return evaluate_ast_node(ast, constants, functions);
    };

    if (ast.type == "number") {
        return std::stod(ast.value, nullptr);
    } else if (ast.type == "identifier") {
        try {
            return constants.at(ast.value);
        } catch (const std::out_of_range& exception) {
            const auto offset = parser::get_offset(ast);
            throw unexpected_entity_exception<entity_type::constant>{offset};
        }
    } else if (ast.type == "atom") {
        const auto type = (+parser::ast_node_type::sequence)._to_string();
        const auto first_child = ast.children[0].type == type
            ? inspect_sequence(ast)[0]
            : ast.children[0];
        return evaluate_with_context(first_child);
    } else if (ast.type == "unary") {
        const auto result = evaluate_with_context(inspect_sequence(ast).back());
        const auto sign = (inspect_sequence(ast).size() - 1) % 2 ? -1 : 1;
        return sign * result;
    } else if (ast.type == "function_call") {
        try {
            const auto name = inspect_sequence(ast)[0].value;
            const auto arguments = inspect_sequence(ast)
                | ranges::view::drop(1)
                | ranges::view::transform([&] (const auto& ast) {
                    return evaluate_with_context(ast);
                });
            const auto function = functions.at(name);
            if (arguments.size() != function.arity) {
                const auto unit = function.arity == 1 ? "argument" : "arguments";
                const auto description =
                    fmt::format("function requires {:d} {:s}", function.arity, unit);
                const auto offset = parser::get_offset(ast);
                throw exceptions::positional_exception{description, offset};
            }

            return function.handler(arguments);
        } catch (const std::out_of_range& exception) {
            const auto offset = parser::get_offset(ast);
            throw unexpected_entity_exception<entity_type::function>{offset};
        }
    } else if (ast.type == "product" || ast.type == "sum") {
        const auto first_operand = evaluate_with_context(inspect_sequence(ast)[0]);
        const auto children_chunks = inspect_sequence(ast)
            | ranges::view::drop(1)
            | ranges::view::chunk(2)
            | ranges::view::transform([] (const auto& chunk) {
                return chunk | ranges::to_<parser::ast_node_group>();
            });
        return ranges::accumulate(
            children_chunks,
            first_operand,
            [&] (const auto& result, const auto& chunk) {
                const auto name = chunk[0].value;
                const auto second_operand = evaluate_with_context(chunk[1]);
                return functions.at(name).handler({result, second_operand});
            }
        );
    } else {
        const auto offset = parser::get_offset(ast);
        throw unexpected_entity_exception<entity_type::node>{offset};
    }
}

int main(int argc, char* argv[]) {
    const auto exit = [] (const auto& code, const auto& message) {
        (code == EXIT_SUCCESS ? std::cout : std::cerr) << message << '\n';
        std::exit(code);
    };
    const auto enrich =
        [] (const auto& exception, const auto& code, const auto& token_size) {
            const auto mark_offset = std::string(exception.offset, ' ');
            const auto mark = std::string(token_size, '^');
            const auto description_lines = std::vector<std::string>{
                exception.what(),
                fmt::format(R"(| "{:s}")", code),
                fmt::format(R"(|  {:s}{:s})", mark_offset, mark)
            };
            return std::runtime_error{description_lines | ranges::view::join('\n')};
        };

    try {
        const auto options = docopt::docopt(usage, {argv + 1, argv + argc}, true);
        const auto expression = options.at("<expression>")
            ? options.at("<expression>").asString()
            : "";
        const auto code = options.at("--stdin").asBool()
            ? std::string{std::istreambuf_iterator<char>{std::cin}, {}}
            : expression;
        const auto verbose = options.at("--verbose").asBool();
        try {
            auto tokens = lexer::tokenize_all(lexemes, lexemes_exceptions, code);
            if (options.at("--target") == "tokens"s) {
                exit(EXIT_SUCCESS, tokens);
            }

            const auto eoi = exceptions::entity_type::eoi;
            try {
                const auto ast = parser::parse_all(make_parser(), tokens);
                if (options.at("--target") == "cst"s) {
                    exit(EXIT_SUCCESS, ast);
                }

                auto buffer = std::ostringstream{};
                const auto precision = options.at("--precision")
                    ? options.at("--precision").asLong()
                    : std::numeric_limits<double>::max_digits10;
                const auto result = evaluate_ast_node(ast, constants, functions);
                buffer << std::setprecision(precision) << result;

                exit(EXIT_SUCCESS, buffer.str());
            } catch (const exceptions::unexpected_entity_exception<eoi>& exception) {
                const auto offset = exception.offset == utilities::integral_infinity
                    ? code.size()
                    : exception.offset;
                throw exceptions::unexpected_entity_exception<eoi>{offset};
            } catch (const exceptions::positional_exception& exception) {
                const auto token = ranges::find_if(tokens, [&] (const auto& token) {
                    return token.offset == exception.offset;
                });
                const auto token_size = token->value.size();
                throw verbose
                    ? enrich(exception, code, token_size)
                    : std::runtime_error{exception};
            }
        } catch (const exceptions::positional_exception& exception) {
            throw verbose ? enrich(exception, code, 1) : std::runtime_error{exception};
        }
    } catch (const std::exception& exception) {
        exit(EXIT_FAILURE, fmt::format("error: {:s}", exception.what()));
    }
}

Репозиторий

Ссылка: https://github.com/thewizardplusplus/wizard-parser/tree/v4.4.

Содержание: код, документация, пример использования.

Лицензия:

• кода — MIT;
• документации — CC BY 4.0.