Problem (tl; dr)

Wenn eine kontextfreie Grammatik , finden Sie eine Reihe von Zeichenfolgen, die mindestens einmal durch jede Produktion führen.$G$$G$

Wie und wie schnell geht das?

Hintergrund

Ich arbeite an einem Compiler, dessen Parser mit einem ähnlichen Tool wie Yacc + Antlr implementiert ist. Ich habe den größten Teil des Parser-Codes geschrieben und möchte einen Code der Objektsprache generieren, der jede Produktion der Grammatik mindestens einmal aufruft, damit ich ihn dem Parser zuführen und sicherstellen kann, dass nichts falsch ist .

Im Interesse eines guten Testens möchte ich wirklich eine kurze Testdatei, die eine bestimmte Produktion "im Test" hat. Daher möchte ich für jede Produktionsregel eine minimale Zeichenfolge generieren, die den Parser aus dem Startzustand durch die getestete Produktion zu einer Reihe von Terminals.

Mögliche Lösungen

Ich stelle mir vor, dass es eine elegante Lösung mit Graphentheorie gibt, aber ich bin mir nicht ganz sicher, was es ist. Ich möchte nur den Dijkstra-Algorithmus verwenden, um kürzeste Pfade durch eine geeignete Struktur zu finden, aber ich denke, dass eine Zeichenfolge eher durch eine kontextfreie Grammatik in einer Baumstruktur als durch einen Pfad analysiert wird, daher weiß ich nicht, wie das funktioniert .

Ich denke, es könnte eine clevere Möglichkeit geben, es als Netzwerkflussproblem darzustellen. So etwas wie das: Nehmen Sie ein Diagramm, das einen Scheitelpunkt für jedes Symbol (Terminal und Nicht-Terminal) und einen Scheitelpunkt für jede Produktion hat. Wenn ein Nichtterminal eine Produktion hat, fügen Sie der Produktion eine gerichtete Kante vom Nichtterminal hinzu. Wenn eine Produktion ein Symbol erzeugt, fügen Sie dem Symbol eine gerichtete Kante aus der Produktion hinzu. Fügen Sie eine Quelle mit einer Kapazität und hängen Sie sie an den Scheitelpunkt an, der dem Startsymbol entspricht. Fügen Sie eine Spüle mit unendlicher Kapazität hinzu und befestigen Sie sie an jedem Terminal.$c$

Wenn ein Nichtterminal einen In-Arc mit einer Kapazität , fügen Sie jeder seiner Produktionen mit der Kapazität einen Bogen vom Nonterminal hinzu . Wenn eine Produktion einen In-Arc mit der Kapazität und einen Out-Arc zu Nichtterminals hat, fügen Sie jedem Nonterminal einen Arc mit der Kapazität aus der Produktion hinzu.$k$$k$$k$$n$$\frac k n$

Führen Sie dann einen Maximum-Flow-Algorithmus im Netzwerk aus und lassen Sie die Produktionen vom Startsymbol zu den Terminals "herunterrinnen". Am Ende sollte ein Flow aus Ihrer Quelle kommen, und Sie können alle Terminals, die Sie mit einem Flow ungleich Null getroffen haben, als Ergebniszeichenfolge zurückgeben. Dann erhalten Sie für jeden Lauf eine Zeitkomplexität von , wobei die Summe der Anzahl der Terminals und Nicht-Terminals in Ihrer Grammatik ist - nicht schlecht.$c$$O(n^3)$$n$

Ich bin mir jedoch immer noch nicht sicher, wie dieses Diagramm aussieht: Ich denke, dass es unendlich sein muss, und ich bin mir nicht sicher, ob Sie den maximalen Fluss eines Netzwerks mit unendlichem Fluss finden können. Danach bin ich mir nicht sicher, wie ich eine Produktion aus der Betrachtung "entfernen" soll, damit ich garantiert für jeden Testlauf eine neue bekomme.

Ich habe gegoogelt und konnte nichts finden. Gibt es eine gute Lösung für dieses Problem?

In einer Nussschale

Da ich die Literatur nicht genug kannte, erarbeitete ich eine Lösung, die im nächsten Abschnitt vorgestellt wird, zusammen mit einem Beweis für den schwierigsten Teil. Sobald ich wusste, was gebraucht wurde, konnte ich in der Literatur nach den richtigen Ideen suchen. Hier ist eine kurze Darstellung des Algorithmus, basierend auf der Literatur, die im Wesentlichen dieselbe ist, die ich entwickelt habe.

