无限循环中的 Prolog DCG，无需直接左递归

Question

TLDR

• 我有一个常见的模式，总是陷入无限循环。

图案是

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

• 我不能 100% 确定无限循环的原因。
• 除了转换为尾递归形式之外，还有哪些替代/首选修复方法？

---

加长版

我在 Prolog 中写 DCG 时总是遇到无限循环。

而且，当我使用递归时，这是相同的模式，并且我没有发现任何左递归。

例如，假设我想捕获一个单词并忽略所有非字母。 （基本上，每当我编写词法分析器时，我只对有意义的术语感兴趣，而不是空格、制表符……）。

我会编写以下 Prolog 代码：

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

当我运行以下查询时：

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

它进入无限循环并且永远不会产生结果。

我可以通过将

word

固定为尾递归形式来修复无限循环，但我无法解释无限递归的确切原因。

在简化语法中，我没有发现任何直接左递归， 但如果 NON_LETTERS 和 WORD 为空，S 可能会导致左递归循环..？

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

并且，将

word

固定到尾递归形式中就可以了。

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

有用的链接

您可以在下面的 SWISH 中尝试上面的示例。

• SWISH 链接：https://swish.swi-prolog.org/p/infinite_loop_dcg.pl

感谢您的浏览！

Answer 1

无限循环的原因是有直接递归。

例如，

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

% NOTE
% S --> S when NON_LETTERS and WORD become e

事实上，调用

WORD

有一个空终端是一个语法错误。

修复方法是使

word

不包含空终端。

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