Geek Answers Handbook

Find out the prologue now! DCG practice example

I am advancing through Learn Prolog Now! as self-education, and now I learn about literate marginal phrases. I am having difficulty with one of the tasks of the Practice Session. The task reads:

The formal language a n b 2m c 2m d n consists of all lines of the following form: a continuous block a s, followed by a continuous block b s, followed by a continuous block c s, followed by a continuous block d s, so that blocks a and d have the same length, and c and d also have the same length and, in addition, consist of an even number c s and d s respectively. For example, & epsilon; , abbccd andaaabbbbccccdddd all belong to a n b 2m with 2t d p . Write the DCG that generates this language.

I can write the rules that generate n d n b 2m c 2m and even a n b 2m and c 2m d n ... but I cannot join all these rules in n b 2m c 2m d n . Below are my rules that can generate a n d n and b 2m c 2m .

s1 --> [].
s1 --> a,s1,d.
a --> [a].
d --> [d].

s2 --> [].
s2 --> c,c,s2,d,d.
c --> [c].
d --> [d].

n b 2m c 2m d n CFG, DCG, , ( ..)? , - , , ?

+5
3

@Timothy, , :

?- length(S,_), s(S,[]).
S = [] ;
S = [a, d] ;
S = [a, d] ;            % XXX
S = [b, b, c, c] ;
S = [a, a, d, d] ;
S = [a, a, d, d] ;      % XXX

, , DCG:

s --> x.
s --> a,s,d.

x --> [].
x --> b,b,x,c,c.

% a, b, c, d the same

:

?- length(S,_), s(S,[]).
S = [] ;
S = [a, d] ;
S = [b, b, c, c] ;
S = [a, a, d, d] ;
S = [a, b, b, c, c, d] ;
S = [a, a, a, d, d, d] ;
S = [b, b, b, b, c, c, c, c] ;
S = [a, a, b, b, c, c, d, d] ;
S = [a, a, a, a, d, d, d, d] ;
+5

, ...

s --> x.
s --> a,d.
s --> a,s,d.

x --> [].
x --> b,b,x,c,c.

a --> [a].
b --> [b].
c --> [c].
d --> [d].

?- s([],[]).
Yes

?- s([a,b,c,c,d],[]).
No

?- s([a,a,a,b,b,c,c,d,d,d],[]).
Yes

: " , ?" , - , - , .

+3

How about something like:

n(L,N) --> n(L,N,0).

n(_,N,N) --> [], !.
n(L,N,K) --> L, {K1 is K + 1}, n(L, N, K1).

abbccd(N,M) -->
    {M1 is 2*M},
    n("a",N),
    n("b",M1),
    n("c",M1),
    n("d",N).

gen :-
    forall((
           between(1,4,N),
        between(1,4,M),
        phrase(abbccd(N,M),S),
        string_to_atom(S,A)
           ),
           writeln(A)).

performance:

 ?- gen.
abbccd
abbbbccccd
abbbbbbccccccd
abbbbbbbbccccccccd
aabbccdd
aabbbbccccdd
aabbbbbbccccccdd
aabbbbbbbbccccccccdd
aaabbccddd
aaabbbbccccddd
aaabbbbbbccccccddd
aaabbbbbbbbccccccccddd
aaaabbccdddd
aaaabbbbccccdddd
aaaabbbbbbccccccdddd
aaaabbbbbbbbccccccccdddd
true.
0
source

More articles:


All Articles