Prolog Question - Simple Grammar Implementation

Question

If I have the following grammar:

S → ε

S → a S b S

How do I implement it in Prolog?

I tried this:

isMatched([]).

isMatched([a,b]).

isMatched([a|[S1|[b|S2]]]) :- isMatched(S1), isMatched(S2).

But it obviously doesn't work because the head of a list cannot be a list.

I then tried implementing a new version as follows:

conc([], R, R).

conc([H|T], L, [H|R]) :- conc(T, L, R).

isMatched([]).

isMatched([a,b]).

isMatched(List) :- conc([a], S1, List3), isMatched(S1), conc(List3, [b], List2), conc(List2, S2, List), isMatched(S2).

But for the input isMatched([a,b,a]), it runs out of stack.

How do I fix this?

Answer 1

Sounds like homework, so I won't try and do it for you.

You might want to take a look at definite clause grammars (DCGs) in Prolog. This is basically syntactic sugar that allows you to write grammars that read more like grammars than Prolog predicates. If you understand how these work, then you'll probably have a decent understanding of how to parse in Prolog.