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?
