Now I'm working on implementation of Jinja template engine for web development on D language.

http://jinja.pocoo.org

I like it's explicit but still rather short syntax inherited from Python. I find it good for writing templates for web pages and other stuff such as configs or maybe CSS files.

But I have a problem in my head about better way of representing parse tree node in D. So I want to ask an advice from people who have some experience in working with grammars, parsing, creating compilers, etc. Currently my lexer algorithm is implemented with small amount of allocations using plain structs everywhere.

So one of my considerations is that it would be good to implement parser with as less allocations as possible or at least consolidate it in one place. In this case it could be possible to switch allocation policy easily.

Now about parse tree nodes. Tree node has set of field of *Node* type, and also can be list of Nodes (Node[]) or can contain plain values (string. bool. int). One way is to implement node as struct like std.json does it.

enum NodeType { /+...+/}

struct Node
{
   NodeType type;

   Node[string] fileds;
   Node[] list;

   //Could store plain values
   int integer;
   bool boolean;
   string str;
   float floating;

   Lexeme lex; //Stores info about corresponding lexeme
}

Some of these fields can be merged into *union* to make it more memory efficient. So there is two data types that will reallocate when I'll be operating on them: array and associative array.

Another way is using of base class/interface for Node and have separate class for each node type. For example

class Node {
   //...
}

class Statement: Node {
   //...
}

class Expr: Node {
   //...
}

class If : Statement {
   Expr test;
   Node body_;
   Node else_;
}

class Literal: Node {

}

class List: Literal {
   Node[] list;
}

class Integer: Literal {
   int value;
}

So as I see there I'll have more allocation taking class allocations into account. And what is the benefit of it if I using parse tree node as just data storing structure without methods?

What is a standard apprach implementing parse tree node?