Introduction
It is a spin-off to my compiler creation.
Problem
Traverse the markargs::syntax_tree
in order, e.g. first goes left_operand
, then operator
, then right_operand
.
It can be used to collect statistics, run searches, transform some nodes, copy into istream
s, etc. In general, it is a good skill to have, in my opinion (although I hate algorithms that are big if-else's). I'm considering moving streaming operator to use this iterator.
Code
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();
}
syntax_tree.hpp (the iterator is public class of it)
#ifndef COMPILER_PARSE_TREE_HPP
#define COMPILER_PARSE_TREE_HPP
#include <string>
#include <queue>
#include <map>
#include <iosfwd>
#include <stack>
#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::map<node*, bool> visited;
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);
};
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();
friend std::ostream& operator<<(std::ostream& os, const syntax_tree& tree);
private:
void parse(std::queue<token>& tokens);
void print(std::ostream& os, const node& n) const;
void recursive_destruct(node* n);
};
}
#endif //COMPILER_PARSE_TREE_HPP
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[current_node] = true;
}
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[current_node] = true;
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 ¤t_node->tk;
}
token* syntax_tree::inorder_iterator::operator->()
{
return ¤t_node->tk;
}
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);
}
}
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)
target_include_directories(syntax_analysis PUBLIC ../lexical_analysis/)
target_link_libraries(syntax_analysis lexical_analysis)
add_executable(syntax_analysis_tests
main.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)
Design decisions
Storing previous nodes as
stack
.The reason behind this is to make it easier to generalize to any binary tree in the future. If you're familiar with
markarg
s syntax and parser's specifications, at any time any node will only have one leaf left child, thus it could be stored by a pointer or optional.Storing visited nodes as
map
.I believe I heard it is possible to use stack for this, but I'm not sure. As a result the iterator has insane memory overhead.
Limiting the iterator to Forward Iterator
I can't think of the cases Bidirectional Iterator would be useful, so to not elevate complexity I decided to stick with Forward Iterator concept.
Private constructor
Since users don't have access to
node
s anyway, public constructor won't make much sense. Public default constructor, which constructs end iterator, is very useful though. End iterator is almost like a functor, since it just checks if the other one setcurrent_node
tonullptr
.
Concerns
Control flow complexity. I believe finding next
node
is expressed in a very non-comprehensive way.Memory efficiency. Current design has noticable memory overhead.
General code quality
Anything else
I know the iterator
is deprecated, but since tools are still in development for C++17, I decided to stick with C++14.
Build script
git clone https://github.com/simmplecoder/markargs.git
cd markargs
git checkout 092a5b37f9ab5af480cb3cb4288869770ac8d42f
mkdir build
cd build
cmake ..
make
If you have already cloned it:
#cd to markargs
git remote add origin https://github.com/simmplecoder/markargs
git fetch origin
git checkout 092a5b37f9ab5af480cb3cb4288869770ac8d42f
mkdir build
cd build
cmake ..
make