在C/ c++中实现解释器所需的引用

I find myself attached to a project to integerate an interpreter into an existing application. The language to be interpreted is a derivative of Lisp, with application-specific builtins. Individual 'programs' will be run batch-style in the application.

我发现自己附加在一个项目上，将一个解释器集成到一个现有的应用程序中。要解释的语言是Lisp的派生语言，具有特定于应用程序的内置项。单独的“程序”将在应用程序中以批处理方式运行。

I'm surprised that over the years I've written a couple of compilers, and several data-language translators/parsers, but I've never actually written an interpreter before. The prototype is pretty far along, implemented as a syntax tree walker, in C++. I can probably influence the architecture beyond the prototype, but not the implementation language (C++). So, constraints:

多年来，我编写了一些编译器和一些数据语言翻译/解析器，但我以前从未真正编写过解释器，这让我感到惊讶。这个原型非常成熟，在c++中实现为语法树游标。我可能会影响原型之外的架构，但不会影响实现语言(c++)。因此,约束:

implementation will be in C++
实现将使用c++
parsing will probably be handled with a yacc/bison grammar (it is now)
解析可能会使用yacc/bison语法处理(现在是)
suggestions of full VM/Interpreter ecologies like NekoVM and LLVM are probably not practical for this project. Self-contained is better, even if this sounds like NIH.
完整的VM/解释器生态系统(如NekoVM和LLVM)的建议可能不适合这个项目。自给自足更好，即使这听起来像NIH。

What I'm really looking for is reading material on the fundamentals of implementing interpreters. I did some browsing of SO, and another site known as Lambda the Ultimate, though they are more oriented toward programming language theory.

我真正想要的是阅读关于实现口译员的基本原理的材料。我浏览了一下，还有一个叫做Lambda the Ultimate的网站，尽管它们更倾向于编程语言理论。

Some of the tidbits I've gathered so far:

到目前为止，我收集了一些趣闻:

Lisp in Small Pieces, by Christian Queinnec. The person recommending it said it "goes from the trivial interpreter to more advanced techniques and finishes presenting bytecode and 'Scheme to C' compilers."

小块的Lisp，由Christian Queinnec。推荐它的人说它“从简单的解释器到更高级的技术，并完成了将字节码和'Scheme to C'编译器。”
NekoVM. As I've mentioned above, I doubt that we'd be allowed to incorporate an entire VM framework to support this project.

NekoVM。正如我上面所提到的，我怀疑是否允许我们合并整个VM框架来支持这个项目。
Structure and Interpretation of Computer Programs. Originally I suggested that this might be overkill, but having worked through a healthy chunk, I agree with @JBF. Very informative, and mind-expanding.

计算机程序的结构和解释。最初我认为这可能有些过头了，但在处理了一大块健康数据后，我同意@JBF的观点。非常有用的,它存在。
On Lisp by Paul Graham. I've read this, and while it is an informative introduction to Lisp principles, is not enough to jump-start constructing an interpreter.

Paul Graham的《论Lisp》。我读过这篇文章，虽然它是对Lisp原理的一篇内容丰富的介绍，但还不足以让我们开始构建解释器。
Parrot Implementation. This seems like a fun read. Not sure it will provide me with the fundamentals.

鹦鹉的实现。这看起来很有趣。我不确定它是否能给我提供基本的知识。
Scheme from Scratch. Peter Michaux is attacking various implementations of Scheme, from a quick-and-dirty Scheme interpreter written in C (for use as a bootstrap in later projects) to compiled Scheme code. Very interesting so far.

计划从头开始。Peter Michaux正在攻击Scheme的各种实现，从用C编写的快速而又脏的Scheme解释器(在以后的项目中用作引导程序)到编译的Scheme代码。到目前为止很有趣。
Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages, recommended in the comment thread for Books On Creating Interpreted Languages. The book contains two chapters devoted to the practice of building interpreters, so I'm adding it to my reading queue.

