RegEx Parser用Prolog编写

Question

我已经在这个家庭作业问题上一直撞到墙上几个小时了.我们必须用Prolog解析正则表达式.在大多数情况下,我使用的谓词,但是有一些正则表达式和字符串组合导致它们在SWI-Prolog中耗尽堆栈空间.这是一个包含两个正则表达式字符串组合的示例,一个有效,另一个没有:

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]并不会为其中一个示例评估为true.

Answer 1

考虑使用DCG表示法以获得更好的可读性并更容易地推断终止属性:

:- op(100, xf, *).

rexp(eps)      --> [].
rexp([T])      --> [T].
rexp(_*)       --> [].
rexp(R*)       --> rexp(R), rexp(R*).
rexp(s(R1,R2)) --> rexp(R1), rexp(R2).
rexp((R1|R2))    --> ( rexp(R1) ; rexp(R2) ).

使用length/2生成越来越长的列表以生成由regexp匹配的字符串的示例:

?- length(Ls, _), phrase(rexp(s(([a]|[b]),[c]*)), Ls).
Ls = [a] ;
Ls = [b] ;
Ls = [a, c] ;
Ls = [b, c] ;
Ls = [a, c, c] ;
etc.

Answer 2

我现在无法访问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当它在星形构造上迭代时强制"吃东西".