Блог

Мне любопытен 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_Resu<
        Result = [Head | Tail_Result]).

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

Теперь у меня есть новая задача: построить дерево синтаксического анализа из этого. Сначала я попытался создать его без грамматики, но это оказалось действительно грязным. Итак, я использую DCGS. Страница Википедии на нем не очень понятна — особенно часть синтаксического анализа с помощью DCGS. Может быть, кто-нибудь может дать мне более четкое представление о том, как я мог бы построить дерево? Я был очень рад узнать, что списки Prolog являются нетипизированными, так что теперь это немного проще, поскольку типы сумм не нужны. Я просто очень смущен вводом в грамматические предложения типа sentence(s(NP,VP)) или verb(v(eats)) (в Вики), почему аргументы имеют такие заумные имена и как я могу начать работу с моим синтаксическим анализатором без особых хлопот.

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

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

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

Вот начало: синтаксический анализ списка атомов 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.
 

Прохладный. Похоже, мы можем принимать списки токенов.

Теперь создайте дерево синтаксического анализа. Это делается путем увеличения термина Prolog с помощью параметров «предикатов 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.