语言实现模式:创建您自己的领域特定的和通用的编程语言，在关于创建解释语言的书籍的注释线程中推荐。这本书有两章是关于建立口译员的实践，所以我把它添加到我的阅读队列中。
New (and yet Old, i.e. 1979): Writing Interactive Compilers and Interpreters by P. J. Brown. This is long out of print, but is interesting in providing an outline of the various tasks associated with the implementation of a Basic interpreter. I've seen mixed reviews for this one but as it is cheap (I have it on order used for around $3.50) I'll give it a spin.
新(还是旧的，比如1979年):由p·j·布朗(P. J. Brown)编写交互式编译器和解释器。这篇文章已经很久没有发表了，但是提供与基本解释器实现相关的各种任务的概要是很有趣的。我曾见过对这款产品褒贬不一的评论，但由于它价格低廉(我订购了大约3.5美元的这款产品)，我将给它一个转转。

So how about it? Is there a good book that takes the neophyte by the hand and shows how to build an interpreter in C/C++ for a Lisp-like language? Do you have a preference for syntax-tree walkers or bytecode interpreters?

怎么呢?有没有一本很好的书，是用新手的手，展示如何用C/ c++为一种类似lisp的语言构建一个解释器?你喜欢语法树步行者还是字节码解释器?

To answer @JBF:

回答@JBF:

the current prototype is an interpreter, and it makes sense to me as we're accepting a path to an arbitrary code file and executing it in our application environment. The builtins are used to affect our in-memory data representation.

当前的原型是一个解释器，当我们接受一个到任意代码文件的路径并在我们的应用程序环境中执行它时，这对我来说是有意义的。内建项用于影响内存中的数据表示。
it should not be hideously slow. The current tree walker seems acceptable.

它不应该慢得可怕。当前的树行走似乎是可以接受的。
The language is based on Lisp, but is not Lisp, so no standards compliance required.

该语言基于Lisp，但不是Lisp，因此不需要遵循标准。
As mentioned above, it's unlikely that we'll be allowed to add a full external VM/interpreter project to solve this problem.
如上所述，不太可能允许我们添加完整的外部VM/解释器项目来解决这个问题。

To the other posters, I'll be checking out your citations as well. Thanks, all!

对于其他的海报，我也会检查你的引文。谢谢,!

5 个解决方案

#1

Short answer:

简短的回答:

The fundamental reading list for a lisp interpreter is SICP. I would not at all call it overkill, if you feel you are overqualified for the first parts of the book jump to chapter 4 and start interpreting away (although I feel this would be a loss since chapters 1-3 really are that good!).

lisp解释器的基本阅读列表是SICP。如果你觉得你对书的第一部分要求过高，那我就不认为这是多余的(尽管我觉得这是一个损失，因为第1-3章真的很好)。

Add LISP in Small Pieces (LISP from now on), chapters 1-3. Especially chapter 3 if you need to implement any non-trivial control forms.

在小片段中添加LISP(从现在开始是LISP)，第1-3章。特别是第3章，如果您需要实现任何重要的控件形式。

See this post by Jens Axel Søgaard on a minimal self-hosting Scheme: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html .

看到这篇文章的Jens Axel Søgaard最小自托管方案:http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html。

A slightly longer answer:

稍微长一点的回答:

It is hard to give advice without knowing what you require from your interpreter.

如果不知道你的翻译需要什么，你很难给出建议。

does it really really need to be an interpreter, or do you actually need to be able to execute lisp code?
它真的需要一个解释器吗?或者你真的需要能够执行lisp代码吗?
does it need to be fast?
它需要快速吗?
does it need standards compliance? Common Lips? R5RS? R6RS? Any SFRIs you need?
是否需要遵循标准?常见的嘴唇吗?R5RS吗?R6RS吗?你需要任何SFRIs ?

If you need anything more fancy than a simple syntax tree walker I would strongly recommend embedding a fast scheme subsystem. Gambit scheme comes to mind: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page .

如果您需要比简单的语法树游标更花哨的东西，我强烈建议您嵌入一个快速方案子系统。“Gambit”计划的主题是:http://dynamo.iro.umontrees.ca/ ~ Gambit /wiki/索引。php / Main_Page。

If that is not an option chapter 5 in SICP and chapters 5-- in LISP target compilation for faster execution.

