Writing a simple interpreter in C ++ using TDD, part 2

In the first part was written lexer . Further development of the parser will be considered.

Parser

The parser will be implemented using the sorting station algorithm, since it is quite simple and does not need recursion. The algorithm itself is as follows:

At the beginning, an empty output stream and an empty stack are given. Let's start reading tokens from the input stream in turn.
')

If this number, then pass it to the output stream.
If this is a left-associative operator, then we push the tokens from the stack into the output stream until it is empty, or the bracket does not meet its top, or the operator with lower priority.
If this is an opening bracket, then put it on the stack.
If this is a closing parenthesis, then push the tokens from the stack into the output stream until the opening bracket is detected. Push the opening bracket from the stack, but do not pass it to the output stream. If the stack is empty and the parenthesis is not found, then we generate an error.

After reaching the end of the input stream, push all the remaining operators on the stack into the output stream. If anything other than operators is found in it, then we generate an error.

Let us estimate what tests may be needed to start.

When an empty list is received, an empty list is returned.
When getting a list with one number, it returns a list with that number.
Upon receipt of [1 + 2], it returns [1 2 +].
Upon receipt of [1 + 2 + 3], it returns [1 2 + 3 +], since the + operator is left associative.
Upon receipt of [1 * 2 + 3], [1 2 * 3 +] is returned.
When receiving [1 + 2 * 3], [1 2 3 * +] is returned, because the * operator has higher priority.

We will deal with brackets and errors later. So, we will write the first test from the list.

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

Like last time, the parser will be a free function in the Parser namespace.

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

Make the test pass by applying ({} → nil).

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

The following test is almost the same as the previous one.

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

Applying (constant → scalar) let's deal with it.

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

~~When an empty list is received, an empty list is returned.~~
~~When getting a list with one number, it returns a list with that number.~~
Upon receipt of [1 + 2], it returns [1 2 +].
...

Further more interesting, it is necessary to process several tokens at once.

  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); }

To begin, slightly change the Parse function without violating previous tests.

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

Now it’s easy to add a stack for operations and get a test to pass

 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; }

~~Upon receipt of [1 + 2], it returns [1 2 +].~~
Upon receipt of [1 + 2 + 3], it returns [1 2 + 3 +], since the + operator is left associative.
...

  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); }

The test does not pass, since all operators are located at the end of the list. We will throw everything from the stack to the output list with each detection of the operator.

 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; }

Understand the priority of operators. Add a test for the function that will determine the priority of the operator transferred to it.

~~Upon receipt of [1 + 2 + 3], it returns [1 2 + 3 +], since the + operator is left associative.~~
Pairs of operators + - and * / should have equal priorities.
The precedence of the + and - operators must be less than that of * and /
...

  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)); }

Add the PrecedenceOf method to the Parser namespace and apply ({} → nil).

 inline int PrecedenceOf(Operator) { return 0; }

The test passes, proceed to the next.

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

Apply (unconditional → if).

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

~~Pairs of operators + - and * / should have equal priorities.~~
~~The precedence of the + and - operators must be less than that of * and /~~
Upon receipt of [1 * 2 + 3], [1 2 * 3 +] is returned.
When receiving [1 + 2 * 3], [1 2 3 * +] is returned, because the * operator has higher priority.

Let's start with the last test, as it seems simpler.

  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); }

It does not pass, because the parser should not push operators with lower priority from the stack. Add to the lambda, pushing operations from the stack, a predicate that determines when to stop.

 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; }

To test the algorithm, add the last test, making it a bit more complicated. Let's try to handle a complex expression with several operations.

  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); }

He immediately passes. Passing tests without writing any code is a dubious practice, but sometimes useful for behaviors in which you are not completely sure. Function Parse , written in a functional style, of course, is short and concise, but poorly expandable. Like last time, we will allocate a separate class into the Detail namespace and transfer all the functionality of the parser into it, leaving the Parse function as the facade. To do this is quite easy, because you do not need to be afraid to break anything.

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

Class Detail :: ShuntingYardParser

 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

Add support for brackets. Make a list of tests, starting with the simplest to implement.

Upon receipt of [(1)], [1] is returned.
Upon receipt of [(1 + 2) * 3], [1 2 + 3 *] is returned.
Upon receipt of [1)], an exception is generated.
Upon receipt of [(1], an exception is generated.

Add the first test.

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

Since at the moment we do not distinguish brackets from other operators, it does not work. Let's make a small change (unconditional → if) to the ParseOperator method.

  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; } }

Before adding the next test, we will refactor the tests currently written. Create static token instances for operators and some numbers. This will significantly reduce the amount of code in the tests.

 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);

As a result, the next test will look much smaller and clearer.

  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 method of the ParseOperator class to match the algorithm described above.

  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; }

