Изучай пролог сейчас!Пример практики DCG - PullRequest
Новая
       9

Изучай пролог сейчас!Пример практики DCG

5 голосов
/ 08 июня 2010

Я прошел через Изучай Пролог сейчас! в качестве самостоятельной работы и теперь изучаю грамматики Определенного предложения. У меня возникли некоторые трудности с одной из задач практической сессии. Задание гласит:

Формальный язык a n b 2m c 2m d n состоит из всех строк следующего вида: непрерывный блок a с, за которым следует непрерывный блок b с, за которым следует непрерывный блок c с, за которым следует непрерывный блок d s, так что блоки a и d имеют одинаковую длину, а блоки c и d также точно такие же длина и, кроме того, состоят из четного числа с с и д с соответственно. Например, & epsilon; , abbccd и aaabbbbccccddd все принадлежат n b 2m c 2m * * д тысяче сорок-семь п * 1 049 *. Напишите DCG, который генерирует этот язык.

Я могу написать правила, которые генерируют n d n , b 2m c 2m и даже n b 2m и c 2m d n ... но я не могу объединить все эти правила в n б * 1 071 * 2m C * +1073 * 2m * * d тысяча семьдесят четыре N . Ниже приведены мои правила, которые могут генерировать n d n и b 2 м с 2 м . 

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, используя только чему учили на уроке (без дополнительных аргументов, кода и т. д.)? Если да, может ли кто-нибудь предложить мне какое-нибудь руководство, как я могу присоединиться к ним, чтобы я мог решить данную задачу?

Ответы [ 3 ]

5 голосов
/ 12 июня 2010

@ Тимоти, ваш ответ работает, но он генерирует дубликаты: 

?- 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] ;
3 голосов
/ 10 июня 2010

Мне кажется, я понял это ... 

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

Забавно посмотреть на решение и подумать: "Я ломал голову над этим ?"Но я думаю, что это половина удовольствия от изучения чего-то нового, особенно когда это что-то вроде логического программирования, основанного на императивном опыте программирования.

0 голосов
/ 08 июня 2010

Как насчет чего-то вроде: 

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

выполнение: 

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