Search code examples
parsingprologcontext-free-grammardcg

writing a parser in prolog

Here is the grammar:

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

I need to write a parser in this grammar.

and when test S([a,a,b,c,c,c],[]). it should return true. in my code I defined match rule to check list elements.


match(H,[H|T],T).
na(X0,X1):-match(a,X0,X2). 
nb(X0,X1):-match(b,X0,X2). 
nc(X0,X1):-match(c,X0,X2).
ns(X0,X1):-na(X0,X2),nb(X2,X3),nc(X3,X1).

what is wrong in this code? it give true but when you trace. it does not working.

Solution 
  • :- set_prolog_flag(double_quotes, chars).

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

    Here they are, sorted by length:

    ?- length(Xs,N),phrase(s, Xs).
   Xs = [a,b,c], N = 3
;  Xs = [a,a,b,c], N = 4
;  Xs = [a,b,b,c], N = 4
;  Xs = [a,b,c,c], N = 4
;  Xs = [a,a,a,b,c], N = 5
;  Xs = [a,a,b,b,c], N = 5
;  ... .