Prolog, Grammar, Beginner

Question

To implement s -> a ,with such a function rule(s,[a]) I came up with below code , but it doesn't work because of lower case s. if we had a grammar based on this format, how can I write the rule?

format: grammar(Nonterminals, Terminals, Rules, Start)

    grammar([s], [a], [rule(s, [a]), rule(s, [s, s])], [s]).          
    rule(A,B):- B is A.  

Answer 1

There are a lot of confused ideas in this (B is A is almost never what you want), and you would surely benefit from reviewing the fundamentals of Prolog some. DCGs are how grammars are implemented in Prolog, but they have nothing to do with the formalism you're trying to work with. Your example grammar would look something like this:

s --> [a].
s --> s, s.

Note that the terminal/nonterminal distinction is implicit. "Terminals" in a DCG context are whatever shows up in the list notation on the right hand side (in this example, the atom a). The rules are implicit because we're reusing Prolog's global predicate namespace. And the start rule is whatever you pass to phrase/2. You would invoke this grammar by calling phrase/2 like this:

phrase(s, X).

where perhaps X is some list you came up with elsewhere. And you could see that this works:

?- phrase(s, X).
X = [a] ;
X = [a, a] ;
X = [a, a, a] ;
X = [a, a, a, a] ;
X = [a, a, a, a, a] .

However, you'll find that if you need to backtrack, this current formalism won't be sufficient:

?- phrase(s, [a,a]).
true ;
ERROR: Out of local stack

This is because the second rule expands s to s, s, which is too much recursion. There are several practical fixes to this problem; the simplest would probably be to change your second rule to this:

s --> [a], s.

If you are dead-set on using your formalism, you're probably going to have to write a meta-interpreter. This task isn't as hard as it sounds, but you're going to want a firmer grounding in the essentials before you aim for it. I myself have never written a DCG meta-interpreter so I can't comment on how much work that is going to entail. I'd want it to look and work more like phrase/2 with DCG-style input than your example; I'd imagine something more like this:

% accept(Grammar, Sentence) is true if Sentence is in Grammar,
%   where Grammar is a structure "grammar(Start, Rules)"
%   and Rules is a list of rules in the DCG notation
accept(grammar(s, [(s --> [a]), (s --> [a], s)]), X).

but I don't know precisely how I'd go about coding accept/2. Hope this helps!