Re: DCGs

[Daniel Diaz]

H,

Le 17 nov. 2012 à 08:05, Christopher Howard a écrit :

> The formal language a^n b^2m c^2m d^n consists of all strings of the
> following form: an unbroken block of a s followed by an unbroken block
> of b s followed by an unbroken block of c s followed by an unbroken
> block of d s, such that the a and d blocks are exactly the same length,
> and the b and c blocks are also exactly the same length and furthermore
> consist of an even number of b s and c s respectively. For example, ϵ ,
> abbccd , and aabbbbccccdd all belong to a^n b^2m c^2m d^n. Write a DCG
> that generates this language.

"generates" does not seem to me the correct verb here. It would be "recognizes" 
(DCG are mainly done for parsing, even if they can be used to generate strings 
according to the grammar this is often very limited - as for any Prolog 
predicate).

> One approach that almost works is this:
> 
> s --> as,m,ds.
> 
> r --> cs,ds.
> r --> cs,r,ds.
> 
> as --> [a].
> as --> [a],as.
> m --> [b,b,c,c].
> m --> [b,b],m,[c,c].
> ds --> [d].
> ds --> ds,[d].

The problem with this grammar is that the number of 'a' and the number of 'd' 
are not related. Recall context-free grammars are grammars which works "by 
nesting" (using a stack) (see a more general course on context-free grammars 
for more information). 

Here is a grammar that works for your language:

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

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

you can check it with:

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

true

NB: this grammar will not work well in generation since it will only generates 
word of the form b^2m c^2m (which are corrects, but no words of other forms can 
be generated).

> s --> as,m,ds,length(as,X),length(ds,Y),X =:= Y.
> 
> However, this dies with: "error(existence_error(procedure,length/4),s/2)". 
> Presumably, this is
> happening because the interpreter is translating the new statements like
> it does the rest of the terms in the DCG statement. 

You are right. To include classical Prolog predicate call inside a DCG you have 
to put it inside curly brackets in the body of the DCG.
E.g., you could write  s --> as,m,ds,{length(as,X),length(ds,Y),X =:= Y}.
However, the arguments of length are wrong here (as and ds are Prolog atoms, 
not lists). You can then extend your DCG non-terminals (e.g., as, ds) with 
arguments (as(La), ds(Ls)) which can be any Prolog term. You will find online a 
lot of information on DCG interacting with Prolog code. But this is not needed 
in this case.

Daniel



-- 
Ce message a ete verifie par MailScanner
pour des virus ou des polluriels et rien de
suspect n'a ete trouve.