用 Prolog 编写的 RegEx 解析器

Question

几个小时以来，我一直在努力解决这个家庭作业问题。我们必须用 Prolog 解析一个正则表达式。在大多数情况下，我使用的谓词是有效的，但是有一些正则表达式和字符串组合会导致它们在 SWI-Prolog 中耗尽堆栈空间。这是一个包含两种 Regex 字符串组合的示例，一种有效，一种无效:

star(star(char(a))), []
star(star(char(a))), [a]

第一个有效，第二个用完堆栈。

这是我正在使用的谓词:

re_match(epsilon, []).
re_match(char(Letter), [Letter]).
re_match(star(_), []).
re_match(seq(Rx1, Rx2), List) :- append(List1, List2, List),  re_match(Rx2, List2),  re_match(Rx1, List1).
re_match(alt(Rx1, Rx2), List) :- re_match(Rx1, List); re_match(Rx2, List).
re_match(star(Rx), List) :- append(List1, List2, List), re_match(Rx, List1), re_match(star(Rx), List2).

我不确定我需要做哪些改变才能让它正常工作，但我不确定还能做什么。

此外，将 List :- append(List1, List2, List) 更改为 [H|T] 对于其中一个示例不会评估为真。

Answer 1

我现在无法访问 SWI Prolog，但这是一个猜测:

尝试改变

re_match(star(Rx), List) :- append(List1, List2, List),
                            re_match(Rx, List1),
                            re_match(star(Rx), List2).

到

re_match(star(Rx), List) :- append([H|List1], List2, List),
                            re_match(Rx, [H|List1]),
                            re_match(star(Rx), List2).

给力 re_match当它迭代星形结构时“吃东西”。