Virtuelle Maschine von regulärem Ausdruck

Question

Ich lese Regular Expression Matching: the Virtual Machine Approach und jetzt versuche ich, einen regulären Ausdruck zu analysieren und eine virtuelle Maschine daraus zu erstellen. Der Tokenizer funktioniert und erstellt seine Token. Nach diesem Schritt schaff' ich die umgekehrte polnische Notation aus dem Token Strom so am Ende ich

a b c | | 

aus dem regulären Ausdruck a|(b|c) bekommen. Nun, jetzt der Schritt, wo ich fest: Ich möchte ein Array

0: split 1, 3 
1: match 'a' 
2: jump 7 
3: split 4, 6 
4: match 'b' 
5: jump 7 
6: match 'c' 
7: noop 

aus dem Stream oben zu bekommen. Und ich habe es nicht richtig verstanden ... Ich benutze ein Ausgabefeld und einen Stapel für die Startpositionen jedes Tokens. Zuerst werden die 3 Werte zum Ausgang hinzugefügt (und es sind Startpositionen zum Stapel).

output    stack 
------------------- ------ 
0: match 'a'  0: 0 
1: match 'b'  1: 1 
2: match 'c'  2: 2 

Mit |, Pop ich die letzten zwei Positionen aus dem Stapel und lege split und jump an den spezifischen Positionen. Die Werte werden basierend auf der aktuellen Stapellänge und der Anzahl der hinzugefügten Elemente berechnet. Am Ende füge ich dem Stack die neue Startposition des letzten Elements hinzu (bleibt in diesem Fall gleich).

output    stack 
------------------- ------ 
0: match 'a'  0: 0 
1: split 2, 4  1: 1 
2: match 'b' 
3: jump 5 
4: match 'c' 

Das scheint in Ordnung. Nun wird die nächste | geknallt ...

output    stack 
------------------- ------ 
0: split 1, 3  0: 0 
1: match 'a' 
2: jump 7 
3: split 2, 4 
4: match 'b' 
5: jump 5 
6: match 'c' 

Und hier ist das Problem. Ich muss alle Adressen aktualisieren, die ich vorher berechnet habe (Zeilen 3 und 5). Das will ich nicht. Ich denke, relative Adressen haben das gleiche Problem (zumindest wenn die Werte negativ sind).

Also meine Frage ist, wie man eine vm aus Regex erstellen. Bin ich auf dem richtigen Weg (mit der RPN-Form) oder gibt es einen anderen (und/oder leichteren) Weg?

Das Ausgabearray wird als Integer-Array gespeichert. Die split -command muss in der Tat 3 Einträge, braucht jump zwei, ...

Answer 1

Ich denke, dass anstelle Adresse während der Verarbeitung des Setzens Sie eine Referenz auf den Befehl speichern, zu der Sie springen möchten, und Im Ausgabe-Array speichern Sie auch die Referenzen (oder Zeiger). Nachdem die gesamte Verarbeitung abgeschlossen ist, fahren Sie mit der generierten Ausgabe fort und weisen die Indizes basierend auf der tatsächlichen Position des referenzierten Befehls im resultierenden Array zu.

Answer 2

RPN ist nicht der beste Weg, um die Ausgabe aufzubauen, die Sie benötigen. Wenn Sie stattdessen einen AST erstellen, wäre es einfach, die Codes mit einer rekursiven Traversierung zu erzeugen.

Nehmen wir an, Sie hatten einen OR-Knoten, zum Beispiel mit zwei Kindern "links" und "rechts". Jeder Knoten implementiert ein Verfahren generate(OutputBuffer), und die Implementierung für einen ODER-Knoten würde wie folgt aussehen:

void generate(OutputBuffer out) 
{ 
int splitpos = out.length(); 
out.append(SPLIT); 
out.append(splitpos+3); //L1 
out.append(0); //reservation 1 
//L1 
left.generate(out); 
int jumppos = out.length(); 
out.append("JUMP"); 
out.append(0); //reservation 2 
//L2 
out.set(splitpos+2, out.length()); //reservation 1 = L2 
right.generate(out); 
//L3 
out.set(jumppos+1, out.length()); //reservation 2 = L3 
}