An AST interpreter interprets an Abstract Syntax Tree (AST)
produced by a Syntax Analyzer.

Task[edit]
Take the AST output from the Syntax analyzer task, and interpret it as appropriate.
Refer to the Syntax analyzer task for details of the AST.

Loading the AST from the syntax analyzer is as simple as (pseudo code)

def load_ast()
    line = readline()
    # Each line has at least one token
    line_list = tokenize the line, respecting double quotes
 
    text = line_list[0] # first token is always the node type
 
    if text == ";"   # a terminal node
        return NULL
 
    node_type = text # could convert to internal form if desired
 
    # A line with two tokens is a leaf node
    # Leaf nodes are: Identifier, Integer, String
    # The 2nd token is the value
    if len(line_list) > 1
        return make_leaf(node_type, line_list[1])
 
    left = load_ast()
    right = load_ast()
    return make_node(node_type, left, right)
 The interpreter algorithm is relatively simple

interp(x)
    if x == NULL return NULL
    elif x.node_type == Integer return x.value converted to an integer
    elif x.node_type == Ident   return the current value of variable x.value
    elif x.node_type == String  return x.value
    elif x.node_type == Assign
                    globals[x.left.value] = interp(x.right)
                    return NULL
    elif x.node_type is a binary operator return interp(x.left) operator interp(x.right)
    elif x.node_type is a unary operator, return return operator interp(x.left)
    elif x.node_type ==  If
                    if (interp(x.left)) then interp(x.right.left)
                    else interp(x.right.right)
                    return NULL
    elif x.node_type == While
                    while (interp(x.left)) do interp(x.right)
                    return NULL
    elif x.node_type == Prtc
                    print interp(x.left) as a character, no newline
                    return NULL
    elif x.node_type == Prti
                    print interp(x.left) as an integer, no newline
                    return NULL
    elif x.node_type == Prts
                    print interp(x.left) as a string, respecting newlines ("\n")
                    return NULL
    elif x.node_type == Sequence
                    interp(x.left)
                    interp(x.right)
                    return NULL
    else
        error("unknown node type")
Notes:

Because of the simple nature of our tiny language, Semantic analysis is not needed.

Your interpreter should use C like division semantics, for both division and modulus. For division of positive operands, only the non-fractional portion of the result should be returned. In other words, the result should be truncated towards 0.

This means, for instance, that 3 / 2 should result in 1.

For division when one of the operands is negative, the result should be truncated towards 0.

This means, for instance, that 3 / -2 should result in -1.

 Test program


 prime.t

 lex <prime.t | parse | interp



/*
 Simple prime number generator
 */
count = 1;
n = 1;
limit = 100;
while (n < limit) {
    k=3;
    p=1;
    n=n+2;
    while ((k*k<=n) && (p)) {
        p=n/k*k!=n;
        k=k+2;
    }
    if (p) {
        print(n, " is prime\n");
        count = count + 1;
    }
}
print("Total primes found: ", count, "\n"); 


3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime
53 is prime
59 is prime
61 is prime
67 is prime
71 is prime
73 is prime
79 is prime
83 is prime
89 is prime
97 is prime
101 is prime
Total primes found: 26


 Additional examples
Your solution should pass all the test cases above and the additional tests found Here.

Reference
The C and Python versions can be considered reference implementations.

Related Tasks
 Lexical Analyzer task
 Syntax Analyzer task
 Code Generator task
 Virtual Machine Interpreter task

struct Anode
    node_type::String
    left::Union{Nothing, Anode}
    right::Union{Nothing, Anode}
    value::Union{Nothing, String}
end
 
make_leaf(t, v) = Anode(t, nothing, nothing, v)
make_node(t, l, r) = Anode(t, l, r, nothing)
 
const OP2 = Dict("Multiply" => "*", "Divide" => "/", "Mod" => "%", "Add" => "+", "Subtract" => "-", 
                 "Less" => "<", "Greater" => ">", "LessEqual" => "<=", "GreaterEqual" => ">=", 
                 "Equal" => "==", "NotEqual" => "!=", "And" => "&&", "Or" => "||")
