ark*_*ate 8 compiler-construction interpreter prolog dcg
我已经熟悉了函数式编程; 我对Haskell和PLT Scheme很熟悉(虽然不精通).我已经使用PLT Scheme为玩具语言建立了很少的解释器(引用PLAI) - 我更喜欢命令式语言.
任何人都可以指导我使用我可以用Prolog建立一个我选择的玩具语言的小型翻译的资源吗？
我主要使用swi-prolog,所以我说的大部分内容都与swi-prolog相关.但是,其他prolog实现可能有类似的谓词/库(可能名称有点不同),因此您可以搜索他们的手册并找到它们.另外,我正在prolog中编写一个编译器而不是一个解释器,所以也许某些部分与解释器无关.
SWI-Prolog的文档站点非常适合查找内容:使用搜索框查找任何谓词或进行典型搜索.有很多库,但您可能希望自己实现一些东西以获得经验.你最终可能会重新发明轮子但它会很有用.
"Prolog的艺术"一书(Sterling,Shapiro)有一章致力于在prolog中构建编译器(这也是prolog的一本好书).
也许有一些工具相当于lex/bison for prolog; 我从未真正搜索过.
Imho,lexer在简单的序言中很容易; 当然,它将主要基于模式匹配.
对于解析器,我建议使用DCG:明确的子句语法:swi-prolog doc,google了解更多详情.
问题是你必须解析整个文件(或者至少我没有办法解决它).顺便说一句,词法分析器也可以用DCG完成,但我不认为它真的更好.
如果您选择使用中间代码,则可以从解析器中轻松生成抽象语法树(您也可以在解析过程中评估很多内容).
关于语义检查:在我的玩具语言编译器中,我在解析期间执行大部分语义检查(范围相关,函数调用),其余部分在单独的步骤中执行.这有点乱
其他有用的东西:检查assert/1,全局变量,元谓词(maplist/[2-6]).
不是纯粹的prolog,你可能会通过滥用它们使你的代码过于强制(然后你可能会有一些非常讨厌的副作用)
对于符号表(如果需要),您可以使用assert/1来添加谓词:swi-prolog使用动态哈希表来表示动态谓词.警告:动态谓词比静态慢,因此,当您完成表并且不会进行任何更改时,请使用compile_predicates/1使它们成为静态.例如,当我完成解析时,我的ST准备好了,所以我编译它.ST的另一个解决方案是使用关联列表.它们用AVL树实现,因此成本为O(log(N)).