Cách nhanh nhất để phân tích cú pháp một dòng trong Delphi là gì?

Question

Tôi có một tệp lớn mà tôi phải phân tích từng dòng một. Tốc độ là bản chất.

Ví dụ về một dòng:

Token-1 Here-is-the-Next-Token  Last-Token-on-Line 
    ^     ^
    Current     Position 
    Position    after GetToken 

GetToken được gọi, trở về "Đây-là-the-Next-Mã" và đặt CurrentPosition đến vị trí của ký tự cuối cùng của thẻ để nó sẵn sàng cho cuộc gọi tiếp theo tới GetToken. Các thẻ được phân tách bằng một hoặc nhiều khoảng trắng.

Giả sử tệp đã có trong một StringList trong bộ nhớ. Nó phù hợp trong bộ nhớ dễ dàng, nói 200 MB.

Tôi chỉ lo lắng về thời gian thực hiện cho việc phân tích cú pháp. Mã nào sẽ tạo ra thực thi nhanh nhất tuyệt đối trong Delphi (Pascal)?

Answer 1

• Sử dụng PChar incrementing cho tốc độ xử lý
• Nếu một số thẻ không cần thiết, chỉ sao chép dữ liệu thẻ theo yêu cầu
• Sao chép PChar để biến địa phương khi thực sự quét qua các nhân vật
• Giữ nguồn dữ liệu trong một đệm đơn trừ khi bạn phải xử lý từng dòng, và thậm chí sau đó, xem xét xử lý xử lý dòng dưới dạng mã thông báo riêng biệt trong trình nhận dạng lexer
• Xem xét xử lý bộ đệm mảng byte đã đi thẳng từ tệp, nếu bạn chắc chắn biết mã hóa; nếu sử dụng Delphi 2009, hãy sử dụng PAnsiChar thay vì PChar, trừ khi tất nhiên bạn biết mã hóa là UTF16-LE.
• Nếu bạn biết rằng khoảng trống duy nhất sẽ là # 32 (không gian ASCII) hoặc một số ký tự giới hạn tương tự, có thể có một số thao tác bit thông minh có thể cho phép bạn xử lý 4 byte cùng một lúc bằng cách sử dụng tính năng quét số nguyên . Tôi sẽ không mong đợi chiến thắng lớn ở đây mặc dù, và mã sẽ được rõ ràng như bùn.

Dưới đây là một lexer mẫu phải khá hiệu quả, nhưng nó giả định rằng tất cả dữ liệu nguồn nằm trong một chuỗi. Reworking nó để xử lý bộ đệm là vừa phải khó khăn do thẻ rất dài.

type 
    TLexer = class 
    private 
    FData: string; 
    FTokenStart: PChar; 
    FCurrPos: PChar; 
    function GetCurrentToken: string; 
    public 
    constructor Create(const AData: string); 
    function GetNextToken: Boolean; 
    property CurrentToken: string read GetCurrentToken; 
    end; 

{ TLexer } 

constructor TLexer.Create(const AData: string); 
begin 
    FData := AData; 
    FCurrPos := PChar(FData); 
end; 

function TLexer.GetCurrentToken: string; 
begin 
    SetString(Result, FTokenStart, FCurrPos - FTokenStart); 
end; 

function TLexer.GetNextToken: Boolean; 
var 
    cp: PChar; 
