Des avis sur un lexeur/parseur simple

Un peu de code review pour nowel ?

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour à vous, zestiens/zestiennnes ! Pendant les vacances, je m'attaque à un problème qui m'a toujours paru un poil difficile (et qui ne l'est pas tant que ça en fait \o/): le parsing d'un DSL (domain specific language).

Le DSL en question est un language de sélection, qui est construit sur des expressions de type condition <op> <value><op> est un opérateur de comparaison (==, =<, >=, …) et condition peut être quelque chose comme name, x (position en x), … Quelques exemples:

1
2
3
name == bar
x < 5.6
z >= 42

Ensuite, ces expressions peuvent être modifiées par l'opérateur not et combinées par les opérateurs and et or.

Le code est articulé autour de deux fonctions: tokenize qui transforme une chaine de charactères en std::vector<Token>, et parse qui crée l'AST. La partie évaluation de l'AST n'est pas encore implémentée, et viendra après. L'ensemble du code est disponible dans cette archive, pour ceux qui voudrait tester (make pour créer un exécutable parser).

Un exemple d'utilisation est dans ce fichier main:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// 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;
}

Le lexer travaille sur un std::string, et découpe cette chaine sur les espaces, puis transforme en le résultat en lexèmes. Voici le .hpp

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#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

Et le .cpp

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#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;
}

Le parseur prend en entrée la partie du std::vector<Token> à transformer en AST, puis effectue cette transformation de manière récursive (dispatch_parsing). Pour cela, le code s'attend à trouver des instanciations manuelle de la fonction template parse<Expr>. Voici le .hpp:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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

Et le .cpp

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#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);
}

Les différentes expressions sont implémentées dans un couple de fichiers séparés:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#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)));
}

Je suis preneur de toute remarque sur ce code, que ce soit au niveau de l'implémentation ou au niveau des bonnes pratiques de programmation. En particulier, je ne suis pas fan des switch à rallonge. Connaissez-vous une manière simple d'implémenter du pattern matching pas trop verbeux en C++ ? J'avais regardé quelque chose à base de templates (qui font du pattern matching sur leurs arguments si je ne m'abuse), mais je n'ai pas réussi à implémenter le tout.

Mon Github — Tuto Homebrew — Article Julia

+1 -0
Auteur du sujet

Est-ce que tu es obligé d'écrire ça toi-même ? Si ton objectif principal n'est pas l'écriture d'un parser, il existe plein de générateurs de parsers.

De ce que j'ai vu, les générateurs de parseurs ont trois inconvénients:

  • Il faut formaliser la grammaire (ici ça va, mais je compte la complexifier un peu avec des fonctions et des références à d'autres expressions en cours de parsage) ;
  • Les messages d'erreur sont moins clairs ;
  • Ils sont moins portables (j'ai comme cible de compilation à la fois GNU/Linux et MSVC). Dites-moi si je me trompe, mais Flex/Bison ou Lex/Yacc sont des outils qui supposent un environnement GNU.

Mon Github — Tuto Homebrew — Article Julia

+0 -0

Justement, formaliser la grammaire c'est une Bonne Chose™, surtout si tu comptes la complexifier. TU verras qu'une fois la grammaire sous forme EBNF écrite, il devient beaucoup plus facile de voir les différents cas à traiter et la structure de l'AST.

Pour ce qui est des messages d'erreurs, j'imagine que c'est personnalisable mais c'est vrai que faire ton propre parser t'apporte plus de flexibilité pour avoir des beaux messages d'erreurs. Je suis pas sûr que ça soit rentable de faire ton propre parser juste pour ça.

Pour ce qui est de la portabilité j'en sais rien. Le générateur de parser devrait normalement produire du code ne dépendant que de la libc donc pas de souci (enfin j'imagine).

+1 -0
  • Ils sont moins portables (j'ai comme cible de compilation à la fois GNU/Linux et MSVC). Dites-moi si je me trompe, mais Flex/Bison ou Lex/Yacc sont des outils qui supposent un environnement GNU.

Luthaf

Lex et Yacc s'intègrent très bien à Visual Studio. Il suffit simplement d'ajouter tes fichiers au projet et de préciser comment les compiler.

Jamais utilisé Flex et Bison sur VS mais le principe doit être identique.

Shave the whales! | Thistle

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte