Последовательный генератор для бесконтекстной грамматики (CFG) в Prolog, возможно, с использованием DCG

Question

Я хочу написать gen (G, S) в Prolog, чтобы сгенерировать действительную последовательность S для данной грамматики G, где G имеет грамматику формата ([список нетерминалов], [список терминалов], [список правил], [начальная последовательность]). Правила находятся в правиле формата (nt, [x]), где x может быть любым списком нетерминалов и/или терминалов.

например. gen (грамматика ([a, b], [t, q, y, z], [правило (a, [t]), правило (a, [z]), правило (b, [y]), правило (b, [a, q])], [a, b]), X).

Возврат: X = [t, y]. X = [t, t, q]. X = [t, z, q]. X = [z, y]. X = [z, t, q]. X = [z, z, q].

Со всей информацией на CFG для Prolog (пробовал в течение 2 дней), я с/б умею выяснить хотя бы один способ сделать это, используя встроенные -> и фразы/2 или с нуля, но не повезло. (Никогда не размещался на SO b4 & Я новичок, поэтому извиняюсь, если этот Q неуместен.)

Answer 1

Нет необходимости прибегать к специальным нелогичным предикатам. Это делает трюк:

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

Answer 2

Вот решение, которое должно по крайней мере указывать на правильное направление. Она отличается тем, что я непосредственно определил терминалы, нетерминалы и правила, как факты Пролога:

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

Отсюда, вам нужен предикат, который принимает последовательность запуска и применяет правила:

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

Если символ является терминалом, он относится к концевой последовательности. Если это не терминал, вы применяете к нему правило, а затем применяете gen/2 к результату. Предполагаю, вы знаете, как работает рекурсия в Prolog, if-else и что делает append/3.

?- [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]. 

Чтобы превратить это в предикат, которого вы ищете, рассмотреть следующие вопросы:

список можно перечислить с помощью member/2:

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

Вы можете добавить факты и правила в базу данных с использованием assertz/1:

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

Y НУ может использовать forall/2, чтобы избежать написания явного цикла:

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

Вы можете использовать member/2 непосредственно в списках, если вы хотите.

Уверен, что есть и другой способ.