Das erste, was Sie tun müssen, ist, eine Terminalzeichenfolge mit minimaler Größe zu finden $\sigma(U)$ für jedes Nicht-Terminal $U$der Grammatik. Dies kann erreicht werden, indem Knuths Erweiterung auf Conc- oder Graphen (auch als CF-Grammatiken bezeichnet) und - oder Graphen des Dijkstra-Algorithmus für kürzeste Wege verwendet wird . Beispiel B in Knuths Artikel macht fast das, was benötigt wird.

Eigentlich berechnet Knuth nur die Länge dieser Terminalzeichenfolgen, aber es ist ziemlich einfach, seinen Algorithmus so zu ändern, dass tatsächlich eine solche Terminalzeichenfolge berechnet wird $\sigma(U)$ für jedes Nicht-Terminal $U$(wie ich es in meiner eigenen Version unten mache). Wir definieren auch$\sigma(a)=a$ für jedes Terminal $a$und wir verlängern $\sigma$ wie üblich in einen String-Homomorphismus.

Dann betrachten wir einen gerichteten Graphen, in dem Nicht-Terminals die Knoten sind und es einen Bogen gibt $(U,V)$ Wenn es eine Regel gibt $U\rightarrow \alpha V\beta$. Wenn mehrere solcher Regeln den gleichen Bogen erzeugen können$(U,V)$Wir behalten eine so, dass die Länge $|\sigma(\alpha\beta)|$ist minimal. Der Bogen ist mit dieser Regel und dieser minimalen Länge gekennzeichnet $|\sigma(\alpha\beta)|$ wird das Gewicht des Bogens.

Schließlich berechnen wir unter Verwendung des Dijkstra-Algorithmus für den kürzesten Pfad den kürzesten Pfad aus dem anfänglichen Nicht-Terminal $S$zu jedem Nicht-Terminal der Grammatik. Gegeben der kürzeste Weg für ein Nicht-Terminal$U$können die Regelbezeichnungen auf den Bögen verwendet werden, um eine Ableitung zu erhalten $S\overset{*}{\Longrightarrow}\alpha U \beta$. Dann zu jeder Regel des Formulars$U\rightarrow\gamma$ In der Grammatik ordnen wir die Terminal-Zeichenfolge mit minimaler Größe zu $\sigma(\alpha\gamma\beta)$ die mit dieser Regel abgeleitet werden können.

Um eine geringe Komplexität zu erreichen , werden sowohl der Dijkstra-Algorithmus als auch die Knuth-Erweiterung mit Haufen und AKA-Prioritätswarteschlangen implementiert . Dies gibt für den Dijkstra-Algorithmus eine Komplexität von$O(n\log n +t)$und für Knuths Algorithmus eine Komplexität $O(m \log n +t)$, wo sind sie $m$ Grammatikregeln und $n$ Nicht-Terminals und $t$ist die Gesamtlänge aller Regeln. Das Ganze wird seitdem von der Komplexität des Knuth-Algorithmus dominiert$m\geq n$.

Was folgt, ist meine eigene Arbeit, bevor ich die kurze Antwort oben produzierte.

Ableiten der Lösung aus dem Algorithmus zur Beseitigung nutzloser Symbole.

Dieser Algorithmus hat mehrere Aspekte. Zur besseren Intuition habe ich mich entschieden, es in drei aufeinander folgenden Versionen zu präsentieren, die zunehmend mehr Funktionen einführen. Die erste Version beantwortet die Frage nicht, ist jedoch ein Standardalgorithmus für die Beseitigung nutzloser Symbole, der eine Lösung vorschlägt. Die zweite Version beantwortet die Frage ohne die Minimalitätsbeschränkung. Die dritte Version gibt eine Antwort auf die Frage und erfüllt die Minimalitätsbeschränkung. Diese dritte Lösung wird dann verbessert, indem eine Anpassung an und / oder Diagramme des Dijkstra-Algorithmus für kürzeste Wege verwendet wird .

Das Endergebnis ist ein sehr einfacher Algorithmus, der es vermeidet, bereits durchgeführte Berechnungen zu überdenken. Aber es ist weniger intuitiv und erfordert einen Beweis.

Diese Antwort versucht nur, die Frage zu beantworten, die durch den Kommentar des OP präzisiert wurde: " Für jede Produktionsregel möchte ich eine minimale Zeichenfolge generieren, die den Parser vom Startzustand über die getestete Produktion zu einer Reihe von Terminals führt. "Daher versuche ich nur, eine Reihe von Zeichenfolgen zu erhalten, sodass für jede Regel eine Zeichenfolge in der Gruppe vorhanden ist, die eine der Zeichenfolgen mit minimaler Größe der Sprache ist, die eine Ableitung unter Verwendung der Regel aufweist.

Es muss jedoch beachtet werden, dass die Tatsache, dass eine Zeichenfolge eine Regel "aufruft", dh eine Ableitung unter Verwendung dieser Regel hat, nicht unbedingt bedeutet, dass die Regel von einem Parser berücksichtigt wird, der mit mehrdeutigen Grammatiken arbeitet und Mehrdeutigkeiten willkürlich auflöst. Die Behandlung einer solchen Situation würde wahrscheinlich genauere Kenntnisse des Parsers erfordern und könnte eine komplexere Frage sein.

Der grundlegende Algorithmus

Um diese Frage zu lösen, kann man mit dem klassischen Algorithmus zum Entfernen nutzloser Symbole in kontextfreien Grammatiken beginnen. Es befindet sich in Abschnitt 4.4, S. 88-89, von Hopcroft & Ullman, Ausgabe 1979. Aber die Präsentation hier kann etwas anders sein.

Der Algorithmus zielt genau darauf ab, das Vorhandensein einer solchen Abdeckung zu beweisen, wie vom OP gefordert, und besteht aus zwei Teilen:

• Lemma 4.1 von H & U, Seite 88: Entfernen aller unproduktiven Nicht-Terminals . Dazu wird versucht, für jedes Terminal eine Terminalzeichenfolge zu finden, von der es abgeleitet werden kann. Eine einfache Möglichkeit, dies zu erklären, lautet wie folgt: Sie erstellen eine Menge$Prod$od produktive Symbole, die Sie mit allen Terminals initialisieren. Dann enthält jede noch nicht verarbeitete Regel alle rechtsseitigen Symbole (RHS)$Prod$Fügen Sie dem Set das linke Terminal (LHS) hinzu $Prod$und Sie entfernen alle Regeln mit demselben LHS-Nicht-Terminal aus dem zu verarbeitenden Regelsatz. Sie wiederholen den Vorgang, bis keine Regel mehr mit allen RHS-Symbolen vorhanden ist$Prod$. Die restlichen Nicht-Terminals, nicht in$Prod$ am Ende dieses Prozesses sind sie nicht produktiv: Sie können nicht in eine Terminalzeichenfolge abgeleitet und somit aus der Grammatik entfernt werden.

• Lemma 4.2 von H & U, Seite 89: Entfernen aller nicht erreichbaren Symbole . Dies geschieht durch die klassische Erreichbarkeit von Knoten in gerichteten Graphen, indem Nicht-Terminals als Knoten betrachtet werden und ein Bogen vorliegt$(U,V)$ Wenn es eine Regel gibt $U\rightarrow \alpha$ so dass $V$ tritt auf in $\alpha$. Sie erstellen ein Set$Reach$ von erreichbaren Symbolen, die nur mit dem Anfangssymbol initialisiert werden $S$. Dann für jedes nicht-terminale Symbol$U$ im $Reach$ oder später hinzugefügt, und für jede Regel $U\rightarrow \alpha$, fügst du hinzu $Reach$ alle Symbole in $\alpha$. Wenn alle Nicht-Terminals in$Reach$ Auf diese Weise wurden alle Symbole (Terminal oder Nicht-Terminals) verarbeitet, die nicht in enthalten sind $Reach$kann nicht in einer vom Anfangssymbol abgeleiteten Zeichenfolge erscheinen und ist daher unbrauchbar. Somit können sie aus der Grammatik entfernt werden.

Diese beiden grundlegenden Algorithmen sind nützlich, um die Rohergebnisse einiger Grammatikkonstruktionstechniken zu vereinfachen, wie sie beispielsweise für die Überschneidung einer kontextfreien Sprache und einer regulären Menge verwendet werden. Dies ist insbesondere nützlich, um die Ergebnisse allgemeiner CF-Parser zu bereinigen .

Das Entfernen von nicht-terminalen Symbolen ist im Zusammenhang mit der Lösung der gestellten Frage erforderlich, da die Regeln, die sie verwenden, von keiner Zeichenfolge der Sprache "aufgerufen" (dh in ihrer Ableitung verwendet) werden können.

Erstellen eines Satzes von Zeichenfolgen, die jede Regel aufrufen

(Wir suchen noch nicht nach minimalen Zeichenfolgen.)

