Predictive recursive descent parser for math expressions

Question

I've been learning about language theory and parsing, and decided to write my first parser: a LL(1) recursive descent parser. But actually, it does a little more than just expressions; it can also parse variable definitions with the "define" keyword. It parses into an AST and then the other portion of the program evaluates the AST, but I'm not posting that half (right now at least).

tree.h:

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>

#include <boost/variant.hpp>

template <typename> struct t_unary_op;
template <typename> struct t_binary_op;
template <typename> struct t_nary_op;

template <typename NumType>
struct t_negate : public t_unary_op<NumType>
{
    template <typename... Args>
    t_negate(Args&&... args): t_unary_op<NumType>(std::forward<Args>(args)...) {}
};

template <typename NumType>
struct t_add : public t_binary_op<NumType>
{
    template <typename... Args>
    t_add(Args&&... args): t_binary_op<NumType>(std::forward<Args>(args)...) {}
};

template <typename NumType>
struct t_subtract : public t_binary_op<NumType>
{
    template <typename... Args>
    t_subtract(Args&&... args): t_binary_op<NumType>(std::forward<Args>(args)...) {}
};

template <typename NumType>
struct t_multiply : public t_binary_op<NumType>
{
    template <typename... Args>
    t_multiply(Args&&... args): t_binary_op<NumType>(std::forward<Args>(args)...) {}
};

template <typename NumType>
struct t_divide : public t_binary_op<NumType>
{
    template <typename... Args>
    t_divide(Args&&... args): t_binary_op<NumType>(std::forward<Args>(args)...) {}
};

template <typename NumType>
struct t_exponentiate : public t_binary_op<NumType>
{
    template <typename... Args>
    t_exponentiate(Args&&... args): t_binary_op<NumType>(std::forward<Args>(args)...) {}
};

template <typename NumType>
struct t_var_occurrance
{
    std::string name;

    t_var_occurrance(std::string _name): name(std::move(_name)) {}
};

template <typename>
struct t_func_invocation;

template <typename NumType>
struct t_arg_placeholder
{
    unsigned int index;

    t_arg_placeholder(unsigned int _index): index(_index) {}
};

template <typename NumType>
using t_expression = boost::variant<
                                    NumType,
                                    boost::recursive_wrapper<t_var_occurrance<NumType>>,
                                    boost::recursive_wrapper<t_func_invocation<NumType>>,
                                    boost::recursive_wrapper<t_arg_placeholder<NumType>>,
                                    boost::recursive_wrapper<t_negate<NumType>>,
                                    boost::recursive_wrapper<t_add<NumType>>,
                                    boost::recursive_wrapper<t_subtract<NumType>>,
                                    boost::recursive_wrapper<t_multiply<NumType>>,
                                    boost::recursive_wrapper<t_divide<NumType>>,
                                    boost::recursive_wrapper<t_exponentiate<NumType>>
                                    >;

template <typename NumType>
struct t_func_invocation
{
    std::string name;
    std::vector<t_expression<NumType>> args;

    t_func_invocation(std::string _name, std::vector<t_expression<NumType>> _args): name(std::move(_name)), args(std::move(_args)) {}
};

template <typename NumType>
struct t_unary_op
{
    t_expression<NumType> op;

    template <typename Op>
    t_unary_op(Op&& _op): op(std::forward<Op>(_op)) {}
};

template <typename NumType>
struct t_binary_op
{
    t_expression<NumType> ops[2];

    template <typename Op1, typename Op2>
    t_binary_op(Op1&& op1, Op2&& op2): ops{std::forward<Op1>(op1), std::forward<Op2>(op2)} {}
};

template <typename NumType>
struct t_nary_op
{
    std::vector<t_expression<NumType>> ops;

    template <typename... Ops>
    t_nary_op(Ops&&... _ops): ops{std::forward<Ops>(_ops)...} {}
};

template <typename NumType>
struct t_var_definition
{
    std::string name;
    t_expression<NumType> val;

