用Prolog编写的RegEx解析器

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： - 追加（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“吃东西“当它在星形结构上迭代时。

Answer 2

考虑使用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)). 

使用长度/ 2逐渐变长的产生实施例列出，以生成由正则表达式匹配的字符串：

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