Wenn man nun speziell die Frage beantwortet, muss man tatsächlich alle nutzlosen Symbole entfernen, ob nicht erreichbare Symbole oder unproduktive nicht-terminale Symbole, sowie nutzlose Regeln mit solchen nutzlosen nicht-terminalen Symbolen wie LHS. Sie haben keine Chance, beim Parsen einer Terminalzeichenfolge jemals sinnvoll aufgerufen zu werden (obwohl einige möglicherweise die Verarbeitungszeit eines Parsers verschwenden, wenn sie nicht entfernt werden; welche Zeit verschwenden können, hängt von der Parsertechnologie ab).

Wir betrachten nun für jede (nützliche) Regel die Erzeugung einer Terminalzeichenfolge, die sie aufruft, dh die unter Verwendung dieser Regel erzeugt werden kann. Dies ist im Wesentlichen das, was diese beiden oben genannten Algorithmen tun, obwohl sie die Informationen nicht speichern, da sie damit zufrieden sind, die Existenz dieser Zeichenfolgen zu beweisen, um sicherzustellen, dass Nicht-Terminals sowohl erreichbar als auch produktiv sind.

Wir modifizieren den ersten Algorithmus (Lemma 4.1), indem wir uns an jedes Nicht-Terminal halten $U$ im Set $Prod$ eine Terminalzeichenfolge $\sigma(U)$ es leitet sich ab auf: $U\overset{*}{\Longrightarrow}\sigma(U)$. Für jedes Terminal definieren wir die$\sigma$als Identitätszuordnung. Wann$U$ wird dem Set hinzugefügt $Prod$ weil eine Regel $U\rightarrow\gamma$ hat alle seine RHS-Symbole in $Prod$, dann definieren wir $\sigma(U)=\sigma(\gamma)$, verlängern $\sigma$ als Homomorphismus auf Strings, und wir entfernen alle $U$-Regeln, das sind alles Regeln mit $U$ als LHS.

Wir modifizieren den zweiten Algorithmus (Lemma 4.2), indem wir jedes nicht-terminale Symbol beibehalten $U$ hinzugefügt zu $Reach$ der Pfad, über den es vom Anfangssymbol aus erreicht wurde $S$, was die aufeinanderfolgenden Regeln gibt, um eine Ableitung zu erhalten $S\overset{*}{\Longrightarrow}\alpha U \beta$.

Dann für jede Regel $U\rightarrow\gamma$In der Grammatik erzeugen wir eine Terminalzeichenfolge, die diese Regel wie folgt "aufruft". Wir nehmen aus dem Ergebnis des zweiten Algorithmus die Ableitung $S\overset{*}{\Longrightarrow}\alpha U \beta$. Dann wenden wir die Regel an, um den String zu erhalten$\alpha \gamma \beta$. Eine Terminalzeichenfolge, die die Regel "aufruft"$U\rightarrow\gamma$ ist $\sigma(\alpha \gamma \beta)$

Erstellen einer Reihe minimaler Zeichenfolgen, die jede Regel "aufrufen"

Wir ignorieren das Problem der Beseitigung nutzloser Symbole, die ein Nebenprodukt dieser modifizierten Algorithmen sein können.

Das Erstellen eines Satzes minimaler Zeichenfolgen setzt voraus, dass zuerst eine minimale abgeleitete Zeichenfolge für jedes Nicht-Terminal abgerufen wird. Dies erfolgt durch weitere Modifikation des ersten Algorithmus (Lemma 4.1). Zuerst entfernen wir alle rekursiven Regeln aus dem zu verarbeitenden Regelsatz (dh mit einem LHS-Symbol in der RHS-Zeichenfolge). Es ist offensichtlich, dass keine dieser Regeln zu einer kürzeren Terminalzeichenfolge führen kann als die nicht rekursiven Regeln mit derselben LHS. Und es muss mindestens eine nicht rekursive Regel geben, wenn die LHS kein nutzloses Nicht-Terminal ist (weil nicht produktiv).

Dann gehen wir wie zuvor vor, um das Set zu erstellen $Prod$ von produktiven Symbolen, die mit jedem Synbol assoziiert sind $U$ eine Terminalzeichenfolge, die wir notieren $\sigma(U)$. Die Saite$\sigma(U)$ wird wie bisher durch Anwendung der Regel hergestellt $U\rightarrow\gamma$, Ersetzen jedes Nicht-Terminals $V$ auftreten in $\gamma$ mit $\sigma(V)$. Bisher war es notwendig, dies nur auf eine Regel mit einem bestimmten Nicht-Terminal anzuwenden$U$ als seine LHS, die erste, die alle seine RHS-Nicht-Terminals in hätte $Prod$und ignorieren Sie dann die anderen, da eine solche abgeleitete Zeichenfolge ausreichen würde. Aber wir suchen jetzt nach einer minimalen abgeleiteten Zeichenfolge. Daher für ein Nicht-Terminal$U$Dies muss für alle Regeln mit gemacht werden $U$als LHS. Wir behalten jedoch nur eine Terminalzeichenfolge$\sigma(U)$Ersetzen des aktuellen durch den neu gefundenen, wenn der neue kleiner ist.

Außerdem, wann immer die Zeichenfolge $\sigma(U)$ wird durch eine kleinere ersetzt, alle Regeln mit einem Vorkommen von $U$in der RHS, die bereits verarbeitet wurde, müssen in den zu verarbeitenden Regelsatz zurückgesetzt werden, da durch Änderung die RHS auf einer kürzeren Zeichenfolge abgeleitet werden kann. Dies erfordert mehr Iterationen, endet jedoch irgendwann, da keine dieser Zeichenfolgen jemals viel kürzer als die leere Zeichenfolge wird.

Am Ende dieses ersten Algorithmus die Zeichenfolge $\sigma(U)$ ist eine der kleinsten Zeichenfolgen, aus denen abgeleitet werden kann $U$. Es kann andere geben.

Jetzt müssen wir auch den zweiten Algorithmus modifizieren, um für jedes Nicht-Terminal zu erhalten $U$, (einer von) der kürzesten Zeichenfolge, die U als einziges Nicht-Terminal enthält. Zu diesem Zweck behalten wir den gleichen gerichteten Graphen mit Nicht-Terminals als Knoten bei und haben einen Bogen$(U,V)$ Wenn es eine Regel gibt $U\rightarrow \alpha V \beta$. Jetzt legen wir Gewichte auf die Bögen, um die Mindestlänge des Terminalkontexts zu berechnen, die mit erreichbaren Nicht-Terminals verknüpft werden muss. Das mit dem Lichtbogen verbundene Gewicht$(U,V)$ oben ist die Länge $|\sigma(\alpha\beta)|$, wo die Zuordnung $\sigma$wird als Identität auf Terminals erweitert und dann erneut als String-Homomorphismus erweitert. Dies ist die Länge (einer) der kürzesten Terminal-Strings, die aus dem String abgeleitet werden können $\alpha\beta$. Beachten Sie, dass$V$wird in dieser Berechnung entfernt. JEDOCH, wenn es mehrere Vorkommen von gibt$V$In der RHS muss nur eine entfernt werden. Es können mehrere möglich sein$(U,V)$ Bögen mit unterschiedlichen Gewichten, wenn es mehrere Regeln mit gibt $U$ als LHS und $V$in der RHS. In einem solchen Fall wird nur einer der leichteren Lichtbögen beibehalten.

In diesem Diagramm suchen wir nicht mehr nur nach der Erreichbarkeit von Knoten von $S$, aber für den kürzesten gewichteten Pfad, der jeden Knoten vom Anfangssymbol aus erreicht $S$. Dies kann mit dem Dijkstra-Algorithmus erfolgen .

Gegeben der kürzeste Weg für ein Nicht-Terminal $U$Wir lesen es wie zuvor als eine Folge von Regeln, aus denen wir eine Dérivation erhalten $S\overset{*}{\Longrightarrow}\alpha U \beta$. Dann zu jeder Regel des Formulars$U\rightarrow\gamma$ In der Grammatik erzeugen wir eine minimale Terminalzeichenfolge, die diese Regel als "aufruft" $\sigma(\alpha\gamma\beta)$

Anmerkung : Dieselbe minimale Zeichenfolge kann wahrscheinlich für mehrere Regeln verwendet werden. Aber die Tatsache, dass eine der Zeichenfolgen eine Regel verwendet$\rho$ in seiner Ableitung bedeutet dies nicht unbedingt, dass es sich um eine minimale Zeichenfolge für diese Regel handelt $\rho$, wie es für eine andere Regel gefunden worden sein kann, während eine kürzere für gefunden werden kann $\rho$. Es kann möglich sein, die Wahrscheinlichkeit zu erhöhen, dass dieselbe minimale Zeichenfolge für mehrere Regeln gefunden wird, indem eine Prioritätsrichtlinie verwendet wird, wenn Flexibilität besteht. Aber ist es die Mühe wert?

Ein schnellerer Algorithmus für minimale Terminalzeichenfolgen, die von einem Nicht-Terminal abgeleitet werden

Aufbau der Funktion $\sigma$ so dass $\sigma(U)$ ist eine minimale Terminalzeichenfolge, die von abgeleitet ist $U$wird oben mit einer eher naiven Technik durchgeführt, die eine iterative Überprüfung der bereits geleisteten Arbeit erfordert, wenn für einige Nicht-Terminals eine neue kleinere abgeleitete Zeichenfolge gefunden wird. Dies ist verschwenderisch, auch wenn der Prozess eindeutig beendet wird.

Wir schlagen hier einen effizienteren Algorithmus vor, dh im Wesentlichen eine Anpassung an den CF-Grammatikgraphen einer Erweiterung des Dijkstra-Algorithmus für kürzeste Pfade zu und / oder Graphen mit einer korrekten Definition des Pfadkonzepts für einen und / oder Graphen . Diese Variante des Algorithmus existiert wahrscheinlich in der Literatur (vorausgesetzt, er ist korrekt), aber ich konnte ihn in den Ressourcen, auf die ich zugreifen kann, nicht finden. Daher beschreibe ich es zusammen mit einem Beweis ausführlicher.

Wie zuvor entfernen wir zuerst alle rekursiven Regeln (dh Regeln mit einem LHS-Symbol in der RHS-Zeichenfolge) aus dem zu verarbeitenden Regelsatz. Es ist offensichtlich, dass keine dieser rekursiven Regeln zu einer kürzeren Terminalzeichenfolge führen kann als die nicht rekursiven Regeln mit derselben LHS. Und für eine LHS$U$ Es muss mindestens eine nicht rekursive vorhanden sein $U$-Regel wenn das Symbol $U$ist kein nutzloses Nicht-Terminal (weil nicht produktiv). Dies ist nicht unbedingt erforderlich, verringert jedoch die Anzahl der Regeln, die später berücksichtigt werden müssen.

Dann gehen wir wie zuvor vor, um das Set zu erstellen $Prod$ von produktiven Symbolen, die mit jedem Synbol assoziiert sind $X$ eine Terminalzeichenfolge, die wir notieren $\sigma(X)$Dies ist eine Terminal-Zeichenfolge mit minimaler Größe, von der abgeleitet werden kann $X$ (Im vorherigen Algorithmus war dies erst nach Beendigung der Fall). Die Menge $Prod$ wird mit allen Terminalsymbolen und für jedes Terminalsymbol initialisiert $a$, wir definieren $\sigma(a)=a$.

Dann betrachten wir jede Regel $U\rightarrow\gamma$ so dass alle RHS-Symbole in sind $Prod$und wir wählen eine so, dass $\sigma(\gamma)$ist minimal minimal. Dann fügen wir hinzu$U$ zu $Prod$mit $\sigma(U)=\sigma(\gamma)$und entfernen Sie alle $U$-Regeln. Wir iterieren, bis alle Produktterminals eingegeben wurden$Prod$. Jedes Nicht-Terminal$U$, einmal eingegeben $Prod$muss nie wieder in Betracht gezogen werden, um sich zu ändern $\sigma(U)$ für eine kleinere Saite.

Beweis :

Die vorherigen Algorithmen waren mehr oder weniger intuitiv offensichtlich. Dieser ist aufgrund des und / oder Charakters des Diagramms etwas kniffliger, und ein Beweis scheint notwendiger zu sein. Alles, was wir brauchen, ist das folgende Lemma, das die Richtigkeit des Algorithmus bei Anwendung auf die letzte Iteration feststellt.

Lemma : Nach jeder Iteration des Algorithmus$\sigma(X)$ ist eine Terminal-Zeichenfolge mit minimaler Größe, von der abgeleitet werden kann $X$, für alle $X$ im $Prod$.

Der Basisschritt ist offensichtlich, da dies per Definition für alle Terminals in gilt $Prod$ wenn es initialisiert ist.

Angenommen, dies ist der Fall, nachdem einige Nicht-Terminals hinzugefügt wurden $Prod$, Lassen $U\rightarrow\gamma$ als Regel ausgewählt werden, um ein neues Nicht-Terminal hinzuzufügen $Prod$. Wir wissen, dass diese Regel gewählt wird, weil $\gamma\in{Prod}^*$ und $\sigma(\gamma)$ ist über alle RHS aller Regeln mit einem RHS in der Größe minimal ${Prod}^*$. Dann$U$ wird hinzugefügt $Prod$und das müssen wir nur beweisen $\sigma(\gamma)$ ist eine Terminal-Zeichenfolge mit minimaler Größe, von der abgeleitet werden kann $U$.

