Produrre una frase da una grammatica con un dato numero di terminali

Question

Di 'che hai una grammatica giocattolo, come: (aggiornato in modo l'output appare più naturale)

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

per es., "Il cane prende il mago rosso", "l'uccello incontra il pesce avvistato o la procedura guidata sposa il cane a righe"

Come si può produrre una frase da questa grammatica secondo il vincolo che deve contenere un totale di n Vs + Come + Ns. Dato un intero la frase deve contenere che molti terminali. (Nota naturalmente in questa grammatica minimo possibile n è 3).

Answer 1

Il seguente codice Python genererà una frase casuale con il dato numero di terminali. Funziona contando il numero di modi per produrre una frase di una data lunghezza, generando un gran numero casuale, e calcolando la frase indicata. Il conteggio viene effettuato in modo ricorsivo, con Memoizzazione. Un lato destro vuoto produce 1 frase se n è 0 e 0 altrimenti frasi. Per contare il numero di frasi prodotte da un lato non vuoto mano destra, sommare i, il numero di terminali utilizzati dal primo simbolo destra. Per ogni i, moltiplicare il numero di possibilità per il resto del lato destro per il numero di possibilità per il primo simbolo. Se il primo simbolo è un terminale, non v'è possibilità 1 se i è 1 e 0 altrimenti. Se il primo simbolo è un non terminale, sommare le possibilità oltre ogni alternativa. Per evitare loop infiniti, dobbiamo stare attenti a potare le chiamate ricorsive quando una quantità è 0. Questo ciclo può ancora infinitamente se la grammatica ha infiniti derivazioni di una frase. Per esempio, nella grammatica

S -> S S
S ->

ci sono infiniti derivazioni della frase vuota: S =>, S => S S =>, S => S S => S S S =>, etc. Il codice per trovare una frase particolare è una modifica diretta del codice di contarli. Questo codice è ragionevolmente efficiente, generando 100 frasi con 100 terminali ciascuno in meno di un secondo.

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

Forse non è la soluzione migliore, ma mi piacerebbe lavorare in modo ricorsivo la mia strada attraverso ogni regola della grammatica fino a quando ho superato il vincolo, quindi pop indietro ed esplorare un altro percorso lungo la grammatica. Mantenere tutte le frasi che soddisfano il vincolo e buttare via tutte le frasi che non lo fanno.

Ad esempio, con n = 3:

S -> ($ {NP} $ {} VP) -> ((il $ {N}) $ {} VP) -> ((la (cane) $ {} VP) -> ... - > ((la (cane) ((calci) (il $ {} NP)))) -> ((la (cane) ((calci) (la (cane)))))

E poi pop torna

((la (cane) ((calci) (il $ {N})))) -> ((la (cane) ((calci) (la (pesce)))))

e un po 'più tardi ...

((la (cane) ($ {V} $ {N}))) -> ((la (cane) ((MEETS) $ {N}))) -> ((la (cane) (( incontra) il (cane))))

ecc.

Essenzialmente una profondità-prima ricerca grafico, solo si sta costruendo il grafico, come si sta cercando (e si smette di costruire parti che superano i vincoli).

Answer 3

Questa domanda contiene un errore di categoria. La grammatica è stata specificata ha l'aspetto di una grammatica libera dal contesto, ma il requisito che ci sia un numero specifico di nodi terminali richiede una grammatica ricorsivamente enumerabile.