Почему мой токенизатор Prolog S-expression не работает в базовом случае?

Чтобы немного изучить Пролог (я использую GNU Prolog) и изучить его возможности синтаксического анализа, я начинаю с написания токенизатора Лиспа (или S-выражения, если быть точным), который с учетом набора токенов, таких как ['(', 'f', 'o', 'o', ')'], должен производить ['(', 'foo', ')']. Это не работает должным образом, поэтому я здесь! Я думал, что мой мыслительный процесс просвечивает в моем псевдокоде:

tokenize([current | rest], buffer, tokens):
    if current is '(' or ')',
        Tokenize the rest,
        And the output will be the current token buffer,
        Plus the parenthesis and the rest.

    if current is ' ',
        Tokenize the rest with a clean buffer,
        And the output will be the buffer plus the rest.
    
    if the tail is empty,
        The output will be a one-element list containing the buffer.
    
    otherwise,
        Add the current character to the buffer,
        And the output will be the rest tokenized, with a bigger buffer.

Я перевел это на Пролог следующим образом:

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

    Chars = [] -> Tokens is [Buffer];

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

print_tokens([]) :- write('.').
print_tokens([T | N]) :- write(T), write(', '), print_tokens(N).

main :-
    % tokenize(['(', 'f', 'o', 'o', '(', 'b', 'a', 'r', ')', 'b', 'a', 'z', ')'], '', Tokens),
    tokenize(['(', 'f', 'o', 'o', ')'], '', Tokens),
    print_tokens(Tokens).

При запуске результата, ниже, вот так: gprolog --consult-file lisp_parser.pl он просто говорит мне no. Я проследил main, и это дало мне трассировку стека ниже. Я не понимаю, почему tokenize не работает для пустого случая. Я вижу, что буфер пуст, так как он был очищен предыдущим ')', но даже если Tokens пуст в этот момент времени, не будет ли Tokens рекурсивно накапливать больший результат? Может ли кто-нибудь, кто хорошо разбирается в Прологе, дать мне несколько советов?

| ?- main.

no
| ?- trace.
The debugger will first creep -- showing everything (trace)

(1 ms) yes
{trace}
| ?- main.
      1    1  Call: main ? 
      2    2  Call: tokenize(['(',f,o,o,')'],'',_353) ? 
      3    3  Call: tokenize([f,o,o,')'],'',_378) ? 
      4    4  Call: atom_concat('',f,_403) ? 
      4    4  Exit: atom_concat('',f,f) ? 
      5    4  Call: tokenize([o,o,')'],f,_429) ? 
      6    5  Call: atom_concat(f,o,_454) ? 
      6    5  Exit: atom_concat(f,o,fo) ? 
      7    5  Call: tokenize([o,')'],fo,_480) ? 
      8    6  Call: atom_concat(fo,o,_505) ? 
      8    6  Exit: atom_concat(fo,o,foo) ? 
      9    6  Call: tokenize([')'],foo,_531) ? 
     10    7  Call: tokenize([],'',_556) ? 
     10    7  Fail: tokenize([],'',_544) ? 
      9    6  Fail: tokenize([')'],foo,_519) ? 
      7    5  Fail: tokenize([o,')'],fo,_468) ? 
      5    4  Fail: tokenize([o,o,')'],f,_417) ? 
      3    3  Fail: tokenize([f,o,o,')'],'',_366) ? 
      2    2  Fail: tokenize(['(',f,o,o,')'],'',_341) ? 
      1    1  Fail: main ? 

(1 ms) no
{trace}
| ?- 

Вы можете использовать для этого грамматику определенного предложения, которая предназначена для обработки списков (символов или других вещей). Но кроме этого, это странно: Tokens is [Buffer, Char | Tail_Tokens]; ... это арифметическая оценка, это, вероятно, не то, что вам здесь нужно. Хочешь atom_concat(Buffer,Char,Token), Tokens = [Token|Tail_Tokens]?

David Tonhofer 17.12.2020 00:16

@DavidTonhofer Я думал, что если бы была скобка, я бы сделал что-то вроде этого: 'a', 'b', '(', 'c' для этого фрагмента, как только токенизатор попадет в круглую скобку, он узнает, что буфер ab был полным токеном, и он может очистить буфер токенов. Тогда Tokens будет частично ['ab', '(', ...]. Можете ли вы объяснить мне, почему я бы поставил скобки вместе с ab? И при чем тут арифметическая оценка? Я новичок, так что вы, вероятно, лучше знаете.

Caspian Ahlberg 17.12.2020 00:31

Ну, если вы вызываете is, то то, что находится справа от is, должно быть арифметическим выражением. Как в X is 4+5. Но вы говорите Tokens is [Buffer, Char | Tail_Tokens]. Наверное должно быть Tokens = [Buffer, Char | Tail_Tokens], Просто унификация.

David Tonhofer 17.12.2020 00:49

Помимо замены is на =, вы также должны добавить базовый случай для рекурсивного определения: tokenize([], _, []).