    t_var_definition(std::string _name, t_expression<NumType> _val): name(std::move(_name)), val(std::move(_val)) {}
};

template <typename NumType>
struct t_func_definition
{
    std::string name;
    unsigned int arity;
    t_expression<NumType> val;

    t_func_definition(std::string _name, unsigned int _arity, t_expression<NumType> _val): name(std::move(_name)), arity(_arity), val(std::move(_val)) {}
};

template <typename NumType>
using t_statement = boost::variant<
                                   t_expression<NumType>,
                                   t_var_definition<NumType>,
                                   t_func_definition<NumType>
                                   >;

and lexer.h:

#include <string>
#include <utility>
#include <exception>
#include <cstdlib>

#include <boost/variant.hpp>

class lex_error : public std::exception
{
public:
    const char* what() const noexcept
    {
        return "Unexpected character in input to lexer";
    }
};

enum class token_tag
{
    Invalid,
    Number,
    Character,
    Identifier,
    EOI
};

struct token
{
    token_tag type;
    boost::variant<boost::blank, double, char, std::string> value;

    token(): type(token_tag::Invalid), value() {}
    token(token_tag _type): type(_type), value() {}
    template <typename ValueType>
    token(token_tag _type, ValueType&& _value): type(_type), value(std::forward<ValueType>(_value)) {}
};

template <typename Iterator>
void skip_spaces(Iterator& first, Iterator last)
{
    while(first != last && isspace(*first)) ++first;
}

template <typename Iterator>
token get_token(Iterator& first, Iterator last)
{
    using namespace std;

    skip_spaces(first, last);
    if(first == last) return token(token_tag::EOI);

    string temp;
    bool decimal = false;

    switch(*first)
    {
    case '+':
    case '-':
    case '*':
    case '/':
    case '^':
    case '(':
    case ')':
    case '=':
        goto accept_operator;

    case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i': case 'j': case 'k': case 'l': case 'm':
    case 'n': case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u': case 'v': case 'w': case 'x': case 'y': case 'z':
        goto id;

    case '.':
        decimal = true;
        // Intentional fall-through
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
        goto number;

    default:
        throw lex_error();
    }

    accept_operator:
        return token(token_tag::Character, *first++);

    id:
        do
        {
            temp.push_back(*first++);
        } while(first != last && islower(*first));
        goto accept_id;

    accept_id:
        return token(token_tag::Identifier, std::move(temp));

    number:
        temp.push_back(*first++);
        if(first != last)
        {
            if(isdigit(*first))
                goto number;
            else if(*first == '.')
            {
                if(decimal == false)
                {
                    decimal = true;
                    goto number;
                }
                else
                    throw lex_error();
            }
        }
        goto accept_number;


    accept_number:
        if(decimal && temp.size() == 1)
            throw lex_error();
        char *dummy;
        double val = strtod(temp.c_str(), &dummy);
        return token(token_tag::Number, val);
}

and parser.h:

#include <sstream>
#include <string>
#include <iterator>
#include <exception>
#include <cmath>

#include <boost/variant.hpp>

#include "lexer.h"
#include "tree.h"

class parse_error : public std::exception
{
    std::string msg;

public:
    parse_error(std::string _msg): exception(), msg(_msg) {}

    const char* what() const noexcept
    {
        return msg.c_str();
    }
};

template <typename Iterator>
struct parser_state
{
    Iterator head, last;
    token lookahead;

    void scan()
    {
        lookahead = get_token(head, last);
    }

    parser_state(Iterator _first, Iterator _last): head(_first), last(_last), lookahead(token_tag::Invalid)
    {
        scan();
    }
};

template <typename Iterator>
parser_state<Iterator> initialize_parser(Iterator first, Iterator last)
{
    return parser_state<Iterator>(first, last);
}

parser_state<std::istreambuf_iterator<char>> initialize_parser(std::istream& is)
{
    return parser_state<std::istreambuf_iterator<char>>(std::istreambuf_iterator<char>(is), std::istreambuf_iterator<char>());
}

