kann der Compiler möglicherweise eine DFA aus einem regulären Ausdruck berechnen?

Question

Beim Modding eines Closed-Source-Spiels modifiziere ich den Maschinencode zur Laufzeit zu jmp in meinen eigenen Code. Um dies auf generische Weise zu tun, verwende ich den Mustervergleich, um die Code-Orte zu finden, die ich ändern möchte. (Die Muster bestehen nur aus Zeichen/Bytes und Platzhaltern, wo Bytes variieren können.) Indem ich einen deterministischen endlichen Automaten aus all meinen Mustern erstelle, kann ich in linearer Zeit suchen.

Allerdings habe ich festgestellt, dass die Erstellung des DFA mehr Zeit in Anspruch nimmt als tatsächlich ausgeführt wird, vor allem in Debug-Builds (die ich während der Entwicklung natürlich will), und das wird nur schlimmer, wenn ich weitere Muster hinzufüge. Aber das könnte offline einfach gemacht werden. Ich denke gerade über das Wie nach; kann der Compiler das tun?

Soweit ich weiß, ist es unmöglich mit constexpr Funktionen, da ich nicht mit ihnen statischen Speicher zuordnen kann. Aber ich habe das vage Gefühl, dass es mit Template-Metaprogrammierung typsicher sein sollte. Oder bin ich wahrscheinlich bei der Erstellung von Automaten mit Hunderten oder Tausenden von Zuständen auf Rekursionslimits gestoßen?

Und unabhängig von technischen Möglichkeiten, ist es sinnvoll? Oder sollte ich lieber eine Quelldatei in einem separaten Build-Schritt berechnen?

Answer 1

Ja, das ist möglich. Die Konstruktion kann mit einem der Standardalgorithmen wie Thompson's construction algorithm durchgeführt werden, um ein NFA zu erhalten und daraus ein DFA zu erstellen. Das Problem ist, dass bei der Umwandlung eines NFA in einen DFA ein exponentieller Anstieg der Anzahl der Zustände möglich ist.

Der Umgang mit der erforderlichen Rekursionstiefe wird in der answers to this question diskutiert.

Es ist möglich, den Algorithmus mithilfe von Template-Metaprogrammierung zu implementieren. Eine Liste der grundlegenden Bausteine ​​finden Sie unter here, in der Sie Werte speichern, Verzweigungen und Funktionen implementieren können. Hier

ist ein Beispiel für eine Funktion aus der linked page:

template<int X, int Y> 
struct Adder 
{ 
    enum { result = X + Y }; 
}; 

Dies ist eine Funktion, die seine beiden Parameter und speichert das Ergebnis in dem Ergebnis enum Element hinzufügt. Sie können dies zur Kompilierzeit mit so etwas wie Adder < 1, 2> :: result aufrufen, was bei kompiliert wird Zeit und genau wie ein Literal 3 in Ihrem Programm handeln.

Seit Thompson-Algorithmus beruht auf Rekursion, hier ein Beispiel für eine Rekursion Bewertung:

template <unsigned n> 
struct factorial 
{ 
    enum { value = n * factorial<n-1>::value }; 
}; 

Dieses eine faktorielle bei der Kompilierung implementiert. Dies könnte dann während der Laufzeit wie folgt verwendet werden factorial<5>::value.