slago 17.12.2020 02:29
Учебная записка [Medium] Leetcode#22 Generate Parentheses
Учебная записка [Medium] Leetcode#22 Generate Parentheses
На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.
1
4
149
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Как насчет этого. Я думаю, это то, что вы хотите сделать, но давайте воспользуемся грамматикой определенных предложений (которые представляют собой просто предложения рога с :- замененным на --> и двумя пропущенными аргументами, содержащими список входных символов и оставшийся список символов. Пример правила DCG:

rule(X) --> [c], another_rule(X), {predicate(X)}.

Правило обработки списка rule//1 гласит: когда вы найдете символ c во входном списке, продолжите обработку списка с помощью another_rule//1, а когда это сработает, вызовите predicate(X) как обычно.

Затем:

% If we encounter a separator symbol '(' or ')', we commit to the
% clause using '!' (no point trying anything else, in particular
% not the clause for "other characters", tokenize the rest of the list,
% and when we have done that decide whether 'MaybeToken', which is 
% "part of the leftmost token after '(' or ')'", should be retained.
% it is dropped if it is empty. The caller is then given an empty
% "part of the leftmost token" and the list of tokens, with '(' or ')'
% prepended: "tokenize('', [ '(' | MoreTokens] )  -->"
 
tokenize('', [ '(' | MoreTokens] ) -->
   ['('],
   !,
   tokenize(MaybeToken,Tokens),
   {drop_empty(MaybeToken,Tokens,MoreTokens)}.
   
tokenize('',[')'|MoreTokens]) --> 
   [')'],
   !,
   tokenize(MaybeToken,Tokens),
   {drop_empty(MaybeToken,Tokens,MoreTokens)}.
   
% No more characters in the input list (that's what '--> []' says).
% We succeed, with an empty token list and an empty buffer fro the
% leftmost token.

tokenize('',[]) --> [].

% If we find a 'Ch' that is not '(' or ')', then tokenize
% more of the list via 'tokenize(MaybeToken,Tokens)'. On
% returns 'MaybeToken' is a piece of the leftmost token found
% in that list, so we have to stick 'Ch' onto its start.

tokenize(LargerMaybeToken,Tokens) --> 
   [Ch],
   tokenize(MaybeToken,Tokens),
   {atom_concat(Ch,MaybeToken,LargerMaybeToken)}.

% ---
% This drops an empty "MaybeToken". If "MaybeToken" is 
% *not* empty, it is actually a token and prepended to the list "Tokens"
% ---

drop_empty('',Tokens,Tokens) :- !.
drop_empty(MaybeToken,Tokens,[MaybeToken|Tokens]).

% -----------------
% Call the DCG using phrase/2
% -----------------

tokenize(Text,Result) :-
   phrase( tokenize(MaybeToken,Tokens), Text ),
   drop_empty(MaybeToken,Tokens,Result),!.

И так:

?- tokenize([h,e,l,l,o],R).
R = [hello].

?- tokenize([h,e,l,'(',l,')',o],R).
R = [hel,(,l,),o].

?- tokenize([h,e,l,'(',l,l,')',o],R).
R = [hel,(,ll,),o].

Я думаю, что в GNU Prolog нотация «привет» генерирует [h,e,l,l,o] напрямую.

Ваш код работает, но я не могу его понять (думаю, это всего лишь мой третий день на Прологе). Перед многими tokenize стоит пустой атом — почему? А также, что здесь означает !? Это меня немного смущает. Спасибо за развернутый ответ, кстати.

Caspian Ahlberg 17.12.2020 01:53

@CaspianAhlberg К этому нужно немного привыкнуть. "!" говорит, что Пролог должен "зафиксировать" текущее выбранное предложение. Если есть какие-либо сбои предикатов «налево» и, следовательно, происходит «повтор» (поиск других решений), выполнение не будет идти справа налево через «!» или другие предложения с тем же именем/арностью не будут проверяться. Вместо этого весь предикат будет считаться неудачным, и будет выбран другой предикат.

David Tonhofer 17.12.2020 09:46

(Я попытался написать не о модели Byrd Box, чтобы объяснить выполнение Пролога, может быть, это поможет: Модель Byrd Box. Вероятно, в ней есть некоторые ошибки.

David Tonhofer 17.12.2020 09:46

«Пустой атом» в tokenize//2 — это состояние буфера. В голове (слева от '-->') это то, что сообщается вызывающему абоненту. Вот почему, когда мы сталкиваемся с '(', левый буфер пуст. Однако, если мы сталкиваемся с 'Ch', то состояние буфера, которое должно быть сообщено вызывающей стороне, равно тому состоянию буфера, которое мы получили при рекурсивном вызове, с буквой «Ч» слева от нее.

David Tonhofer 17.12.2020 09:50

Я не понимаю, почему tokenize не работает для пустого случая.

Причина, по которой что-то терпит неудачу в Прологе, заключается в том, что нет предложения, которое делает это истинным. Если ваше единственное предложение для tokenize имеет форму tokenize([Char | Chars], ...), то ни один вызов формы tokenize([], ...) никогда не сможет соответствовать этому предложению, а поскольку других предложений нет, вызов завершится ошибкой.

Поэтому вам нужно добавить такой пункт. Но сначала:

:- set_prolog_flag(double_quotes, chars).

Это позволяет вам писать ['(', f, o, o, ')'] как "foo".

Кроме того, вы должны предусмотреть случай, когда ввод полностью пуст, или другие случаи, когда вы, возможно, должны выдать токен для буфера, но только если это не '' (поскольку не должно быть '' токенов, засоряющих результат).

finish_buffer(Tokens, Buffer, TokensMaybeWithBuffer) :-
    (   Buffer = ''
    ->  TokensMaybeWithBuffer = Tokens
    ;   TokensMaybeWithBuffer = [Buffer | Tokens] ).

Например:

?- finish_buffer(MyTokens, '', TokensMaybeWithBuffer).
MyTokens = TokensMaybeWithBuffer.

?- finish_buffer(MyTokens, 'foo', TokensMaybeWithBuffer).
TokensMaybeWithBuffer = [foo|MyTokens].

Обратите внимание, что вы можете добавить буфер к списку токенов, даже если вы еще не знаете, что это за список токенов! Это сила логических переменных. Остальная часть кода также использует эту технику.

Итак, случай для пустого ввода:

tokenize([], Buffer, Tokens) :-
    finish_buffer([], Buffer, Tokens).

Например:

?- tokenize([], '', Tokens).
Tokens = [].

?- tokenize([], 'foo', Tokens).
Tokens = [foo].

И остальные случаи:

tokenize([Parenthesis | Chars], Buffer, TokensWithParenthesis) :-
    (   Parenthesis = '('
    ;   Parenthesis = ')' ),
    finish_buffer([Parenthesis | Tokens], Buffer, TokensWithParenthesis),
    tokenize(Chars, '', Tokens).
tokenize([' ' | Chars], Buffer, TokensWithBuffer) :-
    finish_buffer(Tokens, Buffer, TokensWithBuffer),
    tokenize(Chars, '', Tokens).
tokenize([Char | Chars], Buffer, Tokens) :-
    Char \= '(',
    Char \= ')',
    Char \= ' ',
    atom_concat(Buffer, Char, NewBuffer),
    tokenize(Chars, NewBuffer, Tokens).

Обратите внимание, как я использовал отдельные предложения для отдельных случаев. Это делает код более читаемым, но у него есть недостаток по сравнению с (... -> ... ; ...), заключающийся в том, что последнее предложение должно исключать символы, обрабатываемые предыдущими предложениями. Когда у вас есть код в этой форме, и вы довольны тем, что он работает, вы можете преобразовать его в форму, используя (... -> ... ; ...), если вы действительно хотите.

Примеры:

?- tokenize("(foo)", '', Tokens).
Tokens = ['(', foo, ')'] ;
false.

?- tokenize(" (foo)", '', Tokens).
Tokens = ['(', foo, ')'] ;
false.

?- tokenize("(foo(bar)baz)", '', Tokens).
Tokens = ['(', foo, '(', bar, ')', baz, ')'] ;
false.

Наконец, что очень важно, оператор is предназначен только для вычисления арифметических выражений. Он выдаст исключение, когда вы примените его к чему-либо, что не является арифметическим. Унификация отличается от вычисления арифметического выражения. Объединение записывается как =.

?- X is 2 + 2.
X = 4.

?- X = 2 + 2.
X = 2+2.

?- X is [a, b, c].
ERROR: Arithmetic: `[a,b,c]' is not a function
ERROR: In:
ERROR:   [20] throw(error(type_error(evaluable,...),_3362))
ERROR:   [17] arithmetic:expand_function([a,b|...],_3400,_3402) at /usr/lib/swi-prolog/library/arithmetic.pl:175
ERROR:   [16] arithmetic:math_goal_expansion(_3450 is [a|...],_3446) at /usr/lib/swi-prolog/library/arithmetic.pl:147
ERROR:   [14] '$expand':call_goal_expansion([system- ...],_3512 is [a|...],_3492,_3494,_3496) at /usr/lib/swi-prolog/boot/expand.pl:863
ERROR:   [13] '$expand':expand_goal(_3566 is [a|...],_3552,_3554,_3556,user,[system- ...],_3562) at /usr/lib/swi-prolog/boot/expand.pl:524
ERROR:   [12] setup_call_catcher_cleanup('$expand':'$set_source_module'(user,user),'$expand':expand_goal(...,_3640,_3642,_3644,user,...,_3650),_3614,'$expand':'$set_source_module'(user)) at /usr/lib/swi-prolog/boot/init.pl:443
ERROR:    [8] '$expand':expand_goal(user:(_3706 is ...),_3692,user:_3714,_3696) at /usr/lib/swi-prolog/boot/expand.pl:458
ERROR:    [6] setup_call_catcher_cleanup('$toplevel':'$set_source_module'(user,user),'$toplevel':expand_goal(...,...),_3742,'$toplevel':'$set_source_module'(user)) at /usr/lib/swi-prolog/boot/init.pl:443
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.
^  Call: (14) call('$expand':'$set_source_module'(user)) ? abort
% Execution Aborted
?- X = [a, b, c].
X = [a, b, c].

Другие вопросы по теме