const OP1 = Dict("Not" => "!", "Minus" => "-")
 
tobool(i::Bool) = i
tobool(i::Int) = (i != 0)
tobool(s::String) = eval(Symbol(s)) != 0
 
const stac = Vector{Any}()
 
function call2(op, x, y)
    if op in ["And", "Or"]
        x, y = tobool(x), tobool(y)
    end
    eval(Meta.parse("push!(stac, $(x) $(OP2[op]) $(y))"))
    return Int(floor(pop!(stac)))
end
 
call1(op, x) = (if op in ["Not"] x = tobool(x) end; eval(Meta.parse("$(OP1[op]) $(x)")))
evalpn(op, x, y = nothing) = (haskey(OP2, op) ? call2(op, x, y) : call1(op, x))
 
function load_ast(io)
    line = strip(readline(io))
    line_list = filter(x -> x != nothing, match(r"(?:(\w+)\s+(\d+|\w+|\".*\")|(\w+|;))", line).captures)
    text = line_list[1]
    if text == ";"
        return nothing
    end
    node_type = text
    if length(line_list) > 1
        return make_leaf(line_list[1], line_list[2])
    end
    left = load_ast(io)
    right = load_ast(io)
    return make_node(line_list[1], left, right)
end
 
function interp(x)
    if x == nothing return nothing
    elseif x.node_type == "Integer" return parse(Int, x.value)
    elseif x.node_type == "Identifier" return "_" * x.value
    elseif x.node_type == "String" return replace(replace(x.value, "\"" => ""), "\\n" => "\n")
    elseif x.node_type == "Assign" s = "$(interp(x.left)) = $(interp(x.right))"; eval(Meta.parse(s)); return nothing
    elseif x.node_type in keys(OP2) return evalpn(x.node_type, interp(x.left), interp(x.right))
    elseif x.node_type in keys(OP1) return evalpn(x.node_type, interp(x.left))
    elseif x.node_type ==  "If" tobool(eval(interp(x.left))) ? interp(x.right.left) : interp(x.right.right); return nothing
    elseif x.node_type == "While" while tobool(eval(interp(x.left))) interp(x.right) end; return nothing
    elseif x.node_type == "Prtc" print(Char(eval(interp(x.left)))); return nothing
    elseif x.node_type == "Prti" s = interp(x.left); print((i = tryparse(Int, s)) == nothing ? eval(Symbol(s)) : i); return nothing
    elseif x.node_type == "Prts" print(eval(interp(x.left))); return nothing
    elseif x.node_type == "Sequence" interp(x.left); interp(x.right); return nothing
    else
        throw("unknown node type: $x")
    end
end
 
const testparsed = """
Sequence
Sequence
Sequence
Sequence
Sequence
;
Assign
Identifier    count
Integer       1
Assign
Identifier    n
Integer       1
Assign
Identifier    limit
Integer       100
While
Less
Identifier    n
Identifier    limit
Sequence
Sequence
Sequence
Sequence
Sequence
;
Assign
Identifier    k
Integer       3
Assign
Identifier    p
Integer       1
Assign
Identifier    n
Add
Identifier    n
Integer       2
While
And
LessEqual
Multiply
Identifier    k
Identifier    k
Identifier    n
Identifier    p
Sequence
Sequence
;
Assign
Identifier    p
NotEqual
Multiply
Divide
Identifier    n
Identifier    k
Identifier    k
Identifier    n
Assign
Identifier    k
Add
Identifier    k
Integer       2
If
Identifier    p
If
Sequence
Sequence
;
Sequence
Sequence
;
Prti
Identifier    n
;
Prts
String        \" is prime\\n\"
;
Assign
Identifier    count
Add
Identifier    count
Integer       1
;
Sequence
Sequence
Sequence
;
Prts
String        \"Total primes found: \"
;
Prti
Identifier    count
;
Prts
String        \"\\n\"
;  """
 
const lio = IOBuffer(testparsed)
 
interp(load_ast(lio))
 