如何从 Prolog 中的一系列 S 表达式标记构建解析树？

Question

我对作为解析器的 Prolog 很好奇，所以我正在制作一些 Lisp 前端。我已经做了一个分词器，你可以在这里看到：

base_tokenize([], Buffer, [Buffer]).
base_tokenize([Char | Chars], Buffer, Tokens) :-
    (Char = '(' ; Char = ')') ->
        base_tokenize(Chars, '', Tail_Tokens),
        Tokens = [Buffer, Char | Tail_Tokens];

    Char = ' ' ->
        base_tokenize(Chars, '', Tail_Tokens),
        Tokens = [Buffer | Tail_Tokens];

    atom_concat(Buffer, Char, New_Buffer),
    base_tokenize(Chars, New_Buffer, Tokens).

filter_empty_blank([], []).
filter_empty_blank([Head | Tail], Result) :-
    filter_empty_blank(Tail, Tail_Result),
    ((Head = [] ; Head = '') ->
        Result = Tail_Result;
        Result = [Head | Tail_Result]).

tokenize(Expr, Tokens) :-
    atom_chars(Expr, Chars),
    base_tokenize(Chars, '', Dirty_Tokens),
    filter_empty_blank(Dirty_Tokens, Tokens).

我现在有一个新的挑战：从中构建一个解析树。首先，我尝试制作一个没有语法的，但结果真的很乱。所以我正在使用 DCG。维基百科在 it 上的页面不是很清楚 - 尤其是 使用 DCG 解析 部分。也许有人可以让我更清楚地了解如何构建一棵树？我很高兴知道 Prolog 的列表是无类型的，所以现在不需要求和类型就容易多了。我只是对 sentence(s(NP,VP)) 或 verb(v(eats))（在 Wiki 上）这样的语法子句的输入感到困惑，为什么参数具有如此深奥的名称，以及如何轻松开始使用我的解析器.

expr --> [foo].
expr --> list.

seq --> expr, seq.
seq --> expr.

list --> ['('], seq, [')'].

Answer 1

这是一个开始：解析 LISP list-of-atom，它最初是非结构化的 list-of-token:

List = [ '(', '(', foo, bar, ')', baz ')' ].

先接受一下吧

直接写下语法：

so_list         --> ['('], so_list_content, [')'].

so_list_content --> [].
so_list_content --> so_atom, so_list_content.
so_list_content --> so_list, so_list_content.

so_atom         --> [X], { \+ member(X,['(',')']),atom(X) }.

添加一些测试用例（GNU Prolog中有plunit吗？）

:- begin_tests(accept_list).

test(1,[fail])        :- phrase(so_list,[]).
test(2,[true,nondet]) :- phrase(so_list,['(',')']).
test(3,[true,nondet]) :- phrase(so_list,['(',foo,')']).
test(4,[true,nondet]) :- phrase(so_list,['(',foo,'(',bar,')',')']).
test(5,[true,nondet]) :- phrase(so_list,['(','(',bar,')',foo,')']).
test(6,[fail])        :- phrase(so_list,['(',foo,'(',bar,')']).

:- end_tests(accept_list).

所以：

?- run_tests.
% PL-Unit: accept_list ...... done
% All 6 tests passed
true.

酷。看来我们可以接受 lists-of-tokens.

现在构建一个解析树。这是通过“DCG 谓词”的参数增加 Prolog 项来完成的。 head 中的术语（或多个术语）将 body 中出现的术语（或多个术语）自然地收集到一个更大的结构中。到达终端标记后，结构开始填充实际内容：

so_list(list(Stuff))   --> ['('], so_list_content(Stuff), [')'].

so_list_content([])        --> [].
so_list_content([A|Stuff]) --> so_atom(A), so_list_content(Stuff).
so_list_content([L|Stuff]) --> so_list(L), so_list_content(Stuff).

so_atom(X) --> [X], { \+ member(X,['(',')']),atom(X) }.

是的，测试（将预期结果移出测试头，因为视觉噪音太大）

:- begin_tests(parse_list).

test(1,[fail]) :-
   phrase(so_list(_),[]).

test(2,[true(L==Result),nondet]) :-
   phrase(so_list(L),['(',')']),
   Result = list([]).
   
test(3,[true(L==Result),nondet]) :-
   phrase(so_list(L),['(',foo,')']),
   Result = list([foo]).
   
test(4,[true(L==Result),nondet]) :-
   phrase(so_list(L),['(',foo,'(',bar,')',')']),
   Result = list([foo,list([bar])]).
   
test(5,[true(L==Result),nondet]) :-
   phrase(so_list(L),['(','(',bar,')',foo,')']),
   Result = list([list([bar]),foo]).
   
test(6,[fail]) :-
   phrase(so_list(_),['(',foo,'(',bar,')']).

:- end_tests(parse_list).

所以：

?- run_tests.
% PL-Unit: parse_list ...... done
% All 6 tests passed
true.

如何从 Prolog 中的一系列 S 表达式标记构建解析树？

How do I construct a parse tree from a series of S-expression tokens in Prolog?

grammar

parsing

prolog

parse-tree

dcg