7
\$\begingroup\$

I thought that I didn't learn anything new for over a month or two, so I decided to start off with compilers. The code is really crappy, but at least it works.


Problem definition:

Given a bunch of mathematical expressions, find out which are constexpr, e.g. which names can be computed without user input, which ones require user input, and which ones can be computed if others are present. At the end program should ask for user input with names of the variables provided, and output all of the variables with their values after computations.

Example:

a = 12
c = a + b + 1

In the example above, value of a is constexpr computable, value of b requires user input and c will be computable when others will be present.

Language rules:

  • Only + - = operators are allowed
  • No consecutive numbers or variable names or any combination thereof <- implemented in tokenizer
  • No consecutive operators <- implemented in tokenizer
  • No leading operator (any of them) <- implemented in analyze
  • No number on left side of the = <- implemented in analyze
  • Only 1 = per expression <- implemented in analyze
  • variable names with no leading numbers are allowed <- implemented in analyze

Solved subproblem:

Tokenize the expression and detect syntactic errors.


As the first step I implemented tokenizer and syntax checker, although it is called analyze(). I've thrown around 40-50 tests at it manually, and it worked correctly. I have no idea how to write automated tests for it, so I went with manual approach.

Code:

#include <string>
#include <iostream>
#include <vector>
#include <string_view>
#include <cctype>
#include <stdexcept>
#include <sstream>

struct token {
    enum class type { NUMBER, NAME, OP };
    type tp;
    std::string payload;

    token(type t, const std::string& payload_) :
        tp(t),
        payload(payload_)
    {}
};

enum class analyzis_error {
    NAME_FIRST_EXPECTED,
    EQUALS_SECOND_EXPECTED,
    NO_DOUBLE_EQUALS_EXPECTED,
    CLOSING_VALUE_OR_NAME_EXPECTED
};

std::vector<token> tokenize(std::string_view s)
{
    std::vector<token> tokens;

    std::string current_identifier;
    std::string current_number;

    for (char c : s)
    {
        if (std::isalpha((unsigned char)c) || c == '_')
        {
            current_identifier += c;
        }
        else if (std::isdigit((unsigned char)c))
        {
            if (!current_identifier.empty())
            {
                current_identifier += c;
            }
            else
            {
                current_number += c;
            }
        }
        else if (c == '+' || c == '-' || c == '=')
        {
            if (!current_identifier.empty())
            {
                if (!tokens.empty() && (tokens.back().tp == token::type::NAME || tokens.back().tp == token::type::NUMBER))
                {
                    throw std::invalid_argument("any combination of consecutive numbers and names are not allowed");
                }
                tokens.push_back(token{ token::type::NAME, current_identifier });
                current_identifier.clear();
            }
            else if (!current_number.empty()) //they are not allowed to be simultaneously non-empty
            {
                if (!tokens.empty() && (tokens.back().tp == token::type::NAME || tokens.back().tp == token::type::NUMBER))
                {
                    throw std::invalid_argument("any combination of consecutive numbers and names are not allowed");
                }
                tokens.push_back(token{ token::type::NUMBER, current_number });
                current_number.clear();
            }

            if (!tokens.empty() && tokens.back().tp == token::type::OP)
            {
                throw std::invalid_argument("two consecutive operators are not allowed");
            }
            tokens.push_back(token{ token::type::OP, std::string(1, c) });
        }
        else if (std::isspace((unsigned char)c))
        {
            if (!current_identifier.empty())
            {
                if (!tokens.empty() && (tokens.back().tp == token::type::NAME || tokens.back().tp == token::type::NUMBER))
                {
                    throw std::invalid_argument("any combination of consecutive numbers and names are not allowed");
                }
                tokens.push_back(token{ token::type::NAME, current_identifier });
                current_identifier.clear();
            }
            else if (!current_number.empty()) //they are not allowed to be simultaneously non-empty
            {
                if (!tokens.empty() && (tokens.back().tp == token::type::NAME || tokens.back().tp == token::type::NUMBER))
                {
                    throw std::invalid_argument("any combination of consecutive numbers and names are not allowed");
                }
                tokens.push_back(token{ token::type::NUMBER, current_number });
                current_number.clear();
            }
        }
        else
        {
            throw std::invalid_argument("character outside character set is encountered");
        }
    }

    if (!current_identifier.empty())
    {
        tokens.push_back(token{ token::type::NAME, current_identifier });
    }
    else if (!current_number.empty())
    {
        tokens.push_back(token{ token::type::NUMBER, current_number });
    }

    return tokens;
}

std::pair<analyzis_error, bool> analyze(const std::vector<token> tokens)
{

    auto it = tokens.begin();

    if (it->tp != token::type::NAME)
    {
        return { analyzis_error::NAME_FIRST_EXPECTED, true };
    }
    ++it;

    //check for equals operator coming second in an expression
    if (!(it->tp == token::type::OP && it->payload == "="))
    {
        return { analyzis_error::EQUALS_SECOND_EXPECTED, true};
    }
    ++it;

    for (auto i = ++it; i != tokens.end(); ++i)
    {
        if (i->tp == token::type::OP && i->payload == "=")
        {
            return { analyzis_error::NO_DOUBLE_EQUALS_EXPECTED, true };
        }
    }

    if (tokens.back().tp == token::type::OP)
    {
        return { analyzis_error::CLOSING_VALUE_OR_NAME_EXPECTED, true };
    }

    return { {}, false };
}

