Пишем простой интерпретатор на C++ с помощью TDD, часть 2

Парсер

Парсер будет реализован по алгоритму сортировочной станции, так как он достаточно прост и не нуждается в рекурсии. Сам алгоритм таков:

В начале даются пустой выходной поток и пустой стек. Начнём читать токены из входного потока по очереди.

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

После достижения конца входного потока, вытолкнуть все оставшиеся в стеке операторы в выходной поток. Если в нём найдено что-либо кроме операторов, то генерируем ошибку.

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

• При получении пустого списка, возвращается пустой список.
• При получении списка с одним числом, возвращается список с этим числом.
• При получении [1 + 2], возвращается [1 2 +].
• При получении [1 + 2 + 3], возвращается [1 2 + 3 +], так как оператор + является лево ассоциативным.
• При получении [1 * 2 + 3], возвращается [1 2 * 3 +].
• При получении [1 + 2 * 3], возвращается [1 2 3 * +], так как оператор * имеет больший приоритет.

Со скобками и ошибками разберёмся позднее. Итак, напишем первый тест из списка.

TEST_CLASS(ParserTests) { public:     TEST_METHOD(Should_return_empty_list_when_put_empty_list) {         Tokens tokens = Parser::Parse({});         Assert::IsTrue(tokens.empty());     } }; 

Как и в прошлый раз, парсер будет представлять собой свободную функцию в пространстве имён Parser.

namespace Parser { inline Tokens Parse(const Tokens &) { throw std::exception(); } } // namespace Parser 

Заставим тест проходить применив ({} → nil).

inline Tokens Parse(const Tokens &) {     return{}; } 

Следующий тест почти аналогичен предыдущему.

    TEST_METHOD(Should_parse_single_number) {         Tokens tokens = Parser::Parse({ Token(1) });         AssertRange::AreEqual({ Token(1) }, tokens);     } 

Применив (constant → scalar) разберёмся и с ним.

inline Tokens Parse(const Tokens &tokens) {     return tokens; } 

• При получении пустого списка, возвращается пустой список.
• При получении списка с одним числом, возвращается список с этим числом.
• При получении [1 + 2], возвращается [1 2 +].
• …

Дальше интереснее, необходимо обработать сразу несколько токенов.

    TEST_METHOD(Should_parse_num_plus_num) {         Tokens tokens = Parser::Parse({ Token(1), Token(Operator::Plus), Token(2) });         AssertRange::AreEqual({ Token(1), Token(2), Token(Operator::Plus) }, tokens);     } 

Для начала слегка изменим функцию Parse не нарушая предыдущие тесты.

inline Tokens Parse(const Tokens &tokens) {     Tokens output;     for(const Token &token : tokens) {         output.push_back(token);     }     return output; } 

Теперь легко добавить стек для операций и заставить проходить тест.

inline Tokens Parse(const Tokens &tokens) {     Tokens output;     Tokens stack;     for(const Token &token : tokens) {         if(token.Type() == TokenType::Number) {             output.push_back(token);         }         else {             stack.push_back(token);         }     }     std::copy(stack.crbegin(), stack.crend(), std::back_inserter(output));     return output; } 

• При получении [1 + 2], возвращается [1 2 +].
• При получении [1 + 2 + 3], возвращается [1 2 + 3 +], так как оператор + является лево ассоциативным.
• …

    TEST_METHOD(Should_parse_two_additions) {         Tokens tokens = Parser::Parse({ Token(1), Token(Operator::Plus), Token(2), Token(Operator::Plus), Token(3) });         AssertRange::AreEqual({ Token(1), Token(2), Token(Operator::Plus), Token(3), Token(Operator::Plus) }, tokens);     } 

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

inline Tokens Parse(const Tokens &tokens) {     Tokens output, stack;     auto popAll = [&]() { while(!stack.empty()) {         output.push_back(stack.back());         stack.pop_back();     }};     for(const Token &token : tokens) {         if(token.Type() == TokenType::Operator) {             popAll();             stack.push_back(token);             continue;         }         output.push_back(token);     }     popAll();     return output; } 

