A SYNTAX TREE OF OBJECTS
Every interpreter turns a line like 1 + 2 * 3 into a tree before it works anything out: an operation at each branch, a number at each leaf, and the tighter operation lower down. Walking the tree from the top gives the answer. This post builds that tree in satellite, out of spacesuits, and lets each node work out its own value.
One kind of node
A node is either a number (a leaf) or an operation with two children. One spacesuit covers both: its op is "" for a number, and "+" or "*" for an operation, whose children are kept in a list.
(satellite)
satellite.spacesuit node()
{
satellite.public
{
satellite.variable.string op = ""
satellite.variable.number value = 0
satellite.container.list<node> kids = {}
satellite.capsule call_add(node child)
{
kids.append(child)
}
satellite.capsule call_value()
{
satellite.statement.if(op == "")
{
satellite.return(value)
}
satellite.variable.number left = kids[1].call_value()
satellite.variable.number right = kids[2].call_value()
satellite.statement.if(op == "+")
{
satellite.return(left + right)
}
satellite.return(left * right)
}
satellite.capsule call_text()
{
satellite.statement.if(op == "")
{
satellite.return(value.string)
}
satellite.return("(" + kids[1].call_text() + " " + op + " " + kids[2].call_text() + ")")
}
}
satellite.constructor(satellite.variable.string o, satellite.variable.number v)
{
op = o
value = v
}
}
satellite.capsule satellite.main()
{
// 1 + 2 * 3: the * binds tighter, so it is the + node's right child
node one("", 1)
node two("", 2)
node three("", 3)
node times("*", 0)
times.call_add(two)
times.call_add(three)
node plus("+", 0)
plus.call_add(one)
plus.call_add(times)
satellite.console.display(plus.call_text())
satellite.console.display(plus.call_value())
satellite.return(satellite)
}(1 + (2 * 3))
7How it works
- Each node answers for itself.
call_valueon a leaf hands back its number. On an operation it asks its two children for theirs — which asks their children, and so on down — and combines the answers. The recursion follows the shape of the tree, so a tree of any depth works the same way. - The shape is the meaning.
plusis at the top andtimeshangs under it, so2 * 3is worked out first. Build the same numbers the other way round and the answer changes — which is exactly what brackets do in a line of code. call_textwalks the same tree and writes it back out with a bracket round every operation, so you can see the shape.
This is half of an interpreter
A parser is the part that builds this tree from the text 1 + 2 * 3 — reading it one character at a time. Satellite cannot quite do that part yet: looking at one character of a string (s[n], .size()) is the next string milestone. Everything after the parser, though — the tree and the walk that works it out — is what you just ran.
Where next
RECURSION A MILLION DEEP explains how deep a walk like this can go, and BUILD AN INTERPRETER IN C++, THE WAY SATELLITE IS BUILT builds the whole thing — parser included — in C++.
