Macchina virtuale da espressione regolare

Question

Ho letto Regular Expression Matching: the Virtual Machine Approach e ora provo ad analizzare un'espressione regolare e creare una macchina virtuale da esso. Il tokenizer funziona e crea i token. Dopo questo passo, creo la notazione polacca inversa dal flusso di token così alla fine ho

a b c | | 

dall'espressione regolare a|(b|c). Bene, ora il passo dove ho attaccato: Voglio ottenere un 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 

dal flusso sopra. E non ho capito bene ... Io uso un array di output e uno stack per le posizioni iniziali di ciascun token. In primo luogo, i 3 valori vengono aggiunti all'output (e sono le posizioni iniziali nello stack).

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

Con |, ho pop le ultime 2 posizioni dalla pila e inserire split e jump nelle posizioni specifiche. I valori sono calcolati in base alla lunghezza della pila corrente e alla quantità di elementi che aggiungo. Alla fine, aggiungo la nuova posizione iniziale dell'ultimo elemento allo stack (rimane lo stesso in questo caso).

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

Sembra ok. Ora, il prossimo | viene estratto ...

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' 

Ed ecco il problema. Devo aggiornare tutti gli indirizzi che ho calcolato prima (righe 3 e 5). Non è quello che voglio. Suppongo che gli indirizzi relativi abbiano lo stesso problema (almeno se i valori sono negativi).

Quindi la mia domanda è, come creare un vm da regex. Sono sulla strada giusta (con il modulo rpn) o c'è un altro (e/o più semplice) modo?

L'array di output viene archiviato come array di numeri interi. Il split -command ha bisogno in realtà 3 voci, jump ha bisogno di due, ...

Answer 1

Penso che invece di impostare l'indirizzo durante la lavorazione, è possibile memorizzare un di riferimento al comando a cui si desidera passare, e nell'array di output memorizzi anche i riferimenti (o puntatori). Al termine dell'elaborazione, si procede lungo l'output generato e si assegnano gli indici in base alla posizione effettiva del comando di riferimento nell'array risultante.

Answer 2

RPN non è il modo migliore per creare l'output necessario. Se invece hai creato un AST, sarebbe facile generare i codici con un attraversamento ricorsivo.

Diciamo che hai un nodo OR, ad esempio, con due bambini "sinistra" e "destra". Ogni nodo implementa un metodo generate(OutputBuffer), e l'implementazione di un nodo o sarebbe simile a questa:

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 
}