基于 Prolog 的解释器

Question

我已经开始接触函数式编程了。我熟悉(虽然不精通)Haskell 和 PLT Scheme。我已经使用 PLT Scheme 为玩具语言构建了小解释器(引用 PLAI)——我更擅长命令式语言。

谁能指导我使用 Prolog 构建我选择的玩具语言的小型解释器的资源？

Answer 1

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

SWI-Prolog's documentation site非常适合查找内容:使用搜索框查找任何谓词或进行典型搜索。有大量的库，但您可能想自己实现一些东西来获得经验。您最终可能会重新发明轮子，但这会很有用。

“序言的艺术”一书(Sterling，Shapiro)有一章专门介绍在序言中构建编译器(这也是序言的好书)。

也许有一些工具相当于 prolog 的 lex/bison；我从来没有真正搜索过。
恕我直言，词法分析器在简单的序言中很容易；自然，它将在很大程度上基于模式匹配。

对于解析器，我建议使用 DCG:确定子句语法:swi-prolog doc , 谷歌了解更多详情。
问题是你必须解析整个文件(或者至少我没有找到其他方法)。
顺便说一句，词法分析器也可以用 DCG 来完成，但我不认为它真的更好。

如果您选择使用中间代码，则解析器很容易生成抽象语法树(您也可以在解析过程中评估很多东西)。
关于语义检查:在我的玩具语言编译器中，我在解析过程中进行大部分语义检查(范围相关，函数调用)，其余的在单独的步骤中进行。有点乱

其他有用的东西:检查 assert/1、全局变量、meta predicates (maplist/[2-6]).
不是纯序言，您可能会通过滥用它们使您的代码变得过于必要(然后您可能会产生一些非常讨厌的副作用)

对于符号表(如果需要)，您可以使用 assert/1 添加谓词:swi-prolog 使用动态哈希表作为动态谓词。警告:动态谓词比静态更慢，因此，当您完成表格并且不打算进行任何更改时，请使用 compile_predicates/1 使它们成为静态。例如，当我完成解析时，我的 ST 准备好了，所以我编译它。
ST 的另一个解决方案是使用 association lists .它们是用 AVL 树实现的，所以成本是 O(log(N))。