Разберёмся с приоритетом операторов. Добавим тест на функцию, которая будет определять приоритет переданного в неё оператора.

• При получении [1 + 2 + 3], возвращается [1 2 + 3 +], так как оператор + является лево ассоциативным.
• Пары операторов +- и */ должны иметь равные приоритеты.
• Приоритет операторов + и — должен быть меньше, чем у * и /
• …

    TEST_METHOD(Should_get_same_precedence_for_operator_pairs) {         Assert::AreEqual(Parser::PrecedenceOf(Operator::Plus), Parser::PrecedenceOf(Operator::Minus));         Assert::AreEqual(Parser::PrecedenceOf(Operator::Mul), Parser::PrecedenceOf(Operator::Div));     } 

Добавим метод PrecedenceOf в пространство имён Parser и применим ({} → nil).

inline int PrecedenceOf(Operator) { return 0; } 

Тест проходит, переходим к следующему.

    TEST_METHOD(Should_get_greater_precedence_for_multiplicative_operators) {         Assert::IsTrue(Parser::PrecedenceOf(Operator::Mul) > Parser::PrecedenceOf(Operator::Plus));     } 

Применим (unconditional → if).

inline int PrecedenceOf(Operator op) {     return (op == Operator::Mul || op == Operator::Div) ? 1 : 0; } 

• Пары операторов +- и */ должны иметь равные приоритеты.
• Приоритет операторов + и — должен быть меньше, чем у * и /
• При получении [1 * 2 + 3], возвращается [1 2 * 3 +].
• При получении [1 + 2 * 3], возвращается [1 2 3 * +], так как оператор * имеет больший приоритет.

Начнём с последнего теста, так как он кажется более простым.

    TEST_METHOD(Should_parse_add_and_mul) {         Tokens tokens = Parser::Parse({ Token(1), Token(Operator::Plus), Token(2), Token(Operator::Mul), Token(3) });         AssertRange::AreEqual({ Token(1), Token(2), Token(3), Token(Operator::Mul), Token(Operator::Plus) }, tokens);     } 

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

inline Tokens Parse(const Tokens &tokens) {     Tokens output, stack;     auto popToOutput = [&output, &stack](auto whenToEnd) {         while(!stack.empty() && !whenToEnd(stack.back())) {             output.push_back(stack.back());             stack.pop_back();         }};     for(const Token ¤t : tokens) {         if(current.Type() == TokenType::Operator) {             popToOutput([&](Operator top) { return PrecedenceOf(top) < PrecedenceOf(current); });             stack.push_back(current);             continue;         }         output.push_back(current);     }     popToOutput([](auto) { return false; });     return output; } 

Для проверки алгоритма добавим последний тест, немного его усложнив. Попробуем обработать сложное выражение с несколькими операциями.

    TEST_METHOD(Should_parse_complex_experssion) {         // 1 + 2 / 3 - 4 * 5 = 1 2 3 / + 4 5 * -         Tokens tokens = Parser::Parse({             Token(1), Token(Operator::Plus), Token(2), Token(Operator::Div), Token(3),             Token(Operator::Minus), Token(4), Token(Operator::Mul), Token(5)         });         AssertRange::AreEqual({             Token(1), Token(2), Token(3), Token(Operator::Div), Token(Operator::Plus),             Token(4), Token(5), Token(Operator::Mul), Token(Operator::Minus)         }, tokens);     } 

Он сразу же проходит. Прохождение тестов без написания какого-либо кода, является сомнительной практикой, но иногда полезно для поведения, в котором ты не уверен полностью. Функция Parse, написанная в функциональном стиле, конечно, коротка и лаконична, но плохо расширяема. Как и в прошлый раз, выделим отдельный класс в пространство имён Detail и перенесём в него всю функциональность парсера, оставив функцию Parse в качестве фасада. Проделать это достаточно легко, так как не нужно бояться что-либо сломать.

inline Tokens Parse(const Tokens &tokens) {     Detail::ShuntingYardParser parser(tokens);     parser.Parse();     return parser.Result(); } 

namespace Detail {  class ShuntingYardParser { public:     ShuntingYardParser(const Tokens &tokens) : m_current(tokens.cbegin()), m_end(tokens.cend()) {}      void Parse() {         for(; m_current != m_end; ++m_current) {             ParseCurrentToken();         }         PopToOutputUntil(StackIsEmpty);     }      const Tokens &Result() const { return m_output; }  private:     static bool StackIsEmpty() { return false; }      void ParseCurrentToken() {         switch(m_current->Type()) {             case TokenType::Operator:                 ParseOperator();                 break;             case TokenType::Number:                 ParseNumber();                 break;             default:                 throw std::out_of_range("TokenType");         }     }      void ParseOperator() {         PopToOutputUntil([this]() { return PrecedenceOf(m_stack.back()) < PrecedenceOf(*m_current); });         m_stack.push_back(*m_current);     }      void ParseNumber() {         m_output.push_back(*m_current);     }      template<class T>     void PopToOutputUntil(T whenToEnd) {         while(!m_stack.empty() && !whenToEnd()) {             m_output.push_back(m_stack.back());             m_stack.pop_back();         }     }      Tokens::const_iterator m_current;     Tokens::const_iterator m_end;     Tokens m_output;     Tokens m_stack; };  } // namespace Detail 

Добавим поддержку скобок. Составим список тестов, начиная с самого простого для реализации.

• При получении [(1)], возвращается [1].
• При получении [(1 + 2) * 3], возвращается [1 2 + 3 *].
• При получении [1)], генерируется исключение.
• При получении [(1], генерируется исключение.

Добавим первый тест.

    TEST_METHOD(Should_skip_paren_around_number) {         Tokens tokens = Parser::Parse({ Token(Operator::LParen), Token(1), Token(Operator::RParen) });         AssertRange::AreEqual({ Token(1) }, tokens);     } 

Так как в данный момент мы не отличаем скобки от других операторов, то он не проходит. Внесём небольшое изменение (unconditional → if) в метод ParseOperator.

    void ParseOperator() {         const Operator currOp = *m_current;         switch(currOp) {             case Operator::LParen:                 break;             case Operator::RParen:                 break;             default:                 PopToOutputUntil([&]() { return PrecedenceOf(m_stack.back()) < PrecedenceOf(currOp); });                 m_stack.push_back(*m_current);                 break;         }     } 

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

static const Token plus(Operator::Plus), minus(Operator::Minus); static const Token mul(Operator::Mul), div(Operator::Div); static const Token pLeft(Operator::LParen), pRight(Operator::RParen); static const Token _1(1), _2(2), _3(3), _4(4), _5(5); 

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

    TEST_METHOD(Should_parse_expression_with_parens_in_beginning) {         Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, _3 });         AssertRange::AreEqual({ _1, _2, plus, _3, mul }, tokens);     } 

Изменим метод ParseOperator класса ShuntingYardParser таким образом, чтобы он соответствовал описанному выше алгоритму.

    void ParseOperator() {         switch(*m_current) {             case Operator::LParen:                 m_stack.push_back(*m_current);                 break;             case Operator::RParen:                 PopToOutputUntil([this]() { return LeftParenOnTop(); });                 m_stack.pop_back();                 break;             default:                 PopToOutputUntil([this]() { return LeftParenOnTop() || OperatorWithLessPrecedenceOnTop(); });                 m_stack.push_back(*m_current);                 break;         }     }      bool OperatorWithLessPrecedenceOnTop() const {         return PrecedenceOf(m_stack.back()) < PrecedenceOf(*m_current);     }      bool LeftParenOnTop() const {         return static_cast<Operator>(m_stack.back()) == Operator::LParen;     } 

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

    TEST_METHOD(Should_throw_when_opening_paren_not_found) {         Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ _1, pRight }); });     } 

