Search code examples
prologdcgfailure-slice

prolog dcg restriction

I would like to use DCGs as a generator. As of now, the syntax is

s-->a,b.
a-->[].
a-->a,c.
c-->[t1].
c-->[t2].
b-->[t3].
b-->[t4].

I would like to generate all s where the length of a is < someNumber.

Using ?- phrase(a,X),length(X,Y),Y<4. i can get all a with less than 4 items. However, when all combinations are exhausted, the system (SWI-Prolog 6.2.5) seems to stall. Sometimes ago, a similar question was asked here. However, being new to Prolog i am not able to make it work with the grammar above. Any ideas?

Update: There was a comment by (canrememberthename) which got deleted, somehow. Anyway, it was suggested to use between(1,4,Y),length(X,Y),phrase(a,X). to set limits. This worked nicely, after changing my code to a-->c,a.

Solution

  • the nonterminal a//0 is both left recursive and 'epsilon' (generate the empty sequence), and phrase/2 will loop immediately after the empty production.

    You can solve your problem bounding list' length:

    ?- between(1,4,Y),length(X,Y),phrase(a,X).

    and, as you have already done, removing the left recursion.