如何在 Prolog DCG 中不使用剪切来表达“不”

Question

我正在开发 Prolog DCG 解析器，将字符串标记为特定模式。我的目标是解析像

mul(Number,Number)

、

do()

和

don't()

这样的标记，同时忽略所有其他模式。

这是我当前的实现：

parser([Token|Rest]) --> not_token, token(Token), not_token, parser(Rest).
parser([]) --> [].

token(mul(N1, N2)) -->
  "mul(", number(N1), ",", number(N2), ")".
token(do) --> "do()".
token(dont) --> "don't()".

not_token -->
  string(Codes),
  { \+ phrase(token(_), Codes) }.

当我运行以下查询时：

?- phrase(parser(Tokens), `mul(mul(123,456)dommmmulmul(1,2))`).

它确实找到了正确的解决方案，但也找到了错误的解决方案，因为

not_token

的定义方式不同。

Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456), mul(1, 2)] ;
Tokens = [mul(123, 456)] ; -- Incorrect
Tokens = [mul(1, 2)] ; -- Incorrect
false.

我可以使用剪切在第一个解决方案处停止，但是有没有办法在 DCG 中表达

not_token

，以便它只返回正确的结果。

对于更复杂的测试用例，它实际上来自https://adventofcode.com/2024/day/3。 当前的解决方案可以通过剪切解决确切的问题，但我希望能够将我的 DCG 写得更严格，以便它只能找到正确的解决方案。

Answer 1

您可以在回溯中找到每个令牌并使用 findall/3 来收集令牌。这将是全部代码：

:- use_module(library(dcg/basics)).

find_token(T) --> string(_), token(T), string(_).

token(mul(N1, N2)) -->
  "mul(", number(N1), ",", number(N2), ")".
token(do) --> "do()".
token(dont) --> "don't()".

这就是使用 findall 查询它的方式：

?- findall(T, phrase(find_token(T), `mul(mul(123,456)dommmmulmul(1,2))`), Tokens).
Tokens = [mul(123, 456), mul(1, 2)].