如果这不是在SICP和第5章中第5章的选项，在LISP的目标编译中，可以更快地执行。

For faster interpretation I would take a look at the most recent JavaScript interpreters/compilers. There seem to be a lot of thought going into fast JavaScript execution, and you can probably learn from them. V8 cites two important papers: http://code.google.com/apis/v8/design.html and squirrelfish cites a couple: http://webkit.org/blog/189/announcing-squirrelfish/ .

为了获得更快的解释，我将查看最新的JavaScript解释器/编译器。在快速执行JavaScript时，似乎有很多想法，您可能可以从中学习。V8引用了两篇重要的文章:http://code.google.com/apis/v8/design.html和squirrelfish，引用了一对夫妻:http://webkit.org/blog/189/announcing-squirrelfish/。

There is also the canonical scheme papers: http://library.readscheme.org/page1.html for the RABBIT compiler.

还有规范的scheme文件:http://library.readscheme.org/page1.html用于兔子编译器。

If I engage in a bit of premature speculation, memory management might be the tough nut to crack. Nils M Holm has published a book "Scheme 9 from empty space" http://www.t3x.org/s9fes/ which includes a simple stop-the-world mark and sweep garbage collector. Source included.

如果我进行一些过早的猜测，内存管理可能是一个棘手的问题。Nils M Holm已经出版了一本名为“从空空间中获取方案9”的书http://www.t3x.org/s9fes/，其中包括一个简单的停止标记和清除垃圾收集器。源包括在内。

John Rose (of newer JVM fame) has written a paper on integrating Scheme to C: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92 .

John Rose (JVM较新的名声)写了一篇关于将Scheme集成到C的论文:http://library.readscheme.org/servlets/cite.ss?模式= acmdl - ros - 92。

#2

Yes on SICP.

对SICP是的。

I've done this task several times and here's what I'd do if I were you:

我已经做过好几次了，如果我是你，我就会这么做:

Design your memory model first. You'll want a GC system of some kind. It's WAAAAY easier to do this first than to bolt it on later.

首先设计你的内存模型。您将需要某种GC系统。首先做这件事要比以后再做容易得多。

Design your data structures. In my implementations, I've had a basic cons box with a number of base types: atom, string, number, list, bool, primitive-function.

设计你的数据结构。在我的实现中，我有一个基本的cons框，包含许多基本类型:atom、string、number、list、bool、primitive函数。

Design your VM and be sure to keep the API clean. My last implementation had this as a top-level API (forgive the formatting - SO is pooching my preview)

设计您的VM并确保保持API整洁。我的上一个实现将它作为一个*API(请原谅格式化——pooching我的预览也是如此)

ConsBoxFactory &GetConsBoxFactory() { return mConsFactory; }
AtomFactory &GetAtomFactory() { return mAtomFactory; }
Environment &GetEnvironment() { return mEnvironment; }
t_ConsBox *Read(iostream &stm);
t_ConsBox *Eval(t_ConsBox *box);
void Print(basic_ostream<char> &stm, t_ConsBox *box);
void RunProgram(char *program);
void RunProgram(iostream &stm);

RunProgram isn't needed - it's implemented in terms of Read, Eval, and Print. REPL is a common pattern for interpreters, especially LISP.

不需要RunProgram——它是按照读取、Eval和打印来实现的。REPL是解释器的常见模式，特别是LISP。

A ConsBoxFactory is available to make new cons boxes and to operate on them. An AtomFactory is used so that equivalent symbolic atoms map to exactly one object. An Environment is used to maintain the binding of symbols to cons boxes.

有一个ConsBoxFactory可用于制造新的cons包装盒并对其进行操作。一个原子工厂被使用，使等价的符号原子映射到一个物体。一个环境用于维护符号到构造框的绑定。

Most of your work should go into these three steps. Then you will find that your client code and support code starts to look very much like LISP too:

你的大部分工作应该包括这三个步骤。然后你会发现你的客户端代码和支持代码开始看起来很像LISP:

t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list)
{
    return Car(Cdr(list));
}

