Tokenizing string в Prolog с использованием DCG

Question

Предположим, я хочу токенизировать строку слов (символов) и чисел, разделенных пробелами. Например, ожидаемым результатом токенизации "aa 11" будет [tkSym("aa"), tkNum(11)].

Моя первая попытка была ниже код:

whitespace --> [Ws], { code_type(Ws, space) }, whitespace. 
whitespace --> []. 

letter(Let)  --> [Let], { code_type(Let, alpha) }. 
symbol([Sym|T]) --> letter(Sym), symbol(T). 
symbol([Sym]) --> letter(Sym). 

digit(Dg)  --> [Dg], { code_type(Dg, digit) }. 
digits([Dg|Dgs]) --> digit(Dg), digits(Dgs). 
digits([Dg])  --> digit(Dg). 

token(tkSym(Token)) --> symbol(Token). 
token(tkNum(Token)) --> digits(Digits), { number_chars(Token, Digits) }. 

tokenize([Token|Tokens]) --> whitespace, token(Token), tokenize(Tokens). 
tokenize([]) --> whitespace, []. 

Вызов tokenize на "aa bb" оставляет меня несколько возможных ответов:

?- tokenize(X, "aa bb", []). 
X = [tkSym([97|97]), tkSym([98|98])] ; 
X = [tkSym([97|97]), tkSym(98), tkSym(98)] ; 
X = [tkSym(97), tkSym(97), tkSym([98|98])] ; 
X = [tkSym(97), tkSym(97), tkSym(98), tkSym(98)] ; 
false. 

В этом случае, однако, представляется целесообразным рассчитывать только один правильный ответ. Вот еще один, более детерминированный подход:

whitespace --> [Space], { char_type(Space, space) }, whitespace. 
whitespace --> []. 

symbol([Sym|T]) --> letter(Sym), !, symbol(T). 
symbol([])  --> []. 
letter(Let)  --> [Let], { code_type(Let, alpha) }. 

% similarly for numbers 

token(tkSym(Token)) --> symbol(Token). 

tokenize([Token|Tokens]) --> whitespace, token(Token), !, tokenize(Tokens). 
tokenize([]) --> whiteSpace, []. 

Но есть проблема: хотя однозначного ответа на token призвал "aa" теперь хороший список, то tokenize предикат заканчивается в бесконечной рекурсии:

?- token(X, "aa", []). 
X = tkSym([97, 97]). 

?- tokenize(X, "aa", []). 
ERROR: Out of global stack 

Что мне не хватает? Как обычно проблема решается в Prolog?

Answer 1

Основная проблема заключается в том, что в вашей второй версии, token//1 также преуспевает в «пустой» знак:

?- phrase(token(T), ""). 
T = tkSym([]). 

Таким образом, неумышленно, следующий преуспевает тоже, как и произвольное количество маркеров:

?- phrase((token(T1),token(T2)), ""). 
T1 = T2, T2 = tkSym([]). 

Чтобы исправить это, я рекомендую вам настроить определения так, чтобы токен должен состоять как минимум из одного лексического элемента, что также типично. Хорошим способом обеспечения того, чтобы описал хотя бы один элемент, является разделение правил DCG на два набора. Например, как показано на symbol///1:

symbol([L|Ls]) --> letter(L), symbol_r(Ls). 

symbol_r([L|Ls]) --> letter(L), symbol_r(Ls). 
symbol_r([])  --> []. 

Таким образом, можно избежать неограниченную рекурсию, которая может бесконечно потреблять пустые маркеры.

Другие:

всегда использовать phrase/2 для доступа DCGs переносимым способом, то есть, независимо от фактической реализации метода, используемого какой-либо конкретной системы Prolog.

[] в окончательном предложении DCG является излишним, его можно просто удалить.

Также избегайте использования большого количества !/0. Это нормально, чтобы зафиксировать первый сопоставление токенизации, но делать это только в одном месте, например, через once/1, обернутый вокруг вызова phrase/2.

Для обозначения, см. Мой комментарий выше. Я рекомендую использовать tokens//1, чтобы сделать это более декларативным. Примеры запросов, используя приведенное выше определение symbol//1:

?- phrase(tokens(Ts), ""). 
Ts = []. 

?- phrase(tokens(Ls), "a"). 
Ls = [tkSym([97])]. 

?- phrase(tokens(Ls), "a b"). 
Ls = [tkSym([97]), tkSym([98])].