il compilatore può calcolare facilmente un DFA da un'espressione regolare?

Question

Nel modding di un gioco a codice chiuso sto modificando il codice macchina in fase di esecuzione su jmp nel mio codice. Per fare questo in modo generico sto usando la corrispondenza dei modelli per trovare le posizioni del codice che voglio modificare. (I pattern consistono solo di caratteri/byte e caratteri jolly in cui i byte possono variare.) Costruendo un automa finito deterministico da tutti i miei schemi posso cercare in tempo lineare.

Tuttavia, ho scoperto che la creazione di DFA richiede più tempo rispetto all'esecuzione effettiva, in particolare nelle build di debug (che sicuramente desidero durante lo sviluppo) e peggiorerà solo quando aggiungo altri pattern. Ma questo potrebbe facilmente essere fatto offline. Attualmente sto pensando al come; può farlo il compilatore?

Per quanto ne so è impossibile con le funzioni constexpr poiché non posso allocare memoria statica con esse. Ma ho la vaga sensazione che dovrebbe essere fattibile in un modo sicuro dal tipo con la meta-programmazione modello. O sono propenso a incorrere in limiti di ricorsione nella creazione di automi con centinaia o migliaia di stati?

E indipendentemente dalle possibilità tecniche, è ragionevole? O dovrei piuttosto, per esempio, calcolare un file sorgente in una fase di compilazione separata?

Answer 1

Sì, questo è possibile. La costruzione può essere eseguita con uno degli algoritmi standard come Thompson's construction algorithm per ottenere un NFA e quindi creare un DFA da quello. Il problema è che quando si converte un NFA in un DFA è possibile un aumento esponenziale del numero di stati.

Come trattare la profondità di ricorsione richiesta è discusso nel answers to this question.

È possibile implementare l'algoritmo utilizzando la metaprogrammazione del modello. È possibile trovare un elenco di blocchi elementari di base here, che consente di memorizzare valori, implementare rami e funzioni.

Ecco un esempio di una funzione dalla linked page:

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

Questa è una funzione che aggiunge i due parametri e memorizza il risultato nell'elemento risultato enum. Puoi chiamare questo al momento della compilazione con qualcosa come Adder < 1, 2> :: result, che sarà espanso al momento della compilazione e agirà esattamente come un letterale 3 nel tuo programma.

Poiché l'algoritmo di Thompson si basa su ricorsione, qui un esempio per la valutazione di una ricorsione:

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

Questo implementa un fattoriale in fase di compilazione. Questo potrebbe quindi essere utilizzato durante il runtime come questo factorial<5>::value.