Overhauled AST builder for markargs

Question

This is refactoring of the code described in the previous iteration.

Roadmap

I'm trying to follow usual compiler design:

Lexical analysis: 1, 2
Syntactical analysis: 1, 2 <---- you're here
Semantic analysis
User input
Code generation + execution

Language

It is a simple programming language for computing results of complex and long expressions. It allows declaring variables and using it inside of expressions, and providing the value for them later. It has general form of something like this

value = 12 + value2 + _b

For more lexical information, please refer to lexical analysis phase.

Production rules

E->id
E->number
E->E op E

where op is {=, +, -}.

Operator precedence

operator = has lowest precedence. Everything else equal (for now).

Associativity

Left associative.

Parser type

If I understood correctly, my parser is top-down recursive descent, with no backtracking, since no right side of the production rules have common prefix, left associative and does rightmost derivation (according to this post). Less verbose name is, I believe, top-down LR recursive descent parser.

Changes

Vastly simplified control flow.
Most of the loops are named now.
Lifted name in the expression first rule, deferred it to semantic analysis stage.
Fixed some inefficiencies in inorder_iterator with help from the review.
Moved stream operator to use std::transform with inorder_iterators, though due to the lack of const iterator, it accepts tree by non-const reference. I'll close my eyes on that for now, and fix it in the future. Noted it.
Added lexical_analyzer library as dependency, so that CMake will ensure it will be built first.
Renamed test files, since it seem to cause confusion that it is complete compiler, but it is not yet.

Code

syntax_tree_tests.cpp

#include <string>
#include <fstream>
#include <vector>
#include <iterator>
#include <iostream>
#include <map>
#include <stack>
#include <queue>
#include <sstream>

#include <token.hpp>
#include "syntax_tree.hpp"

void test_one(const std::string& inputline, const std::string& correct_answer)
{
    std::stringstream ss(inputline);
    markargs::syntax_tree tree{std::istream_iterator<markargs::token>(ss), {}};
    std::stringstream result;
    result << tree;
    if (result.str() != correct_answer)
    {
        throw std::logic_error{"tree was not build correctly for input: "
                               + inputline};
    }
}

void run_tests()
{
    std::ifstream input_file("input.txt");
    std::ifstream answers_file("answers.txt");
    if (!input_file.is_open() || !answers_file.is_open())
    {
        throw std::runtime_error{"either input or answers file cannot be opened"};
    }

    std::string inputline;
    std::string correct_answer;

    std::cout << "starting simple tests ...\n";
    unsigned int counter = 1;
    while (std::getline(input_file, inputline) && std::getline(answers_file, correct_answer))
    {
        std::cout << "running test #" << counter << '\n';
        test_one(inputline, correct_answer);
        ++counter;
    }

    std::cout << "all tests passed\n\n";
}

void run_throwing_tests()
{
    std::ifstream input_file("failing_input.txt");
    if (!input_file.is_open())
    {
        throw std::runtime_error{"failing_input.txt cannot be opened"};
    }

    unsigned int counter = 1;
    std::cout << "starting throwing tests ...\n";
    std::string input_line;
    while (std::getline(input_file, input_line))
    {
        std::cout << "running test #" << counter << '\n';
        try
        {
            //correct answer can be anything,
            //since it should throw anyway
            test_one(input_line, "");
        }
        catch(std::invalid_argument& err)
        {
            ++counter;
            continue;
        }
        throw std::logic_error{"tree didn't throw on incorrect input"};
    }
    std::cout << "all tests passed\n\n";
}

int main()
{
    using namespace markargs;

    run_tests();
    run_throwing_tests();
}

syntax_tree.hpp

#ifndef COMPILER_PARSE_TREE_HPP
#define COMPILER_PARSE_TREE_HPP

#include <string>
#include <queue>
#include <map>
#include <iosfwd>
#include <stack>
#include <set>

#include <token.hpp>


