问题描述
几个小时以来,我一直在努力解决这个家庭作业问题.我们必须用 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 编写的正则表达式解析器的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!