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?
'k'
inget_token()
? \$\endgroup\$