template <typename Iterator>
void throw_parse_error(parser_state<Iterator>& s, std::string rule, std::string expected)
{
    using namespace std;

    ostringstream o;
    o << "In rule " << rule << ": expected " << expected << ", got ";

    if(s.lookahead.type == token_tag::EOI)
        o << "end-of-input.";
    else if(s.lookahead.type == token_tag::Character)
        o << '\'' << boost::get<char>(s.lookahead.value) << "'.";
    else if(s.lookahead.type == token_tag::Number)
        o << "number " << boost::get<double>(s.lookahead.value) << '.';
    else
        o << "invalid token.";

    throw parse_error(o.str());
}

template <typename Iterator>
void parse_expression(parser_state<Iterator>&, t_expression<double>&);

template <typename Iterator>
void parse_factor(parser_state<Iterator>&, t_expression<double>&);

template <typename Iterator>
void parse_parenthesized_expression(parser_state<Iterator>& s, t_expression<double>& t)
{
    if(s.lookahead.type != token_tag::Character || boost::get<char>(s.lookahead.value) != '(')
        throw_parse_error(s, "parenthesized-expression", "'('");

    s.scan();

    parse_expression(s, t);

    if(s.lookahead.type != token_tag::Character || boost::get<char>(s.lookahead.value) != ')')
        throw_parse_error(s, "parenthesized-expression", "')'");
}

template <typename Iterator>
void parse_atom(parser_state<Iterator>& s, t_expression<double>& t)
{
    using namespace std;

    char op;
    auto type = s.lookahead.type;

    if(type == token_tag::Number)
    {
        t = boost::get<double>(s.lookahead.value);
    }
    else if(type == token_tag::Identifier)
    {
        t = t_var_occurrance<double>(move(boost::get<string>(s.lookahead.value)));
    }
    else if(type == token_tag::Character)
    {
        parse_parenthesized_expression(s, t);
    }
    else
        throw_parse_error(s, "atom", "number, identifier, or '('");

    s.scan();

    if(s.lookahead.type == token_tag::Character)
    {
        op = boost::get<char>(s.lookahead.value);

        if(op == '^')
        {
            s.scan();

            t_expression<double> c;
            parse_factor(s, c);
            t = t_exponentiate<double>(t, c);
        }
    }
}

template <typename Iterator>
void parse_factor(parser_state<Iterator>& s, t_expression<double>& t)
{
    if(s.lookahead.type == token_tag::Character)
    {
        char op = boost::get<char>(s.lookahead.value);

        if(op == '+')
        {
            s.scan();
            parse_factor(s, t);
        }
        else if(op == '-')
        {
            s.scan();

            t_expression<double> c;
            parse_factor(s, c);
            t = t_negate<double>(c);
        }
        else
            parse_atom(s, t);
    }
    else
        parse_atom(s, t);
}

template <typename Iterator>
void parse_term(parser_state<Iterator>& s, t_expression<double>& t)
{
    parse_factor(s, t);
    while(s.lookahead.type == token_tag::Character)
    {
        char op = boost::get<char>(s.lookahead.value);
        if(op != '*' && op != '/')
            break;

        s.scan();

        t_expression<double> c;
        parse_factor(s, c);
        if(op == '*')
            t = t_multiply<double>(t, c);
        else
            t = t_divide<double>(t, c);
    }
}

template <typename Iterator>
void parse_expression(parser_state<Iterator>& s, t_expression<double>& t)
{
    if(s.lookahead.type == token_tag::Character && boost::get<char>(s.lookahead.value) == ')')
        throw_parse_error(s, "expression", "number, identifier, '+', '-' or '('");

    parse_term(s, t);

    while(s.lookahead.type == token_tag::Character)
    {
        char op = boost::get<char>(s.lookahead.value);

        if(op == '+' || op == '-')
        {
            s.scan();

            t_expression<double> c;
            parse_term(s, c);
            if(op == '+')
                t = t_add<double>(t, c);
            else
                t = t_subtract<double>(t, c);
        }
        else break;
    }
}

