Come faccio a generare frasi da una grammatica formale?

Question

Che cosa è un modo comune per la generazione di frasi da un libro di grammatica?

Voglio un algoritmo è un po ' l'opposto di un parser.Che è, dato formale grammatica libera dal contesto (diciamo LL), voglio generare un arbitrario frase che è conforme a quella grammatica.Io uso frase il significato di qualsiasi valida per il corpo del testo, in modo che possa effettivamente essere tutto un programma (anche se non ha alcun senso—come è syntactially corretto).

Esempio grammaticale:

program   : <imports> NEWLINE? <namespace>
imports   : ("import" <identifier> NEWLINE)* 
namespace : "namespace " <identifier> NEWLINE "{" <classes> "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)*
...

Esempio generati programma:

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

Answer 1

Non so che c'è un "comune" algoritmo per fare questo.Programma casuale generazione è utilizzato in programmazione genetica, così si potrebbe cercare una grammatica basata GP di sistema e vedere come gestire la generazione di programmi.Io farei una regola ricorsiva algoritmo di generazione come il pseudo-codice:

void GenerateRule(someRule)
{
  foreach (part in someRule.Parts)
  {
    if (part.IsLiteral) OutputLiteral(part);
    if (part.IsIdentifier) Output(GenerateIdentifier(part)));
    if (part.IsRule) GenerateRule(part.Rule);
  }
}

Questo presuppone che ho letto in tutte le parti in una qualche struttura dati.È inoltre necessario per gestire le ripetizioni(generare in modo casuale il numero di volte in cui si verificano) e regole opzionali (lancia una moneta per vedere se ci sono o non).

---

Edit:Oh, e se la regola è più di un'opzione, devi solo scegliere una delle opzioni per andare con, e del processo allo stesso modo.Quindi, se qualche regola (Letterale|Variabile), devi scegliere in modo casuale tra i due.

Answer 2

Qui è un esempio con l'uso di Python NLTK:

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

L'esempio è tratto da i prenota.Le frasi generate sono sintatticamente corretta, ma ancora totale comuni mortali.

Answer 3

La soluzione dovrebbe seguire il metodo induttivo struttura della grammatica.Come si fa a generare un casuale di esprimersi per ciascuno dei seguenti?

• Simbolo terminale
• Nonterminal simbolo
• Sequenza di destra
• La scelta del lato destro
• Stella di chiusura di destra

Tutto questo sarà molto più chiaro se si scrivere la struttura di dati si utilizza per rappresentare una grammatica.La struttura del set di mutuamente ricorsive generatore di funzioni specchio che struttura dati molto da vicino.

Trattare con una ricorsione infinita, è un po ' rischioso.Il modo più semplice è quello di generare un flusso di parole e di mantenere una profondità di taglio.Oppure, se si utilizza un linguaggio lazy come Haskell è in grado di generare tutti le espressioni e staccare, come molti finiti quelli, come ti piace (un complicato problema di domanda originale, ma molto divertente).

Answer 4

Fuori della parte superiore della mia testa:

Mi piacerebbe lavorare in modo ricorsivo (praticamente il contrario di un ricorsiva decente parser) utilizzando alcune euristiche su cosa fare con intervalli ((...):probabilmente scegliere a caso) optionals (?:vedere [], di seguito), ripetizioni(''Distribuzione di Poisson?).I valori letterali ("...") sono semplici scritti per l'uscita, e subtokens (`<...>') generare una ricorsione.

Questo non dovrebbe essere troppo difficile a meno che non si desidera la garanzia di una sorta di copertura completa.Anche allora, solo la generazione di un mazzo di dati sarebbe un aiuto...

---

[*] È necessario includere optional a meno di 50% del tempo per evitare di regresso all'infinito durante l'elaborazione di regole come

 nonterm:  otherstuff <nonterm>?

Buona cattura da parte zoccolo.

Allo stesso modo, con ripetizioni, di gettare un distribuzioni che converge fortemente.

