ARCHANGEL's blog

ARCHANGEL

Мудрец
Сообщения
81
Реакции
534
Захотелось на днях почитать про компиляторы, лексические анализаторы и синтаксические разборы. Есть занимательный цикл статей здесь
А у меня будет его вольный перевод с комментариями. Предлагаю начать с первой части, пропустив введение. Вот эти все введения, где автор благодарит семью, друзей, кота, спонсора - я их стараюсь не читать даже. Ладно, начнём.

Идея сканнера (лексического анализатора) - получить набор, или, если хотите, массив\список\некий контейнер с возможностью обхода, в котором содержатся токены. У нас имеется какое-то перечисление этих самых типов токенов, и структура, которая описывает токен:

C++:
enum class tokensType
{
    T_PLUS,
    T_MINUS,
    T_STAR,
    T_SLASH,
    T_INTLIT
};

struct token
{
    tokensType type;
    int intValue;
};
Допустим, у нас есть выражение вида "2 + 3 * 5 - 8 / 3", и нам нужно его разобрать на токены. Все имеющиеся в выражении типы токенов у нас представлены в enum'e tokensType, так что всё должно получиться.

C++:
int main(int argc, char* argv[]) try
{
    const std::string content = "2 + 3 * 5 - 8 / 3";
    Lexer lexer(content);
    lexer.ScanContent();

    return 0;
}
catch(const std::exception& error)
{
    std::cout << error.what() << std::endl;
}
У нас есть некий пока не описанный класс Lexer, его конструктор, принимающий std::string, и публичный метод ScanContent, который должен напечатать в консоли что-то типа как у автора в оригинальном туториале. Давайте пару замечаний - здесь мы работаем со строками, а не с файлами - чуть упростим себе жизнь. Плюс у нас здесь есть обработка исключений, которой на может быть в коде на С, потому что там нет исключений. Мы не будем сильно лезть в дебри С++, во всяком случае - пока, но кое-какие моменты всё же будут.

Конструктор у этого класса крайне простой:

C++:
explicit Lexer(const std::string& arg):
        m_content(arg), m_putBack(0), m_line(0)
    {
        
    }
Печать токенов выглядит так:

C++:
void ScanContent()
    {
        static const std::string tokstr[] { "+", "-", "*", "/", "intlit" };

        token T{};

        while (scan(&T))
        {
            printf("Token %s", tokstr[static_cast<int>(T.type)].c_str());
            if (T.type == tokensType::T_INTLIT)
                printf(", value %d", T.intValue);
            printf("\n");
        }
    }
Мы создаём массив строк с печатаемыми именами токенов, и, когда уже имеем тип из перечисления, то обращаемся к этому массиву по индексу, чтобы достать красивое представление для печати - printf("Token %s", tokstr[static_cast<int>(T.type)].c_str());

Основу всего составляет вызываемый в цикле метод scan:

C++:
bool scan(token* t)
    {
        // Skip whitespace
        const auto c = skip();

        // Determine the token based on
        // the input character
        switch (c)
        {
        case EOF:
            return false;
        case '+':
            t->type = tokensType::T_PLUS;
            break;
        case '-':
            t->type = tokensType::T_MINUS;
            break;
        case '*':
            t->type = tokensType::T_STAR;
            break;
        case '/':
            t->type = tokensType::T_SLASH;
            break;
        default:
            // If it's a digit, scan the
            // literal integer value in
            if (isdigit(c)) {
                t->intValue = scanint(c);
                t->type = tokensType::T_INTLIT;
                break;
            }
            char buffer[200]{ 0 };
            snprintf(buffer, sizeof(buffer) - 1, 
                "Unrecognised character %c on line %d\n", c, m_line);
            throw std::logic_error(buffer);        
        }

        // We found a token
        return true;
    }
Здеьс происходит вычитка текущего символа с пропуском разделителей (мы игнорируем пробелы, символы табуляции, символы переноса строки и т.д.), и анализ этого символа с последующим созданием токена на его основе. Арифметические действия описываются однобайтовым символом, потому здесь пока всё тривиально просто. Если попадается какой-то символ, который наш сканер не знает - не цифра и не арифметическая операция из перечисления, то генерируется исключение, и в функции main сработает обработчик.

А вот как выглядят недостающе методы:

C++:
int getNextChar()
    {
        static unsigned int current = 0;
        if (current >= m_content.length())
            return EOF;
        return m_content[current++];
    }

    int next()
    {
        if (m_putBack)
        {
            const auto c = m_putBack;
            m_putBack = 0;
            return c;
        }

        const auto c = getNextChar();
        if ('\n' == c)
            m_line++;
        return c;
    }

    int skip()
    {
        auto c = next();
        while (' ' == c || '\t' == c || '\n' == c || '\r' == c || '\f' == c)
        {
            c = next();
        }
        return c;
    }

    int scanint(int c)
    {
        unsigned int k, val = 0;
        static const std::string alphabet = "0123456789";
        char letter = static_cast<char>(c);

        // Convert each character into an int value
        while ((k = alphabet.find(letter)) != std::string::npos)
        {
            val = val * 10 + k;
            c = next();
            letter = static_cast<char>(c);
        }

        // We hit a non-integer character, put it back.
        m_putBack = c;
        return static_cast<int>(val);
    }
Здесь есть буквально пара моментов, которые стоит пояснить, так как они отличаются от реализации автора в оригинале.
1. Так как мы работает со строками, у нас нет никакого EOF (end of file), потому мы добавлеям его, когда достигнут конец строки:
C++:
if (current >= m_content.length())
            return EOF;
2. У нас для конвертации строки в число используются std::string и их встроенный метод find, но смысл аналогичен - ищем текущий символ в алфавите, если он находится, то старое значение сдвигаем на следующий разряд в десятичной системе (множим на 10) и прибавляем значение текущей позиции.
C++:
 unsigned int k, val = 0;
static const std::string alphabet = "0123456789";
char letter = static_cast<char>(c);
// Convert each character into an int value
while ((k = alphabet.find(letter)) != std::string::npos)
{
    val = val * 10 + k;
    c = next();
    letter = static_cast<char>(c);
}
И теперь всё вместе:

C++:
#include <iostream>
#include <string>
#include <stdexcept>


enum class tokensType
{
    T_PLUS,
    T_MINUS,
    T_STAR,
    T_SLASH,
    T_INTLIT
};

struct token
{
    tokensType type;
    int intValue;
};

class Lexer
{
public:
    explicit Lexer(const std::string& arg):
        m_content(arg), m_putBack(0), m_line(0)
    {
        
    }
    bool scan(token* t)
    {
        // Skip whitespace
        const auto c = skip();

        // Determine the token based on
        // the input character
        switch (c)
        {
        case EOF:
            return false;
        case '+':
            t->type = tokensType::T_PLUS;
            break;
        case '-':
            t->type = tokensType::T_MINUS;
            break;
        case '*':
            t->type = tokensType::T_STAR;
            break;
        case '/':
            t->type = tokensType::T_SLASH;
            break;
        default:
            // If it's a digit, scan the
            // literal integer value in
            if (isdigit(c)) {
                t->intValue = scanint(c);
                t->type = tokensType::T_INTLIT;
                break;
            }
            char buffer[200]{ 0 };
            snprintf(buffer, sizeof(buffer) - 1,
                "Unrecognised character %c on line %d\n", c, m_line);
            throw std::logic_error(buffer);       
        }

        // We found a token
        return true;
    }
    void ScanContent()
    {
        static const std::string tokstr[] { "+", "-", "*", "/", "intlit" };

        token T{};

        while (scan(&T))
        {
            printf("Token %s", tokstr[static_cast<int>(T.type)].c_str());
            if (T.type == tokensType::T_INTLIT)
                printf(", value %d", T.intValue);
            printf("\n");
        }
    }

private:
    std::string m_content;
    int m_putBack;
    int m_line;

    int getNextChar()
    {
        static unsigned int current = 0;
        if (current >= m_content.length())
            return EOF;
        return m_content[current++];
    }

    int next()
    {
        if (m_putBack)
        {
            const auto c = m_putBack;
            m_putBack = 0;
            return c;
        }

        const auto c = getNextChar();
        if ('\n' == c)
            m_line++;
        return c;
    }

    int skip()
    {
        auto c = next();
        while (' ' == c || '\t' == c || '\n' == c || '\r' == c || '\f' == c)
        {
            c = next();
        }
        return c;
    }

    int scanint(int c)
    {
        unsigned int k, val = 0;
        static const std::string alphabet = "0123456789";
        char letter = static_cast<char>(c);

        // Convert each character into an int value
        while ((k = alphabet.find(letter)) != std::string::npos)
        {
            val = val * 10 + k;
            c = next();
            letter = static_cast<char>(c);
        }

        // We hit a non-integer character, put it back.
        m_putBack = c;
        return static_cast<int>(val);
    }
};

int main(int argc, char* argv[]) try
{
    const std::string content = "2 + 3 * 5 - 8 / 3";
    Lexer lexer(content);
    lexer.ScanContent();

    return 0;
}
catch(const std::exception& error)
{
    std::cout << error.what() << std::endl;
}
 

ARCHANGEL

Мудрец
Сообщения
81
Реакции
534
Ох, бро, если мы будем каждый парсер писать по книге дракона, то, боюсь, люди столько не живут )
 

ARCHANGEL