Добавим проверку на наличие открывающий скобки при обработке закрывающей скобки.

            …             case Operator::RParen:                 PopToOutputUntil([this]() { return LeftParenOnTop(); });                 if(m_stack.empty() || m_stack.back() != Operator::LParen) {                     throw std::logic_error("Opening paren not found.");                 }                 m_stack.pop_back();                 break; 

Теперь тест на отсутствие закрывающей скобки.

    TEST_METHOD(Should_throw_when_closing_paren_not_found) {         Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ pLeft, _1 }); });     } 

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

    void Parse() {         for(; m_current != m_end; ++m_current) {             ParseCurrentToken();         }         PopToOutputUntil([this]() {             if(m_stack.back() == Token(Operator::LParen)) {                 throw std::logic_error("Closing paren not found.");             }             return false;         });     } 

Итак, все тесты проходят, можно привести код в классе ShuntingYardParser в порядок.

class ShuntingYardParser { public:     ShuntingYardParser(const Tokens &tokens) : m_current(tokens.cbegin()), m_end(tokens.cend()) {}      void Parse() {         for(; m_current != m_end; ++m_current) {             ParseCurrentToken();         }         PopToOutputUntil([this]() {return StackHasNoOperators(); });     }      const Tokens &Result() const { return m_output; }  private:     void ParseCurrentToken() {         switch(m_current->Type()) {             case TokenType::Operator:                 ParseOperator();                 break;             case TokenType::Number:                 ParseNumber();                 break;             default: throw std::out_of_range("TokenType");         }     }      bool StackHasNoOperators() const {         if(m_stack.back() == Token(Operator::LParen)) {             throw std::logic_error("Closing paren not found.");         }         return false;     }      void ParseOperator() {         switch(*m_current) {             case Operator::LParen:                 PushCurrentToStack();                 break;             case Operator::RParen:                 PopToOutputUntil([this]() { return LeftParenOnTop(); });                 PopLeftParen();                 break;             default:                 PopToOutputUntil([this]() { return LeftParenOnTop() || OperatorWithLessPrecedenceOnTop(); });                 PushCurrentToStack();                 break;         }     }      void PushCurrentToStack() {         return m_stack.push_back(*m_current);     }      void PopLeftParen() {         if(m_stack.empty() || m_stack.back() != Operator::LParen) {             throw std::logic_error("Opening paren not found.");         }         m_stack.pop_back();     }      bool OperatorWithLessPrecedenceOnTop() const {         return PrecedenceOf(m_stack.back()) < PrecedenceOf(*m_current);     }      bool LeftParenOnTop() const {         return static_cast<Operator>(m_stack.back()) == Operator::LParen;     }      void ParseNumber() {         m_output.push_back(*m_current);     }      template<class T>     void PopToOutputUntil(T whenToEnd) {         while(!m_stack.empty() && !whenToEnd()) {             m_output.push_back(m_stack.back());             m_stack.pop_back();         }     }      Tokens::const_iterator m_current, m_end;     Tokens m_output, m_stack; }; 

Для уверенности можно написать тест на разбор сложного выражения.

    TEST_METHOD(Should_parse_complex_experssion_with_paren) {         // (1+2)*(3/(4-5)) = 1 2 + 3 4 5 - / *         Tokens tokens = Parser::Parse({ pLeft, _1, plus, _2, pRight, mul, pLeft, _3, div, pLeft, _4, minus, _5, pRight, pRight });         AssertRange::AreEqual({ _1, _2, plus, _3, _4, _5, minus, div, mul }, tokens);     } 

Он сразу проходит, что и было ожидаемо.

Код к статье на GitHub. Названия коммитов и их порядок соответствуют тестам и рефакторингам, описанным выше. Окончанию первой части соответствует коммит «ParserTests Should_parse_complex_experssion_with_paren».

В следующий части будет рассмотрена разработка вычислителя и фасада для всего интерпретатора, а также рефакторинг всего кода для устранения дублирования.