コードファイルをより速く解析する

Question

ファイルをメモリにロードし、トークンを比較してオペランドや命令として認識されるかどうかを調べる、スタックベースの言語用のかなり複雑なパーサを書きました。

私はstd::stringにファイルバッファからメモリをstd::copyして、残念ながら、これらすべてのコピーがパース遅い作っている `

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

を行い、新たなオペランド/命令を解析する必要がたび。

これらのコピーをすべて避けるにはどうすればよいですか？言語そのものとロジックはかなりシンプルなので、私はいつもトークナイザが必要ないと思っていました。

編集：私はこのコピーは必要ありません様々なオペランドと指示

// 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

のためのコピーを取得コードを追加しています。スライスを操作できます。

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_; 
}; 

私はあなたがそのアイデアを得ることを願っています。もちろん、このスライスは関連する文字列の変更後、特にメモリの再割り当て後に破損します。しかし、新しいファイルを読まない限り、あなたの文字列は変更されていないようです。

Answer 2

コピーだけでなく、文字列比較のカスケード（あなたが示した2つ以上の指示があると仮定します）。

スイッチをオンにする列挙型に命令を変換するルックアップテーブル（std :: mapまたはstd :: unordered_mapのような）を試すとよいでしょう。だから、代わりに：

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

あなたは何だろう：

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 
} 

を超えるいくつかのキーワードがある場合、これはコピーがあることではないかもしれない、その時点ではるかに少ない文字列の比較、になります大規模な取引。もしそうであれば、この提案はコピーを避けるために実際のデータに「スライス」や「ビュー」を使用する他の人と一緒に使うことができます。これについて

Answer 3

方法：

のstd ::文字列パーサ:: read_as_string（、size_tの終わりを開始SIZE_T）
{
     リターンfile_in_memory.substr（開始、終了）。
}

あなたの「read_as_string」機能は、キーワードの定数文字列に対する入力蒸気の接頭辞を比較すると、オーバーヘッドを除いて、標準の「SUBSTR」以外の何物でも、...

Answer 4

コードに簡単ですが、確かにISNもしません速い; N個のキーワードがある場合は、O（N）の文字列を比較します。文字列の平均長さがLの場合、O（N * L）文字のの比較を行います。そのような比較では、数値、識別子、または文字列リテラルを選択することはできません。そのためには、定数文字列を比較するだけではなりません。 （そして、あなたの例が示しているようにプレフィックスをコピーすることは助けになりません）。

あなたが考えるべきことは、あなたのレクサーを実装するための有限状態マシンを構築することです。これは、のソリューションであり、非常に高速になる傾向があるため、地球上のほとんどのプロダクションパーサ/コンパイラが使用しています。 本当にうまく設計されたFSAは、入力文字列の文字ごとに単一の文字検索を行います。それは非常に難しいです。

このようなFSAは、手作業で作成することも、ツールを使用することもできます。

基本的な背景のためにhttp://en.wikipedia.org/wiki/Lexical_analysis、 と広く使用されているユーザのレクサージェネレータの特定のリストを参照してください。