namespace markargs
{
    class syntax_tree
    {
        struct node
        {
            markargs::token tk;
            node* left_operand;
            node* right_operand;

            explicit node(const markargs::token& tk_,
                          node* left_operand_ = nullptr,
                          node* right_operand_ = nullptr);
        };

        node* root;

        std::map<std::string, int> operator_precedence;
    public:
        class inorder_iterator : public std::iterator<std::forward_iterator_tag, token>
        {
            friend syntax_tree;

            node* current_node;
            std::stack<node*> prev_nodes;
            std::set<node*> visited_nodes;
        public:
            inorder_iterator();

            inorder_iterator& operator++();
            inorder_iterator operator++(int);

            token& operator*();
            const token& operator*() const;

            token* operator->();
            const token* operator->() const;

            friend bool operator==(const inorder_iterator& lhs, const inorder_iterator& rhs);
            friend bool operator!=(const inorder_iterator& lhs, const inorder_iterator& rhs);

        private:
            inorder_iterator(node* current);
            node* find_leftmost_node(node* from);
            bool visited(node* n);
        };

        template <typename InputIterator>
        syntax_tree(InputIterator first, InputIterator last):
                root(nullptr),
                operator_precedence
                        {
                {"=", 0},
                {"+", 1},
                {"-", 1}
                        }
        {
            std::queue<token> tokens{std::deque<token>{first, last}};
            parse(tokens);
        }

        syntax_tree(const syntax_tree& other) = delete;
        syntax_tree& operator=(const syntax_tree& other) = delete;

        syntax_tree(syntax_tree&& other) noexcept;
        syntax_tree& operator=(syntax_tree&& other) = delete;

        inorder_iterator inorder_begin();
        inorder_iterator inorder_end();

        ~syntax_tree();
    private:
        void parse(std::queue<token>& tokens);
        void recursive_destruct(node* n);

        void sweep_until_lowerprec(std::stack<node*, std::vector<node*>>& prev_expressions,
                                   std::stack<token, std::vector<token>>& operator_tokens,
                                   const token& current_token);
        void sweep_all(std::stack<node*, std::vector<node*>>& prev_expressions,
                       std::stack<token, std::vector<token>>& operator_tokens);
    };

    std::ostream& operator<<(std::ostream& os, syntax_tree& tree);
}

#endif //COMPILER_PARSE_TREE_HPP

syntax_tree.cpp

#include "syntax_tree.hpp"
#include <utility>
#include <stack>
#include <string>
#include <stdexcept>
#include <algorithm>
#include <iterator>

namespace markargs
{

    syntax_tree::node::node(const markargs::token& tk_, node* left_operand_, node* right_operand_):
            tk(tk_),
            left_operand(left_operand_),
            right_operand(right_operand_)
    {}

    syntax_tree::syntax_tree(syntax_tree&& other) noexcept:
            root(other.root)
    {
        other.root = nullptr;
        std::swap(operator_precedence, other.operator_precedence);
    }

    void syntax_tree::parse(std::queue<markargs::token>& tokens)
    {
        std::stack<node*, std::vector<node*>> prev_expressions;
        std::stack<token, std::vector<token>> operator_tokens;

        constexpr auto name = token::token_type::NAME;
        constexpr auto op = token::token_type::OP;
        constexpr auto number = token::token_type::NUMBER;

        while (!tokens.empty())
        {
            const auto& current_token = tokens.front();

            switch (current_token.type())
            {
                case op:
                    sweep_until_lowerprec(prev_expressions, operator_tokens, current_token);
                    operator_tokens.push(current_token);
                    break;
                case number:
                    prev_expressions.push(new node{current_token});
                    break;
                case name:
                    prev_expressions.push(new node{current_token});
                    break;
                default:
                    throw std::invalid_argument{"unknown token type encountered"};
            }
            tokens.pop();
        }

        //if there are any tokens left, they are in the right order, e.g. expression
        //can be evaluated applying operators from right to left
        sweep_all(prev_expressions, operator_tokens);

        if (prev_expressions.size() != 1)
        {
            throw std::invalid_argument("erroneous number of operands encountered");
        }

        root = prev_expressions.top();
    }

