Producir una frase de una gramática con un número determinado de terminales

Question

Digamos que tienes una gramática juguete, como: (actualizado por lo que la salida se parece más natural)

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 ejemplo., "El perro se inicia el asistente de rojo", "el ave se encuentra con el pescado manchado o el asistente se casa con el perro de rayas"

¿Cómo se puede producir una frase de esta gramática de acuerdo con la restricción de que debe contener un total de n Vs + As + Ns. Dado un número entero la frase que debe contener muchos terminales. (Nota por supuesto, en esta gramática el mínimo posible n es 3).

Answer 1

El siguiente código Python generará una frase al azar con el número dado de terminales. Funciona mediante el recuento del número de maneras de producir una sentencia de una longitud dada, generar un número aleatorio grande, y el cálculo de la frase indicada. El recuento se realiza de forma recursiva, con memoization. Un lado vacío de la derecha produce 1 frase si n es 0 y 0 frases de otro modo. Para contar el número de sentencias producidas por un lado no vacío de la derecha, suma sobre i, el número de terminales utilizados por el primer símbolo en el lado derecho. Para cada i, multiplicar el número de posibilidades para el resto de la derecha por el número de posibilidades para el primer símbolo. Si el primer símbolo es un terminal, hay 1 posibilidad si i es 1 y 0 en caso contrario. Si el primer símbolo es un no terminal, resumir las posibilidades más de cada alternativa. Para evitar bucles infinitos, tenemos que tener cuidado para podar las llamadas recursivas cuando una cantidad es 0. Este bucle puede todavía infinitamente si la gramática tiene infinitas derivaciones de una frase. Por ejemplo, en la gramática

S -> S S
S ->

hay infinitamente muchos derivaciones de la frase vacío: S =>, S => S S =>, S => S S => S S S =>, etc. El código para encontrar una frase en particular es una modificación directa del código de contarlos. Este código es razonablemente eficiente, generando 100 frases con 100 terminales cada uno en menos de un 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

Tal vez no sea la mejor solución, pero me gustaría trabajar de forma recursiva mi camino a través de cada regla de la gramática hasta que haya superado el obstáculo, entonces pop volver y explorar otro camino a lo largo de la gramática. Mantenga todas las oraciones que cumplen la restricción y tirar todas las oraciones que no lo hacen.

Por ejemplo, con n = 3:

S -> ($ {NP} $ {VP}) -> ((el $ {N}) $ {VP}) -> (((pan) $ {VP}) -> ... - > (((pan) ((patadas) (el $ {NP})))) -> (((pan) ((patadas) (el (perro)))))

Y entonces pop volver

(((pan) ((patadas) (el $ {N})))) -> (((pan) ((patadas) (la (pescado)))))

y un poco más tarde ...

((el (perro) ($ {V} $ {N}))) -> ((el (perro) ((cumple) $ {N}))) -> ((el (perro) (( se reúne) el (perro))))

etc.

En esencia una búsqueda gráfica primero en profundidad, sólo se va a crear el gráfico como que está buscando (y que deje de construir piezas que superan las limitaciones).

Answer 3

Esta pregunta contiene un error de categoría. La gramática que ha especificado tiene la apariencia de una gramática libre de contexto, pero el requisito de que haya un número determinado de nodos terminales requiere una gramática recursivamente numerable.