TLDR

• I have a common pattern that always fall in an infinite loop.

The pattern is

s([H|Rest]) --> non_letters, word(H), non_letters, s(Rest).
s([]) --> [].

• I am not 100% sure the cause of an infinite loop.
• What are the alternative/preferred method to fix other than converting into a tail recursion form?

---

Longer version

I always run into an infinite loop when writing DCG in Prolog.

And, it's the same pattern when I use a recursion and I do not spot any left recursion.

For example, say I want to capture a word and ignore every non letters. (basically, whenever I'm writing a lexer like I'm only interested in the meaningful terms rather than space, tabs, ...).

I would write the following Prolog code:

s([H|Rest])    --> non_letters, word(H), non_letters, s(Rest).
s([])          --> [].

non_letters    --> non_letter, non_letters.
non_letters    --> [].

non_letter     --> [C], {\+ code_type(C, alpha)}.

word([L|Rest]) --> letter(L), word(Rest). % <-- NOTE: word also has the same pattern.
word([])       --> [].

letter(C)      --> [C], {code_type(C, alpha)}.

When I run the following query:

?- phrase(s(Out), `Hello World`).

It goes into an infinite loop and never produces a result.

I can fix the infinite loop by fixing word into the tail recursion form, but I can't explain the exact cause of the infinite recursion.

In the simplified grammar, I don't spot any direct left recursion, but S can result in a left recursion loop if NON_LETTERS and WORD are empty..?

S           --> NON_LETTERS WORD NON_LETTERS S | e
NON_LETTERS --> non_letter NON_LETTERS | e
WORD        --> letter WORD | e

And, fixing word into the tail recursion form would work.

% ... <same as before skip> ...

word(Word)           --> letter(L), word_rest([L], Word).

word_rest(Acc, Word) --> letter(L), word_rest([L|Acc], Word).
word_rest(Acc, Out)  --> [], {reverse(Acc, Out)}.

Helpful links

You can try the above example in the following SWISH.

• SWISH link: https://swish.swi-prolog.org/p/infinite_loop_dcg.pl

Thank you for looking !

Here is a minimal explanation, a failure-slice why your program loops. First, you have to modify something in the remaining visible part in order to fix non-termination.

:- set_prolog_flag(double_quotes, chars).

s([H|Rest])    --> non_letters, word(H), non_letters, s(Rest), {false}.
s([])          -->  {false}, [].

non_letters    --> {false}, non_letter, non_letters.
non_letters    --> [].

word([L|Rest]) --> {false}, letter(L), word(Rest).
word([])       --> [].

?- phrase(s(Out), "Hello World"), false.
   loops.