Мудрец
Сообщения
81
Реакции
534
Ребятки, дошли руки почитать часть 2 (напоминаю, что автор ведёт нумерацию с нуля). В общем, здесь уже будет больше С++, ибо нужно как-то менеджить память в деревьях. В дополнение мы разделим лексер и парсер, потому что в оригинале у автора между ними присутствуют жёсткие связи, глобальные переменные (это совсем кака), и сосредоточимся на концепции, меньше внимания уделяя деталям.
Также обсудим упрощения, допущения и недоработки, которые пока будут в парсере. Но это ничего - это так задумано, так пока надо.

Начнём с того, что добавим метод в лексический анализатор. Этот метод будет возвращать все разобранные токены:
C++:
std::vector<lexer::token> lexer::Lexer::GetTokens()
{
    static const std::string tokstr[]{ "+", "-", "*", "/", "intlit" };
    std::vector<lexer::token> result;

    token T{};

    while (scan(&T))
    {
        result.push_back(T);
    }

    return result;
}
В общем, алгоритм парсинга сводитя к тому, что мы из токенов лексера (лексического анализатора) строим абстрактное синтаксическое дерево, а потом совершаем обход этого дерева. Надо понимать, что это возможно, потому что у нас в примере берётся контекстно-свободная грамматика, описание которой в форме РБНФ (расширенная форма Бэкуса — Наура) автор даёт в начале второй части. То есть, если бы описать грамматику в РБНФ было бы невозможно, нам бы понадобился иной подход.

Итак, на верхнем уровне логика выглядит следующим образом:

C++:
int main(int argc, char* argv[]) try
{
    const std::string content = "2 + 3 * 5 - 8 / 3";
    lexer::Lexer lexer(content);
    const auto lexems = lexer.GetTokens();
    const auto root = parser::MakeAstTree(lexems.cbegin(), lexems.cend());
    std::cout << parser::InterpretAST(root) << std::endl;

    return 0;
}
catch(const std::exception& error)
{
    std::cout << error.what() << std::endl;
}
Я позволил себе переименовать методы для большей ясности (их названия теперь, в основном, не совпадают с названием автора). Давайте посмотрим, как создаётся АСТ.

C++:
std::shared_ptr<parser::ASTnode> parser::MakeAstTree(std::vector<lexer::token>::const_iterator cbegin,
    std::vector<lexer::token>::const_iterator cend)
{
    if (cbegin == cend)
    {
        return nullptr;
    }

    std::shared_ptr<parser::ASTnode> n, left, right;

    // Get the integer literal on the left.
    // Fetch the next token at the same time.
    left = primary(cbegin);
    ++cbegin;

    // If no tokens left, return just the left node
    if (cbegin == cend)
    {
        return left;
    }

    // Convert the token into a node type
    const auto nodetype = TokenToAstOperation(cbegin->type);   

    // Recursively get the right-hand tree
    right = MakeAstTree(cbegin + 1, cend);

    // Now build a tree with both sub-trees
    return MakeAstNode(static_cast<int>(nodetype), left, right, 0);
}
Я постарался сохранить оригинальные комментарии автора, но есть и ряд отличий. Во-первых, все узлы дерева представлены в виде умных указателей - std::shared_ptr. Так мы избежим утечек памяти. Во-вторых, нет никаких сканов - у нас уже имеется полный набор токенов, и вместо скана следующего токена мы просто движемся по итератору. Здесь кроется одну упрощение, которое допускает автор. Почему-то он считает, что после нетерминала всегда идёт терминал. Иными словами, после цифры сразу идёт какое-то арифметическое действие. Это выражается таким комментарием (и в оригинале вот таким кодом):

C:
// Get the integer literal on the left.
  // Fetch the next token at the same time.
  left = primary();

  // If no tokens left, return just the left node
  if (Token.token == T_EOF)
    return (left);

  // Convert the token into a node type
  nodetype = arithop(Token.token);

  // Get the next token in
  scan(&Token);
Созданием самих узлов дерева, в общем, особо не отличается от кода автора. Так как АСТ - бинарное дерево, то у каждого узла могут быть либо два потомка, либо 1, либо 0:

C++:
std::shared_ptr<parser::ASTnode> parser::MakeAstNode(int op, std::shared_ptr<ASTnode> left,
                                                     std::shared_ptr<ASTnode> right, int intvalue)
{
    auto n = std::make_shared<parser::ASTnode>();

    // Copy in the field values and return it
    n->op = op;
    n->left = left;
    n->right = right;
    n->intvalue = intvalue;
    return n;
}

std::shared_ptr<parser::ASTnode> parser::MakeAstLeaf(int op, int intvalue)
{
    return MakeAstNode(op, nullptr, nullptr, intvalue);
}

