RegEx Parser escrito en Prolog

Question

He estado golpeando mi cabeza contra la pared en este problema de tarea durante unas horas. Tenemos que analizar una expresión regular con Prolog. En su mayor parte, los predicados que tengo funcionan, pero hay algunas expresiones regulares y combos de cadenas que hacen que se queden sin espacio de pila en SWI-Prolog. He aquí una muestra con dos de las combinaciones expresión regular, uno que funcione y una que no lo hace:

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

El primero funciona y el segundo se queda sin pila.

aquí está el predicados que estoy usando:

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

No estoy seguro de qué cambios tengo que hacer para conseguir que funcione bien, pero no estoy seguro de qué otra cosa hacer.

Además, al cambiar Lista: - anexar (Lista1, Lista2, Lista) a [H | T] no se evalúa como verdadero para uno de los ejemplos.

Answer 1

no tengo acceso a SWI Prolog en este momento, pero aquí es una suposición:

Intente cambiar

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

a

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

para forzar re_match a "comer algo "cuando itera en la construcción de estrella.

Answer 2

Considere el uso de la notación DCG para una mejor legibilidad y razonar con mayor facilidad sobre las propiedades de terminación:

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

Ejemplo usando longitud/2 para generar cada vez más larga lista de generar cadenas que se corresponden con la expresión regular:

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