Создайте предложение из грамматики с заданным количеством терминалов.

Question

Допустим, у вас есть игрушечная грамматика, например: (обновлено, чтобы результат выглядел более естественным)

S -> ${NP} ${VP} | ${S} and ${S} | ${S}, after which ${S}

NP -> the ${N} | the ${A} ${N} | the ${A} ${A} ${N}

VP -> ${V} ${NP}

N -> dog | fish | bird | wizard

V -> kicks | meets | marries

A -> red | striped | spotted

например, «собака пинает красного волшебника», «птица встречает пятнистую рыбу или волшебник женится на полосатой собаке»

Как вы можете составить предложение из этой грамматики в соответствии с условием, что оно должно содержать в общей сложности н Вс + Ас + Нс.Учитывая целое число, предложение должно содержать такое количество терминалов.(обратите внимание, конечно, что в этой грамматике минимально возможный н это 3).

Answer 1

Следующий код Python сгенерирует случайное предложение с заданным количеством терминалов.Он работает путем подсчета количества способов создания предложения заданной длины, генерации большого случайного числа и вычисления указанного предложения.Подсчет ведется рекурсивно, с мемоизацией.Пустая правая часть дает 1 предложение, если n равно 0, и 0 предложений в противном случае.Чтобы подсчитать количество предложений, созданных непустой правой частью, просуммируйте по i — количеству терминалов, используемых первым символом в правой части.Для каждого i умножьте количество возможностей оставшейся части правой части на количество возможностей первого символа.Если первый символ является терминалом, существует 1 возможность, если i равен 1, и 0 в противном случае.Если первый символ нетерминал, просуммируйте возможности по каждой альтернативе.Чтобы избежать бесконечных циклов, мы должны быть осторожны и сокращать рекурсивные вызовы, когда количество равно 0.Этот цикл может продолжаться бесконечно, если грамматика имеет бесконечно много производных от одного предложения.Например, в грамматике

S -> S S
S ->

существует бесконечно много производных от пустого предложения:S => , S => S S => , S => S S => S S S => и т. д.Код для поиска конкретного предложения — это простая модификация кода для его подсчета.Этот код достаточно эффективен: он генерирует 100 предложений со 100 терминалами менее чем за секунду.

import collections
import random

class Grammar:
    def __init__(self):
        self.prods = collections.defaultdict(list)
        self.numsent = {}
        self.weight = {}

    def prod(self, lhs, *rhs):
        self.prods[lhs].append(rhs)
        self.numsent.clear()

    def countsent(self, rhs, n):
        if n < 0:
            return 0
        elif not rhs:
            return 1 if n == 0 else 0
        args = (rhs, n)
        if args not in self.numsent:
            sym = rhs[0]
            rest = rhs[1:]
            total = 0
            if sym in self.prods:
                for i in xrange(1, n + 1):
                    numrest = self.countsent(rest, n - i)
                    if numrest > 0:
                        for rhs1 in self.prods[sym]:
                            total += self.countsent(rhs1, i) * numrest
            else:
                total += self.countsent(rest, n - self.weight.get(sym, 1))
            self.numsent[args] = total
        return self.numsent[args]

    def getsent(self, rhs, n, j):
        assert 0 <= j < self.countsent(rhs, n)
        if not rhs:
            return ()
        sym = rhs[0]
        rest = rhs[1:]
        if sym in self.prods:
            for i in xrange(1, n + 1):
                numrest = self.countsent(rest, n - i)
                if numrest > 0:
                    for rhs1 in self.prods[sym]:
                        dj = self.countsent(rhs1, i) * numrest
                        if dj > j:
                            j1, j2 = divmod(j, numrest)
                            return self.getsent(rhs1, i, j1) + self.getsent(rest, n - i, j2)
                        j -= dj
            assert False
        else:
            return (sym,) + self.getsent(rest, n - self.weight.get(sym, 1), j)

    def randsent(self, sym, n):
        return self.getsent((sym,), n, random.randrange(self.countsent((sym,), n)))

if __name__ == '__main__':
    g = Grammar()
    g.prod('S', 'NP', 'VP')
    g.prod('S', 'S', 'and', 'S')
    g.prod('S', 'S', 'after', 'which', 'S')
    g.prod('NP', 'the', 'N')
    g.prod('NP', 'the', 'A', 'N')
    g.prod('NP', 'the', 'A', 'A', 'N')
    g.prod('VP', 'V', 'NP')
    g.prod('N', 'dog')
    g.prod('N', 'fish')
    g.prod('N', 'bird')
    g.prod('N', 'wizard')
    g.prod('V', 'kicks')
    g.prod('V', 'meets')
    g.prod('V', 'marries')
    g.prod('A', 'red')
    g.prod('A', 'striped')
    g.prod('A', 'spotted')
    g.weight.update({'and': 0, 'after': 0, 'which': 0, 'the': 0})
    for i in xrange(100):
        print ' '.join(g.randsent('S', 3))

Answer 2

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

Например, при n = 3:

S -> (${NP} ${VP}) -> ( (${N}) ${VP}) -> ( (собака) ${VP}) -> ...-> ( ((собака) ( (пинает) (${NP} ) ) ) ) -> ( ((собака) ( (пинает) ((собака)) ) ) )

А затем вернуться обратно

( ((собака) ( (пинает) (${N} ) ) ) ) -> ( ((собака) ( (пинает) ((рыба)) ) ) )

и немного позже...

( ((собака) ( ${V} ${N} ) ) ) -> ( ((собака) ( (встречает) ${N} ) ) ) -> ( ((собака) ( (встречает) (собака) ) ) )

и т. д.

По сути, это поиск по графу в глубину, только вы строите график по мере его поиска (и вы прекращаете создавать части, которые выходят за рамки ограничений).

Answer 3

Этот вопрос содержит ошибку категории.Указанная вами грамматика выглядит как контекстно-свободная грамматика, но требование наличия определенного количества конечных узлов требует рекурсивно перечисляемой грамматики.