Как построить дерево синтаксического анализа из серии токенов S-выражения в Прологе?
Меня интересует Пролог как парсер, поэтому я делаю небольшой интерфейс для Лиспа. Я уже сделал токенизатор, который вы можете увидеть здесь:
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. Может быть, кто-нибудь может дать мне более четкое представление о том, как я буду строить дерево? Я был очень рад узнать, что списки Пролога нетипизированы, так что теперь это немного проще, так как не нужны типы суммы. Меня просто очень смущают входные данные для грамматических предложений, таких как sentence(s(NP,VP)) или verb(v(eats)) (в Wiki), почему аргументы имеют такие заумные имена и как я могу начать работу с моим синтаксическим анализатором без особых хлопот.
expr --> [foo].
expr --> list.
seq --> expr, seq.
seq --> expr.
list --> ['('], seq, [')'].
Да, эта страница Википедии не так хороша, как принято.
Ответы 1
Вот начало: разбор списка атомов LISP, который сначала представляет собой неструктурированный список токенов:
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) }.
Добавьте несколько тестовых примеров (есть ли plunit в GNU Prolog?)
:- 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.
Прохладный. Похоже, мы можем принимать списки токенов.
Теперь постройте дерево синтаксического анализа. Это делается путем увеличения члена Пролога с помощью параметров «предикатов DCG». Термин (или несколько терминов) в голове собирает термины (или несколько терминов), появляющиеся в теле, в более крупную структуру, что вполне естественно. Как только токены терминала достигнуты, структура начинает заполняться фактическим содержимым:
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.
Я не могу найти plunit для GNU Prolog, но, возможно, есть какая-то другая система модульного тестирования. На самом деле, я уже понял, как проверить, действительна ли последовательность токенов — построение дерева — это то, что меня сбивает с толку. Не могли бы вы уточнить этот шаг?
Это было так полезно! Спасибо.
Хорошее введение в dcg, metalevel.at/prolog/dcg. У него есть хороший пример построения дерева.