У меня есть простая грамматика, такая как
S::=a S b
S::=[] (empty string)
Теперь я хочу написать парсер для приведенной выше грамматики, например
cfg('S', [a,'S',b])
который генерирует предложение aaabbb по самому левому производному.
Я недостаточно хорош для обработки dcg/cfg в прологе. Пожалуйста, помогите мне с этим примером, чтобы я мог пойти дальше и попробовать что-то большее.
Рассмотрим этот код DCG:
s-->[].
s-->[a],s,[b].
чтобы запустить предикат, определенный вами DCG, вы должны добавить еще два аргумента в конце: «вход» и то, что осталось. Если вы хотите узнать весь список, просто поставьте []. Итак, при запуске вы получаете:
38 ?- s(C,[]).
C = [] ;
C = [a, b] ;
C = [a, a, b, b] ;
C = [a, a, a, b, b, b] ;
C = [a, a, a, a, b, b, b, b] ;
...
Если вам нужна какая-то строка «возврата», вы можете добавить ее в качестве дополнительного аргумента. Чтобы написать код пролога в предложении dcg, вы используете {}:
s('')-->[].
s(S)-->
[a],s(SI),[b],
{ atomic_list_concat([a,SI,b],S)}.
и вы получаете:
40 ?- s(R,X,[]).
R = '',
X = [] ;
R = ab,
X = [a, b] ;
R = aabb,
X = [a, a, b, b] ;
R = aaabbb,
X = [a, a, a, b, b, b] ;
R = aaaabbbb,
X = [a, a, a, a, b, b, b, b] ;
R = aaaaabbbbb,
...
мы сгенерировали все строки, распознаваемые этой грамматикой; обычно вы просто хотите проверить, распознается ли строка грамматикой. для этого вы просто помещаете его в качестве ввода:
41 ?- s([a,b],[]).
true
42 ?- s([a,b,b],[]).
false.
обратите внимание, что мы поставили правило S::=[] первым, иначе пролог попадет в бесконечный цикл, если вы попросите сгенерировать все решения. Эта проблема может быть нетривиальной для решения в более сложных грамматиках. Чтобы получить решения, вы можете использовать length/2:
?- length(X,_),s(X,[]).
X = [] ;
X = [a, b] ;
X = [a, a, b, b] ;
X = [a, a, a, b, b, b] ;
X = [a, a, a, a, b, b, b, b]
даже если ваш код:
s-->[].
s-->[a],s,[b].