template <typename Iterator>
void parse_definition(parser_state<Iterator>& s, t_statement<double>& t)
{
    using namespace std;

    string name = move(boost::get<string>(s.lookahead.value));

    s.scan();

    if(s.lookahead.type == token_tag::Character && boost::get<char>(s.lookahead.value) == '=')
    {
        s.scan();

        t_expression<double> e;
        parse_expression(s, e);
        t = t_var_definition<double>(move(name), std::move(e));
    }
}

template <typename Iterator>
void parse_root(parser_state<Iterator>& s, t_statement<double>& t)
{
    if(s.lookahead.type == token_tag::Identifier && boost::get<std::string>(s.lookahead.value) == "define")
    {
        s.scan();
        parse_definition(s, t);
    }
    else
    {
        t_expression<double> e;
        parse_expression(s, e);
        t = std::move(e);
    }

    if(s.lookahead.type != token_tag::EOI)
        throw_parse_error(s, "root", "end-of-input");
}

I will post all files on a separate website if anyone requests.

I'm mostly OK with the way my AST is set up, but I feel like the lexer is REALLY messy, and the parser is a little confusing. Any suggestions?

Answer 1

You've posted a lot of code, so this review focuses primarily on lexer.h, which you've indicated may have the most to improve.

Code Style

Use include guards

Include guards ensure that you don't get symbol-redefinition errors when a header is included multiple times. You should wrap your headers with a unique macro definition:

#ifndef MY_PARSER_TREE
#define MY_PARSER_TREE
// header contents go here
#endif

#include organization

It is a good idea to keep your standard library #include directives sorted alphabetically. This makes it easy to spot duplicates, or to add new dependencies in the right position.

Iterator categories

If you have an interface which takes iterators, you should at least specify the category of iterator which your algorithm requires. For instance, if skip_spaces() requires input iterators, you should name the iterator type as such:

template <typename InputIterator> // or InputIt for short

This is the convention followed by the standard library. If you want more safety than mere convention, there are metaprogramming solutions in the standard library (like std::enable_if).

Logic

Don't use goto

While there may be (very, very rare) legitimate uses of goto, it should almost never be used. It makes your program hard to reason about. If you're tempted to use it, take a step back and re-think your design. This is related to my next point:

Reconsider use of switch

I hardly ever use switch statements, usually because there is a better abstraction that serves the same purpose. Your switch statement appears to be handling three distinct cases: digit, lower-case letter, and operator. As a first step, I would create functions that encapsulate the identification and handling of each case:

const auto character = *first;
if (is_operator(character))
{
    // handle it...
}
else if (islower(character))
{
    // handle it...
}
else // etc.

Predicate functions

Creating functions to identify a character is clearer and less error-prone. It's easy to forget to type a letter when you create a case for each lower-case letter. There are two standard-library functions islower() and isdigit() which cover most of the ground in your switch.

Your operators can be represented as a std::set, and then testing is straightforward:

bool is_operator(char c)
{
    const std::set<char> operators = {'+', '-', '*', '/', '^', '(', ')', '='};
    return operators.find(c) != operators.end();
}

If you want to be more flexible, you could read these operator symbols from a file, but the principle is the same.

Reinventing the wheel

Some of your code replicates functionality that already exists in the standard library. skip_spaces can be replaced by find_if_not:

first = std::find_if_not(first, last, isspace);

And your construction of temp under the id label:

string temp; // earlier
do
{
    temp.push_back(*first++);
} while(first != last && islower(*first));

can similarly be clarified using a few algorithms and the string constructor taking iterators:

const auto nonLowercase = std::find_if_not(first, last, islower); // much clearer
const string temp{first, nonLowercase};
first = nonLowercase;

Unnecessary constructor

The single-argument token constructor is only called once, with an Invalid tag. This behavior is identical to the default constructor, so you could remove the constructor and change the single usage to call the default constructor. This will tighten up the interface for token. It doesn't make sense to create a token with no data that isn't Invalid, right?