Dies ist offensichtlich für alle Ableitungen der Fall, die mit der Regel beginnen $U\rightarrow\gamma$, da durch Induktionshypothese, Anwendung der Kartierung $\sigma$ ist so, dass alle Nicht-Terminals in $\sigma$werden durch von ihnen abgeleitete Terminal-Strings mit minimaler Größe ersetzt. Daher kann keine andere Ableitung eine kürzere Terminalzeichenfolge erzeugen.

Wir betrachten daher nur Ableitungen, die mit einer anderen beginnen $U$-Regel $U\rightarrow\beta$, so dass $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$, wo $\Sigma$ ist der Satz von Terminalsymbolen.

Wenn $\beta\in{Prod}^*$, dann ist eine minimale Zeichenfolge, aus der es abgeleitet werden kann $\sigma(\beta)$. Aber da haben wir die Regel gewählt$U\rightarrow\gamma$muss es das sein $|\sigma(\beta)|\geq|\sigma(\gamma)|$. Also die Regel $U\rightarrow\beta$ leitet sich nicht von einem kleineren terminalen Teilstring ab.

Der letzte zu berücksichtigende Fall ist, wann $\beta\notin{Prod}^*$und wir betrachten dann eine Ableitung $\beta\overset{*}{\Longrightarrow}w\in\Sigma^*$. Wenn diese Ableitung nur Nicht-Trminals in betrifft$Prod$, dann $\beta\in{Prod}^*$Dies ist ein Fall, den wir bereits gesehen haben. Daher betrachten wir nur Ableitungen, die Schritte haben, die eine Regel verwenden, deren LHS nicht in ist$Prod$. Lassen$V\rightarrow\alpha$ sei eine solche Regel, so dass $\alpha\in{Prod}^*$Es muss mindestens eine solche Regel geben, da sie teilweise nach Ableitungsreihenfolge geordnet sind, und $w\in{Prod}^*$.

So haben wir $U\Longrightarrow\beta\overset{*}{\Longrightarrow}\mu V\nu$. Wir wissen das$\mu$ und $\nu$ leiten Sie auf eine Zeichenfolge mit einer Größe von mindestens 0 ab, und da nein $V$-Regel mit einer RHS in ${Prod}^*$ gewählt wurde, leiten sie sich an terminalen Strings ab, deren Länge mindestens gleich ist $|\sigma(\gamma)|$. Daher mit der Regel$U\rightarrow\beta$, $U$ leitet sich von einer Terminalzeichenfolge ab, deren Länge mindestens gleich ist $|\sigma(\gamma)|$. $\blacksquare$

Eine einfache Lösung

Wenn Sie sich nicht zu sehr für die Anzahl der Zeichenfolgen interessieren, gibt es eine einfache Lösung. Grundsätzlich generieren wir für jede Produktion einen String, der diese Produktion abdeckt.

Wie machen wir das? Es ist ein einfacher Arbeitslistenalgorithmus. Angenommen, wir möchten die Produktion abdecken$A ::= BCx$. Grundsätzlich führen wir die Breitensuche ab dem Start ohne Terminal durch$S$ um eine Ableitung zu finden, die das Nicht-Terminal enthält $A$ auf der rechten Seite: Anfangs sind alle Nicht-Terminals nicht markiert, und der Satz erreichbarer Nicht-Terminals ist $\{S\}$;; In jeder Iteration wählen wir beispielsweise ein nicht markiertes erreichbares Nicht-Terminal aus$X$und für jede Produktion mit $X$ Auf der linken Seite fügen wir alle Nicht-Terminals auf der rechten Seite zu den erreichbaren Terminals hinzu und markieren sie $X$. Wiederholen, bis dieser Vorgang dies findet$A$ist erreichbar. Wenn dies der Fall ist, erhalten Sie durch Zurückverfolgen eine Ableitung des Formulars$S \to \cdots A \cdots$. Sie können dies auf eine Ableitung des Formulars erweitern$S \to \cdots A \cdots \to \cdots BCx \cdots$.

