使用 DCG 在 Prolog 中标记字符串

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, [].

在 "aa bb" 上调用 tokenize 给我留下了几个可能的回应：

 ?- 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, [].

但是有一个问题：虽然 "aa" 调用的 token 的单一答案现在是一个很好的列表，但 tokenize 谓词最终以无限递归结束：

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

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

我错过了什么？ Prolog中一般是怎么解决这个问题的？

Answer 1

潜在的问题是，在您的第二个版本中，token//1 也成功用于 "empty" 令牌：

?- 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 以可移植的方式访问 DCG，即独立于任何特定 Prolog 系统使用的实际实现方法。

最后一个DCG子句中的[]是多余的，您可以将其删除。

此外，避免使用这么多 !/0。提交第一个匹配的标记化是可以的，但只能在一个地方进行，比如通过 phrase/2 调用周围的 once/1。

命名见我上面的评论。我建议使用 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])].

使用 DCG 在 Prolog 中标记字符串

Tokenizing a string in Prolog using DCG

prolog

dcg