9 ms·
An Abstract Syntax Tree, where each node can have zero children (e.g. a literal value), one child (unary operator like 'Not') or two children (a binary operator
by teo_zero 4y ago
An Abstract Syntax Tree, where each node can have zero children (e.g. a literal value), one child (unary operator like 'Not') or two children (a binary operator like +).
- xigoi 4y agoAnd what exactly is the benefit of restricting such a tree to two children? Why not just allow an arbitrary amount of children and then only use it with 0,1,2? After all, you might later want to extend the language.
- teo_zero 4y agoAllowing arbitrary number of children doesn't come for free. You might need a linked list, which is a waste of memory and access time if you always just use up to two elements. What most parsers do is to provide exactly 2 slots, aptly named left and right, and use zero, one or both of them.