The following are two major kinds of interpreters.
One kind of interpreter is based on an abstract machine language, such as the Java Virtual Machine Language or Microsoft's .Net language.
A compiler translates the program into abstract machine language and an interpreter reads the abstract program into memory and performs the steps that are called for.
This kind of interpreter has some advantages.
The interpreter and compiler run separately. You can compile a program and run the compiled abstract machine code many times without recompiling.
This kind of interpreter runs quickly compared to the other kind, below.
A disadvantage is that this kind of compiler/interpreter combination is larger and so more time-consuming to build than the second kind.
A second kind of interpreter works on a data structure, typically a tree. Each tree has a meaning and the interpreter works by converting a tree to a simpler one that has the same meaning, until it cannot simplify any more.
A compiler typically builds the data structure and immediately runs the interpreter on it. So compilation and execution are done together.
Examples of languages that have been implemented this way are Lisp and SASL.
This approach is generally less time-consuming to implement but runs quite slowly. It is suitable to making a prototype implementation of a programming language.
Abstract syntax trees are representations of expressions, and most simplification rules can be written in terms of expressions.
For example,
| simplify(opNode(op, A, B)) = |
| performOp(op, simplify(A), simplify(B)) |
| simplify(A : B) = |
| cons(simplify(A), simplify(B)) |
| simplify(if A then B else C) = |
| isTrue(simplify(A)) ? simplify(B) : simplify(C) |
| simplify(A B) = |
| performApply(simplify(A), simplify(B)) |
| performApply(functionNode(num,body), arg) = |
| simplify(copyAndReplace (body, num, arg, emptyList)) |
| copyAndReplace(opNode(op, A, B), num, arg, numtbl) = |
| opNode(op, copyAndReplace(A, num, arg, numtbl), copyAndReplace(B, num, arg, numtbl)) |
| copyAndReplace(param(n), num, arg, numtbl) = |
| num == n ? arg : param(assoc(numtbl, n)) |
| copyAndReplace(functionNode(n, body), num, arg, numtbl) = |
| m = newFunctionNumber(); result = functionNode (m, copyAndReplace(body, num, arg, addToList(n,m,numtbl))); |