Wizard Parser, v2.0

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

Мажорный релиз. Добавление лексера на основе регулярных выражений и сериализации AST в JSON, исправление бага с утечкой памяти.

Изменения

• добавлено:
  • лексер:
    • задание лексем посредством регулярных выражений;
    • возможность исключения токенов из результирующего списка;
  • сериализация AST в JSON;
• исправлен баг с утечкой памяти при циклических зависимостях в графе парсеров;
• удалено:
  • представление результата в виде дерева парсинга;
  • объединение нод в AST;
  • сериализация AST в XML;
  • поддержка полноценной грамматики в качестве разделителя для основной;
  • комбинаторы:
    • повторение 1 или больше раз;
    • список с разделителем;
  • парсеры:
    • пустой (ничего не парсит);
    • граница слова (правило \b в регулярных выражениях);
    • парсеры символов:
      • парсер определённого символа;
      • парсер любого символа;
      • парсеры любого символа из определённого набора:
        • парсер любого символа из определённого набора;
        • парсер пробельных символов;
        • парсер букв;
        • парсер цифр;
        • парсер букв, цифр и символа _;
    • парсер определённого текста, ограниченного границами слова (правило \b в регулярных выражениях).

Возможности

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

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

#include <thewizardplusplus/wizard_parser/lexer/lexeme.hpp>
#include <thewizardplusplus/wizard_parser/parser/parsers.hpp>
#include <thewizardplusplus/wizard_parser/parser/macroses.hpp>
#include <thewizardplusplus/wizard_parser/parser/parse.hpp>
#include <regex>
#include <vector>
#include <string>
#include <unordered_set>
#include <cstring>
#include <stdexcept>
#include <iostream>
#include <exception>
#include <cstdlib>

using namespace thewizardplusplus::wizard_parser::lexer;
using namespace thewizardplusplus::wizard_parser::parser;
using namespace thewizardplusplus::wizard_parser::parser::operators;

/* Grammar description in EBNF:
 *
 * expression = disjunction;
 * disjunction = conjunction, {"or", conjunction};
 * conjunction = equality, {"and", equality};
 * equality = comparison, {("==" | "/="), comparison};
 * comparison = sum, {("<" | "<=" | ">" | ">="), sum};
 * sum = product, {("+" | "-"), product};
 * product = unary, {("*" | "/" | "%"), unary};
 * unary = {"-" | "not"}, atom;
 *
 * atom = NUMBER CONSTANT | identifier | function call | ("(", expression, ")");
 * identifier = BASE IDENTIFIER - key words;
 * function call = identifier, "(", [expression, {",", expression}], ")";
 *
 * NUMBER CONSTANT = ? /\d+(\.\d+)?(e-?\d+)?/ ?;
 * BASE IDENTIFIER = ? / [a-z_] \w* /xi ?;
 *
 * key words = "and" | "not" | "or";
 */

const auto lexemes = std::vector<lexeme>{
    {std::regex{"=="}, "equal"},
    {std::regex{"/="}, "not_equal"},
    {std::regex{"<"}, "less"},
    {std::regex{"<="}, "less_or_equal"},
    {std::regex{">"}, "great"},
    {std::regex{">="}, "great_or_equal"},
    {std::regex{R"(\+)"}, "plus"},
    {std::regex{"-"}, "minus"},
    {std::regex{R"(\*)"}, "star"},
    {std::regex{"/"}, "slash"},
    {std::regex{"%"}, "percent"},
    {std::regex{R"(\()"}, "opening_parenthesis"},
    {std::regex{R"(\))"}, "closing_parenthesis"},
    {std::regex{","}, "comma"},
    {std::regex{R"(\d+(?:\.\d+)?(?:e-?\d+)?)"}, "number_constant"},
    {std::regex{R"([A-Za-z_]\w*)"}, "base_identifier"},
    {std::regex{R"(\s+)"}, "whitespace"}
};
const auto ignorable_tokens = std::unordered_set<std::string>{"whitespace"};

namespace {

rule_parser::pointer make_atom_parser(const rule_parser::pointer& expression) {
    RULE(number_constant) = "number_constant"_t;
    RULE(key_words) = "and"_v | "not"_v | "or"_v;
    RULE(identifier) = "base_identifier"_t - key_words;
    IMPORTANT_RULE(function_call) = identifier >> &"("_v >>
        -(expression >> *(&","_v >> expression))
    >> &")"_v;
    return number_constant
        | identifier
        | function_call
        | (&"("_v >> expression >> &")"_v);
}

rule_parser::pointer make_expression_parser() {
    const auto expression_dummy = dummy();
    RULE(atom) = make_atom_parser(expression_dummy);
    RULE(unary) = *("-"_v | "not"_v) >> atom;
    RULE(product) = unary >> *(("*"_v | "/"_v | "%"_v) >> unary);
    RULE(sum) = product >> *(("+"_v | "-"_v) >> product);
    RULE(comparison) = sum >> *(("<"_v | "<="_v | ">"_v | ">="_v) >> sum);
    RULE(equality) = comparison >> *(("=="_v | "/="_v) >> comparison);
    RULE(conjunction) = equality >> *(&"and"_v >> equality);
    RULE(disjunction) = conjunction >> *(&"or"_v >> conjunction);
    expression_dummy->set_parser(disjunction);

    return disjunction >> eoi();
}

}

int main(int argc, char* argv[]) try {
    if (argc < 2 || std::strlen(argv[1]) == 0) {
        throw std::invalid_argument{"the expression isn't specified"};
    }

    RULE(expression) = make_expression_parser();
    const auto ast = parse(lexemes, ignorable_tokens, expression, argv[1]);
    std::cout << ast << '\n';
} catch (const std::exception& exception) {
    std::cerr << "error: " << exception.what() << '\n';
    std::exit(EXIT_FAILURE);
}

Репозиторий

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

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

Лицензия:

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