We do not have any test for matching the closing brackets with the opening. To test the generation of exceptions, the Assert class has a special method ExpectException , which accepts the type of exception as a template parameter, which must be generated.

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

Add a check for the presence of an opening bracket when processing the closing bracket.

  … 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;

Now test for the absence of a closing bracket.

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

This situation can be identified by the presence of opening parentheses in stacks at the end of parsing.

  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; }); }

So, all the tests pass, you can put the code in the class ShuntingYardParser in order.

ShuntingYardParser class after refactoring

 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; };

For confidence, you can write a test to parse a complex expression.

  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); }

He immediately passes, which was expected.

All code at the moment:

Interpreter.h

 #pragma once; #include <vector> #include <wchar.h> #include <algorithm> namespace Interpreter { enum class Operator : wchar_t { Plus = L'+', Minus = L'-', Mul = L'*', Div = L'/', LParen = L'(', RParen = L')', }; inline std::wstring ToString(const Operator &op) { return{ static_cast<wchar_t>(op) }; } enum class TokenType { Operator, Number }; inline std::wstring ToString(const TokenType &type) { switch(type) { case TokenType::Operator: return L"Operator"; case TokenType::Number: return L"Number"; default: throw std::out_of_range("TokenType"); } } class Token { public: Token(Operator op) :m_type(TokenType::Operator), m_operator(op) {} Token(double num) :m_type(TokenType::Number), m_number(num) {} TokenType Type() const { return m_type; } operator Operator() const { if(m_type != TokenType::Operator) { throw std::logic_error("Should be operator token."); } return m_operator; } operator double() const { if(m_type != TokenType::Number) { throw std::logic_error("Should be number token."); } return m_number; } friend inline bool operator==(const Token &left, const Token &right) { if(left.m_type == right.m_type) { switch(left.m_type) { case Interpreter::TokenType::Operator: return left.m_operator == right.m_operator; case Interpreter::TokenType::Number: return left.m_number == right.m_number; default: throw std::out_of_range("TokenType"); } } return false; } private: TokenType m_type; union { Operator m_operator; double m_number; }; }; inline std::wstring ToString(const Token &token) { switch(token.Type()) { case TokenType::Number: return std::to_wstring(static_cast<double>(token)); case TokenType::Operator: return ToString(static_cast<Operator>(token)); default: throw std::out_of_range("TokenType"); } } typedef std::vector<Token> Tokens; namespace Lexer { namespace Detail { class Tokenizer { public: Tokenizer(const std::wstring &expr) : m_current(expr.c_str()) {} void Tokenize() { while(!EndOfExperssion()) { if(IsNumber()) { ScanNumber(); } else if(IsOperator()) { ScanOperator(); } else { MoveNext(); } } } const Tokens &Result() const { return m_result; } private: bool EndOfExperssion() const { return *m_current == L'\0'; } bool IsNumber() const { return iswdigit(*m_current) != 0; } void ScanNumber() { wchar_t *end = nullptr; m_result.push_back(wcstod(m_current, &end)); m_current = end; } bool IsOperator() const { auto all = { Operator::Plus, Operator::Minus, Operator::Mul, Operator::Div, Operator::LParen, Operator::RParen }; return std::any_of(all.begin(), all.end(), [this](Operator o) {return *m_current == static_cast<wchar_t>(o); }); } void ScanOperator() { m_result.push_back(static_cast<Operator>(*m_current)); MoveNext(); } void MoveNext() { ++m_current; } const wchar_t *m_current; Tokens m_result; }; } // namespace Detail inline Tokens Tokenize(const std::wstring &expr) { Detail::Tokenizer tokenizer(expr); tokenizer.Tokenize(); return tokenizer.Result(); } } // namespace Lexer namespace Parser { inline int PrecedenceOf(Operator op) { return (op == Operator::Mul || op == Operator::Div) ? 1 : 0; } 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([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; Tokens::const_iterator m_end; Tokens m_output; Tokens m_stack; }; } // namespace Detail inline Tokens Parse(const Tokens &tokens) { Detail::ShuntingYardParser parser(tokens); parser.Parse(); return parser.Result(); } } // namespace Parser } // namespace Interpreter

