Руководство по lexertl

Все статьи / Руководство по lexertl

C++ библиотека lexertl во многом лучше GNU Flex. Она умеет создавать лексические анализаторы из правил в runtime, может обрабатывать unicode, и даже умеет генерировать код сканера на C++. Библиотека header-only и очень проста в установке.

Пример к статье доступен на github

Библиотека lexertl служит для разбора регулярных грамматик. Иными словами, с её помощью можно написать лексический анализатор (англ. lexer или scanner), который обработает входной текст и превратить его в поток токенов, который гораздо легче использовать в полноценном парсере.

Установка lexertl

lexertl является header-only библиотекой для C++, и для установки достаточно

выкачать исходный код из репозитория на github
добавить путь к каталогу с исходным кодом в пути поиска заголовков

После этих шагов создайте новый файл или проект на C++, добавьте туда простой пример кода и соберите:

#include "lexertl/generator.hpp"
#include "lexertl/lookup.hpp"
#include <iostream>

int main()
{
    lexertl::rules rules;
    lexertl::state_machine sm;

    rules.push("[0-9]+", 1);
    rules.push("[a-z]+", 2);
    lexertl::generator::build(rules, sm);

    std::string input("abc012Ad3e4");
    lexertl::smatch results(input.begin(), input.end());

    // Read ahead
    lexertl::lookup(sm, results);

    while (results.id != 0)
    {
        std::cout << "Id: " << results.id << ", Token: '" <<
            results.str () << "'\n";
        lexertl::lookup(sm, results);
    }

    return 0;
}

Пишем сканер выражений калькулятора с lexertl

У библиотеки есть Web-страница с документацией: www.benhanson.net/lexertl.html

Представленная ниже программа выводит номера и строки токенов для входного выражения с идентификаторами и числами. Ввод читается построчно из stdin, для выхода из программы достаточно ввести символ конца файла.

>velocity + 27 * accel / 19
Id: 2, Token: 'velocity'
Id: 3, Token: '+'
Id: 1, Token: '27'
Id: 5, Token: '*'
Id: 2, Token: 'accel'
Id: 6, Token: '/'
Id: 1, Token: '19'

Библиотека состоит лишь из заголовочных файлов и не требует компоновки. Конечный автомат для лексического анализа может быть собран в runtime. Поэтому реализация состоит всего лишь из одного файла:

#include "lexertl/generator.hpp"
#include "lexertl/iterator.hpp"
#include <boost/range/iterator_range.hpp>
#include <iostream>
#include <memory>

enum {
    // ID пользовательских токенов должны начинаться с 1,
    //  т.к. число 0 lexertl резервирует для ID "конец ввода".
    // Если один из ID равен нулю, программа аварийно завершится.
    TK_NUMBER = 1,
    TK_IDENTIFIER,
    TK_PLUS,
    TK_MINUS,
    TK_MULTIPLY,
    TK_DIVIDE,
};

// Создаёт детерминированный конечный автомат (DFA)
//  для лексического анализа грамматики калькулятора
std::unique_ptr<lexertl::state_machine> BuildCalcLexer()
{
    lexertl::rules rules;

    // Метод push добавляет правило
    rules.push("[0-9]+", TK_NUMBER);
    rules.push("[a-z]+", TK_IDENTIFIER);
    rules.push("\\+", TK_PLUS);
    rules.push("\\-", TK_MINUS);
    rules.push("\\*", TK_MULTIPLY);
    rules.push("\\/", TK_DIVIDE);

    // Метод skip возвращает специальный ID,
    //  который означает, что это совпадение игнорируется.
    // Так мы можем пропустить пробельные символы.
    rules.push("[ \t\r\n]+", rules.skip());

    auto lexer = std::make_unique<lexertl::state_machine>();
    lexertl::generator::build(rules, *lexer);

    return lexer;
}

// Возвращает диапазон для прохода слева направо,
//  который при запросе следующего элемента
//  получает его из строки `line` с помощью лексера `lexer`
decltype(auto) TokenizeLine(const lexertl::state_machine &lexer, std::string &line)
{
    lexertl::siterator begin(line.begin(), line.end(), lexer);
    lexertl::siterator end;

    // Непосредственно при вызове токенизации не происходит,
    //  такой подход называется lazy evaluation with generators.
    return boost::make_iterator_range(begin, end);
}

int main()
{
    auto lexer = BuildCalcLexer();

    while (std::cin)
    {
        std::string line;
        std::getline(std::cin, line);
        for (auto &token : TokenizeLine(*lexer, line))
        {
            std::cout << "Id: " << token.id << ", Token: '" << token.str() << "'\n";
        }
    }

    return 0;
}

Генерация C++ кода

Можно легко модифицировать предыдущий пример, чтобы сгенерировать исходный код функции, реализующей лексический анализ той же самой регулярной грамматики. Полученный код по-прежнему использует библиотеку lexertl, но уже не требует конструирования лексера во время выполнения.

Первым делом подключите два новых заголовка:

#include "lexertl/generator.hpp"
#include "lexertl/generate_cpp.hpp"

Затем в функцию BuildCalcLexer после вызова lexertl::generator::build добавьте всего две строки кода:

// Минимизируем детерминированный конечный автомат,
//  это занимает немного времени, но взамен ускорит работу сканера.
lexer->minimise();

// Генерируем table-driven лексер на C++,
// В качестве имени функции передаём LookupExprToken.
lexertl::table_based_cpp::generate_cpp("LookupExprToken", *lexer, false, std::cout);

Запустите изменённый пример, и при старте программа выведет в консоль C++ код функции lookupExprToken, который выглядит примерно так:

template<typename iter_type, typename id_type>
void LookupExprToken (lexertl::match_results<iter_type, id_type> &results_)
{
    // ...table-driven реализация разбора следующего токена...
}

Сгенерированный код можно поместить в файл “LookupExprToken.hpp”, и после этого для реализации лексера достаточно подключить заголовок и написать управляющую функцию. Полученная программа будет вести себя так же, как в предыдущем примере:

#include "lexertl/iterator.hpp"
#include "LookupExprToken.hpp"

int main()
{
    while (std::cin)
    {
        std::string line;
        std::getline(std::cin, line);

        // Заполняем буфер состояния.
        lexertl::smatch results(line.begin(), line.end());

        // Cчитываем первый токен
        LookupExprToken(results);
        while (results.id != 0)
        {
            std::cout << "Id: " << results.id << ", Token: '" << results.str() << "'\n";
            LookupExprToken(results);
        }
    }

    return 0;
}

Отладочный вывод структуры ДКА

Можно выполнить отладочную печать состояний и переходов созданного в lexertl ДКА.

Во-первых нужно подключить ещё один заголовок:

#include "lexertl/debug.hpp"

Затем в функцию BuildCalcLexer после вызова lexertl::generator::build добавьте вызов отладочной печати:

// Минимизируем детерминированный конечный автомат,
//  это занимает немного времени, но взамен уменьшит объём таблицы.
lexer->minimise();

// Выводим в stdout человекочитаемые таблицы состояний и переходов.
lexertl::debug::dump(*lexer, std::cout);

Все статьи / Руководство по lexertl

Содержание

Установка lexertl

Пишем сканер выражений калькулятора с lexertl

Генерация C++ кода

Отладочный вывод структуры ДКА