CODEWITHSUNDEEP
prologcontext-free-grammardcg
Anil
Anil

Reputation: 2455

Generating string of symbols(sentence) for a given context free grammar

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.

Upvotes: 2

Views: 1384

Answers (1)

thanos
thanos

Reputation: 5858

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

Upvotes: 5

Related Questions