Des avis sur un lexeur/parseur simple

// Main.cpp
#include <iostream>
#include "parser.hpp"

int main(int argc, char* argv[]){
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << " \"input selection\"" << std::endl;
        return -1;
    }

    try {
        auto tokens = tokenize(argv[1]);
        auto ast = parse(std::begin(tokens), std::end(tokens));
    } catch (const LexerError& e) {
        std::cout << "Lexer error: " << e.what() << std::endl;
    } catch (const ParserError& e) {
        std::cout << "Parsing error: " << e.what() << std::endl;
    }

    return 0;
}

#ifndef CHFL_LEXER_HPP
#define CHFL_LEXER_HPP
#include <string>
#include <vector>
#include <ostream>
#include <cassert>

/*! A token in the selection stream
 *
 * Various tokens are alowed here:
 *
 *    - binary comparison operators (== != < <= > >=);
 *    - boolean operators (and not or);
 *    - numbers, the scientific notation is alowed;
 *    - identifiers, obeing to the ([a-Z][a-Z_1-9]+) regular expression
 */
class Token {
public:
    //! Available token types
    enum TokenType {
        LPAREN, //! Left parenthesis
        RPAREN, //! Right parenthesis
        EQ,     //! "==" token
        NEQ,    //! "!=" token
        LT,     //! "<" token
        LE,     //! "<=" token
        GT,     //! ">" token
        GE,     //! ">=" token
        NOT,    //! "not" token
        AND,    //! "and" token
        OR,     //! "or" token
        IDENT,  //! Generic identifier
        NUM,    //! Number
    };

    //! Basic copy and move constructors
    Token(const Token&) = default;
    Token& operator=(const Token&) = default;
    Token(Token&&) = default;
    Token& operator=(Token&&) = default;

    //! Create an identifier token with `data` name
    //! \post `type()` is IDENT.
    Token(const std::string& data): Token(IDENT, data, 0.0) {}
    //! Create a number token with `data` value
    //! \post `type()` is NUM.
    Token(double data): Token(NUM, "", data) {}
    //! Create a token with type `ttype`.
    //! \pre `ttype` can not be NUM or IDENT.
    //! \post `type()` is `ttype`.
    Token(TokenType ttype): Token(ttype, "", 0.0) {
        assert(ttype != IDENT && ttype != NUM && "Can only use this constructor for token without data");
    }

    //! Get the number value associated with this token.
    //! \pre type() must be `NUM`.
    float number() const {
        assert(type_ == NUM && "Can only get number from NUM token");
        return number_;
    }

    //! Get the string which is at the origin of this token
    std::string str() const;

    //! Get the identifier name associated with this token.
    //! \pre type() must be `IDENT`.
    const std::string& ident() const {
        assert(type_ == IDENT && "Can only get identifiers from IDENT token");
        return ident_;
    }

    //! Check whether this token is a boolean operator, *i.e.* one of `and`, `or` or `not`
    bool is_boolean_op() const {
        return (type_ == AND) || (type_ == OR) || (type_ == NOT);
    }

    //! Check whether this token is a binary comparison operator, *i.e.* one of `==`, `!=`
    //! `<`, `<=`, `>` or `>=`.
    bool is_binary_op() const {
        return (type_ == EQ) || (type_ == NEQ) ||
               (type_ == LT) || (type_ == LE)  ||
               (type_ == GT) || (type_ == GE);
    }

    //! Check whether this token is an operator, either a binary comparison operator or a
    //! boolean operator
    bool is_operator() const {
        return is_binary_op() || is_boolean_op();
    }

    //! Get the precedence if this token. Parentheses have a precedence of 0, operators
    //! are classified by precedence.
    //! \pre This token must be an operator (`is_operator()` is `true`) or a parenthese.
    unsigned precedence() const;
    //! Get the token type of this token
    TokenType type() const {return type_;}
private:
    Token(TokenType ttype, const std::string& s_data, double f_data): type_(ttype), number_(f_data), ident_(s_data) {}
    //! Token type
    TokenType type_;
    //! Value of the number if the token is a TokenType::NUM
    double number_;
    //! Value of the identifier if the token is a TokenType::IDENT
    std::string ident_;
};

using token_iterator_t = std::vector<Token>::const_iterator;

//! Show a token to the `out` stream.
std::ostream& operator<<(std::ostream& out, const Token& token);

//! Convert an `input` string to a stream of tokens
//!
//! \throws LexerError if the input string can not be tokenized
std::vector<Token> tokenize(const std::string& input);

//! \exception LexerError Any error created during the lexing of a string.
class LexerError: std::runtime_error {
public:
    LexerError(const std::string& message): std::runtime_error(message) {}
    using std::runtime_error::what;
};

#endif

#include <algorithm>
#include "lexer.hpp"

std::ostream& operator<<(std::ostream& out, const Token& token) {
    switch (token.type()) {
    case Token::LPAREN:
        out << "LPAREN";
        break;
    case Token::RPAREN:
        out << "RPAREN";
        break;
    case Token::EQ:
        out << "EQ";
        break;
    case Token::NEQ:
        out << "NEQ";
        break;
    case Token::LT:
        out << "LT";
        break;
    case Token::LE:
        out << "LE";
        break;
    case Token::GT:
        out << "GT";
        break;
    case Token::GE:
        out << "GE";
        break;
    case Token::NOT:
        out << "NOT";
        break;
    case Token::AND:
        out << "AND";
        break;
    case Token::OR:
        out << "OR";
        break;
    case Token::IDENT:
        out << "IDENT(" << token.ident() << ")";
        break;
    case Token::NUM:
        out << "NUM(" << token.number() << ")";
        break;
    default:
        throw std::runtime_error("Hit the default case in Token::operator<<");
    }
    return out;
}

std::string Token::str() const {
    switch (type()) {
    case Token::LPAREN:
        return "(";
    case Token::RPAREN:
        return ")";
    case Token::EQ:
        return "==";
    case Token::NEQ:
        return "!=";
    case Token::LT:
        return "<";
    case Token::LE:
        return "<=";
    case Token::GT:
        return ">";
    case Token::GE:
        return ">=";
    case Token::NOT:
        return "not";
    case Token::AND:
        return "and";
    case Token::OR:
        return "or";
    case Token::IDENT:
        return ident();
    case Token::NUM:
        return std::to_string(number());
    default:
        throw std::runtime_error("Hit the default case in Token::operator<<");
    }
}

unsigned Token::precedence() const {
    assert(is_operator() || type_ == RPAREN || type_ == LPAREN);
    switch (type_) {
    case LPAREN:
    case RPAREN:
        return 0;
    case AND:
    case OR:
        return 100;
    case NOT:
        return 150;
    case EQ:
    case NEQ:
    case LT:
    case LE:
    case GT:
    case GE:
        return 200;
    default:
        throw std::runtime_error("Hit default case in Token::priority");
    }
}

static std::vector<std::string> split(const std::string& data) {
    std::string token;
    std::vector<std::string> tokens;
    for(auto c: data) {
        if (c == '(' || c == ')') {
            // Handle parenthese token. They may not be separated from the others tokens
            // by spaces, so let split them manually.
            if (token.length()) {
                tokens.emplace_back(token);
            }
            token.clear();
            tokens.push_back(std::string{c});
        } else if (!std::isspace(c)) {
            token += c;
        } else {
            if (token.length()) {
                tokens.emplace_back(token);
            }
            token.clear();
        }
    }
    // Last token
    if (token.length()) {
        tokens.emplace_back(token);
    }
    return tokens;
}

static const auto C_LOCALE = std::locale("C");

static bool is_identifier(const std::string& token) {
    if (token.length() == 0 || !std::isalpha(token[0], C_LOCALE)) {
        return false;
    }
    auto it = std::find_if_not(std::begin(token), std::end(token), [](char c){
        auto is_alpha = std::isalpha(c, C_LOCALE);
        auto is_digit = std::isdigit(c, C_LOCALE);
        return is_alpha || is_digit || c == '_';
    });
    return it == std::end(token);
}

static bool is_number(const std::string& token) {
    auto it = std::find_if_not(std::begin(token), std::end(token), [&](char c) {
        auto is_digit = std::isdigit(c, C_LOCALE);
        return is_digit || c == '.' || c == 'e' || c == '-' || c == '+';
    });
    return it == std::end(token);
}