InterpreterTests.cpp

 #include "stdafx.h" #include "CppUnitTest.h" #include "Interpreter.h" #pragma warning(disable: 4505) namespace InterpreterTests { using namespace Microsoft::VisualStudio::CppUnitTestFramework; using namespace Interpreter; using namespace std; namespace AssertRange { template<class T, class ActualRange> static void AreEqual(initializer_list<T> expect, const ActualRange &actual) { auto actualIter = begin(actual); auto expectIter = begin(expect); Assert::AreEqual(distance(expectIter, end(expect)), distance(actualIter, end(actual)), L"Size differs."); for(; expectIter != end(expect) && actualIter != end(actual); ++expectIter, ++actualIter) { auto message = L"Mismatch in position " + to_wstring(distance(begin(expect), expectIter)); Assert::AreEqual<T>(*expectIter, *actualIter, message.c_str()); } } } // namespace AssertRange 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_CLASS(LexerTests) { public: TEST_METHOD(Should_return_empty_token_list_when_put_empty_expression) { Tokens tokens = Lexer::Tokenize(L""); Assert::IsTrue(tokens.empty()); } TEST_METHOD(Should_tokenize_single_plus_operator) { Tokens tokens = Lexer::Tokenize(L"+"); AssertRange::AreEqual({ plus }, tokens); } TEST_METHOD(Should_tokenize_single_digit) { Tokens tokens = Lexer::Tokenize(L"1"); AssertRange::AreEqual({ _1 }, tokens); } TEST_METHOD(Should_tokenize_floating_point_number) { Tokens tokens = Lexer::Tokenize(L"12.34"); AssertRange::AreEqual({ 12.34 }, tokens); } TEST_METHOD(Should_tokenize_plus_and_number) { Tokens tokens = Lexer::Tokenize(L"+12.34"); AssertRange::AreEqual({ plus, Token(12.34) }, tokens); } TEST_METHOD(Should_skip_spaces) { Tokens tokens = Lexer::Tokenize(L" 1 + 12.34 "); AssertRange::AreEqual({ _1, plus, Token(12.34) }, tokens); } TEST_METHOD(Should_tokenize_complex_experssion) { Tokens tokens = Lexer::Tokenize(L"1+2*3/(4-5)"); AssertRange::AreEqual({ _1, plus, _2, mul, _3, div, pLeft, _4, minus, _5, pRight }, tokens); } }; TEST_CLASS(TokenTests) { public: TEST_METHOD(Should_get_type_for_operator_token) { Token opToken(Operator::Plus); Assert::AreEqual(TokenType::Operator, opToken.Type()); } TEST_METHOD(Should_get_type_for_number_token) { Token numToken(1.2); Assert::AreEqual(TokenType::Number, numToken.Type()); } TEST_METHOD(Should_get_operator_code_from_operator_token) { Token token(Operator::Plus); Assert::AreEqual<Operator>(Operator::Plus, token); } TEST_METHOD(Should_get_number_value_from_number_token) { Token token(1.23); Assert::AreEqual<double>(1.23, token); } }; TEST_CLASS(ParserTests) { public: TEST_METHOD(Should_return_empty_list_when_put_empty_list) { Tokens tokens = Parser::Parse({}); Assert::IsTrue(tokens.empty()); } TEST_METHOD(Should_parse_single_number) { Tokens tokens = Parser::Parse({ _1 }); AssertRange::AreEqual({ _1 }, tokens); } TEST_METHOD(Should_parse_num_plus_num) { Tokens tokens = Parser::Parse({ _1, plus, _2 }); AssertRange::AreEqual({ _1, _2, plus }, tokens); } TEST_METHOD(Should_parse_two_additions) { Tokens tokens = Parser::Parse({ _1, plus, _2, plus, _3 }); AssertRange::AreEqual({ _1, _2, plus, _3, plus }, tokens); } 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)); } TEST_METHOD(Should_get_greater_precedence_for_multiplicative_operators) { Assert::IsTrue(Parser::PrecedenceOf(Operator::Mul) > Parser::PrecedenceOf(Operator::Plus)); } TEST_METHOD(Should_parse_add_and_mul) { Tokens tokens = Parser::Parse({ _1, plus, _2, mul, _3 }); AssertRange::AreEqual({ _1, _2, _3, mul, plus }, tokens); } TEST_METHOD(Should_parse_complex_experssion) { Tokens tokens = Parser::Parse({ _1, plus, _2, div, _3, minus, _4, mul, _5 }); AssertRange::AreEqual({ _1, _2, _3, div, plus, _4, _5, mul, minus }, tokens); } TEST_METHOD(Should_skip_parens_around_number) { Tokens tokens = Parser::Parse({ pLeft, _1, pRight }); AssertRange::AreEqual({ _1 }, tokens); } 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); } TEST_METHOD(Should_throw_when_opening_paren_not_found) { Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ _1, pRight }); }); } TEST_METHOD(Should_throw_when_closing_paren_not_found) { Assert::ExpectException<std::logic_error>([]() {Parser::Parse({ pLeft, _1 }); }); } 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); } }; }

The code for the article on GitHub . The names of commits and their order correspond to the tests and refactoring described above. The end of the second part corresponds to the label "End of the second part"

In the next part, we will consider the development of a calculator and a facade for the entire interpreter, as well as refactoring of the entire code to eliminate duplication.

Source: https://habr.com/ru/post/232081/

All Articles

Writing a simple interpreter in C ++ using TDD, part 2

Parser

More articles: