Wie erzeuge ich Sätze aus einer formalen Grammatik?

Question

Was ist eine gängige Methode zum Generieren von Sätzen aus einer Grammatik?

Ich möchte einen Algorithmus, der das Gegenteil von einem Parser ist. Das heißt, bei einer formalen kontextfreien Grammatik (zB LL) möchte ich einen beliebigen Satz erzeugen, der dieser Grammatik entspricht. Ich benutze Satz hier, um jeden gültigen Textkörper zu meinen, so kann es tatsächlich ein ganzes Programm sein (auch wenn es keinen Sinn ergibt - solange es syntaktisch korrekt ist).

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 { ... } 
} 

Answer 1

Ich weiß nicht, dass es einen "gemeinsamen" Algorithmus dafür gibt. Die Zufallsprogrammgenerierung wird in der genetischen Programmierung verwendet, so dass Sie nach einem grammatikbasierten GP-System suchen und sehen können, wie sie mit der Programmgenerierung umgehen. Ich würde eine rekursive Regel Erzeugungsalgorithmus wie der Pseudo-Code 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 müssen auch mit den Wiederholungen umgehen (zufällig die Anzahl der Male, die sie auftreten) und optionalen Regeln (werfen Sie eine Münze 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. Wenn also eine Regel (Literal | Variable) wäre, würden Sie zufällig zwischen den beiden wählen.

Answer 2

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

beschrieben, einige gemeinsame verwendete Algorithmen.

Answer 3

Mein erster Vorschlag wäre eine breite erste Suche. Richten Sie einfach ein Regeldiagramm ein und durchsuchen Sie sie. Sie werden anfangen, Programme zu starten, beginnend mit den kleinsten möglichen, und langsam größer werden. Sie werden jedoch wahrscheinlich feststellen, dass Ihre Grammatik für eine bestimmte Anzahl von Regeln exponentiell mehr Programme ausspuckt und Sie wahrscheinlich nicht mehr als 30 Token in einem Programm mit einem DFS erhalten.

Das Problem mit einer Tiefensuche ist, dass die Suche in der Endlosschleife endet, wenn Sie eine linksrekursive Regel haben.

Ein anderes großes Problem ist, dass syntaktisch korrekte Programme von semantisch korrekten Programmen weit entfernt sind. Die Erzeugung des letzteren Typs ist wahrscheinlich in allen, außer den grundlegendsten Fällen, völlig unmöglich.

Answer 4

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

Man könnte einfach Proben von Hand leichter finden. :)

Answer 5

Aus der Spitze von meinem Kopf:

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

Dies sollte nicht zu schwer sein, es sei denn, Sie wollen eine vollständige Abdeckung garantieren. Selbst dann würde nur eine Bündel von Daten erzeugen eine Hilfe sein ...

---

[*] Sie müssen optionals weniger als 50% der Zeit schließen unendliche Regress zu verhindern, wenn Regeln der Verarbeitung wie

nonterm: otherstuff <nonterm>? 

Guter Fang von plinth.

Ebenso mit Wiederholungen, werfen Sie eine Verteilung, die stark konvergiert.

Sie müssen zuerst die Eingabegrammatik analysieren, wenn sie wie hier in einem BNF-Formular angezeigt wird. Am einfachsten wäre es, ein Mapping (name, string) zu verwenden und dann mit dem Token der höchsten Ebene zu beginnen (was man annehmen könnte, dass es der erste ist ...).

Dies gibt Ihnen:

("Programm", "<Importe> NEWLINE <Namespace>? ")

(" Importe", ("Import" <Kennung> NEWLINE) *)

...

Die du startest mit "program", hit "<importe>", damit du immer wieder kommst, hist "NEWLINE?", also wirf die würfel und schreibe oder nicht, drücke "<namespace>", so wiederhole ... an Rückkehr du bist fertig.

---

Ich finde, ich selbst vermute, dass dies zuvor getan wurde. Wenn Sie nur die Ausgabe benötigen, würde ich das Web durchsuchen ... Vielleicht http://portal.acm.org/citation.cfm?doid=966137.966142, obwohl die riesige Anzahl von Parser Generatoren da draußen den Suchraum überfluten ... Versuchen Sie this paper, auch.

BTW-- Ihre lokale Universität hat wahrscheinlich Online-Abonnements für diese Zeitschriften, so dass Sie sie kostenlos erhalten, indem Sie in der Bibliothek zugreifen.

Answer 6

Das Problem, das Sie haben werden, ist, dass die rekursive Natur des Graphen so ist, dass Sie korrekte Grammatiken unendlicher Größe erzeugen können. Sie werden wahrscheinlich so etwas wie einen Hash der Knotentypen in Ihrer Grammatik einrichten wollen, mit Zählungen und Grenzen davon, wie oft Sie sich erlauben, diesen Knoten zu treffen.Dann suche zuerst nach deinem Herzen.

Answer 7

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

• Klemmenbez
• Nonterminal Symbol
• Reihenfolge der rechten Seiten
• Wahl der rechten Seiten
• Stern Schließung der rechten Seiten

Dies wird alle viel klarer, wenn Sie die Datenstruktur aufschreiben, die Sie verwenden, um eine Grammatik darzustellen. Die Struktur Ihrer wechselseitig rekursiven Generatorfunktionen spiegelt diese Datenstruktur sehr genau wider.

Der Umgang mit unendlichen Rekursion ist ein bisschen heikel. Der einfachste Weg besteht darin, einen Strom von Äußerungen zu erzeugen und eine Tiefenbegrenzung beizubehalten. Oder wenn Sie eine faule Sprache wie Haskell verwenden, können Sie alle Äußerungen erzeugen und so viele endliche abziehen, wie Sie möchten (ein kniffligeres Problem als die ursprüngliche Frage, aber sehr unterhaltsam).

Answer 8

Wie üblich werde ich davon abraten, das Rad neu zu erfinden. Ich habe eine von diesen für ARM-Assembler geschrieben, aber ich bin auf dem Protokoll als bedauere es (Software: Praxis und Erfahrung April 2007):

"Im Nachhinein sollte ein Standard-Expression-Generator haben wurde verwendet, um zufällige ARM-Assembly-Anweisungen zum Vergleich zu erzeugen. Stattdessen wurde inkrementell ein Perl-Skript erstellt, das jede ARM-Anweisungsdefinition verwendet und Instanzen generiert. Ein Vorteil des inkrementellen In-House-Ansatzes war jedoch, dass einfache Substitutionen einfache Fehler aufspürten und die Suche nach Fehlern schrittweise fortgeführt werden konnte. "

Ich fürchte, ich erinnere mich nicht, was mich dazu gebracht hat, meine Meinung zu ändern, und ich bezweifle, dass es für deine spezifischen Bedürfnisse relevant wäre, aber ich schlage vor, nach einer bereits bestehenden Lösung zu suchen. Es erfordert weniger Disziplin, solche Dinge selbst zu schreiben, aber es dauert immer länger als erwartet.

Answer 9

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

das Beispiel aus dem book angepasst ist. Die erzeugten Sätze sind syntaktisch korrekt, aber immer noch totales Kauderwelsch.