This is refactoring of the code described in the previous iteration. RoadmapI'm trying to follow usual compiler design:Lexical analysis: 1, 2Syntactical analysis: 1, 2 <---- you're hereSemantic analysisUser inputCode generation + executionLanguageIt 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 thisvalue = 12 + value2 + _bFor more lexical information, please refer to lexical analysis phase.Production rulesE->idE->numberE->E op Ewhere op is {=, +, -}.Operator precedenceoperator = has lowest precedence. Everything else equal (for now).AssociativityLeft associative.Parser typeIf 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.ChangesVastly 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.Codesyntax_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.hppvoid 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_HPPsyntax_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.hppnamespace 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.hppvoid 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.txtcmake_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 codeGitHub link.SHA of the commit in the question is 075ab88823965fa247fe8abb0a50dd349ead9d25.ConcernsCorrect understanding of the conceptsVast inefficiencies (e.g. like super bad ones)General code qualityMisc.
Overhauled AST builder for markargs
c++;parsing;c++14;math expression eval