Phân tích cú pháp các tệp mã nhanh hơn

Question

Tôi đã viết một trình phân tích cú pháp khá phức tạp cho một ngôn ngữ dựa trên ngăn xếp để tải một tệp vào bộ nhớ và sau đó tiến hành bằng cách so sánh mã thông báo để xem nó có được công nhận là toán hạng hay hướng dẫn hay không.

Mỗi lần tôi phải phân tích một toán hạng mới/hướng dẫn tôi std::copy bộ nhớ từ bộ đệm tập tin vào một std::string và sau đó làm một '

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

tiếc là tất cả các bản sao này đang làm cho phân tích chậm.

Tôi nên xử lý điều này như thế nào để tránh tất cả các bản sao này? Tôi luôn nghĩ rằng tôi không cần một tokenizer từ ngôn ngữ chính nó và logic là khá đơn giản.

Edit: tôi thêm mã nơi tôi nhận được bản sao cho các toán hạng khác nhau và hướng dẫn

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

sao chép này là không cần thiết. Bạn có thể hoạt động trên các lát cắt.

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

Tôi hy vọng bạn sẽ có ý tưởng. Tất nhiên, slice này sẽ phá vỡ sau bất kỳ thay đổi nào trong chuỗi liên kết, đặc biệt là tái phân bổ bộ nhớ. Nhưng có vẻ như chuỗi của bạn không thay đổi trừ khi bạn đọc một tệp mới.

Answer 2

Đó có thể không chỉ là việc sao chép mà còn là chuỗi các so sánh chuỗi (giả sử bạn có nhiều hơn hai hướng dẫn bạn đã trình bày).

Bạn có thể thử bảng tra cứu (như std :: map hoặc std :: unordered_map) để chuyển đổi hướng dẫn thành loại enum mà bạn bật. Vì vậy, thay vì:

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

Bạn muốn làm:

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 
} 

Nếu có nhiều hơn một vài từ khóa, điều này sẽ dẫn đến sự so sánh chuỗi rất ít, lúc này các bản sao có thể không có lớn của một thỏa thuận. Và nếu có, đề xuất này có thể được sử dụng kết hợp với những người khác sử dụng "lát" hoặc "chế độ xem" vào dữ liệu thực tế để tránh sao chép.

Answer 3

Làm thế nào về điều này:

std :: string Parser :: read_as_string (size_t bắt đầu, kết thúc size_t)
{
      trở file_in_memory.substr (bắt đầu, kết thúc);
}

của bạn "read_as_string" chức năng không gì hơn là tiêu chuẩn "substr", trừ chi phí ...

Answer 4

So sánh tiền tố của của hơi nước đầu vào đối với các hằng xâu cho các từ khóa rất đơn giản để mã nhưng chắc chắn isn không nhanh; nếu bạn có N từ khóa, bạn sẽ thực hiện so sánh O (N) chuỗi. Nếu các chuỗi có độ dài trung bình, L, bạn sẽ thực hiện so sánh O (N * L) ký tự. Và những so sánh như vậy sẽ không cho phép bạn nhận số, số nhận dạng hoặc chuỗi ký tự, mà bạn không thể chỉ so sánh chuỗi không đổi. (Và sao chép tiền tố như ví dụ của bạn dường như không giúp ích gì).

Điều bạn nên làm là xây dựng một máy hữu hạn dựa trên trạng thái để thực hiện lexer của bạn. Đây là giải pháp được sử dụng bởi hầu như mọi trình phân tích cú pháp/trình biên dịch sản xuất trên hành tinh, bởi vì chúng có xu hướng rất nhanh. FSA thực sự được thiết kế tốt sẽ thực hiện tra cứu ký tự đơn cho mỗi ký tự của chuỗi đầu vào; đó là khá khó để đánh bại.

Bạn có thể tạo FSA như vậy bằng tay hoặc bạn có thể sử dụng công cụ.

Xem http://en.wikipedia.org/wiki/Lexical_analysis cho nền cơ bản, và danh sách cụ thể về máy phát lexer người dùng rộng rãi.