NFA DFA und Regex nach Transition Tabelle

Ich habe nach einem Algorithmus Ausschau gehalten, der einen regulären Ausdruck oder eine Zeichenkette eingibt und diese in ein NFA und dann ein DFA konvertiert, und das würde tatsächlich die Übergangstabelle von ausgeben das entsprechende finale DFA.NFA DFA und Regex nach Transition Tabelle

Ich frage mich also, ob es bereits einen Algorithmus oder C oder Python-Bibliothek, die das tut, oder wenn Sie Vorschläge für Algorithmen haben, die ich implementieren könnte.

Vielen Dank.

Quelle

2013-10-20 Anoracx

Wie geschrieben, ist Ihre Frage ein bisschen zu weit/subjektiv zu beantworten: Sie fragen, ob Sie es selbst codieren sollten oder ob es eine vorhandene Bibliothek gibt. Fragen dieser Formulare sind hier auf Stack Overflow nicht wirklich angebracht. Könnten Sie Ihre Frage aktualisieren, um etwas Konkreteres zu haben, zum Beispiel "Wie verwende ich Bibliothek X, um dieses Problem zu lösen?" oder "welcher Algorithmus wäre hier am besten geeignet?" – templatetypedef

Nun, ich fragte, ob es eine vorhandene Bibliothek gibt, oder ob ich es von Grund auf implementieren sollte, oder (und deshalb erwähnte ich den Thomson) Wenn jemand einen Algorithmus kennt, den ich implementieren könnte. Aber ich habe ein bisschen die Frage geändert, ich hoffe, es ist klarer. – Anoracx

http://projectsgeek.com/2011/05/regular-expression-to-dfa-code-in-c-language.html –

Ich bin nicht sicher, ob einer dieser Links Ihnen helfen könnte.

Die ersten bieten eine sehr einfache NFA/DFA-Implementierung in Python mit Konvertierung von NFA nach DFA. Es erzeugt zwar nicht die NFA aus einer Regex, aber es ist nicht so schwierig zu tun. Die zweite Seite bietet eine lange Diskussion über NFA gegenüber DFA, einschließlich zahlreicher Codebeispiele (hauptsächlich in C) und Links zu externen Bibliotheken, von denen ich wenig weiß. Der dritte und der vierte Link stellen den Quellcode von zwei Regex-Engine-Implementierungen bereit, die vom Autor des zweiten Artikels entwickelt wurden, einschließlich der Analyse von Regex nach NFA und dann die Konvertierung von NFA nach DFA. Beachten Sie jedoch, dass ich mir keines dieser Projekte angesehen habe.

Ansonsten würde ich erwähnen, dass die meisten realen Welt regex Motoren NFA verwenden, nicht DFA, weil einige erweiterte Funktionen, die einfach nicht mit einem DFA durchgeführt werden. Wenn also keiner der obigen Links Ihnen helfen kann, dann haben Sie vielleicht etwas Glück, wenn Sie sich Compiler-Compiler ansehen, da sie diejenigen sind, die tatsächlich DFAs verwenden.

Quelle

2013-10-24 21:47:17 jwatkins

Danke für die Hilfe, aber leider habe ich die Links nach oben geschaut und konnte keinen der Algorithmen finden, der die Statustabelle des entsprechenden finalen DFA ausdruckt. – Anoracx

Sie können die Übergangstabelle nicht bereits drucken _, aber das Extrahieren aus dem endgültigen berechneten DFA ist einfach genug ... Sie müssen lediglich über jeden Knoten gehen und ihm eine eindeutige sequenzielle Kennung zuweisen. Gehen Sie dann erneut über das Diagramm und geben Sie diese Knoten-ID aus, die Liste der möglichen Übergänge mit der ID des Nachfolgerknotens für jeden Übergang. Die Berechnung des DFA in Strukturen, die Sie untersuchen können, ist wirklich der schwierigere Teil. – jwatkins

NFA DFA und Regex nach Transition Tabelle

Antwort

Verwandte Themen