std::shared_ptr<parser::ASTnode> parser::MakeAstUnary(int op, std::shared_ptr<ASTnode> left, int intvalue)
{
    return MakeAstNode(op, left, nullptr, intvalue);
}
Конвертация токена в операцию АСТ тоже тривиальна и отличается от оригинала только генерацией исключения, а не завершением всей программы:

C++:
parser::AstTypes parser::TokenToAstOperation(lexer::tokensType tok)
{
    switch (tok)
    {
    case lexer::tokensType::T_PLUS:
        return (AstTypes::A_ADD);
    case lexer::tokensType::T_MINUS:
        return (AstTypes::A_SUBTRACT);
    case lexer::tokensType::T_STAR:
        return (AstTypes::A_MULTIPLY);
    case lexer::tokensType::T_SLASH:
        return (AstTypes::A_DIVIDE);
    default:
        throw std::logic_error("Unknown token " + std::to_string(static_cast<int>(tok)));
    }
}
Мы не всегда захотим на практике завершить работу всего приложения, если вдруг в каком-то компоненте парсинг не удался.И остаётся функция primary:

C++:
std::shared_ptr<parser::ASTnode> parser::primary(std::vector<lexer::token>::const_iterator cbegin)
{
    // For an INTLIT token, make a leaf AST node for it
    // and scan in the next token. Otherwise, a syntax error
    // for any other token type.
    const auto token = *cbegin;
    switch (token.type)
    {
    case lexer::tokensType::T_INTLIT:
    {
        return parser::MakeAstLeaf(static_cast<int>(AstTypes::A_INTLIT), token.intValue);
    }
    default:
        throw std::logic_error("syntax error at token with id "
            + std::to_string(static_cast<int>(token.type)));
    }
}
Ожидается, что первый токен не может описывать ничего другого, кроме как численное значение. Что ж - пока это действительно так.

Парсинг такого бинарного дерева выглядит и того проще. Он рекусривный, и просто берёт значение левого поддерева, правого поддерева и применяет к ним обработчика терминального символа, которому соответвует значение терминала в корне:

C++:
int parser::InterpretAST(std::shared_ptr<ASTnode> n)
{
    int leftval{}, rightval{};

    // Get the left and right sub-tree values
    if (n->left)
        leftval = InterpretAST(n->left);
    if (n->right)
        rightval = InterpretAST(n->right);

    switch (static_cast<AstTypes>(n->op))
    {
    case AstTypes::A_ADD:
    {
        std::cout << leftval << " + " << rightval << std::endl;
        return (leftval + rightval);
    }
    case AstTypes::A_SUBTRACT:
    {
        std::cout << leftval << " - " << rightval << std::endl;
        return (leftval - rightval);
    }
    case AstTypes::A_MULTIPLY:
    {
        std::cout << leftval << " * " << rightval << std::endl;
        return (leftval * rightval);
    }
    case AstTypes::A_DIVIDE:
    {
        std::cout << leftval << " / " << rightval << std::endl;
        return (leftval / rightval);
    }
    case AstTypes::A_INTLIT:
    {
        return (n->intvalue);
    }
    default:
        throw std::logic_error("unsupported ast type: " + std::to_string(n->op));
        break;
    }
}
Если запустить такое приложение, то получится следующий вывод:

Код:
8 / 3
5 - 2
3 * 3
2 + 9
11
Что говорит об отсутствии приоритетов операторов. Сейчас любое арифметическое действие имеет одинаковый с остальными приоритет. Это, конечно же, неверно. И в третьей части Джон стал городским спасателем автор обещает нам всё исправить.

Сейчас проект разросся, потому я приаттачу файлы. Это всё тот же проект с части 1, но улучшеный непоправимо. До новых встреч, друзья.

Да, это те ссылки, которые пару месяцев назад скидывал mak, но я медлительный, дошёл до них только сейчас.
 

Прикрепленные файлы:

DMA/STY

Новичок
Сообщения
54
Реакции
7
Евгений, если когда-нибудь перед вами встанет проблема: чего бы еще интересного написать в блог? Небольшое пожелание по C/C++ ( шаблоны, макросы ). Советовать же всегда легче. :)


Для начала:


МАКРОСЫ


Макросы в С и С++
https://habr.com/ru/post/546946/


Грязные трюки с макросами C++
https://habr.com/ru/post/246971/


Вред макросов для C++ кода
https://habr.com/ru/company/pvs-studio/blog/444612/


Макросы с переменным числом параметров
https://habr.com/ru/post/138150/




ШАБЛОНЫ

Основы шаблонов С++: шаблоны функций
https://habr.com/ru/post/436880/


Просто о шаблонах C++
https://habr.com/ru/post/599801/


А далее может еще дополнить чем интересным?
 
Верх Низ