www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Representing parse tree node

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?
Nov 02 2014