begin 
    cp := FCurrPos; // copy to local to permit register allocation 

    // skip whitespace; this test could be converted to an unsigned int 
    // subtraction and compare for only a single branch 
    while (cp^ > #0) and (cp^ <= #32) do 
    Inc(cp); 

    // using null terminater for end of file 
    Result := cp^ <> #0; 

    if Result then 
    begin 
    FTokenStart := cp; 
    Inc(cp); 
    while cp^ > #32 do 
     Inc(cp); 
    end; 

    FCurrPos := cp; 
end; 

Answer 2

Lăn của riêng bạn là cách nhanh nhất để chắc chắn. Để biết thêm về chủ đề này, bạn có thể thấy Synedit's source code chứa các từ vựng (được gọi là tô sáng trong ngữ cảnh của dự án) cho bất kỳ ngôn ngữ nào trên thị trường. Tôi đề nghị bạn lấy một trong những lexers như là một cơ sở và sửa đổi cho việc sử dụng của riêng bạn.

Answer 3

Tôi đã thực hiện một máy phân tích từ vựng dựa trên công cụ trạng thái (DFA). Nó hoạt động với một cái bàn và khá nhanh. Nhưng có thể lựa chọn nhanh hơn.

Nó cũng phụ thuộc vào ngôn ngữ. Một ngôn ngữ đơn giản có thể có một thuật toán thông minh.

Bảng là một mảng bản ghi chứa 2 ký tự và 1 số nguyên. Đối với mỗi mã thông báo, người lexer đi qua bàn, bắt đầu tại vị trí 0:

state := 0; 
result := tkNoToken; 
while (result = tkNoToken) do begin 
    if table[state].c1 > table[state].c2 then 
    result := table[state].value 
    else if (table[state].c1 <= c) and (c <= table[state].c2) then begin 
    c := GetNextChar(); 
    state := table[state].value; 
    end else 
    Inc(state); 
end; 

Nó đơn giản và hoạt động như một sự quyến rũ.

Answer 4

Tôi nghĩ rằng nút cổ chai lớn nhất luôn là đưa tệp vào bộ nhớ. Một khi bạn có nó trong bộ nhớ (rõ ràng không phải tất cả cùng một lúc, nhưng tôi sẽ làm việc với bộ đệm nếu tôi là bạn), việc phân tích cú pháp thực tế sẽ không đáng kể.

Answer 5

Cách nhanh nhất để viết mã có thể là tạo TStringList và gán mỗi dòng trong tệp văn bản của bạn vào thuộc tính CommaText. Theo mặc định, khoảng trắng là dấu phân cách, vì vậy bạn sẽ nhận được một mục StringList cho mỗi mã thông báo.

MyStringList.CommaText := s; 
for i := 0 to MyStringList.Count - 1 do 
begin 
    // process each token here 
end; 

Có thể bạn sẽ nhận được hiệu suất tốt hơn bằng cách phân tích cú pháp từng dòng.

Answer 6

Dưới đây là một thực thi ass lame của một lexer rất đơn giản. Điều này có thể cung cấp cho bạn một ý tưởng.

Lưu ý các giới hạn của ví dụ này - không có đệm liên quan, không có Unicode (đây là trích đoạn từ dự án Delphi 7). Bạn có lẽ sẽ cần những người trong một thực hiện nghiêm túc.

{ Implements a simpe lexer class. } 
unit Simplelexer; 

interface 

uses Classes, Sysutils, Types, dialogs; 

type 

    ESimpleLexerFinished = class(Exception) end; 

    TProcTableProc = procedure of object; 

    // A very simple lexer that can handle numbers, words, symbols - no comment handling 
    TSimpleLexer = class(TObject) 
    private 
    FLineNo: Integer; 
    Run: Integer; 
    fOffset: Integer; 
    fRunOffset: Integer; // helper for fOffset 
    fTokenPos: Integer; 
    pSource: PChar; 
    fProcTable: array[#0..#255] of TProcTableProc; 
    fUseSimpleStrings: Boolean; 
    fIgnoreSpaces: Boolean; 
    procedure MakeMethodTables; 
    procedure IdentProc; 
    procedure NewLineProc; 
    procedure NullProc; 
    procedure NumberProc; 
    procedure SpaceProc; 
    procedure SymbolProc; 
    procedure UnknownProc; 
    public 
    constructor Create; 
    destructor Destroy; override; 
    procedure Feed(const S: string); 
    procedure Next; 
    function GetToken: string; 
    function GetLineNo: Integer; 
    function GetOffset: Integer; 

    property IgnoreSpaces: boolean read fIgnoreSpaces write fIgnoreSpaces; 
    property UseSimpleStrings: boolean read fUseSimpleStrings write fUseSimpleStrings; 
    end; 

implementation 

{ TSimpleLexer } 

constructor TSimpleLexer.Create; 
begin 
    makeMethodTables; 
    fUseSimpleStrings := false; 
    fIgnoreSpaces := false; 
end; 

destructor TSimpleLexer.Destroy; 
begin 
    inherited; 
end; 

procedure TSimpleLexer.Feed(const S: string); 
begin 
    Run := 0; 
    FLineNo := 1; 
    FOffset := 1; 
    pSource := PChar(S); 
end; 

procedure TSimpleLexer.Next; 
begin 
    fTokenPos := Run; 
    foffset := Run - frunOffset + 1; 
    fProcTable[pSource[Run]]; 
end; 

function TSimpleLexer.GetToken: string; 
begin 
    SetString(Result, (pSource + fTokenPos), Run - fTokenPos); 
end; 

function TSimpleLexer.GetLineNo: Integer; 
begin 
    Result := FLineNo; 
end; 

function TSimpleLexer.GetOffset: Integer; 
begin 
    Result := foffset; 
end; 

procedure TSimpleLexer.MakeMethodTables; 
var 
    I: Char; 
begin 
    for I := #0 to #255 do 
    case I of 
     '@', '&', '}', '{', ':', ',', ']', '[', '*', 
     '^', ')', '(', ';', '/', '=', '-', '+', '#', '>', '<', '$', 
     '.', '"', #39: 
     fProcTable[I] := SymbolProc; 
     #13, #10: fProcTable[I] := NewLineProc; 
     'A'..'Z', 'a'..'z', '_': fProcTable[I] := IdentProc; 
     #0: fProcTable[I] := NullProc; 
     '0'..'9': fProcTable[I] := NumberProc; 
     #1..#9, #11, #12, #14..#32: fProcTable[I] := SpaceProc; 
    else 
     fProcTable[I] := UnknownProc; 
    end; 
end; 

procedure TSimpleLexer.UnknownProc; 
begin 
    inc(run); 
end; 

procedure TSimpleLexer.SymbolProc; 
begin 
    if fUseSimpleStrings then 
    begin 
    if pSource[run] = '"' then 
    begin 
     Inc(run); 
     while pSource[run] <> '"' do 
     begin 
     Inc(run); 
     if pSource[run] = #0 then 
     begin 
      NullProc; 
     end; 
     end; 
    end; 
    Inc(run); 
    end 
    else 
    inc(run); 
end; 

procedure TSimpleLexer.IdentProc; 
begin 
    while pSource[Run] in ['_', 'A'..'Z', 'a'..'z', '0'..'9'] do 
    Inc(run); 
end; 

procedure TSimpleLexer.NumberProc; 
begin 
    while pSource[run] in ['0'..'9'] do 
    inc(run); 
end; 

procedure TSimpleLexer.SpaceProc; 
begin 
    while pSource[run] in [#1..#9, #11, #12, #14..#32] do 
    inc(run); 
    if fIgnoreSpaces then Next; 
end; 

procedure TSimpleLexer.NewLineProc; 
begin 
    inc(FLineNo); 
    inc(run); 
    case pSource[run - 1] of 
    #13: 
     if pSource[run] = #10 then inc(run); 
    end; 
    foffset := 1; 
    fRunOffset := run; 
end; 

procedure TSimpleLexer.NullProc; 
begin 
    raise ESimpleLexerFinished.Create(''); 
end; 

end. 

Answer 7

Điều này đặt ra một câu hỏi khác - Lớn như thế nào? Hãy cho chúng tôi một đầu mối như # dòng hoặC# hoặc Mb (Gb)? Sau đó, chúng tôi sẽ biết nếu nó phù hợp trong bộ nhớ, cần phải được dựa trên đĩa vv

Lúc đầu, tôi sẽ sử dụng WordList của tôi (S: String; AList: TStringlist);

thì bạn có thể truy cập từng mã thông báo là Alist [n] ... hoặc sắp xếp chúng hoặc bất kỳ thứ gì.

Answer 8

Tốc độ sẽ luôn liên quan đến những gì bạn đang làm khi phân tích cú pháp. Trình phân tích cú pháp từ vựng cho đến nay là phương pháp nhanh nhất để chuyển đổi thành mã thông báo từ luồng văn bản bất kể kích thước. TParser trong đơn vị lớp học là một nơi tuyệt vời để bắt đầu.

Cá nhân đã được một thời gian kể từ khi tôi cần viết một trình phân tích cú pháp, nhưng một phương pháp khác đã được thử nghiệm và đúng hơn sẽ là sử dụng LEX/YACC để xây dựng ngữ pháp, sau đó chuyển ngữ pháp thành mã bạn có thể sử dụng để thực hiện quá trình xử lý của bạn. DYacc là một phiên bản Delphi ... không chắc chắn nếu nó vẫn biên dịch hay không, nhưng đáng xem nếu bạn muốn làm những điều học cũ. Các dragon book ở đây sẽ được giúp đỡ lớn, nếu bạn có thể tìm thấy một bản sao.

Answer 9

Nếu tốc độ là bản chất, mã tùy chỉnh là câu trả lời. Kiểm tra API Windows sẽ ánh xạ tệp của bạn vào bộ nhớ. Sau đó, bạn có thể chỉ cần sử dụng một con trỏ đến ký tự tiếp theo để thực hiện các mã thông báo, di chuyển qua theo yêu cầu.

Đây là mã của tôi để làm một ánh xạ:

procedure TMyReader.InitialiseMapping(szFilename : string); 
var 
// nError : DWORD; 
    bGood : boolean; 
begin 
    bGood := False; 
    m_hFile := CreateFile(PChar(szFilename), GENERIC_READ, 0, nil, OPEN_EXISTING, 0, 0); 
    if m_hFile <> INVALID_HANDLE_VALUE then 
    begin 
     m_hMap := CreateFileMapping(m_hFile, nil, PAGE_READONLY, 0, 0, nil); 
     if m_hMap <> 0 then 
     begin 
      m_pMemory := MapViewOfFile(m_hMap, FILE_MAP_READ, 0, 0, 0); 
      if m_pMemory <> nil then 
      begin 
       htlArray := Pointer(Integer(m_pMemory) + m_dwDataPosition); 
       bGood := True; 
      end 
      else 
      begin 
//    nError := GetLastError; 
      end; 
     end; 
    end; 
    if not bGood then 
     raise Exception.Create('Unable to map token file into memory'); 
end;