    syntax_tree::inorder_iterator syntax_tree::inorder_begin()
    {
        return inorder_iterator{root};
    }

    syntax_tree::inorder_iterator syntax_tree::inorder_end()
    {
        return {};
    }

    void syntax_tree::recursive_destruct(node* n)
    {
        if (n->left_operand != nullptr)
        {
            recursive_destruct(n->left_operand);
        }

        if (n->right_operand != nullptr)
        {
            recursive_destruct(n->right_operand);
        }

        delete n;
    }

    syntax_tree::~syntax_tree()
    {
        if (root != nullptr)
        {
            recursive_destruct(root);
        }
    }



    void syntax_tree::sweep_until_lowerprec(std::stack<node*, std::vector<node*>>& prev_expressions,
                                            std::stack<token, std::vector<token>>& operator_tokens,
                                            const token& current_token)
    {
        while (!operator_tokens.empty() &&
               operator_precedence[operator_tokens.top().payload()] >=
               operator_precedence[current_token.payload()])
        {
            auto oper = operator_tokens.top();
            operator_tokens.pop();

            if (prev_expressions.size() < 2)
            {
                throw std::invalid_argument{"either or both left or right side operands are missing"};
            }

            auto right_operand = prev_expressions.top();
            prev_expressions.pop();
            auto left_operand = prev_expressions.top();
            prev_expressions.pop();

            prev_expressions.push(new node{oper, left_operand, right_operand});
        }
    }

    void syntax_tree::sweep_all(std::stack<node*, std::vector<node*>>& prev_expressions,
                                std::stack<token, std::vector<token>>& operator_tokens)
    {
        while (!operator_tokens.empty())
        {
            auto oper = operator_tokens.top();
            operator_tokens.pop();

            if (prev_expressions.size() < 2)
            {
                throw std::invalid_argument{"either or both left or right side operands are missing"};
            }

            auto right_operand = prev_expressions.top();
            prev_expressions.pop();
            auto left_operand = prev_expressions.top();
            prev_expressions.pop();

            prev_expressions.push(new node{oper, left_operand, right_operand});
        }
    }

    std::ostream& operator<<(std::ostream& os, syntax_tree& tree)
    {
        std::transform(tree.inorder_begin(), tree.inorder_end(),
                       std::ostream_iterator<std::string>(os),
                       [](const token& tk){
                           return tk.payload();
                       });
    }
}

inorder_iterator.cpp

#include "syntax_tree.hpp"

namespace markargs
{
    syntax_tree::inorder_iterator::inorder_iterator(node* current) :
            current_node(current)
    {
        current_node = find_leftmost_node(current);
        visited_nodes.insert(current_node);
    }

    syntax_tree::node* syntax_tree::inorder_iterator::find_leftmost_node(node* from)
    {
        if (from->left_operand != nullptr)
        {
            prev_nodes.push(from);
            return find_leftmost_node(from->left_operand);
        }

        return from;
    }

    syntax_tree::inorder_iterator::inorder_iterator() :
            current_node(nullptr)
    {}

    syntax_tree::inorder_iterator& syntax_tree::inorder_iterator::operator++()
    {
        if (current_node->left_operand != nullptr && !visited(current_node->left_operand))
        {
            prev_nodes.push(current_node);
            current_node = current_node->left_operand;
            return ++*this; //recurse
        }

        if (!visited(current_node))
        {
            visited_nodes.insert(current_node);
            return *this;
        }
        else
        {
            //prev_nodes.pop();
            if (current_node->right_operand != nullptr)
            {
                current_node = current_node->right_operand;
                return ++*this;
            }
            else
            {
                if (!prev_nodes.empty())
                {
                    current_node = prev_nodes.top();
                    prev_nodes.pop();
                    return ++*this;
                }
                else
                {
                    current_node = nullptr;
                    return *this;
                }
            }
        }
    }

