CODEWITHSUNDEEP
rubylispinterpreter
bennybdbc
bennybdbc

Reputation: 1425

How to write an interpreter?

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.

Upvotes: 15

Views: 11295

Answers (10)

Inaimathi
Inaimathi

Reputation: 14065

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.

Upvotes: 1

uliwitness
uliwitness

Reputation: 8793

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.

Upvotes: 1

Ashley Davis
Ashley Davis

Reputation: 10040

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

Upvotes: 0

triggerNZ
triggerNZ

Reputation: 4761

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.

Upvotes: 2

allenwei
allenwei

Reputation: 4127

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

Upvotes: 2

Sebastian
Sebastian

Reputation: 2786

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

Upvotes: 2

Vijay Mathew
Vijay Mathew

Reputation: 27174

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!

Upvotes: 2

Joshua Fox
Joshua Fox

Reputation: 19655

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.

Upvotes: 5

Camilo Martin
Camilo Martin

Reputation: 37898

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.

Upvotes: 1

Greg Hewgill
Greg Hewgill

Reputation: 993075

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.

Upvotes: 30

Related Questions