Entwickler-Ecke :: Thema anzeigen - rekursiver blockparser

realcrazy - So 17.04.05 06:28
Titel: rekursiver blockparser

Hallo Forum,

ich bin zur Zeit dabei einen rekursiven Blockparser zu schreiben. Die Funktion besteht darin eine Textdatei z.B.

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

zu parsen und in einen globalen Array:

Delphi-Quelltext

1:	g_a_blocks : array[1..255,1..2] of longword;

die jeweilige Zeile der sich oeffenden Klammer mit der Zeile der sich schliessenden zuzuordnen. Es sollte z.B. bei der oberen Text-Datei ein solches Array erzeugt werden:

Quelltext

1:
2:

1   2   6   7   12  15  17  19
23  11  9   8   14  22  21  20

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:

function blockparse(s_filename:string;inzeile:longword):longword;
  var
    f_scriptfile         : textfile;
    s_block              : string;
    i_zeile              : Longword;

  begin
  AssignFile(f_scriptfile, s_filename);
  Reset(f_scriptfile);

  i_zeile := 0;
   while not eof(f_scriptfile) do
    begin
      Readln(f_scriptfile,s_block);
      inc(i_zeile);

      if i_zeile >= inzeile then
        begin
          if pos('{',s_block) >= 1 then
            begin
              inc(g_a_blocks[1,1]);
              if g_a_blocks[1,2] > 0 then
                begin
                  g_a_blocks[g_a_blocks[1,1]+g_a_blocks[1,2]-1,2] := blockparse(s_filename,i_zeile+1);
                  g_a_blocks[g_a_blocks[1,1]+g_a_blocks[1,2]-1,1] := i_zeile;
                  inzeile := g_a_blocks[g_a_blocks[1,1]+g_a_blocks[1,2]-1,2]+1;
                end
              else
                begin
                  g_a_blocks[g_a_blocks[1,1]+1,2] := blockparse(s_filename,i_zeile+1);
                  g_a_blocks[g_a_blocks[1,1]+1,1] := i_zeile;
                  inzeile := g_a_blocks[g_a_blocks[1,1]+1,2]+1;
                end;
              dec(g_a_blocks[1,1]);
            end;
        end;

       if i_zeile >= inzeile then
        begin
          if pos('}',s_block) >= 1 then
            begin
              result:= i_zeile;
              inc(g_a_blocks[1,2]);
              exit;
            end;
        end;

    end;

end;

In diesem Quellcodebeispiel wird im globalen Array der Eintrag [1,1] und [1,2] fuer die Zwischenspeicherung von Arbeitsdaten benutzt. Die Nutzdaten werden erst ab [2,1] eingetragen. Nun zu meinen Problem: Die Rekursivitaet laeuft nur zum Teil, (Im Bespiel der oberen Textdatei: Die letzten drei Klammerungen werden nicht richtig im Array nach links geschoben und ueberschreiben sich somit selbst.) und ich komme einfach nicht weiter - Falls jemand eine Idee hat, oder zufaellig jemand einen aehnlichen Parser bereits einmal geschrieben hat, so bitte helft mir - Ich haenge jetzt schon 2 Tage an diesen Problem und bekomme es einfach nicht gebacken... Vielen Dank fuer alle Bemuehungen im vorraus!!!

Zur Zeit fehlerbehaftetes Array unter verwendung der oberen Textdatei und des Quellcodes:

Quelltext

1:
2:

1   2   6   7   12  0   0  15
23  11  9   8   14  0   0  22

Letzten 3 Klammerungen werden nicht richtig nach links geschoben....

.Chef - So 17.04.05 10:42

Verschiedenes zuerst:
1. Ich würde hier gar nicht rekursiv vorgehen. Es würde genügen, einfach zeilenweise die Klammerntiefe zu zählen.
2. In deiner Prozedur öffnest du jedesmal wieder die Datei, wenn ich das richtig sehe. Nicht gut ...
3. Lies die gesamte Datei lieber einmalig in eine Stringliste und arbeite dann mit der wie mit einem Array.

Und so könnte es aussehen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:

procedure StartParser;
var
  s : TStringList;
  st, ar : Integer;
  a : array[0..255,1..2] of Integer;
procedure Parse;
var
  x : Integer;
begin
  while s[st][1] <> '}' do
  begin
    if s[st][1] = '{' then
    begin
      a[ar,1]:=st+1;
      Inc(ar);
      Inc(st);
      Parse;
    end;
    Inc(st);
    if st >= s.Count then Exit;
  end;
  for x:=ar-1 downto 0 do
    if a[x,2] = 0 then
    begin
      a[x,2]:=st+1;
      Break;
    end;
end;
begin
  s:=TStringList.Create;
  s.LoadFromFile('HALLO.TXT');
  ar:=0;
  st:=0;
  FillChar(a,SizeOf(a),0);
  Parse;
  s.Free;
end;

Noch eleganter wäre, die Positionsmarker (st, ar) gleich mit der Prozedur Parse zu übergeben, aber ich will dir ja auch noch etwas Spaß übrig lassen. ;-)

Gruß,
Jörg

delfiphan - So 17.04.05 11:45

Wenn es die Stacks nicht gäbe, müsste man sie erfinden ;)

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

var
 Strings: TStringList;
 Stack: TStack;
 i, j: Integer;
begin
 Strings := TStringList.Create;
 Strings.LoadFromFile('hallo.txt');
 Stack := TStack.Create;
 j := 0;
 for i := 0 to Strings.Count-1 do
  if pos('{',Strings[i])>0 then
  begin
   inc(j);
   g_a_blocks[Integer(Stack.Push(Pointer(j))),1] := i+1;
  end else
   if pos('}',Strings[i])>0 then
    g_a_blocks[Integer(Stack.Pop),2] := i+1;
 Stack.Free;
 Strings.Free;
end;

.Chef - Mo 18.04.05 00:21

@delfiphan: Das ist so, wie ich oben meinte. Ich habe allerdings bewusst eine rekursive Demo gewählt, da der Threadersteller es ja auf diesem Weg machen wollte. :-)

realcrazy - Mo 18.04.05 01:00

DANKE. Laeuft alles so wie es soll.

Noch eine andere dumme Frage: Unter welcher Lizenz steht der hier gepostete Quellcode? Da das ganze einmal frueher oder spaeter 1:1 in ein kommerzielles Projekt einfliessen koennte waere mir natuerlich Public Domain am liebsten ^^

delfiphan - Mo 18.04.05 02:07

Generell gilt:

Zitat:

Copyright

Das Kopieren oder Vervielfältigen dieser Internetseiten, oder Bestandteile daraus, ist nur mit ausdrücklicher, schriftlicher Genehmigung des jeweiligen Autors erlaubt!

Wenn nichts besonderes vermerkt ist mir aber egal, was du mit meinen geposteten Sources tust. Ich garantiere einfach nicht, dass etwas erwartungsgemäss läuft. Das übliche halt. Verwendung auf eigene Gefahr.

.Chef - Mo 18.04.05 13:54

Dito. Antwortquelltexte auf Fragen sind bei mir auch frei weiterverwendbar. Was hätte ich auch davon, wenn es nicht so wäre? Wenn ich meinen Quelltext zum jeweiligen Problem nicht preisgeben will, brauche ich ja nicht zu antworten. ;)

Anders verhält es sich bei Projekten, die ich u.a. hier im Open-Source-Bereich veröffentliche. Die dürfen nur nicht-kommerziell weiterverwendet werden (andernfalls Rücksprache). Aber das sind ja dann auch eigenständige Projekte von mir, so dass ich nicht einsehe, warum jemand anderes Geld damit verdienen sollte.