Einfachen Parser generieren

[Peter666]

Hi ich muss für ein Projekt einen Parser für folgende Datenstrukturen erstellen:

Code:

descriptor 81 mosaic_descriptor [
** *mosaic_entry_point * * * * * * * * * * 1
** *number_of_horizonal_elementary_cells * 3
** *reserved_future_use * * * * * * * * * *1 *ones
** *number_of_vertical_elementary_cells * *3
** *for length [
** * * *logical_cell_id * * * * * * * * * *6
** * * *reserved_future_use * * * * * * * *7 *ones
** * * *logical_cell_presentation * * * * *3
** * * *elementary_cell_field_length * * * 8 *byte_counter
** * * *for N [
** * * * * *reserved_future_use * * * * * *2 *ones
** * * * * *elementary_cell_id * * * * * * 6
** * * *]
** * * *cell_linkage_info * * * * * * * * *8
** * * *if [cell_linkage_info = 1] [
** * * * * *bouquet_id * * * * * * * * * * 16
** * * *]
** * * *if [cell_linkage_info = 2] [
** * * * * *original_network_id * * * * * *16 hex
** * * * * *transport_stream_id * * * * * *16 hex
** * * * * *service_id * * * * * * * * * * 16
** * * *]
** * * *if [cell_linkage_info = 3] [
** * * * * *original_network_id * * * * * *16 hex
** * * * * *transport_stream_id * * * * * *16 hex
** * * * * *service_id * * * * * * * * * * 16
** * * *]
** * * *if [cell_linkage_info = 4] [
** * * * * *original_network_id * * * * * *16 hex
** * * * * *transport_stream_id * * * * * *16 hex
** * * * * *service_id * * * * * * * * * * 16
** * * * * *event_id * * * * * * * * * * * 16
** * * *]
** *]
*
** *enum logical_cell_presentation [
** * * *0 *"undefined"
** * * *1 *"video"
** * * *2 *"still picture"
** * * *3 *"graphics/text"
** *]
*
** *enum cell_linkage_info [
** * * *0 *"undefined"
** * * 1 *"bouquet related"
** * * *2 *"service related"
** * * *3 *"other mosaic related"
** * * *4 *"event related"
** *]
]

Jeder descriptor kann recht verschachtelt sein und schaut ähnlich wie der obige aus. Length ist die komplette Länge in Byte, die Zahlen rechts sind in Bit. Hat jemand eine Idee wie ich das ganze möglichst flexibel gestalte, ohne gleich mit einem Riesen Compiler/Lexer arbeiten zu müssen?

Peter
PS: Von Compilerbau hab ich das letzte mal was vor 10+ Jahren mal im Studium gehört *herrje bin ich alt* :/

[himitsu]

Was soll denn das Ergebnis des Parsens werden?

Reicht es nicht, wenn du das in einen passenden Record reinbekommst?
[add] OK, eine Klassenstruktur wäre eventuell auch angebracht.

PS: Für welche Delphiversion wird das denn? (ab TDE/D2006 gibt es da eine ganz einfache Lösung)
[edit] Ups, die zweite Verschachtelungsebene übersehn, da geht es dann doch nicht so einfach.



Aber ein rießiger Compiler ist nicht unbedingt nötig (wenn nicht unbedingt erwünscht).
Mit ein paar kleinen Lesebefehlen und zwei Schleifchen sollte sich das recht leicht auslesen lassen.

[hathor]

Digital broadcasting systems for television,sound and data services;
Specification for Service Information (SI) in Digital Video Broadcasting (DVB) systems
ETSI
http://www.etsi.org/deliver/etsi_en/...68v010301p.pdf

[Peter666]

Die Descriptoren sind von SI Daten die über Transportstreams überragen werden. Davon gibt's einig, für die Auswertung bieten sich solche Skripte an - insbesonderende danman so leicht Erweiterungen testen kann

Peter

[Namenloser]

Zuerst würde ich mal eine GetToken() -Funktion schreiben: Diese liefert dir jeweils das nächste „Wort“, also entweder

• ein Schlüsselwort (if, for),
• einen Eigenschaftsnamen (z.B. mosaic_entry_point),
• einen String (z.B. "undefined", "video", "still picture")
• eine Zahl oder
• eine „Einheit“ (hex, ones, byte_counter)

