0

I am trying to develop a grammar graph structure within C++. The current goal is to write a program which can check if expressions in a user-generated grammar are valid. This ultimately reduces to generating a directed syntax graph that expressions attempt to traverse.

One of the ways I have tried to keep the tokenization portion of the code separate from the syntax checker is by supplying the tokens as iterators as opposed to formal container types (e.g. std::vector<token>). I am happy with this decision, however it eliminates possibility to generate graph nodes in the canonical OOP style, i.e.

// Unfortunately, virtual functions can not be templated
struct node{
    template<class TokenIt>
    virtual bool match(TokenIt begin, TokenIt end);
};

// Many node subtypes which all 'match' in their own way

Because I know the finite number of node subtypes at compile time, I have instead tried to use std::variant to conglomerate all of the nodes as a single type for use in containers and token matching. A current attempt (which does not compile) is shown below.

class node_t;

class string_literal{
private:
    std::string str;
public:
    template<class TokenIt>
    bool match(TokenIt begin, TokenIt end){ 
        // try to match tokens to str
    }
};

class wildcard{
private:
    node_t node;
public
    template<class TokenIt>
    bool match(TokenIt begin, TokenIt end){
        // try to match 'node' zero or more times
    }
};

// Many more node types ...

using node_t = std::variant<string_literal, wildcard /*, more node types */>;

Is there any way in which I can eliminate the cyclic dependency of node_t and classes which encapsulate a node_t while maintaining a overall similar design? I'm sorry if this question appears a bit vague, but I am beginning to hit a wall with solutions.

Wil
  • 115
  • 6
  • Related to [using-stdvariant-with-recursion-without-using-boostrecursive-wrapper](https://stackoverflow.com/questions/39454347/using-stdvariant-with-recursion-without-using-boostrecursive-wrapper) – Jarod42 Sep 04 '19 at 22:37
  • So you have to use (smart-)pointers to "break" the cyclic dependency. – Jarod42 Sep 04 '19 at 22:42
  • 1
    Per Jarod42, possible duplicate of [Using std::variant with recursion, without using boost::recursive\_wrapper](https://stackoverflow.com/questions/39454347/using-stdvariant-with-recursion-without-using-boostrecursive-wrapper) (the answer doesn’t depend on having used Boost). – Davis Herring Sep 04 '19 at 22:43
  • Ah, so dynamic allocation is the necessary evil for this to work. – Wil Sep 05 '19 at 19:49

0 Answers0