std::vector<Token> tokenize(const std::string& input) {
    auto tokens = std::vector<Token>();
    for (auto& word: split(input)) {
        if (word == "(") {
            tokens.emplace_back(Token(Token::LPAREN));
            continue;
        } else if (word == ")") {
            tokens.emplace_back(Token(Token::RPAREN));
            continue;
        } else if (word == "==") {
            tokens.emplace_back(Token(Token::EQ));
            continue;
        } else if (word == "!=") {
            tokens.emplace_back(Token(Token::NEQ));
            continue;
        } else if (word == "<") {
            tokens.emplace_back(Token(Token::LT));
            continue;
        } else if (word == "<=") {
            tokens.emplace_back(Token(Token::LE));
            continue;
        } else if (word == ">") {
            tokens.emplace_back(Token(Token::GT));
            continue;
        } else if (word == ">=") {
            tokens.emplace_back(Token(Token::GE));
            continue;
        } else if (is_identifier(word)) {
            if (word == "or") {
                tokens.emplace_back(Token(Token::OR));
                continue;
            } else if (word == "and") {
                tokens.emplace_back(Token(Token::AND));
                continue;
            } else if (word == "not") {
                tokens.emplace_back(Token(Token::NOT));
                continue;
            }
            // Default identifier. This will be resolved during parsing phase
            tokens.emplace_back(Token(word));
            continue;
        } else if (is_number(word)) {
            try {
                double data = std::stod(word);
                tokens.emplace_back(Token(data));
                continue;
            } catch (const std::exception& e) {
                throw LexerError("Could not parse number in: '" + word + "'");
            }
        } else {
            throw LexerError("Could not parse '" + word + "' in selection: '" + input + "'");
        }
    }
    return tokens;
}

#ifndef CHFL_PARSER_HPP
#define CHFL_PARSER_HPP
#include <memory>
#include "lexer.hpp"

class Expr {
public:
    virtual std::vector<bool> evaluate() const = 0;
    virtual std::string print(unsigned delta = 0) const = 0;
    virtual ~Expr() = default;

    Expr() = default;
    Expr(const Expr&) = delete;
    Expr& operator=(const Expr&) = delete;
    Expr(Expr&&) = default;
    Expr& operator=(Expr&&) = default;
};
std::ostream& operator<<(std::ostream& out, const std::unique_ptr<Expr>& expr);

typedef std::unique_ptr<Expr> Ast;

std::ostream& operator<<(std::ostream& out, const Ast& expr);
Ast parse(token_iterator_t begin, token_iterator_t end);
Ast dispatch_parsing(token_iterator_t& begin, token_iterator_t& end);

class ParserError: std::runtime_error {
public:
    ParserError(const std::string& message): std::runtime_error(message) {}
    using std::runtime_error::what;
};

#endif

#include "parser.hpp"
#include "expr.hpp"
#include <sstream>
#include <stack>
#include <algorithm>

// Standard shutting-yard algorithm, as described in Wikipedia
// https://en.wikipedia.org/wiki/Shunting-yard_algorithm
//
// This convert infix expressions into an AST-like expression, while checking parentheses.
// The following input:
//      name == bar and x <= 56
// is converted to:
//      and <= 56 x == bar name
// which is the AST for
//            and
//        /         \
//       ==         <=
//      /  \       /  \
//  name   bar    x   56
static std::vector<Token> shutting_yard(token_iterator_t token, token_iterator_t end) {
    std::stack<Token> operators;
    std::vector<Token> output;
    while (token != end) {
        if (token->type() == Token::IDENT || token->type() == Token::NUM) {
            output.push_back(*token);
        } else if (token->is_operator()) {
            while (!operators.empty() && token->precedence() <= operators.top().precedence()) {
                output.push_back(operators.top());
                operators.pop();
            }
            operators.push(*token);
        } else if (token->type() == Token::LPAREN) {
            operators.push(*token);
        } else if (token->type() == Token::RPAREN) {
            while (!operators.empty() && operators.top().type() != Token::LPAREN) {
                output.push_back(operators.top());
                operators.pop();
            }
            if (operators.empty() || operators.top().type() != Token::LPAREN) {
                throw ParserError("Parentheses mismatched");
            } else {
                operators.pop();
            }
        }
        token++;
    }
    while (!operators.empty()) {
        if (operators.top().type() == Token::LPAREN || operators.top().type() == Token::RPAREN) {
            throw ParserError("Parentheses mismatched");
        } else {
            output.push_back(operators.top());
            operators.pop();
        }
    }
    // AST come out as reverse polish notation, let's reverse it for easier parsing after
    std::reverse(std::begin(output), std::end(output));
    return output;
}

