What programming languages have the most easily-implemented interpreters?_问答_开发者

I need to implement an interpreter for a programming language as part of a project I'm working on. I don't think the details of this project are too relevant, except that it requires me to implement an interpreter from scratch, I can't use an existing programming language (the requirements include supporting portable delimited continuations, and being able to write an interpreter for it in Javascript, and also in Java).

Obviously I would really rather avoid inventing a whole new programming language, so I'm hoping there is some very simple langu开发者_开发知识库age I could copy, or at least draw inspiration from.

My first thought was Forth or a rudimentary Lisp-like language, however I'd really prefer the language have a syntax closer to more popular programming languages like Java, Python, or Ruby. In particular, this means supporting infix operators (a+b), and also a=b assignment of variables.

To put it another way, I'd like this language to feel reasonably familiar to people who program in PHP today, and I don't believe either Forth or Lisp meet this criteria.

Can anyone offer any suggestions for such a language?

I think that Lisp and Forth have some of the easiest naive interpreters.

You can choose a simple dynamic language, and the hardest part would be building the parser. For example, a subset of JavaScript might work. The interpreter is basically traversing the AST and doing the operations of each node.

In any case, research existing scripting languages that can be embedded in your development environment, and avoid rolling your own at all costs. Implementing compilers (in the broad sense) is very fun to do, but it can be expensive to maintain in the long run.

This sounds like a job for Lua.

It's a small language, designed to be simple to implement
There are already several implementations in Java and at least works in progress for Javascript.
Its syntax meets your requirements (assignments, infix operators).

The work you'd have left is to implement delimited continuations, but you knew that already when you ruled out Lisp/Scheme.

Tcl. The syntax is about as simple as Lisp, and it has an expr proc for infix arithmetic. It even uses {} for blocks so if you squint just right you can tell people it's a C-like language.

It doesn't have infix assignment a=b, but once you start going down the road of general infix notation, languages get really complex really fast, so I'm not sure how that's compatible with your other requirements.

Smalltalk and Io both have wonderfully simple but expressive syntaxes.

Brainfuck? I mean it just has 8 commands which each map to a single character.

Logo is a simple Lisp-like language without parentheses and a few hundred implementations.

Logo information on Wikipedia.

See this PDF for information about implementations: Logo tree.

Build a LISP interpreter first, this will be relatively simple.

You will gain a lot of experience in language parsing, without being hampered by additional feature requirements.

I assume this is as much an exercise for your own edification as a desire for a useful final product.

In that case, I must agree with the others who have recommended variants on Lisp-like languages, at least for the first pass, especially if you haven't done this before.

Lua is a pretty popular scripting language for this sort of thing that requires small, not particularly performant user scripts.

You might also consider whether javascript itself (or a subset) meets your requirements.

Also consult the list here: http://en.wikipedia.org/wiki/Continuation#Programming_language_support

PCF

Bootstrapping a simple compiler from nothing

You can use a Lisp subset and still have a more-natural notation if you use sweet-expressions, or at least curly-infix notation:

Curly-infix adds infix, by reading {a + b} as (+ a b), and supports traditional functional notation like f(x). See more in SRFI-105.
Sweet-expressions build on curly-infix, and add syntactically-relevant indentation. See more here in SRFI-110. Its URL is http://srfi.schemers.org/srfi-110/ (for SRFI-105, just replace "110" with "105").

Both have been implemented by the Readable Lisp S-expressions Project: http://readable.sourceforge.net/

Enjoy!

I recommend you start with a subset of lisp--basically car, cdr, cons, and quote. Make sure you have a basic scanner that handles invalid characters, and then invalid types (like cons requires 2 args, 2nd must be a list). You can get this done with a knowledge of basic data structures (linked lists alone could do it, but doubly linked or circular are much better).