[Tutorial] Implementing an interpreter for a custom programming language

After the positive response to my AES tutorial and my block cipher modes of operation tutorial, I thought that I would write a tutorial about something less common, which is writing an interpreter for a custom, self-defined, programming language.

The language, which I'll call Pandora, is a very basic programming language designed for mathematical purposes. It will be to only handle numeric data (integers and double) but it is a good entry point to the much wider domain of parsing/interpretation/compilation. While the data types of Pandora are rather limited, the language is capable of defining&using functions, using loops and control structures such as if/else, mathematical operations (addition, subtraction, multiplication, division, exponentiation, modulo) and logical algebra (negation, AND, OR).

By guiding the user through the numerous stages from the input text through the scanner, parser, the tree generation and finally the tree interpretation. Every stage will be explained in detail, the grammar given as well as the final source code. At the end of the tutorial, the Pandora interpreter will be able to correctly execute programs like the following (Pandora-syntax):

Code:

---

  // Recursive definition
  def factorial1(x) = {
    var res = 1;
    if (x > 0) set res = x * factorial1(x - 1);
    return res;
  };

  // Tail-recursive definition
  def factorial2aux(x, acc) = {
    var res = acc;
    if (x > 0) set res = factorial2aux(x - 1, acc * x);
    return res;
  };

  def factorial2(x) = factorial2aux(x, 1);

  // Iterative definition
  def factorial3(x) = {
    var p = 1;
    while (x > 0) {
      set p = p * x;
      set x = x - 1;
    }
    return p;
  };

{
  var x = 5;
  printInt(factorial1(x));
  printInt(factorial2(x));
  printInt(factorial3(x));
}

---