在C/C++中实现解释器所需的参考

我发现自己依附于一个项目,将一个解释器整合到一个现有的应用程序中.要解释的语言是Lisp的衍生物,具有特定于应用程序的内置.各个"程序"将在应用程序中以批处理方式运行.

我很惊讶多年来我编写了几个编译器和几个数据语言翻译器/解析器,但我以前从未真正编写过翻译器.原型很远,用C++实现为语法树walker.我可能会影响原型之外的架构,但不能影响实现语言(C++).所以,约束:

实现将在C++中

解析可能会用yacc/bison语法处理(现在是)

像NekoVM和LLVM这样的完整虚拟机/解释器生态系统的建议可能对这个项目不实用.自包含更好,即使这听起来像NIH.

我真正想要的是阅读有关实施口译员基础知识的材料.我做了一些浏览SO,另一个名为Lambda the Ultimate的网站,虽然他们更倾向于编程语言理论.

到目前为止我收集的一些花絮:

Lisp in Small Pieces,作者:Christian Queinnec.推荐它的人说它"从简单的解释器到更高级的技术并完成呈现字节码和'Scheme to C'编译器."

NekoVM.正如我上面提到的,我怀疑我们是否可以合并整个VM框架来支持这个项目.

计算机程序的结构与解释.最初我建议这可能是矫枉过正,但是通过一个健康的块,我同意@JBF.信息量大,思维扩张.

关于保罗格雷厄姆的Lisp.我已经读过这篇文章,虽然它是对Lisp原理的一个信息性介绍,但还不足以快速开始构建一个解释器.

鹦鹉实施.这看起来很有趣.不确定它会为我提供基本面.

来自Scratch的计划.Peter Michaux正在攻击Scheme的各种实现,从用C编写的快速脏方案解释器(用作后续项目中的引导程序)到编译的Scheme代码.到目前为止非常有趣.

语言实现模式:创建自己的特定于域的和通用编程语言,在关于创建解释语言的书籍的注释主题中推荐.这本书包含两章专门介绍构建解释器的实践,所以我将它添加到我的阅读队列中.

New(and old,即1979):由PJ Brown 编写交互式编译器和解释器.这已经绝版了,但是提供与基本解释器的实现相关的各种任务的概述很有趣.我已经看到这个混合评论,但因为它便宜(我订购时使用的价格约为3.50美元)我会给它一个旋转.

那怎么样？是否有一本很好的书,用手拿新手,并展示了如何在C/C++中为类似Lisp的语言构建一个解释器？您是否喜欢语法树步行器或字节码解释器？

回答@JBF:

当前的原型是一个解释器,当我们接受任意代码文件的路径并在我们的应用程序环境中执行它时,它对我有意义.内置函数用于影响我们的内存数据表示.

它不应该是非常缓慢.目前的树木行走者似乎可以接受.

该语言基于 Lisp,但不是Lisp,因此不需要符合标准.

如上所述,我们不太可能允许添加完整的外部VM /解释器项目来解决此问题.

对于其他海报,我也会检查你的引文.谢谢,全部!

简短回答:

lisp解释器的基本读取列表是SICP.如果你觉得你的书的第一部分过于资格而跳到第4章并开始解释,我根本不会称之为矫枉过正(虽然我觉得这会是一个损失,因为第1-3章确实很好!) .

在小件中添加LISP(从现在起LISP),第1-3章.特别是第3章,如果你需要实现任何非平凡的控制形式.

请参阅JensAxelSøgaard关于最小自助托管计划的这篇文章:http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html.

一个稍长的答案:

如果不知道口译员的要求,很难提供建议.

它真的真的需要成为一个解释器,还是你真的需要能够执行lisp代码？

它需要快吗？

它是否需要符合标准？常见的嘴唇？R5RS？R6RS？您需要的任何SFRI？

如果你需要比简单的语法树walker更有趣的东西,我强烈建议嵌入一个快速方案子系统.想到了Gambit计划:http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page.

如果这不是SICP的第5章和第5章 - LISP目标编译中的选项,则可以更快地执行.

为了更快地解释,我将看看最新的JavaScript解释器/编译器.似乎有很多想法进入快速JavaScript执行,你可以从中学习.V8引用了两篇重要论文:http://code.google.com/apis/v8/design.html和squirrelfish引用了一对:http://webkit.org/blog/189/announcing-squirrelfish/.

还有规范方案论文:http : //library.readscheme.org/page1.html用于RABBIT编译器.

如果我进行一些过早的猜测,内存管理可能是一个难以破解的难题.Nils M Holm出版了一本书"空间方案9" http://www.t3x.org/s9fes/,其中包括一个简单的世界标记和扫描垃圾收集器.来源包括.

John Rose(较新的JVM成名)撰写了一篇关于将Scheme集成到C的论文:http://library.readscheme.org/servlets/cite.ss ?pattern = AcmDL-Ros-92.

在SICP上是的.

我已经好几次完成了这项任务,如果我是你,我会做的就是这样:

首先设计您的内存模型.您需要某种GC系统.WAAAAY比以后更容易做到这一点.

设计您的数据结构.在我的实现中,我有一个基本的缺点框,其中包含许多基本类型:atom,string,number,list,bool,primitive-function.

设计您的VM并确保保持API清洁.我的最后一个实现将此作为顶级API(原谅格式化 - SO正在点我的预览)

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 &stm, t_ConsBox *box);
void RunProgram(char *program);
void RunProgram(iostream &stm);

不需要RunProgram - 它是在Read,Eval和Print方面实现的.REPL是口译员的常见模式,尤其是LISP.

ConsBoxFactory可用于制作新的缺点框并对其进行操作.使用AtomFactory,以便等效的符号原子映射到一个对象.环境用于维护符号与缺陷框的绑定.

你的大多数工作都应该进入这三个步骤.然后你会发现你的客户端代码和支持代码看起来也非常像LISP:

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

你可以在yacc/lex中编写解析器,但为什么要这么麻烦？Lisp是一个非常简单的语法和扫描/递归下降解析器对,它大约需要两个小时的工作.最糟糕的部分是编写谓词来识别标记(即IsString,IsNumber,IsQuotedExpr等),然后编写例程将标记转换为cons框.

可以轻松地将胶水写入和输出C代码,并在出现问题时轻松调试问题.

来自Samuel Kamin的书" 编程语言,基于翻译的方法"的Kamin口译员,由Timothy Budd翻译成C++.我不确定裸源代码有多么有用,因为它本书也适用,但它是一本很好的书,涵盖了用较低级语言实现Lisp的基础知识,包括垃圾收集等.(这不是本书的重点,一般是编程语言,但它已被涵盖.)

Lisp in Small Pieces更深入,但这对你的情况既好又坏.有很多关于编译的材料,这些材料与你无关,而且它的简单解释器是Scheme,而不是C++.

肯定是SICP很好.没有矫枉过正,但当然,编写口译员只是本书的一小部分.

JScheme的建议也是一个很好的建议(它包含了我的一些代码),但不会帮助你处理像GC这样的事情.

我可能会在稍后提出更多建议.

编辑:有些人说他们从我的awklisp中学到了东西.这无疑是一种奇怪的建议,但它非常小,可读,实际可用,与其他微小但可读的玩具Lisp不同,它实现了自己的垃圾收集器和数据表示,而不是依赖于底层的高级实现语言.提供他们.