Das ist recht einfach umzusetzen, da du nur zu Anfang schauen musst, ob das aktuelle Zeichen ein Anführungszeichen ('"') ist. Wenn ja, suchst du einfach das nächste Anführungszeichen und lieferst den dazwischenliegenden String als Ergebnis zurück (Escaping ist hier jetzt nicht berücksichtigt, wenn zwischen den Anführungszeichen wiederum Anführungszeichen in Form von Dopplung oder \-Escaping stehen können, wird es minimal komplizierter). Wenn es ein anderes Zeichen (z.B. eine Ziffer oder ein Buchstabe) ist, suchst du einfach den nächsten Whitespace, und kopierst, was dazwischen liegt. Für Klammern bräuchte man noch eine Sonderbehandlung, diese sollten immer direkt als Token angesehen werden, auch wenn kein Whitespace folgt.

In einer übergeordneter Routine kannst du dann prüfen, ob das zurückgelieferte Token ein Schlüsselwort ist, und entsprechend reagieren (z.B. Sub-Routine aufrufen, die nur für das Parsen der jeweiligen Struktur zuständig ist). Wenn du es so machst, hast du auch gleich das Verschachtelungs-Problem gelöst, da du ansonsten einen extra Stack bräuchtest.

[implementation]

Ich würde mir an deiner Stelle einfach mal die ersten Kapitel aus Crenshaw's Compilerbau-Tutorial durchlesen
(alle brauchst du ja eben nicht ^^)
Dort geht es erstmal einfach ums Einlesen von Mathe-Termen, das kannst du dann sicherlich auf deinen Zweck umlegen

http://www.penguin.cz/~radek/book/le...ld_a_compiler/

Und wie passend: Es ist auch noch in Pascal!

[Peter666]

Danke für das Buch ich les mir den Text heut mal durch

[Luckie]

Freudsche Fehlleistung. Ich habe gelesen: Einfachen Perser generieren.

[implementation]

Zitat von Luckie:

Freudsche Fehlleistung. Ich habe gelesen: Einfachen Perser generieren.

Och, da gibt's schlimmere. Hier gab's mal 'nen Thread namens "BSoD auf die harte Tour" oder so - was glaubste, was ich gelesen hab?

[Peter666]

Ich schreib mal den derzeitigen "Ist"-Stand:

Eine der größeren Tabellen schaut wie folgt aus:

Code:

descriptor 129 ac3_audio_descriptor [
    sample_rate_code                 3
    bsid                             5
    ; bit_rate_code                    6
    bit_rate_limit                   1
    bit_rate_code                    5
    surround_mode                    2
    bsmod                            3
    num_channels                     4
    full_svc                         1
    langcod                          8
    if [num_channels = 0] [
        langcod2                     8
    ]
    if [bsmod < 2] [
        mainid                       3
        reserved                     5   ones
    ]
    else [
        asvcflags                    8
    ]
    textlen                          7
    text_code                        1
    text                             textlen  binary
    ; break serves no purpose here
    additional_info                  length   binary


    enum sample_rate_code [
        0   "48 kHz"
        1   "44.1 kHz"
        2   "32 kHz"
        3   "reserved"
        4   "48 or 44.1 kHz"
        5   "48 or 32 kHz"
        6   "44.1 or 32 kHz"
        7   "48 or 44.1 or 32 kHz"
    ]

    enum bit_rate_code [
        0   "32 kbps"
        1   "40 kbps"
        2   "48 kbps"
        3   "56 kbps"
        4   "64 kbps"
        5   "80 kbps"
        6   "96 kbps"
        7   "112 kbps"
        8   "128 kbps"
        9   "160 kbps"
        10  "192 kbps"
        11  "224 kbps"
        12  "256 kbps"
        13  "320 kbps"
        14  "384 kbps"
        15  "448 kbps"
        16  "512 kbps"
        17  "576 kbps"
        18  "640 kbps"
    ]

    enum num_channels [
        0   "1+1"
        1   "1/0"
        2   "2/0"
        3   "3/0"
        4   "2/1"
        5   "3/1"
        6   "2/2"
        7   "3/2"
        8   "1"
        9   "<=2"
        10  "<=3"
        11  "<=4"
        12  "<=5"
        13  "<=6"
        14  "reserved"
        15  "reserved"
    ]

    enum bsmod [
        0   "Main: Complete Main"
        1   "Main: Music and Effects"
        2   "Assoc: Visually Impaired"
        3   "Assoc: Hearing Impaired"
        4   "Assoc: Dialog"
        5   "Assoc: Commentary"
        6   "Assoc: Emergency"
        7   "Assoc: Voice Over or Main: Karaoke"
    ]

    enum surround_mode [
        0   "Not indicated"
        1   "NOT Dolby Surround encoded"
        2   "Dolby Surround encoded"
        3   "reserved"
    ]
]

Was ich bis jetzt habe ist eine einfachere Klasse die mir die Token liefert:

Code:

 TSource = class
  private
    FSource: string;
    FSourceSize: word;
    FSourceIndex: word;
    FSourceLine: word;
    FLineStart: word;
    FToken: string;
    procedure SkipBlanks;
    function DropChar: char;
    function NextChar: char;
    procedure ReadAlpha;
    procedure ReadNumber;

    function GetEOF: Boolean;
  public
    constructor Create(const AFileName: string);
    destructor Destroy; override;
    function NextToken: string;
    property EOF: Boolean read GetEOF;
  end;

...

procedure RemoveAllComments(List: TStringlist);
// Removes all unnecessary lines
var s: string;
  i, j: integer;
begin
  for i := List.count - 1 downto 0 do
  begin
    s := list[i];
    j := pos(';', s);
    if j > 0 then delete(s, j, length(s));
    s := trim(s);
    if s = '' then list.delete(i) else list[i] := s;
  end;
end;

constructor TSource.Create(const AFileName: string);
var list: TStringlist;
begin
  list := TStringlist.Create;
  try
    list.LoadFromFile(AFileName);
    RemoveAllComments(List);
    FSource := list.text;
  finally
    list.free;
  end;
  FSourceSize := length(Fsource);
  FSourceIndex := 1;
  FSourceLine := 1;
  FLineStart := 0;
end;

destructor TSource.Destroy;
begin
  inherited;
end;

function TSource.NextToken: string;
begin
  repeat
    SkipBlanks;
    FToken := DropChar;
    case UpCase(FToken[1]) of
      'A'..'Z', '_': ReadAlpha;
      '0'..'9': ReadNumber;
      '>': if NextChar = '=' then FToken := FToken + DropChar;
      '<': if NextChar = '>' then FToken := FToken + DropChar else begin
          if NextChar = '=' then begin
            FToken := FToken + DropChar;
            if NextChar = '>' then FToken := FToken + DropChar;
          end;
        end;
    end;
    result := FToken;
  until FToken <> '';
end;

procedure TSource.SkipBlanks;
var
  c: char;
begin
  while (FSourceIndex < FSourceSize) do
  begin
    c := FSource[FSourceIndex];
    if c = #13 then inc(FSourceLine);
    if c = #10 then FLineStart := FSourceIndex + 1;
    if c in [#9, #10, #13, ' '] then
      Inc(FSourceIndex)
    else
      exit;
  end;
end;

function TSource.DropChar: char;
begin
  result := NextChar;
  if result <> #0 then
  begin
    inc(FSourceIndex);
    if result = #13 then inc(FSourceLine);
    if result = #10 then FLineStart := FSourceIndex + 1;
  end;
end;

function TSource.NextChar: char;
begin
  if FSourceIndex < FSourceSize then
    result := FSource[FSourceIndex] else result := #0;

end;

procedure TSource.ReadAlpha;
var
  c: char;
begin
  c := NextChar;
  while UpCase(c) in ['A'..'Z', '_'] do begin
    FToken := FToken + c; inc(FSourceIndex);
    ReadNumber;
    c := NextChar;
  end;
end;

procedure TSource.ReadNumber;
var
  c: char;
begin
  c := NextChar;
  while UpCase(c) in ['0'..'9'] do begin
    FToken := FToken + c; inc(FSourceIndex);
    c := NextChar;
  end;
end;

function TSource.GetEOF: Boolean;
begin
  result := FSourceIndex >= FSourceSize;
end;

Schön schaut sicherlich anders aus, aber immerhin ist es leserlich
Jetzt fehlt eigentlich "nur" noch der wichtigste Code der mir einen Baum mit den Variablen inkl. der dazugehörigen Schleifen erstellt. So eine richtige Idee wie ich das wohl am besten erstelle hab ich allerdings nicht.
Mir schwebt eine Liste vor die sowas in der Art beinhaltet:

Code:

 TClassType=(cVar, cWhile,cIf, cElse);
 TScope=integer;

 TSymbol=class
  Name: String;
  ClassType: TClassType;
  ValueAsInteger: Integer;
  ValueAsString: String;
 end;

Wobei bei While If und Else der übernächste Eintrag mit dem aktuellen Symbol verglichen wird, wobei das Symbol dazwischen als Operator verwendet wird.

Vielleicht hat ja jemand eine einfachere Idee?

Peter

Peter