Генерация строки символов (предложения) для заданной контекстно-свободной грамматики - PullRequest
Новая
       13

Генерация строки символов (предложения) для заданной контекстно-свободной грамматики

2 голосов
/ 18 ноября 2011

У меня есть простая грамматика, такая как 

S::=a S b
S::=[] (empty string)

Теперь я хочу написать синтаксический анализатор для вышеуказанной грамматики, такой как 

cfg('S', [a,'S',b])

, который генерирует предложение aaabbb по левому краю деривации.

Я недостаточно хорош для обработки dcg / cfg в прологе.Поэтому, пожалуйста, помогите мне с этим примером, чтобы я мог пойти дальше и попробовать что-то большее.

1 Ответ

5 голосов
/ 18 ноября 2011

Рассмотрим код 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].
...