在Delphi中解析一行最快的方法是什么？

Question

我有一个巨大的文件，我必须逐行解析。速度是至关重要的。一行的

实施例：

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

为gettoken被调用时，返回“在这里-是最下一页令牌”，并设置CurrentPosition到令牌的最后一个字符的位置以便为下一次调用GetToken做好准备。令牌由一个或多个空格分隔。

假设文件已经在内存中的StringList中。它很容易适应内存，比如说200 MB。

我只担心解析的执行时间。什么代码会在Delphi（Pascal）中产生绝对最快的执行？

Answer 1

• 使用PChar类型递增处理
• 的速度。如果不需要一些标记，仅在需要
• 复制PChar类型复制令牌数据到本地变量时，实际上是通过文字扫描
• 保留源数据中除非您必须逐行处理，并且即使如此，也应考虑将行处理作为词法分析识别器中的单独标记进行处理。
• 如果您确实知道编码，请考虑处理直接来自文件的字节数组缓冲区;如果使用Delphi 2009，请使用PAnsiChar代替PChar，除非您知道编码是UTF16-LE。
• 如果您知道唯一的空格将是＃32（ASCII空间）或类似的有限字符集，可能会有一些巧妙的位操作入侵，可以让您一次处理4个字节使用整数扫描。尽管如此，我不希望大胜，而且代码将像泥巴一样清晰。

下面是一个样例词法分析器，它应该非常高效，但它假定所有源数据都在单个字符串中。由于非常长的令牌，重新处理它以处理缓冲区是非常棘手的。

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

滚动你自己是确保最快的方法。有关此主题的更多信息，您可以看到Synedit's source code，其中包含市场上任何语言的词法分析器（称为项目上下文中的荧光笔）。我建议你以这些词法分析器中的一个作为基础，并根据自己的用法进行修改。

Answer 3

我做了一个基于状态引擎（DFA）的词法分析器。它适用于一张桌子，速度相当快。但有可能更快的选择。

它也取决于语言。一个简单的语言可能会有一个智能算法。

该表是一个记录数组，每个记录包含2个字符和1个整数。对于每个令牌，词法分析器遍历表，从位置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; 

它很简单，像魅力一样工作。

Answer 4

我认为最大的瓶颈总是将文件存入内存。一旦你把它放在内存中（显然不是全部，但如果我是你，我会用缓冲区），实际的解析应该是微不足道的。

Answer 5

最快的方法写代码可能会创建一个TStringList并将您的文本文件中的每一行分配给CommaText属性。默认情况下，空格是一个分隔符，因此每个标记将获得一个StringList项目。

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

不过，您可能会通过自己解析每一行来获得更好的性能。

Answer 6

这是一个非常简单的词法分析器的蹩脚屁股实现。这可能会给你一个想法。

请注意此示例的局限性 - 不涉及缓冲区，无Unicode（这是Delphi 7项目的摘录）。你可能需要那些认真的实施。

{ 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

这引出了另一个问题 - 有多大？ 给我们一些线索，如＃行或＃或Mb（Gb）？然后我们会知道它是否适合内存，需要基于磁盘等。

第一遍我会用我的WordList（S：String; AList：TStringlist）;

然后你可以访问每个令牌作为Alist [n] ... 或排序他们或任何。

Answer 8

速度总是与您在解析之后所做的相关。到目前为止，词法分析器是从文本流转换为令牌的最快方法，无论大小如何。班级中的TParser是一个很好的开始。

就我个人而言，我需要编写一个解析器，但另一个更为过时的尝试和真正的方法是使用LEX/YACC构建语法，然后将语法转换为可用于执行的代码你的处理。 DYacc是一个德尔福版本...不知道它是否仍然编译，但值得一看，如果你想做旧事的东西。如果你能找到一份副本，这里的dragon book会有很大的帮助。

Answer 9

如果速度至关重要，自定义代码就是答案。查看将您的文件映射到内存的Windows API。然后，您可以使用指向下一个角色的指针来执行您的令牌，并根据需要前进。

这是我做的映射代码：

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;