Search code examples
regexprologdcg

RegEx Parser written in Prolog

I've been banging my head against the wall on this homework problem for a few hours now. We have to parse a regular expression with Prolog. For the most part, the predicates I have work, but there's a few regular expression and string combos which cause them to run out of stack space in SWI-Prolog. Here's a sample with two of the Regex string combinations, one that works and one that doesn't:

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

The first one works and the second one runs out of stack.

Here's the predicates I'm using:

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

I'm not sure what change I need to make to get it to work right, but I'm not sure what else to do.

Also, changing List :- append(List1, List2, List) to [H|T] does not evaluate to true for one of the examples.

Solution

  • I don't have access to SWI Prolog right now, but here is a guess:

    Try changing

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

    to

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

    to force re_match to "eat something" when it iterates on the star construct.