    syntax_tree::inorder_iterator syntax_tree::inorder_iterator::operator++(int)
    {
        auto copy = *this;
        ++*this;
        return copy;
    }

    const token& syntax_tree::inorder_iterator::operator*() const
    {
        return current_node->tk;
    }

    token& syntax_tree::inorder_iterator::operator*()
    {
        return current_node->tk;
    }

    const token* syntax_tree::inorder_iterator::operator->() const
    {
        return &current_node->tk;
    }

    token* syntax_tree::inorder_iterator::operator->()
    {
        return &current_node->tk;
    }

    bool syntax_tree::inorder_iterator::visited(node* n)
    {
        return visited_nodes.find(n) != visited_nodes.end();
    }

    bool operator==(const syntax_tree::inorder_iterator& lhs, const syntax_tree::inorder_iterator& rhs)
    {
        return lhs.current_node == rhs.current_node;
    }

    bool operator!=(const syntax_tree::inorder_iterator& lhs, const syntax_tree::inorder_iterator& rhs)
    {
        return !(lhs == rhs);
    }
}

inorder_iterator_tests.cpp

#include <sstream>
#include <iterator>
#include <string>
#include <algorithm>
#include <fstream>
#include <iostream>

#include <token.hpp>
#include "syntax_tree.hpp"

void test_one(const std::string& inputline, const std::string& correct_answer)
{
    std::stringstream ss(inputline);
    markargs::syntax_tree tree{std::istream_iterator<markargs::token>(ss), {}};
    std::ostringstream result;

    auto begin = tree.inorder_begin();
    auto end = tree.inorder_end();

    for (; begin != end; ++begin)
    {
        result << begin->payload();
    }

    if (result.str() != correct_answer)
    {
        std::cout << result.str() << '\n';
        throw std::logic_error{"tree was not build correctly for input: "
                               + inputline};
    }
}

void run_tests()
{
    std::ifstream input_file("input.txt");
    std::ifstream answers_file("answers.txt");
    if (!input_file.is_open() || !answers_file.is_open())
    {
        throw std::runtime_error{"either input or answers file cannot be opened"};
    }

    std::string inputline;
    std::string correct_answer;

    std::cout << "starting inorder iterator tests ...\n";
    unsigned int counter = 1;
    while (std::getline(input_file, inputline) && std::getline(answers_file, correct_answer))
    {
        std::cout << "running test #" << counter << '\n';
        test_one(inputline, correct_answer);
        ++counter;
    }

    std::cout << "all tests passed\n\n";
}

int main()
{
    run_tests();
}

CMakeLists.txt

cmake_minimum_required(VERSION 3.2)
project(compiler)

set(CMAKE_CXX_STANDARD 14)

add_library(syntax_analysis syntax_tree.hpp syntax_tree.cpp inorder_iterator.cpp)

add_dependencies(syntax_analysis lexical_analysis)
target_include_directories(syntax_analysis PUBLIC ../lexical_analysis/)
target_link_libraries(syntax_analysis lexical_analysis)

add_executable(syntax_analysis_tests
        syntax_tree_tests.cpp
        syntax_tree.hpp
        )
target_link_libraries(syntax_analysis_tests syntax_analysis)
target_include_directories(syntax_analysis_tests PUBLIC ../lexical_analysis/)

configure_file(./input.txt ${CMAKE_CURRENT_BINARY_DIR}/input.txt COPYONLY)
configure_file(./input.txt ${CMAKE_CURRENT_BINARY_DIR}/answers.txt COPYONLY)
configure_file(./failing_input.txt ${CMAKE_CURRENT_BINARY_DIR}/failing_input.txt COPYONLY)

