I have a simple grammar such as
S::=a S b
S::=[] (empty string)
Now i want to write a parser for the above grammar like
cfg('S', [a,'S',b])
which generates a sentence aaabbb by left most derivation.
I'm not good enough to handle dcg/cfg in prolog. So pls help me with this example so that i can go ahead and try something bigger.
Consider this DCG code:
s-->[].
s-->[a],s,[b].
to run a predicate you defined by DCG you should add two more arguments at the end: the "input" and what it's left. If you want to recognize the whole list you simply put []. So, when you run it you get:
38 ?- s(C,[]).
C = [] ;
C = [a, b] ;
C = [a, a, b, b] ;
C = [a, a, a, b, b, b] ;
C = [a, a, a, a, b, b, b, b] ;
...
If you wanted some sort of "return" string you could add it as an extra arg. To write prolog code in a dcg clause you use {}:
s('')-->[].
s(S)-->
[a],s(SI),[b],
{ atomic_list_concat([a,SI,b],S)}.
and you get:
40 ?- s(R,X,[]).
R = '',
X = [] ;
R = ab,
X = [a, b] ;
R = aabb,
X = [a, a, b, b] ;
R = aaabbb,
X = [a, a, a, b, b, b] ;
R = aaaabbbb,
X = [a, a, a, a, b, b, b, b] ;
R = aaaaabbbbb,
...
we generated all the strings that are recognized by this grammar; usually you just want to check if a string is recognized by the grammar. to do that you simply put it as input:
41 ?- s([a,b],[]).
true
42 ?- s([a,b,b],[]).
false.
note that we put the S::=[] rule first otherwise prolog would fall in a infinite loop if you asked to generate all the solutions. This problem might not be trivial to solve in more complex grammars. To get the solutions you can use length/2:
?- length(X,_),s(X,[]).
X = [] ;
X = [a, b] ;
X = [a, a, b, b] ;
X = [a, a, a, b, b, b] ;
X = [a, a, a, a, b, b, b, b]
even if your code is:
s-->[].
s-->[a],s,[b].