1
\$\begingroup\$

In a larger project, I need a (rather simple) expression parser able to accept numerical values, operators and string identifiers. Fine, a lexical parser fed with some input which gives tokens one at the time to the syntactic parser. As a token can contain one single value type at a time, I decide to use an union. Problems came soon when I realized that an identifier was an arbitrary string of unknown length, and that std::string inside unions was not the simplest thing...

The general design is to initialize a lexical parser with some input, and the expression parser repeatedly calls its next member to get one token at a time. My 2 first attemps in designing a Token class ended in awfully complex code for the first, and code invoking UB for the second.

Before going further I would like to be sure whether my current Token class can be used to build the full machinery above it. In my tests I can successfully create tokens of all the types, copy them or store them in stacks or vectors and access their types and values, but I also know that it works neither means it is correct according to the standard and portable, nor it does not contain anti-patterns... For the C++ versions, I expect to follow the C++14 and above standards.

/**
* Token represents a token extracted by a lexical parser.
* 
* It has a type among integer, double, operator (single char) or string and
* contains an appropriate value, except for the special type Eof which has
* no value and represents the end of the input data
* 
* It is a copyable and default constructible type (default constructor gives
* an Eof token) or can be constructed from a value of an acceptable type to
* produce a token of that type.
*/
class Token {
public:
    enum class Type { Int, Double, Operator, Identifier, Eof } type;
protected:
    // only 1! member at at time => union
    union  Foo {
        // group trivial member to be able to process them as a whole
        // because Bar is a trival union
        union Bar {
            int val;
            double fval;
            char op;
        } y;
        // one non trivial member: shall define all special methods
        Foo() { y.val = 0; }
        Foo(int i) { y.val = i; }
        Foo(double d) { y.fval = d; }
        Foo(char c) { y.op = c; }
        Foo(const std::string& str) : str(str) {};
        ~Foo() {}

        std::string str;
    } x;
public:
    // Simple ctors from nothing (Eof) or an acceptable type
    Token() : type(Type::Eof) {}
    Token(int i) : type(Type::Int), x(i) {};
    Token(double d) : type(Type::Double), x(d) {};
    Token(char c) : type(Type::Operator), x(c) {};
    Token(const std::string& str) : type(Type::Identifier), x(str) {};

    //Copy ctor handles specifically the string member
    Token(const Token& other): type(other.type) {
        if (type == Type::Identifier) {
            // in place construction for the string
            new (&x.str) std::string(other.x.str);
        }
        else {
            x.y = other.x.y;  // magic of the trivial member y
        }
    }

    // Explicit dtor destroys a possible string member
    ~Token() {
        if (type == Type::Identifier) {
            x.str.~basic_string();
        }
    }

    // assignment operator again handles the string member
    Token& operator = (const Token& other) {
        if (type == Type::Identifier) {
            if (other.type == Type::Identifier) {
                x.str = other.x.str;
            }
            else {
                // different types: we can safely destroy the destination
                x.str.~basic_string(); 
                x.y = other.x.y;
            }
        }
        else {
            if (other.type == Type::Identifier) {
                // we shall construct a new string member
                new (&x.str) std::string(other.x.str);
            }
            else {
                x.y = other.x.y;
            }
        }
        type = other.type;
        return *this;
    }

    // const accessors...
    int getVal() const { return x.y.val; }
    double getFval() const { return x.y.fval; }
    char getOp() const { return x.y.op; }
    std::string getStr() const { return x.str; }
    Type getType() const { return type; }
};

// and a stream injector to ease debugging traces
std::ostream& operator << (std::ostream& out, const Token& tok) {
    switch (tok.getType()) {
    case Token::Type::Int:
        out << tok.getVal();
        break;
    case Token::Type::Double:
        out << tok.getFval();
        break;
    case Token::Type::Operator:
        out << tok.getOp();
        break;
    case Token::Type::Identifier:
        out << tok.getStr();
        break;
    case Token::Type::Eof:
        out << "__EOF__";
    }
    return out;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You’ve basically just reimplemented std::variant. \$\endgroup\$
    – indi
    Aug 13 '21 at 15:57
  • \$\begingroup\$ @indi: My problem is that variant requires c++17 or boost. And c++14 is one of my requirements... \$\endgroup\$ Aug 13 '21 at 16:35
  • 3
    \$\begingroup\$ std::variant requires C++17, boost::variant or boost::variant2::variant require Boost… but a C++17-compatible variant type requires only C++11. There are dozens of implementations out there you could use or copy. If you can’t use std::variant, you should at least use a compatible type, so that when you can use std::variant, the transition is painless. \$\endgroup\$
    – indi
    Aug 13 '21 at 17:58
1
\$\begingroup\$

In order to do what you want, you can either have (non-union'ed) members of different types and only one is populated, which is your approach;
or, you can use a byte array buffer large enough to hold any of the different types, and in-place construct and destruct the actual object there. That's how Boost's variant was implemented before you could put such types in a primitive union.

I suggest finding an off-the-shelf, mature version of variant to include in your project, even if you are not using Boost's or including all of Boost's libraries. Doing this well is difficult and something that's already been done by others.

Also, have you considered using a string_view instead of a string? You don't need to copy the token, if you can refer to it in the original input. That would avoid the issues you are running into.

(Again, if you don't have std::string_view, obtain a stand-alone implementation to include in your project. Remember, all these fancy new library types were proofed out and well-worn before being included in the ISO standard!)

\$\endgroup\$

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.