Produire une phrase d'une grammaire avec un certain nombre de terminaux

Question

Dites que vous avez une grammaire de jouets, comme: (mis à jour de sorte que la sortie semble plus naturel)

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

par exemple., « Le chien lance l'assistant rouge », « l'oiseau rencontre le poisson repéré ou l'assistant se marie avec le chien rayé »

Comment peut-on produire une phrase de cette grammaire selon la contrainte qu'il doit contenir un total de n Vs + As + Ns. Étant donné un entier la phrase doit contenir que de nombreux terminaux. (Note bien sûr dans cette grammaire minimum possible n est 3).

Answer 1

Le code Python suivant va générer une phrase au hasard avec le nombre donné de terminaux. Il fonctionne en comptant le nombre de façons de produire une phrase d'une longueur donnée, la génération d'un grand nombre aléatoire, et calculer la phrase indiquée. Le compte est fait récursive, avec memoization. Un côté droit vide produit 1 phrase si n est 0 et 0 phrases autrement. Pour compter le nombre de phrases produites par un côté droit non vide, somme sur i, le nombre de terminaux utilisés par le premier symbole dans le côté droit. Pour chaque i, il faut multiplier le nombre de possibilités pour le reste du côté droit par le nombre de possibilités pour le premier symbole. Si le premier symbole est un terminal, il y a 1 possibilité si i est 1 et 0 sinon. Si le premier symbole est un non-terminal, la somme des possibilités sur chaque alternative. Pour éviter des boucles infinies, nous devons faire attention à élaguer les appels récursifs lorsqu'une quantité est 0. Cela peut encore boucle infinie si la grammaire a une infinité de dérivations d'une phrase. Par exemple, dans la grammaire

S -> S S
S ->

il y a une infinité de dérivations de la phrase vide: S =>, S => S S =>, S => S S => S S S =>, etc. Le code pour trouver une phrase particulière est une modification simple du code pour les compter. Ce code est raisonnablement efficace, générant 100 phrases avec 100 bornes chacun en moins d'une seconde.

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

Peut-être pas la meilleure solution, mais je travaillerais récursive mon chemin à travers chaque règle de la grammaire jusqu'à ce que je l'ai dépassé la contrainte, puis de nouveau pop et d'explorer un autre chemin le long de la grammaire. Gardez toutes les phrases qui correspondent à la contrainte et jeter toutes les phrases qui ne sont pas.

Par exemple, avec n = 3:

S -> ($ {NP} $ {VP}) -> ((le $ {N}) $ {VP}) -> ((le (chien) $ {VP}) -> ... - > ((le (chien) ((coups de pied) (le $ {NP})))) -> ((le (chien) ((coups de pied) (le (chien)))))

Et puis de nouveau pop

((le (chien) ((coups de pied) (le $ {N})))) -> ((le (chien) ((coups de pied) (le (poisson)))))

et un peu plus tard ...

((le (chien) ($ {V} $ {N}))) -> ((le (chien) ((MEETS) $ {N}))) -> ((le (chien) (( rencontre) le (chien))))

etc.

Pour l'essentiel une recherche graphique en profondeur d'abord, que vous construisez le graphique que vous êtes à la recherche (et vous arrêtez la construction des pièces qui dépassent les contraintes).

Answer 3

Cette question contient une erreur de catégorie. La grammaire que vous avez spécifié a l'apparence d'un contexte grammaire libre, mais l'exigence qu'il y ait un certain nombre de noeuds terminaux nécessite une grammaire récursive dénombrable.