Unrul August 4, 2014 at 17:36

Writing a Simple C ++ Interpreter Using TDD, Part 2

Tutorial

In the first part, a lexer was written . Next, the development of the parser will be considered.

Parser

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

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

If this is a 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 a bracket appears at its top, or an operator with a lower priority.
If this is an opening bracket, then put it on the stack.
If this is a closing bracket, then we 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 bracket 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’s figure out what tests you might need to get started.

When an empty list is received, an empty list is returned.
When receiving a list with one number, a list with that number is returned.
Upon receipt of [1 + 2], [1 2 +] is returned.
Upon receipt of [1 + 2 + 3], [1 2 + 3 +] is returned, since the + operator is left-associative.
Upon receipt of [1 * 2 + 3], [1 2 * 3 +] is returned.
Upon receipt of [1 + 2 * 3], [1 2 3 * +] is returned, since the * operator has a 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 namespace Parser.

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 next 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) we will deal with it.

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

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

More interesting, you need 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 with, slightly change the function Parsewithout 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 make the test 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], [1 2 +] is returned.~~
Upon receipt of [1 + 2 + 3], [1 2 + 3 +] is returned, 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 fails, since all operators are located at the end of the list. We will transfer everything from the stack to the output list each time an operator is detected.

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

We will deal with the priority of the operators. Add a test for a function that will determine the priority of the operator passed to it.

~~Upon receipt of [1 + 2 + 3], [1 2 + 3 +] is returned, since the + operator is left-associative.~~
The pairs of operators + - and * / must have equal priorities.
The priority of the operators + and - should 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, go to the next.

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

We apply (unconditional → if).

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

~~The pairs of operators + - and * / must have equal priorities.~~
~~The priority of the operators + and - should be less than that of * and /~~
Upon receipt of [1 * 2 + 3], [1 2 * 3 +] is returned.
Upon receipt of [1 + 2 * 3], [1 2 3 * +] is returned, since the * operator has a 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, since the parser should not push operators with lower priority from the stack. Add a predicate to the lambda that pushes operations from the stack 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, complicating it a bit. Let's try to process 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 passes right away. Passing tests without writing any code is a dubious practice, but sometimes useful for behavior that you are not completely sure about. A function Parsewritten in a functional style is, of course, short and concise, but poorly extensible. Like last time, select a separate class in the namespace Detailand transfer all the parser functionality into it, leaving the function Parseas a facade. This is easy enough to do, as you don’t need to be afraid to break something.

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
    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 parenthesis support. Let's make a list of tests, starting with the simplest to implement.

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

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 pass. Make a small change (unconditional → if) to the method 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;
        }
    }

Before adding the next test, we will refactor the currently written tests. Create static instances of tokens 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 more compact and understandable.

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

Change the ParseOperatorclass method ShuntingYardParserso that it matches 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(m_stack.back()) == Operator::LParen;
    }

We do not have any check on the closure of parentheses for opening brackets. To test the generation of exceptions, the class Asserthas a special method ExpectExceptionthat takes as the template parameter the type of exception that should be thrown.

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

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

            …
            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 a test for the absence of a closing parenthesis.

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

This situation can be determined by the presence of opening brackets in the stacks at the end of the 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 tests pass, you can put the code in the class ShuntingYardParserin 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(m_stack.back()) == Operator::LParen;
    }
    void ParseNumber() {
        m_output.push_back(*m_current);
    }
    template
    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;
};

To be sure, 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, as was expected.

All code at the moment:

Interpreter.h

#pragma once;
#include 
#include 
#include 
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(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(token));
        case TokenType::Operator:
            return ToString(static_cast(token));
        default:
            throw std::out_of_range("TokenType");
    }
}
typedef std::vector 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(o); });
    }
    void ScanOperator() {
        m_result.push_back(static_cast(*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(m_stack.back()) == Operator::LParen;
    }
    void ParseNumber() {
        m_output.push_back(*m_current);
    }
    template
    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
static void AreEqual(initializer_list 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(*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::Plus, token);
    }
    TEST_METHOD(Should_get_number_value_from_number_token) {
        Token token(1.23);
        Assert::AreEqual(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([]() {Parser::Parse({ _1, pRight }); });
    }
    TEST_METHOD(Should_throw_when_closing_paren_not_found) {
        Assert::ExpectException([]() {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);
    }
};
}

Code for the article on GitHub . The names of the commits and their order correspond to the tests and refactoring described above. The end of the second part corresponds to the label “End_second_part”.

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

Tags:

Writing a Simple C ++ Interpreter Using TDD, Part 2

Parser

Also popular now: