Constructing a simple interpreter

2019-01-23 07:45发布

问题:

I’m starting a project where I need to implement a light-weight interpreter. The interpreter is used to execute simple scientific algorithms. The programming language that this interpreter will use should be simple, since it is targeting non- software developers (for example, mathematicians.)

The interpreter should support basic programming languages features:

  • Real numbers, variables, multi-dimensional arrays
  • Binary (+, -, *, /, %) and Boolean (==, !=, <, >, <=, >=) operations
  • Loops (for, while), Conditional expressions (if)
  • Functions

MathWorks MatLab is a good example of where I’m heading, just much simpler. The interpreter will be used as an environment to demonstrate algorithms; simple algorithms such as finding the average of a dataset/array, or slightly more complicated algorithms such as Gaussian elimination or RSA.

Best/Most practical resource I found on the subject is Ron Ayoub’s entry on Code Project (Parsing Algebraic Expressions Using the Interpreter Pattern) - a perfect example of a minified version of my problem.

The Purple Dragon Book seems to be too much, anything more practical?

The interpreter will be implemented as a .NET library, using C#. However, resources for any platform are welcome, since the design-architecture part of this problem is the most challenging.

Any practical resources?

(please avoid “this is not trivial” or “why re-invent the wheel” responses)

回答1:

I would write it in ANTLR. Write the grammar, let ANTLR generate a C# parser. You can ANTLR ask for a parse tree, and possibly the interpreter can already operate on the parse tree. Perhaps you'll have to convert the parse tree to some more abstract internal representation (although ANTLR already allows to leave out irrelevant punctuation when generating the tree).



回答2:

It might sound odd, but Game Scripting Mastery is a great resource for learning about parsing, compiling and interpreting code.

You should really check it out:

http://www.amazon.com/Scripting-Mastery-Premier-Press-Development/dp/1931841578



回答3:

One way to do it is to examine the source code for an existing interpreter. I've written a javascript interpreter in the D programming language, you can download the source code from http://ftp.digitalmars.com/dmdscript.zip

Walter Bright, Digital Mars



回答4:

I'd recommend leveraging the DLR to do this, as this is exactly what it is designed for.

Create Your Own Language ontop of the DLR



回答5:

Lua was designed as an extensible interpreter for use by non-programmers. (The first users were Brazilian petroleum geologists although the user base has broadened considerably since then.) You can take Lua and easily add your scientific algorithms, visualizations, what have you. It's superbly well engineered and you can get on with the task at hand.

Of course, if what you really want is the fun of building your own, then the other advice is reasonable.



回答6:

Have you considered using IronPython? It's easy to use from .NET and it seems to meet all your requirements. I understand that python is fairly popular for scientific programming, so it's possible your users will already be familiar with it.



回答7:

The programming language that this interpreter will use should be simple, since it is targeting non- software developers.

I'm going to chime in on this part of your question. A simple language is not what you really want to hand to non-software developers. Stripped down languages require more effort by the programmer. What you really want id a well designed and well implemented Domain Specific Language (DSL).

In this sense I will second what Norman Ramsey recommends with Lua. It has an excellent reputation as a base for high quality DSLs. A well documented and useful DSL takes time and effort, but will save everyone time in the long run when domain experts can be brought up to speed quickly and require minimal support.



回答8:

I am surprised no one has mentioned xtext yet. It is available as Eclipse plugin and IntelliJ plugin. It provides not just the parser like ANTLR but the whole pipeline (including parser, linker, typechecker, compiler) needed for a DSL. You can check it's source code on Github for understanding how, an interpreter/compiler works.