7

我已经涉足函数式编程了。我熟悉（虽然不精通）Haskell 和 PLT 方案。我使用 PLT Scheme 为玩具语言构建了小解释器（参考 PLAI）——我更擅长命令式语言。

任何人都可以指导我使用我可以使用 Prolog 构建我选择的玩具语言的小型解释器的资源吗？

4

3 回答 3

6

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

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

“Prolog 的艺术”一书（Sterling，Shapiro）有一章专门介绍在 prolog 中构建编译器（对于 prolog 来说这也是一本不错的书）。

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

对于解析器，我建议使用 DCG：确定子句语法：swi-prolog doc，google 了解更多详细信息。
问题是您将不得不解析整个文件（或者至少我还没有找到其他方法）。顺便说一句，词法分析器也可以用 DCG 完成，但我认为它并没有更好。

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

其他有用的东西：检查 assert/1、全局变量、元谓词（maplist/[2-6]）。
不是纯粹的序言，您可能会滥用它们使您的代码过于迫切（然后您可能会产生一些非常讨厌的副作用）

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

于 2011-11-05T10:43:16.373 回答
4

Markus Triska（这里是他的主页）展示了一些你可能会感兴趣的东西：例如玩具 LISP，或者元解释器的一些技巧。

于 2011-11-05T17:24:44.000 回答
0

我在 Prolog 中为函数式编程语言编写了一个简单的解释器。此处显示了完整的实现及其用法示例：

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :- functional_syntax((
            writeln(factorial(3)+factorial(4)),
            Concatenated_string = "hello" + " " + "world",
            writeln(Concatenated_string),
            writeln(length(Concatenated_string)),
            writeln(type(Concatenated_string)),
            writeln(nth0(0,Concatenated_string)),
            writeln(msort([1,3,2,15,-1]))
        ),true).

factorial(N,Output) :-
    functional_syntax((
        (N=1 -> Output = 1);
        Output = N*factorial(N-1)
    )).

type(A,B) :-
    functional_syntax(A,A1),
    (number(A),B='number';
    is_list(A),B='list';
    atom(A),B='atom').

functional_syntax(A) :- functional_syntax(A,true).
functional_syntax(A,A) :- number(A);var(A);atom(A).
functional_syntax(not(X),Output) :-
    functional_syntax((X = false),Output).
functional_syntax(writeln(A),true) :-
    functional_syntax(A,A1),writeln(A1).
functional_syntax(A+B,C) :-
    functional_syntax([A,B],[A1,B1]),
    ((number(A1),number(B1)) ->
        C is A1+B1;
    (is_list(A1),is_list(B1)) ->
        append(A1,B1,C)).
functional_syntax(A-B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1-B1.
functional_syntax(A*B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1*B1.
functional_syntax(A/B,C) :-
    functional_syntax([A,B],[A1,B1]),C is A1/B1.
functional_syntax(A=B,Result) :-
    functional_syntax(B,B1),
    (A=B1,Result=true;dif(A,B1),Result=false).
functional_syntax(A->B,Result) :-
    (functional_syntax(A,A1),A1=true) -> (functional_syntax(B,B1),Result=true,B1=true);
    Result=false.
functional_syntax([],[]).
functional_syntax([A|B],[A1|B1]) :-
    functional_syntax(A,A1),functional_syntax(B,B1).
functional_syntax((A,B),Result) :-
    functional_syntax([A,B],[A1,B1]),
    (A1,B1,Result=true;([A1,B1]=[true,false];[A1,B1]=[false,true]),Result=false).
functional_syntax((A;B),Result) :-
    (functional_syntax(A,A1),call(A1);
    functional_syntax(B,B1),call(B1)) -> (Result = true);
    (functional_syntax(A,A1),A1=false,Result=false).
functional_syntax(Input,Output1) :-
    not(number(Input)),
    Input =.. [Name|Params],
    \+member(Name,['=','->',not,'[|]',',',';',+,-,*,/]),
    length(Params,Params_length),
    Params_length > 0,
    functional_syntax(Params,Params1),
    append([Name|Params1],[Output1],Input0),
    Input1 =.. Input0,
    call(Input1).

同样，可以在 Prolog 中为命令式编程语言编写解释器。

于 2018-05-07T01:36:08.140 回答