如何从 Prolog 中的一系列 S 表达式标记构建解析树?
How do I construct a parse tree from a series of S-expression tokens in Prolog?
我对作为解析器的 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, [')'].
这是一个开始:解析 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 很好奇,所以我正在制作一些 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, [')'].
这是一个开始:解析 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.