Wizard Parser, v2.1

Лексический анализ

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

Рефакторинг, добавление новых парсеров и комбинаторов и покрытие примера тестами.

Изменения

Убрать ненужную универсальность из парсера флагов #23
Вынести общую функциональность из парсеров с присваиванием #22
Добавить парсер пустоты #21
Добавить комбинатор списка с разделителем #20
Заменить комбинатор опциональности на комбинатор повторений #19
Добавить поддержку негативного просмотра вперёд в комбинатор просмотра вперёд #18
Переименовать комбинатор сокрытия ноды в комбинатор просмотра вперёд #17
Объединить парсеры определённого текста и определённой лексемы #16
Добавить поддержку указания лимитов в комбинаторе повторений #15
Заменить иерархию парсеров на её листья #14
Заменить итераторы токенов на тип span из библиотеки Microsoft/GSL #13
Заменить класс lexer::tokenizer на набор функций #12
Заменить строковые итераторы на тип string_span из библиотеки Microsoft/GSL #11
Добавить тесты из Wizard Steps (на основе Bats) для примера #10
Добавить поддержку чтения выражения из stdin в пример #9
Добавить опцию -t/--tokens для вывода списка токенов в пример #8
Использовать библиотеку docopt/docopt.cpp для парсинга опций в примере #7
Использовать библиотеку fmtlib/fmt для форматирования строк #6
Заменить флаг parser::parsing_result::is_parsed на тип optional из библиотеки akrzemi1/Optional #5
Заменить тип std::pair<T, bool> на тип optional из библиотеки akrzemi1/Optional #4
Удалить функцию utilities::contains() #3
Использовать библиотеку nlohmann/json для сериализации #2
Реализовать функцию to_string() в пару к каждой функции operator<<() #1

Возможности

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

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

#include "vendor/docopt/docopt.hpp"
#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/lexer/tokenize.hpp>
#include <thewizardplusplus/wizard_parser/parser/parse.hpp>
#include <regex>
#include <vector>
#include <string>
#include <unordered_set>
#include <iostream>
#include <iterator>
#include <cstdlib>
#include <exception>

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 usage =
R"(Usage:
  ./example -h | --help
  ./example [-t | --tokens] <expression>
  ./example [-t | --tokens] (-s | --stdin)

Options:
  -h, --help    - show this message;
  -t, --tokens  - show a token list instead an AST;
  -s, --stdin   - read an expression from stdin.)";
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)
    >> &")"_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);
    RULE(sum) = product % ("+"_v | "-"_v);
    RULE(comparison) = sum % ("<"_v | "<="_v | ">"_v | ">="_v);
    RULE(equality) = comparison % ("=="_v | "/="_v);
    RULE(conjunction) = equality % &"and"_v;
    RULE(disjunction) = conjunction % &"or"_v;
    expression_dummy->set_parser(disjunction);

    return disjunction >> eoi();
}

}

int main(int argc, char* argv[]) try {
    auto code = std::string{};
    const auto options = docopt::docopt(usage, {argv + 1, argv + argc}, true);
    if (!options.at("--stdin").asBool()) {
        code = options.at("<expression>").asString();
    } else {
        code = std::string{std::istreambuf_iterator<char>{std::cin}, {}};
    }

    auto tokens = tokenize(lexemes, ignorable_tokens, code);
    if (options.at("--tokens").asBool()) {
        std::cout << tokens << '\n';
        std::exit(EXIT_SUCCESS);
    }

    RULE(expression) = make_expression_parser();
    const auto ast = parse(expression, tokens, code.size());
    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.1.

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

Лицензия:

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