Ast dispatch_parsing(token_iterator_t& begin, token_iterator_t& end) {
    if (begin->is_boolean_op()) {
        switch (begin->type()) {
        case Token::AND:
            return parse<AndExpr>(begin, end);
            break;
        case Token::OR:
            return parse<OrExpr>(begin, end);
            break;
        case Token::NOT:
            return parse<NotExpr>(begin, end);
            break;
        default:
            throw std::runtime_error("Hit the default case in dispatch_parsing");
        }
    } else if (begin->is_binary_op()) {
        if ((end - begin) < 3 || begin[2].type() != Token::IDENT) {
            std::stringstream tokens;
            for (auto tok = end - 1; tok != begin - 1; tok--) {
                tokens << tok->str() << " ";
            }
            throw ParserError("Bad binary operator: " + tokens.str());
        }

        auto ident = begin[2].ident();
        if (ident == "name") {
            return parse<NameExpr>(begin, end);
        } else if (ident == "x" || ident == "y" || ident == "z") {
            return parse<PositionExpr>(begin, end);
        } else if (ident == "vx" || ident == "vy" || ident == "vz") {
            return parse<VelocityExpr>(begin, end);
        } else {
            throw ParserError("Unknown operation: " + ident);
        }
    } else {
        throw ParserError("Could not parse the selection");
    }
    throw std::runtime_error("Whaaat ? This should be unreachable...");
}

Ast parse(token_iterator_t begin, token_iterator_t end) {
    auto ast = shutting_yard(begin, end);
    begin = std::begin(ast);
    end = std::end(ast);
    return dispatch_parsing(begin, end);
}

#ifndef CHFL_EXPR_IMPL_HPP
#define CHFL_EXPR_IMPL_HPP
#include <memory>
#include <vector>
#include <string>
#include "lexer.hpp"
#include "parser.hpp"

template<typename T>
Ast parse(token_iterator_t& begin, token_iterator_t& end);

// Existing binary operators
enum class BinOp {
    EQ = Token::EQ,     //! "=="
    NEQ = Token::NEQ,   //! "!="
    LT = Token::LT,     //! "<"
    LE = Token::LE,     //! "<="
    GT = Token::GT,     //! ">"
    GE = Token::GE,     //! ">="
};

//! "name == <ident>" or "name != <ident>" expression
class NameExpr final: public Expr {
public:
    NameExpr(std::string name, bool equals): Expr(), name_(name), equals_(equals) {}
    std::vector<bool> evaluate() const override;
    std::string print(unsigned delta) const override;
private:
    std::string name_;
    bool equals_;
};

//! "[x|y|z] <binop> <num>" expression
class PositionExpr final: public Expr {
public:
    enum Coordinate {
        X,
        Y,
        Z
    };
    PositionExpr(Coordinate coord, BinOp op, double val): Expr(), coord_(coord), op_(op), val_(val) {}
    std::vector<bool> evaluate() const override;
    std::string print(unsigned delta) const override;
private:
    Coordinate coord_;
    BinOp op_;
    double val_;
};

//! "[vx|vy|vz] <binop> <num>" expression
class VelocityExpr final: public Expr {
public:
    enum Coordinate {
        X,
        Y,
        Z
    };
    VelocityExpr(Coordinate coord, BinOp op, double val): Expr(), coord_(coord), op_(op), val_(val) {}
    std::vector<bool> evaluate() const override;
    std::string print(unsigned delta) const override;
private:
    Coordinate coord_;
    BinOp op_;
    double val_;
};

//! "<expr> and <expr>"
class AndExpr final: public Expr {
public:
    AndExpr(Ast&& lhs, Ast&& rhs): Expr(), lhs_(std::move(lhs)), rhs_(std::move(rhs)) {}
    std::vector<bool> evaluate() const override;
    std::string print(unsigned delta) const override;
private:
    Ast lhs_;
    Ast rhs_;
};

