RegEx Parser scritto in Prolog

Question

Ho battuto la testa contro il muro su questo problema di compiti a casa per alcune ore. Dobbiamo analizzare un'espressione regolare con Prolog. Per la maggior parte, i predicati funzionano, ma ci sono alcune espressioni regolari e combinazioni di stringhe che fanno sì che finiscano lo spazio di stack in SWI-Prolog. Ecco un esempio con due delle combinazioni di stringhe Regex, quello che funziona e uno che non lo fa:

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

Il primo funziona e il secondo esaurisce la pila.

Ecco i predicati che sto 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). 

Non sono sicuro di quale cambiamento ho bisogno di fare per farlo funzionare bene, ma non sono sicuro che altro fare.

Inoltre, la modifica dell'elenco: - append (Elenco1, Elenco2, Elenco) su [H | T] non viene valutata come vera per uno degli esempi.

Answer 1

Non ho accesso a SWI Prolog in questo momento, ma qui è una supposizione:

Provare a cambiare

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

per costringere re_match a "mangiare qualcosa "quando itera sul costrutto stellare.

Answer 2

Considerare l'utilizzo di DCG notazione per una migliore leggibilità e di ragionare più facilmente sulle proprietà di terminazione:

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

Esempio con lunghezza/2 per generare sempre più elenca per generare le stringhe che è compensato dal 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.