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

It's not sooo hard. here's a LISP interpreter in ruby and the source is so small you are supposed to copy/paste it. but are you gonna learn LISP now? hehe.

Answer 3

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 4

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 5

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

Answer 6

The standard Stack Overflow resource for writing interpreters and compilers is http://stackoverflow.com/questions/1669/learning-to-write-a-compiler

Answer 7

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

Answer 8

I had a similar idea a couple of days ago. LISP is by far the easiest to implement because the syntax is so simple, and the data structures that the language manipulates are the same structures that the code is written in. Hence you need only a minimal implementation, and can define the rest in terms of itself.

However, if you are trying to learn about parsing, you may want to do a more complex language with Abstract Syntax Trees, etc.

If you want to check out my (literally two days old) Java implementation of lisp, check out mylisp.googlecode.com. I'm still working on it but it is incredible how short a time it took to get the existing stuff working.