//! "<expr> or <expr>"
class OrExpr final: public Expr {
public:
    OrExpr(Ast&& lhs, Ast&& rhs): Expr(), lhs_(std::move(lhs)), rhs_(std::move(rhs)) {}
    std::vector<bool> evaluate() const override;
    std::string print(unsigned delta) const override;
private:
    Ast lhs_;
    Ast rhs_;
};

//! "not <expr>"
class NotExpr final: public Expr {
public:
    explicit NotExpr(Ast&& ast): Expr(), ast_(std::move(ast)) {}
    std::vector<bool> evaluate() const override;
    std::string print(unsigned delta) const override;
private:
    Ast ast_;
};

#endif

#include "expr.hpp"

std::ostream& operator<<(std::ostream& out, const std::unique_ptr<Expr>& expr) {
    out << expr->print();
    return out;
}

//! Get the associated string to a binary operator as opstr<Op>::str;
static std::string binop_str(BinOp op) {
    switch (op) {
    case BinOp::EQ:
        return "==";
    case BinOp::NEQ:
        return "!=";
    case BinOp::LT:
        return "<";
    case BinOp::LE:
        return "<=";
    case BinOp::GT:
        return ">";
    case BinOp::GE:
        return ">=";
    default:
        throw std::runtime_error("Hit the default case in binop_str");
        break;
    }
}

/****************************************************************************************/
std::vector<bool> NameExpr::evaluate() const {
    // TODO
    return std::vector<bool>();
}

std::string NameExpr::print(unsigned) const {
    if (equals_) {
        return "name == " + name_;
    } else {
        return "name != " + name_;
    }
}

template<> Ast parse<NameExpr>(token_iterator_t& begin, token_iterator_t& end) {
    assert(end - begin >= 3);
    assert(begin[2].type() == Token::IDENT);
    assert(begin[2].ident() == "name");
    if (begin[1].type() != Token::IDENT || !(begin->type() == Token::EQ || begin->type() == Token::NEQ)) {
        throw ParserError("Name selection must follow the pattern: 'name == {name} | name != {name}'");
    }
    auto equals = (begin->type() == Token::EQ);
    auto name = begin[1].ident();
    begin += 3;
    return Ast(new NameExpr(name, equals));
}

/****************************************************************************************/
std::vector<bool> PositionExpr::evaluate() const {
    // TODO
    return std::vector<bool>();
}

std::string PositionExpr::print(unsigned) const {
    std::string res;
    if (coord_ == X) {
        res += "x ";
    } else if (coord_ == Y) {
        res += "y ";
    } else if (coord_ == Z) {
        res += "z ";
    };

    res += binop_str(op_);
    res += " " + std::to_string(val_);
    return res;
}

template<> Ast parse<PositionExpr>(token_iterator_t& begin, token_iterator_t& end) {
    assert(end - begin >= 3);
    assert(begin[2].type() == Token::IDENT);
    assert(begin[2].ident() == "x" || begin[2].ident() == "y" || begin[2].ident() == "z");
    assert(begin->is_binary_op());

    decltype(PositionExpr::X) coord;
    auto coord_name = begin[2].ident();
    if (coord_name == "x") {
        coord = PositionExpr::X;
    } else if (coord_name == "y") {
        coord = PositionExpr::Y;
    } else if (coord_name == "z") {
        coord = PositionExpr::Z;
    } else {
        throw std::runtime_error("Hit the default case in coordinate identification");
    }

    auto op = BinOp(begin->type());
    if (begin[1].type() != Token::NUM) {
        throw ParserError("Position selection can only contain number as criterium.");
    }
    auto val = begin[1].number();
    begin += 3;
    return Ast(new PositionExpr(coord, op, val));
}

/****************************************************************************************/
std::vector<bool> VelocityExpr::evaluate() const {
    // TODO
    return std::vector<bool>();
}

std::string VelocityExpr::print(unsigned) const {
    std::string res;
    if (coord_ == X) {
        res = "vx ";
    } else if (coord_ == Y) {
        res = "vy ";
    } else if (coord_ == Z) {
        res = "vz ";
    };

    res += binop_str(op_);
    res += " " + std::to_string(val_);
    return res;
}

