Многие из нас проходили собеседования при трудоустройстве. И не понаслышке знают каким стрессом являются тестовые задания для кандидата перед принятием в штат. Если говорить о секторе высоких технологий, то наиболее частым тестовым заданием при собеседовании на должность разработчика является программирование калькулятора. Бывают и другие варианты, например разработка календаря, но поскольку компьютер в основном предназначен для решения вычислительных задач, то далее будет рассматриваться реализация простейшего калькулятора, поддерживающего базовые математические операции.

Задача

Требуется разработать программу, которая вычисляет значения операций сложения, вычитания, умножения и деления, при этом учитывая приоритеты операций и скобок. Также нужно обеспечить высокую точность вычислений, при этом вывод значения должен содержать до двух знаков после запятой.

Требования

Решение должно работать на всех известных платформах, включая ОС Windows, MacOS, Ubuntu и т.д., а также поддерживать архитектуры arm, x86-64, x86. Также необходима возможность компиляции исходного кода на всех перечисленных платформах. Помимо этого, требуется максимальная производительность, другими словами, в программе должны быть применены наиболее популярные и известные подходы для оптимизации вычислений.

Интсрументарий

Для того, чтобы удовлетворить требования к компиляции проекта, в качестве системы сборки будет использована программа CMake, свободно распространяющаяся и доступная на указанных платформах.

Лучший способ учесть требования к архитектуре процессора и производительности - использование языка программирования C++ (как следствие компилятора clang++) и виртуальной машины llvm с её широкими возможностями в области оптимизации вычислений. Перечисленные инструменты также распространяются свободно и могут быть использованы на приведенных выше архитектурах процессоров.

Архитектура

Ядро программы будет состоять из следующих компонентов

1. TokensParser

2. SyntacticAnalyzer

3. CodeGenerator

4. Calculator

TokensParser принимает в качестве входных данных строку с выражением, подлежащем вычислению. После чего разбирает это выражение на составляющие - так называемые токены. Использование токенов упрощает дальнейший анализ выражения.

SyntacticAnalyzer выполняет анализ полученных на предыдущем этапе токенов и на их основе строит абстрактное синтаксическое дерево выражения. Правила, по которым составляется абстрактное синтаксическое дерево определены в грамматике калькулятора.

CodeGenerator выполняет генерацию промежуточного представления (кода) для последующей компиляции с помощью llvm.

Calculator объединяет и координирует работу всех приведенных выше модулей, выполняя вычисление значения выражения.

TokensParser

Достаточно тривиальный сервис, который посимвольно считывает исходную строку текста с тем, чтобы определить, какой токен сформировать в результате.

class TokensParser {
public:
    TokensParser(string source);

    Token getToken();

private:
    stringstream stream;

    map<char, Operator> operators {
        { '+', Operator::plus },
        { '-', Operator::minus },
        { '*', Operator::multiplication },
        { '/', Operator::division }
    };

    map<char, Punctuator> punctuators {
        { '(', Punctuator::left_parenthesis },
        { ')', Punctuator::right_parenthesis }
    };

    char getCharacter();
    double getNumber(char character);
    optional<Operator> getOperator(char character);
    optional<Punctuator> getPunctuator(char character);
};

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

class Token {
public:
    enum class Kind {
        number,
        _operator,
        punctuator,
        endOfInput,
        unknown
    };

    Token(Kind kind);
    Token(Kind kind, double value);
    Token(Operator op);
    Token(Punctuator punctuator);

    Kind getKind() const;
    double getNumber() const;
    Operator getOperator() const;
    Punctuator getPunctuator() const;

private:
    Kind kind;
    optional<double> number;
    optional<Operator> _operator;
    optional<Punctuator> punctuator;
};

SyntacticAnalyzer

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

class SyntacticAnalyzer {
    public:
        SyntacticAnalyzer(TokensParser& tokensParser);

        shared_ptr<Expression> parse();

    private:
        using Precedence = int;

        TokensParser& tokensParser;

        shared_ptr<Expression> parseExpression();
        shared_ptr<Expression> parseExpression(Precedence precedence, shared_ptr<Expression> lhs, shared_ptr<BinaryOperator> binaryOperator);
        shared_ptr<Expression> parseUnaryExpression();
        shared_ptr<UnaryOperator> parseUnaryOperator(Token token);
        shared_ptr<BinaryOperator> parseBinaryOperator(Token token);
        shared_ptr<Operand> parseOperand(Token token);
        Precedence getPrecedence(Token token);
        Precedence getPrecedence(Operator op);
        Precedence getPrecedence(Punctuator punctuator);
        Token getToken();
    };

Как уже говорилось, абстрактное синтаксическое дерево реализовано с использованием наследования, поэтому базовым компонентом дерева является узел, который может удерживать ссылку на себе подобные узлы. Раз уж количество узлов большое, они не будут приведены в данной статье. Вместо этого читателю предлагается ознакомиться с исходным кодом проекта для детального изучения.

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

CodeGenerator

Компонент, который при проходе по абстрактному синтаксическому дереву выполнят генерацию так называемого промежуточного представления (кода) llvm. После завершения прохода, выполняется проверка на корректность продукта генерации, а также оптимизация уже сгенерированного кода. Таким образом достигается максимальная производительность, о которой было упомянуто в требованиях к калькулятору.

class CodeGenerator {
public:
    CodeGenerator(DataLayout& dataLayout);

    ThreadSafeModule generate(string functionName, shared_ptr<Expression> expression);

private:
    unique_ptr<LLVMContext> context;
    unique_ptr<Module> module;
    IRBuilder<> builder;
    unique_ptr<legacy::FunctionPassManager> passManager;

    Value* generate(shared_ptr<Expression> expression);
    Value* generate(shared_ptr<UnaryExpression> unaryExpression);
};

Calculator

Финальный компонент, который замыкает четверку, составляющую ядро системы. Для своей работы ему требуются все из перечисленных ранее сервисов. Его введение обусловлено необходимостью тестирования всего решения, а также переиспользования в любой точке программы.

class Calculator {
public:
    Calculator();

    double calculate(string expression);

private:
    unique_ptr<JIT> jit;
};

Здесь нужно обратить внимание на наличие JIT - модуля, который выполняет компиляцию промежуточного представления llvm в реальном времени. Именно с помощью этого модуля выполняются вычисления выражений.

Заключение

Возвращаясь к истокам программирования можно проследить общие черты, характерные при реализации вычислительных программ, будь то обычный калькулятор или более сложный компилятор. Эти черты можно описать как наличие парсера токенов (часто называется Lex, Lexer, Scanner) и парсера абстрактного синтаксического дерева (часто называется AST, SyntacticAnalyzer).

И еще, можно указать на большую перспективу в плане расширения возможностей представленного калькулятора. Поскольку в проекте используется llvm, то не составит особого труда добавить общеизвестные методы, такие как вычисление синуса или косинуса, степени числа и т.д. Но такой материал выходит за рамки статьи и предлагается к самостоятельному изучению.

Ссылки

1. Оригинал статьи

2. Исходный код проекта, зеркало

3. LLVM project

4. Learn LLVM 12: A beginner's guide to learning LLVM compiler tools and core libraries with C++