基于Prolog的解释器

Question

我已经习惯了函数式编程;我对Haskell和PLT计划很熟悉（尽管不太熟练）。我已经使用PLT Scheme来构建玩具语言的小解释器（参考PLAI） - 我用命令式语言更好。

任何人都可以指引我使用资源，我可以用它来构建一个我用Prolog选择的玩具语言的小解释器吗？

Answer 1

我主要使用swi-prolog，所以我说的大部分将会与swi-prolog有关。然而，其他prolog实现可能有类似的谓词/库（可能有不同的名称），因此您可以搜索他们的手册并找到它们。另外，我在编程中写了一个编译器，而不是解释器，所以也许有些部分不是与解释器相关的。

SWI-Prolog's documentation site非常适合查找内容：使用搜索框查找任何谓词或执行典型搜索。有大量的图书馆，但你可能想自己实施一些东西来获得经验。你可能会重新发明轮子，但它会很有用。

“Prolog的艺术”一书（Sterling，Shapiro）有一章致力于在prolog中编译编译器（对于prolog也是一本很好的书）。

也许有一些工具相当于lex/bison for prolog;我从没真正搜过。
Imho，词法分析器在普通序言中很容易;自然，它将很大程度上依赖于模式匹配。

对于解析器，我建议使用DCG：明确子句语法：swi-prolog doc，google了解更多详情。
问题是，你将不得不解析整个文件（或者至少我没有找到一种方法来做到这一点）。 顺便说一句，词法分析器也可以用DCG完成，但我不认为它更好。

如果您选择具有中间代码，那么抽象语法树很容易从解析器中生成（您也可以在解析过程中评估很多东西）。
关于语义检查：在我的编译器中，对于玩具语言，我在解析过程中执行了大部分语义检查（与范围有关的函数调用），其余部分在单独的步骤中进行。这是一个有点乱

其他有用的东西：先检查断言/ 1，全局变量，meta predicates (maplist/[2-6]).
不是纯粹的序言中，你可能使你的代码滥用他们（然后你可以有一些非常讨厌的副作用）也势在必行

对于符号表（如果您需要的话），您可以使用assert/1来添加谓词：swi-prolog使用动态哈希表作为动态谓词。警告：动态谓词比静态更慢，因此，当您完成表并且不会进行任何更改时，请使用compile_predicates/1将它们设置为静态。例如，当我完成语法分析时，我的ST已经准备就绪，所以我编译它。 ST的另一个解决方案是使用association lists。它们使用AVL树实现，因此成本为O（log（N））。

Answer 2

Markus Triska（here他的主页）显示了几件有趣的事情，例如：toy LISP，或者meta interpreters。