Prolog, grammar parser

Question

I am a very green when it comes to prolog, but essentially what I am trying to do is implement recursion to parse a grammar rule. What I have seems to be correct logically but obviously not because I am not getting the expected outcome.

Here is the rule I want to parse:

S -> X Y Z
X -> a X | a
Y -> b Y | b
Z -> c Y | c

Here is the prolog code:

match(X, [X|T], T).

xs(X0, X):- match(a, X0, X).
xs(X0, X):- xs(X0, X).
ys(X0, X):- match(b, X0, X).
ys(X0, X):- ys(X0, X).
zs(X0, X):- match(c, X0, X).
zs(X0, X):- zs(X0, X).

s(X0, X):- xs(X0, X1), ys(X1, X2), zs(X2, X).

Any help in understanding what I am doing wrong would be greatly appreciated.

Cheers.

Answer 1

maybe the grammar translation must be completed, like in

xs(X0, X):- match(a, X0, X).
xs(X0, X):- match(a, X0, X1), xs(X1, X).
...

I would suggest to take a look at the translation that a DCG has to offer:

s --> x,y,z.
x --> [a], x | [a].
y --> [b], y | [b].
z --> [c], y | [c].

consulted and listed results in

z(A, C) :-
    (   A=[c|B],
        y(B, C)
    ;   A=[c|C]
    ).

y(A, C) :-
    (   A=[b|B],
        y(B, C)
    ;   A=[b|C]
    ).

x(A, C) :-
    (   A=[a|B],
        x(B, C)
    ;   A=[a|C]
    ).

s(A, D) :-
    x(A, B),
    y(B, C),
    z(C, D).

Answer 2

In each XS YS ZS method when calling recursively need to call match again.