template<> Ast parse<VelocityExpr>(token_iterator_t& begin, token_iterator_t& end) {
    assert(end - begin >= 3);
    assert(begin[2].type() == Token::IDENT);
    assert(begin[2].ident() == "vx" || begin[2].ident() == "vy" || begin[2].ident() == "vz");
    assert(begin->is_binary_op());

    decltype(PositionExpr::X) coord;
    auto coord_name = begin[2].ident();
    if (coord_name == "vx") {
        coord = PositionExpr::X;
    } else if (coord_name == "vy") {
        coord = PositionExpr::Y;
    } else if (coord_name == "vz") {
        coord = PositionExpr::Z;
    } else {
        throw std::runtime_error("Hit the default case in coordinate identification");
    }

    auto op = BinOp(begin->type());
    if (begin[1].type() != Token::NUM) {
        throw ParserError("Veclocity selection can only contain number as criterium.");
    }
    auto val = begin[1].number();
    begin += 3;
    return Ast(new PositionExpr(coord, op, val));;
}

/****************************************************************************************/
std::vector<bool> AndExpr::evaluate() const {
    // TODO
    return std::vector<bool>();
}

std::string AndExpr::print(unsigned delta) const {
    auto lhs = lhs_->print(7);
    auto rhs = rhs_->print(7);
    return "and -> " + lhs + "\n" + std::string(delta, ' ') + "    -> " + rhs;
}

template<> Ast parse<AndExpr>(token_iterator_t& begin, token_iterator_t& end) {
    assert(begin->type() == Token::AND);
    begin += 1;
    if (begin == end) throw ParserError("Missing right-hand side operand to 'and'");

    Ast rhs = nullptr;
    try {
        rhs = dispatch_parsing(begin, end);
    } catch (const ParserError& e) {
        throw ParserError(std::string("Error in right-hand side operand to 'and': ") + e.what());
    }

    if (begin == end) throw ParserError("Missing left-hand side operand to 'and'");

    Ast lhs = nullptr;
    try {
        lhs = dispatch_parsing(begin, end);
    } catch (const ParserError& e) {
        throw ParserError(std::string("Error in left-hand side operand to 'and': ") + e.what());
    }
    return Ast(new AndExpr(std::move(lhs), std::move(rhs)));
}

/****************************************************************************************/
std::vector<bool> OrExpr::evaluate() const {
    // TODO
    return std::vector<bool>();
}

std::string OrExpr::print(unsigned delta) const {
    auto lhs = lhs_->print(6);
    auto rhs = rhs_->print(6);
    return "or -> " + lhs + "\n" + std::string(delta, ' ') + "   -> " + rhs;
}

template<> Ast parse<OrExpr>(token_iterator_t& begin, token_iterator_t& end) {
    assert(begin->type() == Token::OR);
    begin += 1;
    if (begin == end) throw ParserError("Missing right-hand side operand to 'or'");

    Ast rhs = nullptr;
    try {
        rhs = dispatch_parsing(begin, end);
    } catch (const ParserError& e) {
        throw ParserError(std::string("Error in right-hand side operand to 'or': ") + e.what());
    }

    if (begin == end) throw ParserError("Missing left-hand side operand to 'or'");

    Ast lhs = nullptr;
    try {
        lhs = dispatch_parsing(begin, end);
    } catch (const ParserError& e) {
        throw ParserError(std::string("Error in left-hand side operand to 'or': ") + e.what());
    }
    return Ast(new OrExpr(std::move(lhs), std::move(rhs)));
}


/****************************************************************************************/
std::vector<bool> NotExpr::evaluate() const {
    // TODO
    return std::vector<bool>();
}

std::string NotExpr::print(unsigned) const {
    auto ast = ast_->print(4);
    return "not " + ast;
}

template<> Ast parse<NotExpr>(token_iterator_t& begin, token_iterator_t& end) {
    assert(begin->type() == Token::NOT);
    begin += 1;
    if (begin == end) throw ParserError("Missing operand to 'not'");

    Ast ast = nullptr;
    try {
        ast = dispatch_parsing(begin, end);
    } catch (const ParserError& e) {
        throw ParserError(std::string("Error in operand of 'not': ") + e.what());
    }

    return Ast(new NotExpr(std::move(ast)));
}