Delphi에서 한 줄을 구문 분석하는 가장 빠른 방법은 무엇입니까?
https://stackoverflow.com/questions/287789
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
한 줄씩 구문 분석해야 하는 거대한 파일이 있습니다.속도가 핵심입니다.
라인의 예:
Token-1 Here-is-the-Next-Token Last-Token-on-Line ^ ^ Current Position Position after GetToken
GetToken이 호출되어 "Here-is-the-Next-Token"을 반환하고 CurrentPosition을 토큰의 마지막 문자 위치로 설정하여 GetToken에 대한 다음 호출을 준비합니다.토큰은 하나 이상의 공백으로 구분됩니다.
파일이 이미 메모리의 StringList에 있다고 가정합니다.예를 들어 200MB와 같이 메모리에 쉽게 맞습니다.
오직 파싱 실행 시간만 걱정됩니다.Delphi(Pascal)에서 가장 빠른 실행을 생성하는 코드는 무엇입니까?
해결책
- 처리 속도를 위해 PCHREMENT를 사용하십시오
- 일부 토큰이 필요하지 않은 경우 주문시 토큰 데이터 만 복사하십시오.
- 실제로 문자를 통해 스캔 할 때 PCHAR를 로컬 변수로 복사합니다.
- 라인별로 처리하지 않아도 단일 버퍼로 소스 데이터를 유지하고 Lexer 인식기에서 라인 처리를 별도의 토큰으로 고려하십시오.
- 인코딩을 확실히 알고 있다면 파일에서 바로 나오는 바이트 배열 버퍼를 처리하는 것을 고려하십시오. Delphi 2009를 사용하는 경우 PCHA 대신 Pansichar를 사용하십시오. 물론 인코딩이 UTF16-le입니다.
- 유일한 공백이 #32 (ASCII 공간) 또는 유사하게 제한된 문자 세트가 될 것이라는 것을 알고 있다면 정수 스캔을 사용하여 한 번에 4 바이트를 처리 할 수있는 영리한 비트 조작 해킹이있을 수 있습니다. 나는 여기서 큰 승리를 기대하지 않을 것이며, 코드는 진흙만큼 분명 할 것입니다.
다음은 매우 효율적이어야하는 샘플 Lexer가 있지만 모든 소스 데이터가 단일 문자열에 있다고 가정합니다. 버퍼를 처리하기 위해 재 작업하는 것은 매우 긴 토큰으로 인해 적당히 까다 롭습니다.
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;
다른 팁
다음은 매우 간단한 Lexer의 절름발이 엉덩이 구현입니다. 이것은 당신에게 아이디어를 줄 수 있습니다.
이 예제의 제한 사항에 유의하십시오 - 버퍼링과 관련이없고, 유니 코드가 없음 (이것은 델파이 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.
상태 엔진(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;
그것은 간단하고 매력처럼 작동합니다.
속도가 본질이라면 사용자 정의 코드가 답입니다. 파일을 메모리에 매핑하는 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;
가장 큰 병목 현상은 항상 파일을 메모리로 가져 오는 것이라고 생각합니다. 일단 메모리에 그것을 가지고 있다면 (분명히 한 번에 모든 것이 아니라, 내가 당신이라면 나는 버퍼와 함께 일할 것입니다), 실제 구문 분석은 중요하지 않아야합니다.
이것은 또 다른 질문을 제기합니다 - 얼마나 큰가요? 선 또는 # 또는 MB (GB)와 같은 단서를 알려주세요. 그런 다음 메모리에 맞는지 알 수 있습니다. 디스크 기반 등이 필요합니다.
첫 번째 패스에서 나는 내 워드리스트 (s : string; alist : tstringlist)를 사용합니다.
그런 다음 각 토큰에 Alist [N]로 액세스하거나 정렬 할 수 있습니다.
속도는 항상 구문 분석되면 당신이하는 일과 상대적입니다. 어휘 파서는 크기에 관계없이 텍스트 스트림에서 토큰으로 변환하는 가장 빠른 방법입니다. 클래스 유닛의 TPARSER는 시작하기에 좋은 곳입니다.
개인적으로 파서를 작성해야했던 이후로 오랜 시간이 지났지 만, 또 다른 데이트를 시도했지만 또 다른 시도와 진정한 방법은 Lex/YACC를 사용하여 문법을 구축 한 다음 문법을 처리하는 데 사용할 수있는 코드로 변환하는 것입니다. dyacc 델파이 버전입니다 ... 여전히 컴파일되는지 아닌지는 확실하지 않지만 오래된 학교를하고 싶다면 살펴볼 가치가 있습니다. 그만큼 용 책 사본을 찾을 수 있다면 큰 도움이 될 것입니다.
자신을 굴리는 것이 가장 빠른 방법입니다. 이 주제에 대한 자세한 내용은 확인할 수 있습니다 Synedit의 소스 코드 여기에는 시장의 모든 언어에 대한 Lexers (프로젝트 컨텍스트에서 형광펜이라고 함)가 포함되어 있습니다. 나는 당신이 그 Lexers 중 하나를 기본으로 가져 와서 자신의 사용을 위해 수정하는 것이 좋습니다.
가장 빠른 방법 쓰다 코드는 아마도 tstringlist를 만들고 텍스트 파일의 각 줄을 comeMatext 속성에 할당하는 것일 것입니다. 기본적으로 공백은 구분 기호이므로 토큰 당 하나의 StringList 항목을 얻게됩니다.
MyStringList.CommaText := s;
for i := 0 to MyStringList.Count - 1 do
begin
// process each token here
end;
하지만 각 라인을 직접 구문 분석하여 더 나은 성능을 얻을 수 있습니다.
