Regular Expressions in Prolog

6
votes

To learn a little about regular expressions in Prolog, I'm trying to write functions that determine whether the input fits the pattern; my functions are as follows:

split(W, [[], W]).

split([X|W], [[X|W1], W2]) :- split(W, [W1, W2]).

match(eps, []).
match(symb(A), [ A ]).
match(union(R1, R2), W) :- match(R1, W).
match(union(R1, R2), W) :- match(R2, W).
match(conc(R1, R2), W)  :- split(W, [W1, W2]), W1 \= [], W2 \= [], match(R1, W1), match(R2, W2).
match(star(R), W)       :- match(R, eps).
match(star(R), W)       :- split(W, [W1, W2]), W1 \= [], match(R, W1), match(star(R), W2).

I enter into SWIPL the following and get the following results:

?- match(star(symb(a)),[a,a,a,a]).
false.

?- match(star(symb(b)),[b]).
false.

As far as I can tell, the other functions are working correctly. Can somebody tell me where I went wrong with handling star?

Thank you!

1
regexprolog
Have you traced your program? - nhahtdh
Note that your program will not be able to match string bbbbbb with regex a*b. If you have learnt about cut, you can also make the program output true and end without going through all other possible cases. - nhahtdh
you should check some answer with [DCG] tag - CapelliC
Your implementation is inefficient, because you split a sequence before looking if it can be a match at all. Search for these three tags to see better solutions. - false
Of interest: SWI-Prolog package regex - Guy Coder

1 Answers

0
votes

Ah, never mind I'm a fool. I needed to change

match(star(R), W) :- match(R, eps).

to just

match(star(R), []).

I kept getting stackoverflows because there was no base case. Live and learn I guess!