Пролог: объединение грамматик DCG с другими ограничениями - PullRequest
Новая
       44

Пролог: объединение грамматик DCG с другими ограничениями

10 голосов
/ 29 июня 2011

Я очень впечатлен DCG Пролога и тем, как быстро я могу создать все возможные структуры, которые соответствуют определенной грамматике.

Но я хотел бы объединить этот поиск с другими ограничениями.Например, определите сложную грамматику и попросите Пролога сгенерировать все предложения, содержащие не более 10 слов.Или все предложения, которые не повторяют одно и то же слово дважды.

Можно ли добавить подобные ограничения в грамматику DCG?Или мне нужно перевести DCG обратно в обычные предложения Prolog и начать их модифицировать?

Ответы [ 2 ]

9 голосов
/ 29 июня 2011

Если вы хотите видеть только все сгенерированные предложения, очень удобно использовать следующее: 

?- length(Xs, N), phrase(mynonterminal, Xs).

Конечно, это генерирует все предложения. Но это очень полезно, и это экономит ваше время, чтобы подумать о конкретном пределе. Если вы хотите ограничить это, добавьте цель between(0,10,N) впереди.

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

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

a --> {length(Es,10)}, seq(Es), {phrase(mynonterminal,Es)}.

Если вы все еще не счастливы, то вы хотите выразить пересечение двух нетерминалов. Это равносильно тому, чтобы просить пересечение двух контекстно-свободных языков, что в общем случае неразрешимо. Но гораздо раньше у вас будут проблемы с терминацией. Так что помните об этом в следующем: 

:- op( 950, xfx, &).

(NT1 & NT2) -->
     call(Xs0^Xs^(phrase(NT1,Xs0,Xs),phrase(NT2,Xs0,Xs))).

Следующее необходимо, только если вы не используете library (lambda) : 

^(V0, Goal, V0, V) :-
      call(Goal,V).

^(V, Goal, V) :-
     call(Goal).

Итак, теперь вы можете выразить пересечение двух нетерминалов. Но, пожалуйста, имейте в виду, что завершение здесь очень хрупкое. В частности, завершение первого нетерминала не обязательно ограничивает второе.

6 голосов
/ 29 июня 2011

хорошо, вы всегда можете использовать {} и написать любой предикат пролога между ними, например: 

foo(X)-->
    { valid(X) },
    [a].
foo(X)-->
    [b].

, чтобы вы могли добавить какой-то счетчик слов.Конечно, если каждый токен является словом, вы можете просто написать что-то вроде: длина (L, N), N <11, начало (L, []). </p>

с другой стороны, возможно, это будетЛучше, в зависимости от сложности ограничений, кодировать их в другой части.что-то вроде parser-> semantic checker в компиляторах.

...