add_test(syntax-analysis-tests syntax_analysis_tests)

add_executable(inorder_iterator_tests
        inorder_iterator_tests.cpp
        syntax_tree.hpp)

target_link_libraries(inorder_iterator_tests syntax_analysis)

Full code

GitHub link.

SHA of the commit in the question is 075ab88823965fa247fe8abb0a50dd349ead9d25.

Concerns

Correct understanding of the concepts
Vast inefficiencies (e.g. like super bad ones)
General code quality
Misc.

Rakete1111 · Accepted Answer · 2017-08-21 18:36:36Z

Looks good, good job! Here are a few points:

My opinion is you could be a bit more defensive, like using final and noexcept everywhere.
Commenting code like this //prev_nodes.pop(); is not that good. Maybe you can add a comment explaining why you didn't remove the statement or just remove it completely.
It makes little sense to be why you would delete the move assignment operator but keep the move constructor. It's also a bit counter intuitive. Consider adding it?
operator_precedence is the same in every instance, why not make it static and const?

You can simplify your move constructor:

syntax_tree::syntax_tree(syntax_tree&& other) noexcept:
        root(std::exchange(other.root, nullptr))
{}

Even if you didn't include it, writing the name again is not very pretty token::token_type::NAME in my opinion. Why not use token::type::NAME?
Even though you manually allocate memory using new without any problems, you should still consider using std::unique_ptr to avoid any possible problem in the future (just to be on the safe side) and remove recursive_destruct.
You don't actually need the constructor of node (you do if you use std::make_unique) if you always use aggregate initialization.
Just because you need to modify tokens (in parse) and want to avoid a copy doesn't mean you need to use a lvalue reference, as it is pretty limiting (see constructor of syntax_tree).

Instead, pass by value. If you don't want to pay the cost of copying an lvalue, you can introduce some additional overloads:
```
void parse(std::queue<token>& tokens); // 1)
void parse(std::queue<token>&& tokens); // 2) calls 1)
void parse(const std::queue<token>& tokens); // 3) makes copy and calls 1)
```
Using operator<< on a stream for syntax_tree with const syntax_trees is not supported, because you used a non-const lvalue reference. That's limiting (see point 9). You're only outputting the tokens, so should not care if syntax_tree is const or not.
recursive_destruct, sweep_until_lowerprec and sweep_all can all be marked const.
You could introduce some const here and there for variables.

Leverage fallthrough in switches:

case number:
case name:
    prev_expressions.push(new node{current_token});
    break;

Unique ptr cannot be used with stacks :) they require copy constructor. I could store nodes linearly in vector and then use raw pointers in stack, but that is too complicated for the simple case. — Incomputable, Commented Aug 21, 2017 at 18:38
@Incomputable Really? Because it doesn't seem like it. Am I missing something? — Rakete1111, Commented Aug 21, 2017 at 18:42
popping will free the resources. And one will need to get contents of the top of stack. — Incomputable, Commented Aug 21, 2017 at 18:43
@Incomputable I don't understand what you mean. There is no requirement for elements in std::stack (apart from the obvious ones - complete type, ...). To add them using push for the default container just requires them to be MoveInsertable. top works just fine. — Rakete1111, Commented Aug 21, 2017 at 18:48
I'll explain my reasoning later, cannot use computer keyboard atm. — Incomputable, Commented Aug 21, 2017 at 18:52

Stack Exchange Network

Overhauled AST builder for markargs

Roadmap

Language

Production rules

Operator precedence

Associativity

Parser type

Changes

Code

Full code

Concerns

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged
c++
parsing
c++14
math-expression-eval
or ask your own question.

Linked

Hot Network Questions

Overhauled AST builder for markargs

Roadmap

Language

Production rules

Operator precedence

Associativity

Parser type

Changes

Code

Full code

Concerns

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++parsingc++14math-expression-eval or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c++
parsing
c++14
math-expression-eval
or ask your own question.