You can write the parser in yacc/lex, but why bother? Lisp is an incredibly simple grammar and scanner/recursive-descent parser pair for it is about two hours of work. The worst part is writing predicates to identify the tokens (ie, IsString, IsNumber, IsQuotedExpr, etc) and then writing routines to convert the tokens into cons boxes.

您可以在yacc/lex中编写解析器，但是为什么要麻烦呢?Lisp是一种非常简单的语法和扫描仪/递归解析器对，因为它大约需要两个小时的工作时间。最糟糕的部分是编写谓词来标识令牌(即IsString、IsNumber、IsQuotedExpr等)，然后编写例程将令牌转换为cons。

Make it easy to write glue into and out of C code and make it easy to debug issues when things go wrong.

在C代码中编写胶水很容易，在出现问题时也很容易调试。

#3

The Kamin Interpreters from Samuel Kamin's book Programming Languages, An Interpreter-Based Approach, translated to C++ by Timothy Budd. I'm not sure how useful the bare source code will be, as it was meant to go with the book, but it's a fine book that covers the basics of implementing Lisp in a lower-level language, including garbage collection, etc. (That's not the focus of the book, which is programming languages in general, but it is covered.)

来自Samuel Kamin《编程语言》一书的Kamin口译员，一种基于口译的方法，由Timothy Budd翻译成c++。我不知道有用的源代码,它是为了这本书,但这本书是一个很好的覆盖实现Lisp在低级语言的基本知识,包括垃圾收集等。(这不是这本书的重点,这是编程语言,但它是覆盖)。

Lisp in Small Pieces goes into more depth, but that's both good and bad for your case. There's a lot of material on compiling and such that won't be relevant to you, and its simpler interpreters are in Scheme, not C++.

小块中的Lisp会更深入，但这对您的情况有好处也有坏处。有许多关于编译的材料，这些材料与您无关，它的更简单的解释器是Scheme，而不是c++。

SICP is good, definitely. Not overkill, but of course writing interpreters is only a small fraction of the book.

SICP是好的,肯定。这并不过分，但写翻译当然只是本书的一小部分。

The JScheme suggestion is a good one, too (and it incorporates some code by me), but won't help you with things like GC.

JScheme的建议也很好(它包含了我的一些代码)，但不会帮助您使用GC之类的东西。

I might flesh this out with more suggestions later.

我以后可能会提出更多的建议来充实这一点。

Edit: A few people have said they learned from my awklisp. This is admittedly kind of a weird suggestion, but it's very small, readable, actually usable, and unlike other tiny-yet-readable toy Lisps it implements its own garbage collector and data representation instead of relying on an underlying high-level implementation language to provide them.

编辑:一些人说他们从我的笨拙中学到了很多。这确实是一个奇怪的建议，但它非常小，可读，实际上是可用的，而且与其他小的可读的玩具Lisps不同，它实现了自己的垃圾收集器和数据表示，而不是依赖底层的高级实现语言来提供它们。

#4

Check out JScheme from Peter Norvig. I found this amazingly simple to understand and port to C++. Uh, dunno about using scheme as a scripting language though - teaching it to jnrs is cumbersome and feels dated (helloooo 1980's).

看看Peter Norvig的JScheme。我发现这个非常简单，可以理解并移植到c++。呃，不知道如何使用scheme作为一种脚本语言——教它到jnrs是很麻烦的，而且感觉很过时(helloooo 80年代)。

#5

I would like to extend my recommendation for Programming Languages: Application and Interpretation. If you want to write an interpreter, that book takes you there in a very short path. If you read through writing the code you read and doing the exercise you end up with a bunch of similar interpreters but different (one is eager, the other is lazy, one is dynamic, the other has some typing, one has dynamic scope, the other has lexical scope, etc).

我想扩展一下我对编程语言的推荐:应用和解释。如果你想写一个解释器，那本书会用很短的时间带你去那里。如果你通读你读过的代码并做了练习，你会得到一堆相似的解释器，但是不同(一个是渴望的，另一个是懒惰的，一个是动态的，另一个有一些类型，一个有动态范围，另一个有词汇范围，等等)。

#1