std::ostream& operator<<(std::ostream& os, const std::vector<token>& tokens)
{
    std::string initial_expr;
    for (const token& t : tokens)
    {
        std::string type_str;
        switch (t.tp)
        {
        case token::type::NAME:
            type_str = "name";
            break;
        case token::type::NUMBER:
            type_str = "number";
            break;
        case token::type::OP:
            type_str = "operator";
            break;
        default:
            throw std::logic_error("unknown token encountered");
        }
        os << "token type: " << type_str << '\n' 
            << "payload: " << t.payload << "\n--------------------\n";
        initial_expr += t.payload;
    }
    std::cout << "initial expression: " << initial_expr << '\n';

    return os;
}

std::ostream& operator<<(std::ostream& os, analyzis_error err)
{
    switch (err)
    {
    case analyzis_error::EQUALS_SECOND_EXPECTED:
        os << "equals are expected as the second token in an expression";
        break;
    case analyzis_error::NAME_FIRST_EXPECTED:
        os << "name is expected as the first token in an expression";
        break;
    case analyzis_error::NO_DOUBLE_EQUALS_EXPECTED:
        os << "equals operator appeared twice or more, but not allowed to";
        break;
    case analyzis_error::CLOSING_VALUE_OR_NAME_EXPECTED:
        os << "expression ended with an operator, which is noted allowed";
        break;
    default:
        os << "unknown error";
    }

    return os;
}

int main()
{
    std::string expr;
    std::getline(std::cin, expr);
    std::vector<token> tokens;
    try
    {
        tokens = tokenize(expr);
    }
    catch (std::invalid_argument& err)
    {
        std::cout << err.what() << '\n';
        return 0;
    }
    std::cout << tokens.size() << '\n';
    std::cout << tokens;

    auto analyzis_result = analyze(tokens);
    if (analyzis_result.second)
    {
        std::cout << analyzis_result.first << '\n';
    }
    else
    {
        std::cout << "analyzis didn't find any errors\n";
    }
}

I know that bison and other tools exist, but I'd like to do it manually first time around, cause I don't have any idea about grammars, rules, etc. I think that encountering the stuff written in textbooks should help me out.


The only C++17 feature used is std::string_view, you can just replace it with const std::string& to compile with older libraries. The code doesn't have any dependencies.

My refactoring attempts:

  • Turning it into a class

    Turning anything to a class lead to a lot of questions whether variables should be member or local, and in most cases I couldn't give definitive answer. It looks more like an action, or a set of them. Any ownership semantics look weird on it.

  • Aggregating

    I don't think it would add much value to it. It would be opinion based improvement.

  • Finite automata

    I have no idea what this is. I believe what I did resembles it, in some ways. Though I believe the usual automata is a gigantic switch statement. I don't really know on what I could switch on. May be having some bit mask with properties of the input and constexpr variables to improve readability, but I couldn't finalize it.

Concerns:

  • A lot of code duplication.

    Some logic gets repeated, but I wasn't sure how exactly should I extract them. Grabbing whole current state into it won't be good, and I thought I might get into bugs in the future.

  • Nasty enums

    When I add new one, I need to add one in opertor<<, and sometimes I forget. Is there a way to do it automagically?

  • Better data structure

    Is there a better data structure for result of the tokenizer? I didn't go into full AST, since I'm not sure how I'll execute it later, so I decided to stick with plain old vector.

  • Anything else that comes to mind.

\$\endgroup\$
  • \$\begingroup\$ I believe this might be a good community challenge too. \$\endgroup\$ – Incomputable Jul 29 '17 at 3:14
3
\$\begingroup\$

Observation

First observation use Flex/Bison. Learn it once it makes all this stuff trivial.

OK. Got that out the way. Looking at the current code.

Style

You treat tokenizing and analyzing as two distinct phases. In most compilers this is not how it works.

Normally the analyzer will read a stream of tokens (not from a list of prepared tokens). The easist way to read a stream of tokens is to ask the tokenizer for the next token (it could have already tokenized the whole stream but it is easier to just read one token at a time).

int main()
{
    Table t = buildTable(std::cin);
    for(auto cosnt& ident: t) {
        if (t.notDefined()) {
            // User Input needed.
        }
    }
}
void buildTable(std::istream& in)
{
    Expression e;
    while(in >> e)
    {
        // Add Expression to Table
    }
}
std::istream& operator>>(std::istream& s, Expression& e)
{
    Token token;
    while(s >> token && token.type != expressionEnd)
    {
        // Add token to expression;
    }
    return s;
}
std::istream& operator>>(std::istream& s, Token& t)
{
    // Read One token from the stream.
    t = readToken(s);
    return s;
}

Tokenizer is complex

You can seriously simplify by using self documenting code (split reading each token into its own function).

