Prolog DCG非直接左递归下无限循环问题及非尾递归修复方案

• 遇到一种会触发无限循环的Prolog DCG常见模式，代码示例：

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

• 无法完全确定该无限循环的成因
• 除转换为尾递归形式外，寻求更优的替代修复方法

编写Prolog DCG时多次遇到同类无限循环问题，均为采用递归但未发现直接左递归的相同模式。例如，为实现提取单词、忽略所有非字母字符（类似词法分析器，仅关注有效术语，忽略空格、制表符等），编写了如下代码：

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). % ← 注意：word也采用相同模式
word([])       --> [].

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

运行查询：

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

程序陷入无限循环，无法返回结果。

已知将word改为尾递归形式可修复问题，但无法明确无限递归的确切成因。简化语法后未发现直接左递归，但怀疑当NON_LETTERS和WORD为空时，是否会导致S形成左递归循环：

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

将word改为尾递归形式后的修复代码：

% ... 其余代码同上，省略 ...

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)}.

内容的提问来源于Stack Exchange，提问作者Mo...