How to write an interpreter?

I have decided to write a small interpreter as my 开发者_JAVA技巧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.

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.

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.

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!

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

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

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.

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.

If you're just doing this for fun, make up your own, simple language and just try it. My recommendation would be something like a really simple classic BASIC (no visual basic or object oriented stuff). With line numbers, GOTO, INPUT and PRINT and that's it. You get to do the basics, and you get a better understanding of how things work.

The knowledge you'll need?

• Tokenizing (turning that huge chunk of characters into something more efficiently readable, effectively splitting it up into 'words')
• Parsing (going over the tokens and building a data structure from it)
• Interpreting (looping over the data structure and executing each command)

And for that last one you'll also need a way to keep around variables. Usually you'd just implement a "stack", one huge block of data where you can mark off an area at the end.

It's not implemented in Lisp, but I found Write Yourself A Scheme in 48 Hours to be a very useful document while I was starting out with Haskell (though I didn't get anywhere near finishing it after 48 hours; YMMV). It also gives you a lot of insight into interpreters in general.

I can recommend this book. It discusses patterns for writing parsers and interpreters and more:

http://www.amazon.co.uk/s/ref=nb_sb_noss?url=search-alias%3Daps&field-keywords=language+implementation+patterns&x=0&y=0