用 Prolog 编写的正则表达式解析器 [英] RegEx Parser written in Prolog

问题描述

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

I've been banging my head against the wall on this homework problem for a few hours now. We have to parse a regular expression with Prolog. For the most part, the predicates I have work, but there's a few regular expression and string combos which cause them to run out of stack space in SWI-Prolog. Here's a sample with two of the Regex string combinations, one that works and one that doesn't:

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

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

The first one works and the second one runs out of stack.

这是我正在使用的谓词:

Here's the predicates I'm using:

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

我不确定我需要进行哪些更改才能使其正常工作，但我不确定还可以做什么.

I'm not sure what change I need to make to get it to work right, but I'm not sure what else to do.

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

Also, changing List :- append(List1, List2, List) to [H|T] does not evaluate to true for one of the examples.

推荐答案

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

I don't have access to SWI Prolog right now, but here is a guess:

尝试改变

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 在迭代星型结构时吃点东西".

to force re_match to "eat something" when it iterates on the star construct.

这篇关于用 Prolog 编写的正则表达式解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！