---

È necessario analizzare l'ingresso di grammatica prima se si è presentato in un BNF forma come qui.Cosa più semplice da fare sarebbe usare una mappatura (name, string), poi iniziare con il più alto livello di token (che si potrebbe supporre significa il primo...).

Questo ti dà:

("programma", "<imports> NEWLINE?<namespace>")

(le"importazioni", ("import" <identifier> NEWLINE)*)

...

Si inizia con "programma" hit "<imports>"così non si ripresenterà...al ritorno, hist "NEWLINE?", così gettare i dadi e scrivere o non, ha colpito "<namespace>"così si ripresenterà...al ritorno ti sei fatto.

---

Trovo la mia auto sospettare che questo è stato fatto prima.Se avete solo bisogno dell'uscita, mi piacerebbe cercare sul web...Forse http://portal.acm.org/citation.cfm?doid=966137.966142, anche se l'enorme numero di generatori di parser là fuori ingombrare lo spazio di ricerca...Provare questa carta, troppo.

BTW-- locale università, probabilmente, è online abbonamenti a queste riviste, in modo che si può ottenere gratuitamente da collegare alla biblioteca.

Answer 5

Il problema è che la natura ricorsiva del grafico è tale che si può generare correttamente le grammatiche di dimensioni infinite.Probabilmente si vuole fare qualcosa di come impostare un hash di tipi di nodo nella tua grammatica con i conti e i limiti di quante volte si consente a voi stessi di colpire quel nodo.Quindi la profondità di ricerca al contenuto del vostro cuore.

Answer 6

Il mio primo suggerimento sarebbe una larghezza di ricerca.Basta impostare un grafico di regole e di ricerca attraverso di loro.Potrai iniziare a sputare fuori programmi a partire dai più piccoli possibili, e lentamente diventando sempre più grandi.È probabile, però, che la tua grammatica farà sputare esponenzialmente più programmi per un certo numero di regole e probabilmente non superare 30 gettoni in un programma che utilizza un DFS.

Il problema con una profondità prima ricerca è che la seconda si dispone di un sinistro ricorsiva regola, la tua ricerca sarà ottenere bloccato in un ciclo infinito.

Un altro grosso problema è che sintatticamente corretto programmi sono una lunga strada da semanticamente corretto programmi.La generazione di quest'ultimo tipo è probabile completamente unfeasable in tutti i casi di base.

Answer 7

Come al solito, ho intenzione di consigliare contro di reinventare la ruota.Ho scritto uno di questi per il BRACCIO assembler, ma io ho il record come pentito (Software:La pratica e l'Esperienza Aprile 2007):

“Col senno di poi, un off-the-shelf espressione del generatore deve essere stata utilizzata per generare casuale BRACCIO di montaggio istruzioni per il confronto.Invece uno script Perl è stato costruito in modo incrementale, l'assunzione di ogni BRACCIO istruzione di definizione e generazione di istanze.Un vantaggio, però, di incrementale in-house approccio, semplici sostituzioni rilevato un semplice bug e bug hunting potrebbe procedere in modo incrementale.”

Ho paura di non ricordo cosa mi ha fatto cambiare la mia mente, e dubito che sarebbe opportuno per le vostre esigenze specifiche, ma io suggerisco alla ricerca di più di un preesistente soluzione.Richiede meno di disciplina a scrivere cose come questo da soli, ma ci vuole sempre più tempo del previsto.

Answer 8

non una risposta, ma controllare la voce di wikipedia sulla grammatica generazione:http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

ha descritto alcuni comuni algoritmi utilizzati.

Answer 9

Mentre l'idea è bella (ho pensato molte volte prima di), la realtà è che senza alcuni esempi di dati e/o le tonnellate di generatore di vincoli/limiti di sforzo, è piuttosto un grande lavoro.

Si potrebbe solo trovare esempi di scrittura a mano più facile.:)