Обработка пролога контекстной свободной грамматики - PullRequest
Новая
       16

Обработка пролога контекстной свободной грамматики

3 голосов
/ 30 ноября 2011

С учетом CFG 

S --> a S b | c | d

Я хочу написать предикат вроде грамматика ('S', предложение) , которая генерирует все возможные 

sentences like
sentence=acb,
sentence=acd,
sentence=c,
sentence=ab......................

Используя крайний левый вывод , если встреченный символ терминал , он должен распечатать этот терминал, а если встреченный символ не терминал 'S' , следует откатить и заменить одну из грамматик a S b или c или d и повторить процесс.

Я не хочу никакого кода ... просто помогите мне с некоторыми советами, как начать с

1 Ответ

8 голосов
/ 01 декабря 2011

Давайте использовать DCG для буквального кодирования вашей грамматики! 

s --> [a], s, [b] | [c] | [d].

?- phrase(s,Xs).
ERROR: Out of local stack

Похоже, этот запрос не заканчивается.Т.е. очень простая стратегия исполнения Пролога не нашла решения.С другой стороны, подумайте об этом: ваша грамматика описывает бесконечный набор предложений.Если вы перечисляете бесконечный набор, легко начать «с неправильного конца».Вот что на самом деле делает Пролог.

Но все не так уж и плохо.Как насчет перечисления всех предложений фиксированной длины.Я попробую 5: 

?- length(Xs,5), phrase(s,Xs).
Xs = "aacbb" ;
Xs = "aadbb" ;
false.

В этом случае все предложения найдены, и Пролог даже уверяет нас, что больше нет предложений. 

?- length(Xs,4), phrase(s,Xs).
false.

Нет предложений длины 4.

Теперь мы можем перечислить все предложения, по длине . 

?- length(Xs,N), phrase(s,Xs).
Xs = "c",
N = 1 ;
Xs = "d",
N = 1 ;
Xs = "acb",
N = 3 ;
Xs = "adb",
N = 3 ;
Xs = "aacbb",
N = 5 ;
Xs = "aadbb",
N = 5 ;
Xs = "aaacbbb",
N = 7

Какой вид деривации мы здесь использовали?Честно говоря, я не знаю, и мне все равно.Что важно знать, это когда Пролог прекратит работу.В этом случае оно прекратится, если длина известна.И это все, что нам нужно знать, чтобы гарантировать, что у нас есть честное перечисление бесконечного множества.Все даже немного лучше: s//0 также прекратит работу в случаях, когда длина неизвестна, например, 

?- Xs = [a,a,b|_], phrase(s,Xs).
false.

?- Xs = [a,a,c|_], phrase(s,Xs).
Xs = "aacbb" ;
false.

?- dif(X,Y), Xs = [X,Y|_], phrase(s,Xs).
X = a,
Y = c,
Xs = "acb" ;
X = a,
Y = d,
Xs = "adb" ;
false.

Редактировать: я получил несколько вопросов об ответах верхнего уровня, используя "acb" для списка [a,c,b]: Пожалуйста, обратитесь к этот ответ для объяснения и library(double_quotes).

...