Wie generiere ich Sätze aus einer formalen Grammatik?

StackOverflow https://stackoverflow.com/questions/603687

Frage

Was ist eine gängige Methode, Sätze aus einer Grammatik zu generieren?

Ich möchte einen Algorithmus, der Art des anderen eines Parsers ist. Das heißt, eine formale kontextfreie Grammatik gegeben (sagen LL), ich mag einen beliebigen Satz erzeugen, das zu dieser Grammatik entspricht. Ich benutze Satz hier jeden gültigen Textkörper zu verstehen, so kann es tatsächlich ein ganzes Programm sein (auch wenn es keinen Sinn-wie macht lange es syntactially korrekt).

Beispiel Grammatik: 

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

Beispiel erzeugt Programm : 

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}
War es hilfreich?

Lösung

Ich weiß nicht, dass es ein „gemeinsamer“ Algorithmus ist, dies zu tun. Zufallsprogramm Generation wird in der genetischen Programmierung verwendet, so dass Sie für eine Grammatik basiert GP-System aussehen könnte und sehen, wie sie die Programmerstellung behandeln. Ich würde wie der Pseudo-Code einen rekursiven Regelerzeugungsalgorithmus tun: 

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);
  }
}

Dies setzt voraus, dass Sie in allen Teilen in eine Datenstruktur gelesen habe. Sie würden auch die Wiederholungen behandeln müssen (nach dem Zufall die Anzahl der Male erzeugen sie auftreten) und optionale Regeln (eine Münze werfen, um zu sehen, ob sie da sind oder nicht).

Edit: Ach ja, und wenn die Regel mehr als eine Option hat, dann würden Sie nur eine der Optionen wählen, mit zu gehen, und es die gleiche Art und Weise zu verarbeiten. Also, wenn eine Regel war. (Wörtliche | Variable), dann würden Sie zufällig zwischen den beiden wählen

Andere Tipps

Hier ist ein Python-Beispiel unter Verwendung des 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()))

Das Beispiel aus dem Buch angepasst. Die Sätze erzeugt sind syntaktisch korrekt, aber immer noch total Kauderwelsch.

Ihre Lösung sollte die induktive Struktur der Grammatik folgen. Wie generieren Sie eine zufällige Äußerung für jeden der folgenden?

  • Terminal Symbol
  • Nonterminal Symbol
  • Reihenfolge der rechten Seiten
  • Wahl der rechten Seiten
  • Star Schließung der rechten Seiten

Das wird alles viel klarer, wenn Sie die Datenstruktur Sie eine Grammatik darzustellen verwenden aufzuschreiben. Die Struktur Ihres Satzes von gegenseitig rekursive Generator Funktionen wird sehr genau, dass die Datenstruktur widerspiegelt.

mit unendlicher Rekursion Der Umgang ist ein bisschen heikel. Der einfachste Weg ist es, einen Strom von Äußerungen zu erzeugen, und eine Tiefe Cutoff zu halten. Oder wenn Sie einen faulen Sprache wie Haskell verwenden, können Sie erzeugen alle Äußerungen und abblättern so viele endlich diejenigen, wie Sie möchten (ein heikler Problem als die ursprüngliche Frage, aber sehr unterhaltsam).

Aus der Spitze von meinem Kopf:

Ich würde rekursiv arbeiten (im Grunde das Gegenteil eines rekursiven anständigen Parser) mit einiger Heuristik über das, was mit Bereichen zu tun ((...): wahrscheinlich zufällig wählen) optionals (?: siehe [], unten), Wiederholungen ( '' Poisson-Verteilung?). Literale ("...") sind einfach in die Ausgabe geschrieben, und subtokens ( `<...> ') eine Rekursion erzeugen.

Dies sollte nicht zu schwer sein, es sei denn, Sie irgendeine Art von vollständiger Abdeckung gewährleisten wollen. Selbst dann, nur ein Bündel zu erzeugen von Daten wäre eine Hilfe sein ...

[*] Sie müssen Extras enthalten weniger als 50% der Zeit unendliche Regress zu verhindern, wenn Regeln der Verarbeitung wie 

 nonterm:  otherstuff <nonterm>?

Guter Fang von Sockel .

Ebenfalls mit Wiederholungen, werfen eine Verteilung, die stark konvergiert.

Sie müssen die Eingabegrammatik analysieren zuerst, wenn es wie hier in einer BNF-Form präsentiert wird. Einfachste, was zu tun wäre eine Zuordnung (name, string) verwenden, dann mit dem höchsten Niveau Token beginnen (die man annehmen könnte, bedeutet die ersten ...).

Das gibt Ihnen:

  

( "Programm", " NEWLINE? ")

     

( "Importe", ( "Import" NEWLINE) *)

     

...

Das Sie mit „Programm“ zu starten, klicken Sie auf „“, so dass Sie sich wiederholen ... auf Rückwegs, hist „NEWLINE?“, So würfeln und schreiben oder nicht, klicken Sie auf „“ so wiederkehren ... bei der Rückkehr Sie sind fertig.

Ich finde mich selbst zu ahnen, dass dies zuvor getan wurde. Wenn Sie nur den Ausgang benötigen, würde ich die Web-Suche ... Vielleicht http: / /portal.acm.org/citation.cfm?doid=966137.966142 , obwohl die große Anzahl von Parser-Generatoren gibt, den Suchraum verunstaltet ... Versuchen Sie dieses Papier , zu.

BTW-- Sie örtliche Universität wahrscheinlich Online-Abonnements auf diese Zeitschriften hat, so dass Sie sie kostenlos durch Einhaken in der Bibliothek erhalten.

Das Problem haben Sie besteht darin, dass die rekursive Natur des Graphen ist, so dass Sie richtig Grammatiken von unendlicher Größe erzeugen können. Sie werden wahrscheinlich so etwas wie die Einrichtung eines Hash von Knotentypen in Ihrer Grammatik mit Zählungen und Grenzen machen wollen, wie oft Sie erlaubt sich, dass der Knoten zu treffen. Dann Tiefe zuerst zu Inhalt Ihres Herzens suchen.

Mein erster Vorschlag wäre eine Breitensuche sein. Stellen Sie einfach eine grafische Darstellung der Regeln und durchsuchen sie. Sie werden spucken Programme starten von den kleinsten möglichen, beginnen und langsam immer größer. Sie werden wahrscheinlich finden Sie jedoch, dass Ihre Grammatik für eine bestimmte Anzahl von Regeln exponentiell mehr Programme ausspucken wird und Sie erhalten wahrscheinlich nicht über 30 oder so Token in einem Programm eine DFS verwenden.

Das Problem mit einer Tiefensuche ist, dass die zweiten Sie eine linksrekursive Regel haben, wird Ihre Suche in einer Endlosschleife stecken.

Ein weiteres großes Problem ist, dass syntaktisch korrekte Programme von semantisch korrekten Programmen ein langer Weg. Der letztgenannte Typ Erzeugung wahrscheinlich völlig undurchführbar in allen außer den einfachsten Fällen.

Wie üblich, ich werde gegen das Rad neu erfinden beraten. Ich habe eine dieser für ARM-Assembler geschrieben, aber ich bin auf Aufzeichnung, wie es ( Software: Praxis und Erfahrung April 2007): Bedauern darüber,

„Im Nachhinein ein Off-the-shelf-Expression Generator verwendet haben sollte worden Anweisungen zufällig Armbaugruppe zum Vergleich zu erzeugen. Stattdessen wurde ein Perl-Skript schrittweise aufgebaut, wobei jede ARM-Befehl Definition zu nehmen und Instanzen zu erzeugen. Ein Vorteil war jedoch der inkrementalen in-house-Ansatzes, dass einfache Substitutionen einfache Fehler erkannt und Fehlersuche könnte schrittweise vorgehen.“

Ich fürchte, ich erinnere mich nicht, was mich meine Meinung ändern, und ich bezweifle, dass es auf Ihre speziellen Bedürfnisse relevant sein würde, aber ich schlage vor, suche härter für eine bereits existierende Lösung. Es erfordert weniger Disziplin Sachen wie diese selbst zu schreiben, aber es dauert immer länger als erwartet.

keine Antwort, aber überprüfen Sie die Wikipedia-Eintrag auf Grammatikgenerierung: http://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

beschrieben, einige gemeinsame Algorithmen verwendet.

Während die Idee ist schön (ich habe schon oft daran gedacht), die Realität ist, dass ohne einige Beispieldaten und / oder Tonnen-Generator Einschränkungen / Aufwand Grenzen, es ist eine ziemlich große Aufgabe.

Man könnte nur finden Proben von Hand zu schreiben einfacher. :)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top