CODEWITHSUNDEEP
parsingprologsequencegrammardcg
hkm
hkm

Reputation: 23

Sequence Generator for Context-free Grammar (CFG) in Prolog possibly using DCG

I want to write gen(G,S) in Prolog to generate a valid sequence S for a given grammar G, where G is of the format grammar([list of nonterminals], [list of terminals], [list of rules], [starting sequence]). The rules are in the format rule(nt,[x]) where x can be any list of nonterminals and/or terminals.

e.g. gen(grammar([a,b], [t,q,y,z], [rule(a,[t]), rule(a,[z]), rule(b,[y]), rule(b,[a,q])], [a,b]), X).

Returns: X = [t,y]. X = [t,t,q]. X = [t,z,q]. X = [z,y]. X = [z,t,q]. X = [z,z,q].

With all the info out there on CFG for Prolog (been trying for 2 days), I s/b able to figure out at least 1 way to do this, either using the built-in --> and phrase/2 or from scratch, but no luck. (Never posted on SO b4 & I'm a beginner, so my apologies if this Q is inappropriate.)

Upvotes: 2

Views: 779

Answers (2)

user1812457
user1812457

Reputation:

Here is a solution that should at least point you to the right direction. It is different, because I have directly defined the terminals, non-terminals and rules as Prolog facts:

nt(a). nt(b).

t(t). t(q). t(y). t(z).

rule(a, [t]).
rule(a, [z]).
rule(b, [y]).
rule(b, [a,q]).

From here, you need a predicate that takes a starting sequence and applies the rules:

gen([], []).
gen([A|As], S) :-
    (   t(A)
    ->  S = [A|Ts]
    ;   nt(A)
    ->  rule(A, Bs),
        gen(Bs, Cs),
        append(Cs, Ts, S)
    ),
    gen(As, Ts).

If the symbol is a terminal, it belongs to the end sequence. If it is a non-terminal, you apply a rule to it, then apply gen/2 to the result. I assume you know how recursion in Prolog works, the if-else, and what append/3 does.

?- [gen].
% gen compiled 0.00 sec, 13 clauses
true.

?- gen([a,b], S).
S = [t, y] ;
S = [t, t, q] ;
S = [t, z, q] ;
S = [z, y] ;
S = [z, t, q] ;
S = [z, z, q].

To transform this into the predicate you are looking for, consider the following:

A list can be enumerated using member/2:

?- member(NT, [a,b]).
NT = a ;
NT = b.

You can add facts and rules to the database using assertz/1:

?- assertz(t(t)), assertz(t(q)). % etc

You could use forall/2 to avoid writing an explicit loop:

?- forall(member(R, Rules), assertz(R)).

You could use member/2 directly on the lists if you want.

I am sure there is another way too.

Upvotes: 0

Christian Fritz
Christian Fritz

Reputation: 21384

There is no need to resort to special, non-logical predicates. This does the trick:

gen(grammar(_NTE, _TE, _Rules, []), []).

gen(grammar(NTE, TE, Rules, [H|T]), X) :-
    member(H, NTE),
    member(rule(H, Res), Rules),
    append(Res, T, NewT),
    gen(grammar(NTE, TE, Rules, NewT), X).

gen(grammar(NTE, TE, Rules, [H|T]), [H|X2]) :-
    member(H, TE),
    gen(grammar(NTE, TE, Rules, T), X2).

Upvotes: 1

Related Questions