Изучите пролог теперь! Пример практики DCG
Я прогрессировал через, Изучают Пролог Теперь! как самостоятельное обучение и теперь узнаю об Определенных Грамматиках Пункта. Я испытываю некоторые трудности с одной из задач Практической Сессии. Чтения задачи:
Формальный язык anb2mc2mdnсостоит из всех строк следующей формы: неповрежденный блок, как сопровождается неповрежденным блоком бакалавра наук, сопровождаемого неповрежденным блоком cs, сопровождаемого неповрежденным блоком ds, такого, что a и d блоки являются точно той же длиной, и c и d блоками, является также точно той же длиной и кроме того состоит из четного числа cs и ds соответственно. Например, ε, abbccd, и aaabbbbccccddd все принадлежат anb2mc2mdn. Запишите DCG, который генерирует этот язык.
Я могу записать правила, которые генерируют andn, b2mc2m, и даже anb2mи c2mdn..., но я, может казаться, не присоединяюсь ко всем этим правилам в anb2mc2mdn. Следующее является моими правилами, которые могут генерировать andnи b2mc2m.
s1 --> [].
s1 --> a,s1,d.
a --> [a].
d --> [d].
s2 --> [].
s2 --> c,c,s2,d,d.
c --> [c].
d --> [d].
anb2mc2mdn является действительно CFG, и действительно ли возможно записать использование DCG только, что преподавалось на уроке (никакие дополнительные аргументы или код, и т.д.)? Если так, кто-либо может предложить мне некоторое руководство, как я могу присоединиться к ним так, чтобы я мог решить данную задачу?
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] ;
Кажется, я понял это ...
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
Забавно смотреть на решение и думать: «Я ломал голову над этим ?» Но я думаю, что это половина удовольствия от изучения чего-то нового, особенно когда это что-то вроде логического программирования, исходящего из императивного программирования.
Как насчет чего-то вроде:
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.