How to write an interpreter?

Question

I have decided to write a small interpreter as my next project, in Ruby. What knowledge/skills will I need to have to be successful?
I haven't decided on the language to interpret yet, but I am looking for something that is not a toy language, but would be relatively easy to write an interpreter for. Thanks in advance.

Answer 1

You will have to learn at least:

• lexical analysis (grouping characters into tokens)
• parsing (grouping tokens together into structure)
• abstract syntax trees (representing program structure in a data structure)
• data representation (assuming your language will have variables)
• an evaluation loop that "runs" your program

An excellent introduction to some of these topics can be found in the introductory text Structure and Interpretation of Computer Programs. The language used in that book is Scheme, which is a robust, well-specified language that is ideally suited for your first interpreter implementation. Highly recommended.

Answer 2

I haven't decided on the language to interpret yet, but I am looking for something that is not a toy language, but would be relatively easy to write an interpreter for. Thanks in advance.

Try some dialect of Lisp like Scheme or Clojure. (Now there's an idea: Clojure-in-Ruby, which integrates with Ruby as well as Clojure does with Java.)

With Lisp, there is no need to bother with idiosyncracies of syntax, as Lisp's syntax is much closer to the abstract syntax tree.

Answer 3

This SICP chapter shows how to write a Lisp interpreter in Lisp (a metacircular evaluator). In my opinion this is the best place to start. Then you can move on to Lisp in Small Pieces to learn how to write advanced interpreters and compilers for Lisp. The advantage of implementing a language like Lisp (in Lisp itself!) is that you get the lexical analyzer, parser, AST, data/program representation and REPL for free. You can concentrate on the task of getting your great language working!

Answer 4

There is Tree top project wich can be helpful for you http://treetop.rubyforge.org/

Answer 5

You can checkout Ruby Draft Specification http://ruby-std.netlab.jp/