Your current code is complicated because you are trying to read all the different types at the same time. The good thing is that you can tell the next token simply by seeing the first character of the next token.

std::vector<token> tokenize(std::string_view s)
{
    std::string::size_t pos = 0;
    std::vector<token>  result;

    while(pos < s.size())
    {
        pos      = dropWhiteSpace(s, pos);
        nextChar = s[pos];
        if (std::isalpha(nextChar) || nextChar == '_') {
            result.push_back(readIdentifier(s, pos));
        }
        else if (std::isdigit(nextChar)) {
            result.push_back(readNumber(s, pos));
        }
        else if (nextChar == '+' || nextChar == '-' || nextChar == '=') {
            result.push_back(readOperator(s, pos));
        }
    }
    return result;
}

If we change from your reading all the tokens into an array; but rather read a single token and return it. Then it becomes even simpler:

Token readToken(std::istream& s)
{
        char nextChar;
        s >> nextChar;
        s.unget(nextChar);
        if (std::isalpha(nextChar) || nextChar == '_') {
            return readIdentifier(s);
        }
        else if (std::isdigit(nextChar)) {
            return readNumber(s);
        }
        else if (nextChar == '+' || nextChar == '-' || nextChar == '=') {
            return readOperator(s);
        }
        else {
            // ERROR
        }
}
\$\endgroup\$
  • \$\begingroup\$ I run into an issue: how do I tell what was previous token? Should I just keep a vector of them? I believe that would defeat stream design (I'm implementing tokenizer as a stream with std::istream* as constructor argument). Should I just implement those checks outside of tokenizer? It seems like even after 1.5 years of you teaching me I'm still not that great in design decisions :) \$\endgroup\$ – Incomputable Jul 30 '17 at 7:24
  • \$\begingroup\$ Pass the stream by reference to the constructor (to avoid nullptr). Internally to the class you can store as a non owning pointer if you want too (so that it is easy to copy/move). \$\endgroup\$ – Martin York Jul 30 '17 at 19:48
  • \$\begingroup\$ In the semantic analysis phase (building the expression). It is quite common to need to maintain history (its quite common to need to know what the previous few tokens was). So in the Expression object you can keep a set of tokens (vector of tokens) as you work out the exact expression. This is how flex does it. Underneath the hood you will find a stack of tokens that build up. Once it works out the exact context you should be able to pop of tokens and replace with an expression. \$\endgroup\$ – Martin York Jul 30 '17 at 19:51
  • \$\begingroup\$ PS 1.5 years is nothing. I have been building compilers for 30. My first one took my ages (3 years PhD building the SISAL compiler (which just translated SISAL into C)). But I remember every mistake I made and every problem I had to push through. \$\endgroup\$ – Martin York Jul 30 '17 at 19:53
  • \$\begingroup\$ I believe 30 years ago parallelism didn't exist? \$\endgroup\$ – Incomputable Jul 30 '17 at 20:05
2
\$\begingroup\$

This is a great exercise! Parsing can be a very useful skill to learn. Once you've done it yourself, you should definitely look up lex and yacc (or flex and bison, if you prefer). They make these sorts of things pretty easy.

Refactoring

As you mentioned, there are some repeated sections that you could refactor. I would take the sections where you are putting tokens onto the stack and factor them all out to a single function like this:

void appendOperandToken(std::string& operand, std::vector<token>& tokens, const token::type tokenType)
{
    if (!tokens.empty() && (tokens.back().tp == token::type::NAME || tokens.back().tp == token::type::NUMBER))
    {
        throw std::invalid_argument("any combination of consecutive numbers and names are not allowed");
    }
    tokens.push_back(token{ tokenType, operand });
    operand.clear();
}

Now you can call it from the blocks where you get an operator or a space.

Just Return An Error

Why does analyze return a pair that contain both an analyzis_error and a bool? In every case where you return an error code, the bool is true, and when you don't return an error, the bool is false. It seems like you're returning the same data twice. Any callers could just check to see if an error was returned and ignore the bool.

Also, it's really frustrating trying to talk about or describe code where things aren't named. Since you are returning 2 values as a std::pair<>, I have to keep saying "the bool" and you have to use contextual clues to understand what I mean. If instead you had used a struct, then the bool would have a proper name and it would be easy to talk (and think) about.

Don't Name Things "type"

You have a type named type. The word "type" is one of those words that basically loses all meaning when it's put into code, like "data," "info," "record," or "value." You're storing the type of the token, so I would name it something like token_type to make it more clear.

Errors

It looks to me like the parser does accept some invalid inputs. For example, for this input:

a = 12qt34

it produces this output:

3
token type: name
payload: a
--------------------
token type: operator
payload: =
--------------------
token type: name
payload: qt34
--------------------
initial expression: a=qt34
analyzis didn't find any errors
\$\endgroup\$
  • \$\begingroup\$ Woops, yeah. I knew that poor testing is playing russian roulette. Thanks for the review. I thought of formally expressing relations between tokens, but I didn't get anywhere with it. Probably will implement it in the next version. \$\endgroup\$ – Incomputable Jul 29 '17 at 4:12

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.