7
\$\begingroup\$

Roadmap

I'm trying to follow usual compiler design:

  1. Lexical analysis (1, 2)

  2. Syntactical analysis <---- you're here

  3. Semantic analysis

  4. User input

  5. Code generation + execution


Background

I think I understood the first golden rule of newbie in compiler creation:

When in doubt, create gigantic if-else/switch chain.

and that pretty much describes my understanding of the topic.

This part was hardest for me, for now. I struggled quite a lot. After like 5-6 days, I thought, what is the most known AST? Result of shunting yard! This post helped me a lot, and got me past the halt point. Before that I just kept complicating things ...


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.


Code

main.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 <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:
        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();

        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

syntax_tree.cpp

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

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_)
    {}

    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;

        if (tokens.front().type() != token::token_type::NAME)
        {
            throw std::invalid_argument{"name must be first in the expression"};
        }


        prev_expressions.push(new node{tokens.front()});
        tokens.pop();

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

            if (current_token.type() == op)
            {

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

                operator_tokens.push(current_token);
            }
            else if (current_token.type() == number)
            {
                prev_expressions.push(new node{current_token});
            }
            else if (current_token.type() == name)
            {
                prev_expressions.push(new node{current_token});
            }
            else
            {
                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
        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});
        }

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

        root = prev_expressions.top();
    }

    void syntax_tree::print(std::ostream& os, const node& n) const
    {
        const node* current = &n;
        if (current->left_operand != nullptr)
        {
            print(os,*(current->left_operand));
        }

        os << current->tk.payload();

        if (current->right_operand != nullptr)
        {
            print(os, *(current->right_operand));
        }
    }

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

    std::ostream& operator<<(std::ostream& os, const syntax_tree& tree)
    {
        tree.print(os, *tree.root);
    }
}

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

Why not smart pointers?

Stacks work only with copyable types. Move-only types will cause compilation error, even though the move is noexcept. Also, I'm not deleting nodes outside of destructor, so it should be fine.

What is that weird constructor?

It opens a possibility for plan B, C, etc. It will allow moving from one implementation to another without many problems (I hope so).


Testing methodology

I decided to stick with input files, since recompiling every time will probably become counter productive due to the code size (I know that usually compiler is smart enough to not do redundant recompilation, but I'd like to be more "professional").

I didn't check what exactly has been thrown in throwing tests, since I found it hard to maintain. I just check if the right exception type was thrown.

For the following input:

input.txt

a=b+c-s+m
c=1+23
d=1+2

and

failing_input.txt

12 = 12 + a
asd = 2 2 2 2 2
asd = + + + + ++
d = - + 2 + 4

it prints:

starting simple tests ...
running test #1
running test #2
running test #3
all tests passed

starting throwing tests ...
running test #1
running test #2
running test #3
running test #4
all tests passed

Full code

Github

git clone https://github.com/simmplecoder/markargs.git
cd markargs
git checkout 2c782e8b8a051b44eeb173a8bfc481928d6db13c
mkdir build && cd build
cmake ..
make
ctest -T memcheck

Important note

If you modify input files, please rerun build system, so it will copy modified ones into binary directory.


Concerns

  • Architecture

  • General code quality

  • Misc

\$\endgroup\$
  • \$\begingroup\$ I don't recommend looking at commit history, if you don't want to have heart attacks :) \$\endgroup\$ – Incomputable Aug 16 '17 at 5:28
  • \$\begingroup\$ Wooops, forgot to remove the target_include_directories for the test executable. Will probably remove it in the next iteration. \$\endgroup\$ – Incomputable Aug 16 '17 at 5:30
  • \$\begingroup\$ I believe I found weird behavior: it enforces name coming first, but not an expression being assignment. I guess I'll need to either nuke the enforcement or allow only assignment expressions. I wouldn't say it is a bug though. \$\endgroup\$ – Incomputable Aug 16 '17 at 6:23
4
\$\begingroup\$
  • The tests do not belong where you put them.

    Imagine me wanting to use your language. I'd expect a standalone compiler executable, and the set of tests - which I can may freely manipulate - driven by an external program, preferably some shell script.

    I do trust the shell script to test the compiler; I cannot trust compiler's main to do that. No offense.

    To expand here, I would love to see a script fragment like

        compiler input_file -o output file || crash_report $input_file
        diff output_file expected_output || error_report $input_file
    
  • If I understand correctly, the centerpiece of the code is syntax_tree::parse. While it looks all right, it is very hard to review (and therefore would be very hard to extend) because it violates a no naked loops principle.

    Every loop is there for a purpose. It implements some non-trivial algorithm. As such it deserves a name - especially if you feel that it requires an introductory comment - and therefore deserves to be a function. Do yourself a favour, and factor those loops out.

  • recursive_destruct is a subject to a standard simplification:

       void recursive_destruct(node * n) {
           if (n == null)
               return;
           recursive_destruct(n->left_operand);
           recursive_destruct(n->right_operand);
           delete n;
       }
    
\$\endgroup\$
  • \$\begingroup\$ Could you please expand a bit more on the first point? I guess you expected something like $ compiler input_file? \$\endgroup\$ – Incomputable Aug 16 '17 at 6:19
  • \$\begingroup\$ @Incomputable Possibly so, or something along the lines of $(compiler input_file) = $(cat expected_results_file) \$\endgroup\$ – vnp Aug 16 '17 at 6:25
1
\$\begingroup\$

In the same veign as @vnp

The print can be made easier to read by printing the pointers rather than the value:

void syntax_tree::print(std::ostream& os, node const& n) const
{
    print(os, &n);
}

void syntax_tree::print(std::ostream& os, node const* n) const
{
    if (n == null) {
        return;
    }

    print(os, current->left_operand);
    os << current->tk.payload();
    print(os, current->right_operand);
}

Too late at night to try and decode shunting yarr. I'll look in the morning.

\$\endgroup\$
1
\$\begingroup\$

Traversal methods

It might be beneficial to introduce some traversal methods in order to:

  • reduce code duplication
  • decouple operation on a given node from traversal order
  • prevent stack overflow errors

With the current implementations of syntax_tree::recursive_destruct and syntax_tree::print you risk getting stack overflows in case of very deep branches (around \$2^{16}\$ or \$2^{17}\$ on 64-bit or 32-bit windows with default stack size of 1 MiB, different values for different OSes), even with the potential fixes from @vnp and @LokiAstari. Not only that, but you would probably need them for future additions anyways (e.g. a Constant-Folding optimization pass is easy to implement with a post-order traversal).

I might implement something along these lines:

void syntax_tree::in_order_traversal(std::function<void(node *)> operation) const {
    if(root == nullptr) return;

    auto path = std::stack<node *>{};
    auto current = root;

    do {
        while(current != nullptr) {
            path.push(current);
            current = current->left_operand;
        }

        auto next = path.top();
        path.pop();

        current = next->right_operand;

        operation(next);
    } while(!path.empty() || current != nullptr);
}

This would allow to reduce operator<<(std::ostream&, const syntax_tree&) and syntax_tree::~syntax_tree to:

std::ostream& operator<<(std::ostream& os, const syntax_tree& tree)
{
    tree.in_order_traversal([&](syntax_tree::node* n) { os << n->tk.payload(); });

    return os;
}

syntax_tree::~syntax_tree() {
    in_order_traversal([](node *n) { delete n; });
    root = nullptr;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.