Analisi veloce dei file di codice

Question

Ho scritto un parser abbastanza complesso per un linguaggio basato sullo stack che carica un file in memoria e quindi procede confrontando i token per vedere se è riconosciuto come operando o istruzione.

Ogni volta che devo analizzare un nuovo operando/istruzioni I std::copy la memoria dal buffer file a un std::string e poi fare un `

if(parsed_string.compare("add") == 0) { /* handle multiplication */} 
else if(parsed_string.compare("sub") == 0) { /* handle subtraction */ } 
else { /* This is an operand */ } 

purtroppo tutte queste copie stanno facendo il parsing lento.

Come devo gestirlo per evitare tutte queste copie? Ho sempre pensato di non aver bisogno di un tokenizer dal linguaggio stesso e la logica è piuttosto semplice.

Edit: sto aggiungendo il codice in cui ottengo le copie per i vari operandi e le istruzioni

// This function accounts for 70% of the total time of the program 
    std::string Parser::read_as_string(size_t start, size_t end) { 

    std::vector<char> file_memory(end - start); 
    read_range(start, end - start, file_memory); 
    std::string result(file_memory.data(), file_memory.size()); 
    return std::move(result); // Intended to be consumed 
    } 

    void Parser::read_range(size_t start, size_t size, std::string& destination) { 

    if (destination.size() < size) 
     destination.resize(size); // Allocate necessary space 

    std::copy(file_in_memory.begin() + start, 
     file_in_memory.begin() + start + size, 
     destination.begin()); 
    } 

Answer 1

Questa copia non è necessario. Puoi operare su fette.

struct StrSlice { 
    StrSlice(const std::string& embracingStr, std::size_t startIx, std::size_t length) 
    : begin_(/* todo */), end_(/* todo */) // Assign begin_ and end_ here 
    {} 

    StrSlice(const char* begin, const char* end) 
    : begin_(begin), end_(end) 
    {} 
    // Define some more constructors 
    // Be careful about implicit conversions 
    //... 

    //Define lots of comparasion routines with other strings here 
    bool operator==(const char* str) const { 
    ... 
    } 

    bool operator==(const StrSlice& str) const { 
    ... 
    } 

    // You can take slice of a slice in O(1) time 
    StrSlice subslice(std::size_t startIx, std::size_t length) { 
    assert(/* do some range checks here */); 
    const char* subsliceBegin = begin_ + startIx; 
    const char* subsliceEnd = subsliceBegin + length; 
    return StrSlice(subsliceBegin, subsliceEnd); 
    } 
private: 
    const char* begin_; 
    const char* end_; 
}; 

Spero che tu abbia l'idea. Naturalmente, questa sezione si interromperà dopo ogni cambiamento nella stringa associata, specialmente la riallocazione della memoria. Ma sembra che la tua stringa non cambierà se non leggi un nuovo file.

Answer 2

È probabile non solo la copia ma anche la cascata di confronti tra stringhe (supponendo che tu abbia più delle due istruzioni che hai mostrato).

Si potrebbe provare una tabella di ricerca (come std :: map o std :: unordered_map) che converte le istruzioni in un tipo enum che si accende. Così, invece di:

if(parsed_string.compare("add") == 0) { /* handle multiplication */} 
else if(parsed_string.compare("sub") == 0) { /* handle subtraction */ } 
... 
else { /* This is an operand */ } 

Faresti:

const auto it = keywords.find(parsed_string); 
if (it != keywords.end()) { 
    switch (it->second) { 
    case kAdd: // handle addition 
    case kSub: // handle subtraction 
    ... 
    } 
} else { 
    // handle operand 
} 

Se ci sono più di alcune parole chiave, questo si tradurrà in molti meno confronti di stringhe, a quel punto le copie non può essere che grande di un affare. E se lo sono, questo suggerimento può essere usato insieme ad altri che usano "fette" o "viste" nei dati reali per evitare la copia.

Answer 3

ne dite di questo:

std :: string Parser :: read_as_string (size_t inizio, fine size_t)
{
      ritorno file_in_memory.substr (inizio, fine);
}

La funzione "read_as_string" non fa altro che lo standard "substr", tranne in testa ...

Answer 4

Confrontando il prefisso del vapore di ingresso contro le stringhe costanti per parole chiave è semplice da codice, ma certamente isn essere veloce; se hai N parole chiave, farai O (N) string confronti. Se le stringhe hanno lunghezza media, L, farai O (N * L) caratteri confronti. E tali confronti non ti permetteranno di raccogliere numeri, identificatori o stringhe letterali, per i quali non puoi semplicemente confrontare una stringa costante. (E copiare il prefisso come il tuo esempio sembra fare non aiuta).

Quello che dovresti considerare è costruire una macchina a stati finiti per implementare il tuo lexer. Questa è la la soluzione utilizzata da praticamente ogni parser/compilatore di produzione sul pianeta, perché tendono ad essere molto veloci. Gli FSA ben progettati eseguiranno una ricerca a singolo carattere per carattere della stringa di input; è abbastanza difficile da battere.

È possibile produrre manualmente tale FSA oppure è possibile utilizzare uno strumento.

Vedere http://en.wikipedia.org/wiki/Lexical_analysis per lo sfondo di base, e elenco specifico di generatori di lexer generici.