Als nächstes müssen wir die Ableitung abschließen, indem wir einen Weg wählen, um sie so zu vervollständigen, dass sie alle Nicht-Terminals sind. Das ist auch einfach. Für jedes Nicht-Terminal finden wir die kürzeste Zeichenfolge in der Sprache, die von diesen Nicht-Terminals generiert wird. Dies kann durch eine Arbeitslisteniteration erreicht werden. Lassen$\ell(A)$ bezeichnen die Länge der kürzesten Zeichenfolge, die wir bisher in der von generierten Sprache gefunden haben $A$. Zunächst setzen wir$\ell(A)=\infty$ für alle Nicht-Terminals $A$, es sei denn, es gibt eine Produktion $A ::= xyz$wobei alle Symbole auf der rechten Seite Terminals sind; In diesem Fall setzen wir$\ell(A)$ entsprechend (z. $\ell(A)=3$ wenn die Produktion uns das sagt $xyz$ ist in $L(A)$). Jetzt suchen wir iterativ nach einer Möglichkeit, eine kürzere Zeichenfolge zu finden. Wenn Sie eine Produktion wie haben$A ::= xBCy$, Du weißt, dass $\ell(A) \le 2 + \ell(B) + \ell(C)$;; So finden Sie jedes Mal eine neue kürzere Zeichenfolge in$L(B)$ oder $L(C)$ (dh jedes Mal, wenn Sie aktualisieren $\ell(B)$ oder $\ell(C)$ um kleiner zu sein) können Sie überprüfen, ob Sie dadurch eine neue kürzere Zeichenfolge erhalten $L(A)$und wenn ja, reduzieren Sie den Wert von $\ell(A)$... was wiederum andere kaskadierende Änderungen verursachen kann. Wenden Sie alle kaskadierenden Änderungen so lange an, bis keine weiteren Änderungen mehr ausgelöst werden. Zu diesem Zeitpunkt haben Sie einen festen Punkt erreicht, und durch Zurückverfolgen kennen Sie für jedes Nicht-Terminal die kürzeste Zeichenfolge (von Terminals), die von diesem Nicht-Terminal abgeleitet werden kann.

Nun, angesichts Ihrer Ableitung des Formulars $S \to \cdots BCx \cdots$, finden Sie einen Weg, um die Ableitung abzuschließen: Ersetzen Sie jedes Nicht-Terminal in $\cdots BCx \cdots$ mit der kürzesten Zeichenfolge (von Terminals), die daraus abgeleitet werden kann.

Dies gibt Ihnen eine Reihe (von Terminals), die die Produktion abdeckt $A ::= BCx$. Tun Sie dies einmal für jede Produktion, bis alle abgedeckt sind.

Die Anzahl der Saiten entspricht der Anzahl der Produktionen. Die Laufzeit ist quadratisch: Der Prozess ist für jede Produktion linear. (Sie könnten es wahrscheinlich insgesamt auf einen linearen Zeitalgorithmus reduzieren, aber ich vermute, dass dies in der Praxis gut genug ist.)

Optimierungen

Wenn Sie die Anzahl der Zeichenfolgen reduzieren möchten, stellen Sie möglicherweise fest, dass jede Zeichenfolge normalerweise viele Produktionen abdeckt, sodass wahrscheinlich eine Teilmenge dieser Zeichenfolgen ausreicht.

Es gibt viele Möglichkeiten, die Anzahl der Zeichenfolgen zu verringern. Eine einfache Möglichkeit besteht darin, den Standardalgorithmus für die gierige Approximation für die Set-Abdeckung zu verwenden. Generieren Sie zunächst alle oben genannten Zeichenfolgen, eine für jede Produktion, und zählen Sie, wie viele Produktionen jede Zeichenfolge abdeckt. Behalten Sie die Saite, die die meisten Produktionen abdeckt. das, was Sie definitiv wollen, also fügen Sie es Ihren Bewahrern hinzu. Jetzt werden einige der Produktionen von diesem Keeper abgedeckt, sodass wir keine neuen Streicher benötigen, die sie erneut abdecken. Daher sollten Sie Ihre Anzahl für jede Zeichenfolge aktualisieren: für Zeichenfolge$s$Zählen Sie die Anzahl der Produktionen, die von abgedeckt werden $s$werden aber von keinem Torhüter abgedeckt. Wählen Sie die Zeichenfolge mit der größten Anzahl aus, fügen Sie sie Ihrer Gruppe von Keepern hinzu und aktualisieren Sie die Anzahl erneut. Wiederholen, bis alle Produktionen abgedeckt sind. Dadurch erhalten Sie wahrscheinlich einen erheblich kleineren Satz von Zeichenfolgen, die alle Produktionen in Ihrer Grammatik abdecken.