webentwicklung-frage-antwort-db.com.de

Schritte zum Erstellen eines NFA aus einem regulären Ausdruck

Ich habe Probleme, "jeden Schritt zu beschreiben", wenn Sie einen NFA aus einem regulären Ausdruck erstellen. Die Frage lautet wie folgt:

Konvertieren Sie den folgenden regulären Ausdruck in einen nicht deterministischen Automaten (NFA), der die Schritte des verwendeten Algorithmus eindeutig beschreibt: (B | a) * b (a | b)

Ich habe eine einfache 3-Zustandsmaschine erstellt, die aber sehr aus Intuition besteht ... Dies ist eine Frage aus einer früheren Prüfung, die von meinem Dozenten geschrieben wurde, der auch die folgende Erklärung des Algorithmus von Thompson schrieb: http: // www .cs.may.ie/staff/jpower/Kurse/Vorheriges/Parsing/node5.html

Kann irgendjemand klären, wie jeder Schritt eindeutig beschrieben wird? Es scheint nur ein Satz von Grundregeln zu sein, als ein Algorithmus mit Schritten, die zu befolgen sind.

Vielleicht gibt es einen Algorithmus, den ich irgendwo überarbeitet habe, aber bisher habe ich ihn nur mit einer fundierten Vermutung erstellt.

22
kiliki

Kurzfassung für die allgemeine Herangehensweise.
Es gibt ein Algo namens Thompson-McNaughton-Yamada-Konstruktionsalgorithmus oder manchmal auch nur "Thompson-Konstruktion". Man baut dazwischenliegende NFAs auf, füllt die Teile auf und beachtet dabei die Rangfolge der Operatoren: Zuerst Klammern, dann Kleene Star (z. B. a *), dann Verkettung (z. B. ab), gefolgt von Abwechslung (z. B. a | b).

Hier ist eine detaillierte exemplarische Vorgehensweise zum Erstellen der NFA von (b | a) * b (a | b)

Aufbau der obersten Ebene

  1. Behandeln Sie Klammern. Hinweis: In der tatsächlichen Implementierung kann es sinnvoll sein, Klammern über einen rekursiven Aufruf ihres Inhalts zu behandeln. Aus Gründen der Klarheit werde ich die Bewertung von Elementen innerhalb von Parens verschieben.

  2. Kleene-Sterne: nur ein * vorhanden, daher bauen wir eine Platzhalter-Kleene-Stern-Maschine namens P (die später b | a enthalten wird). Zwischenergebnis:
    Non-Deterministic Finite Automata for P*

  3. Verkettung: Fügen Sie P an b und b an einen Platzhalter mit dem Namen Q (der (a | b) enthält). Zwischenergebnis:
    Non-Deterministic Finite Automata for P*bQ

  4. Außerhalb von Klammern gibt es keine Abwechslung, daher überspringen wir diese.

Jetzt sitzen wir auf einer P * bQ-Maschine. (Beachten Sie, dass unsere Platzhalter P und Q nur Verkettungsmaschinen sind.) Wir ersetzen die P-Kante durch die NFA für b | a und die Q-Kante durch die NFA für a | b durch rekursive Anwendung der obigen Schritte.


Gebäude P

  1. Überspringen. Keine Eltern.

  2. Überspringen. Keine Kleene-Sterne.

  3. Überspringen. Keine Verkettung.

  4. Bauen Sie die Wechselmaschine für b | a. Zwischenergebnis:
    NFA for b or a


Integration von P

Als nächstes kehren wir zu dieser P * bQ-Maschine zurück und reißen die P-Kante heraus. Wir haben die Quelle der P-Kante als Startzustand für die P-Maschine und das Ziel der P-Kante als Zielstatus für die P-Maschine. Wir lassen diesen Staat auch ablehnen (nehmen ihm das Eigentum, ein akzeptierter Staat zu sein). Das Ergebnis sieht so aus:
enter image description here


Gebäude Q

  1. Überspringen. Keine Eltern.

  2. Überspringen. Keine Kleene-Sterne.

  3. Überspringen. Keine Verkettung.

  4. Baue die Wechselmaschine für a | b. Im Übrigen ist die Abwechslung kommutativ, also ist a | b logisch äquivalent zu b | a. (Lesen Sie: Überspringen dieses kleinen Fußnotendiagramms aus Faulheit.)


Q integrieren

Wir machen das, was wir oben mit P gemacht haben, außer dass wir die Q Edge durch die von uns konstruierte intermedtae b | a Maschine ersetzen. Das ist das Ergebnis:
enter image description here

Tada! Äh, ich meine, QED.


Möchten Sie mehr wissen?

Alle obigen Bilder wurden mit einem Online-Tool zur automatischen Konvertierung regulärer Ausdrücke in nicht deterministische endliche Automaten generiert. Sie finden den Quellcode für den Thompson-McNaughton-Yamada-Konstruktionsalgorithmus online.

Der Algorithmus wird auch in Ahos Compilers: Principles, Techniques and Tools angesprochen, obwohl seine Erklärung kaum Einzelheiten zur Implementierung enthält. Sie können auch aus eine Implementierung der Thompson-Konstruktion in C durch den hervorragenden Russ Cox lernen, der sie in einem beliebten Artikel über Übereinstimmung mit regulären Ausdrücken ausführlich beschrieb.

62
Wayland Smith

Im GitHub-Repository unten finden Sie eine Java-Implementierung von Thompsons Konstruktion, bei der zuerst ein NFA aus dem Regex erstellt wird und dann eine Eingabezeichenfolge mit diesem NFA abgeglichen wird:

https://github.com/meghdadFar/regex

1
MAZDAK

https://github.com/White-White/RegSwift

Keine langweiligen Worte mehr. Schauen Sie sich dieses Repo an, es übersetzt Ihren regulären Ausdruck in eine NFA und zeigt Ihnen visuell die Statusübergänge einer NFA.

0
SomeHowWhite