High-order DCG: blanks non-termination

General
1

Anyone knows why t2/2 doesn’t terminate? Note that t2/2 uses blanks//0 instead of blank//0.

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

t1(List) :-
   Str = `this is a test`,
   phrase(  (sequence(nonblanks,blank,List)),
             Str).

t2(List) :-
   Str = `this is a test`,
   phrase(  (sequence(nonblanks,blanks,List)),
             Str).

Query:


7 ?- t1(L).
L = [[116, 104, 105, 115], [105, 115], [97], [116, 101, 115, 116]].

8 ?- t2(L).
% doesn't terminate
2

the problem is that both nonblanks//1 and blanks//0 accept 0 or more tokens from input, thus backtracking cannot advance analysis.

t2/1 should use instead

phrase(  (sequence(nonblanks,(blank,blanks),List)), Str)

I’ve been bitten (far ago) from this bug in more complex contexts, where I was using string//1 in sparse nonterminals, and happened that 2 string//1 calls had no tokens in between.

HTH

3 Likes
3

Good catch! Had me scratching my head! Appreciate your reply.