Produzir uma frase de uma gramática com um determinado número de terminais

Question

Say você tem uma gramática brinquedo, como: (atualizado para os olhares de saída mais naturais)

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

por exemplo., "Os cães chutes a Red Wizard", "o pássaro encontra o peixe manchado ou as casar assistente o cão listrado"

Como você pode produzir uma sentença deste gramática de acordo com a restrição de que ele deve conter um total de n VS + As + Ns. Dado um número inteiro a sentença deve conter que muitos terminais. (Nota do curso nesta gramática o mínimo possível n é 3).

Answer 1

O seguinte código Python irá gerar uma frase aleatória com um dado número de terminais. Ele funciona através da contagem do número de maneiras de produzir uma sentença de um determinado comprimento, gerando um grande número aleatório, e calcular a frase indicada. A contagem é feita de forma recursiva, com memoization. Um lado da mão direita vazio produz uma frase, se n for 0 e 0 frases de outra forma. Para contar o número de sentenças produzidas por um lado nonempty direita, soma sobre i, o número de terminais utilizados pelo primeiro símbolo no lado direito. Para cada i, multiplique o número de possibilidades para o resto do lado direito pelo número de possibilidades para o primeiro símbolo. Se o primeiro símbolo é um terminal, existe uma possibilidade, se i é 1 e 0 caso contrário. Se o primeiro símbolo é um não-terminal, resumir as possibilidades mais de cada alternativa. Para evitar loops infinitos, temos que ter cuidado para podar as chamadas recursivas quando uma quantidade é 0. Este ciclo pode ainda infinitamente se a gramática tem infinitas derivações de uma frase. Por exemplo, na gramática

S -> S S
S ->

existem infinitamente muitas derivações da frase vazia: S =>, S => S S =>, S => S S => S S S =>, etc. O código para encontrar uma frase em particular é uma modificação simples do código de contá-las. Este código é razoavelmente eficiente, gerando 100 frases com 100 terminais de cada um em menos de um segundo.

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

Talvez não seja a melhor solução, mas eu recursivamente trabalhar o meu caminho através de cada regra da gramática até que eu tenha excedido a restrição, em seguida, pop para trás e explorar um outro caminho ao longo da gramática. Mantenha todas as frases que atendam a restrição e jogar fora todas as frases que não.

Por exemplo, com n = 3:

S -> ($ {NP} $ {VP}) -> ((o $ {N}) $ {VP}) -> ((o (cão) $ {VP}) -> ... - > ((o (cão) ((chutes) (o $ {NP})))) -> ((o (cão) ((chutes) (a (cão)))))

E, em seguida, pop volta

((o (cão) ((chutes) (o $ {N})))) -> ((o (cão) ((chutes) (o (peixe)))))

e um pouco mais tarde ...

((o (cão) ($ {V} $ {N}))) -> ((o (cão) ((atende) $ {N}))) -> ((o (cão) (( atende) o (cão))))

etc.

Essencialmente uma pesquisa gráfico em profundidade, só você está construindo o gráfico que você está procurando (e você parar de construir peças que excedam as restrições).

Answer 3

Esta questão contém um erro de categoria. A gramática que você especificou tem a aparência de uma gramática livre de contexto, mas a exigência de que haja um número específico de nós terminais requer uma gramática recursiva enumeráveis.