Nicht byte-weise Protokolle in C - Wie am besten vorgehen?

[Daniel A. (daniel-a)]

(Die die nicht alles lesen wollen, siehe den Abschnitt [Frage] weiter 
unten).

# Ausgangslage

Ich bin gerade dabei etwas zwischen einem Parser und einem Lexer zu 
schreiben. Ich habe da dann eine zu parsende Syntax, z.B.

@root = calculation ;
digit = [0-9] ;
number = digit+ ;
space = " " ;
operator = plus: "+"
         | minus: "-"
         ;
calculation = number space* operator space* number ;

Und eine Datei mit dem zu parsenden Inhalt, die ich direkt per mmap in 
den Speicher mappe. z.B.

3 + 10

Daraus baue ich dann eine Baumstruktur auf, von Token und Subtoken, und 
welche Bereiche vom Input diesen zugeordnet wird. Ein bisschen wie ein 
AST, wenn  man will. z.B.

0-6 calculation
  0-1 number
    0-1 digit
  1-2 space
  2-3 operator: plus
  3-4 space
  4-6 number
    4-5 digit
    5-6 digit

# Das Problem

Das Problem am ganzen ist, wenn ich den Baum / all die Metadaten, 
unkomprimiert im Speicher lasse, kann das zu enormem overhead führen. 
Sagen wir, z.B. meine Token wären in so einer Struktur gespeichert:

struct hlex_string {
  size_t length;
  // Note: not null terminated
  const uint8_t* data;
};
struct hlex_token {
  const struct hlex_token_type* token;
  const char* label; // Most of the time probably null
  struct hlex_string content; // points inside hlex_root::mmap
  size_t child_count;
  const struct hlex_token* children;
  const struct hlex_token* parent;
};

Dann wären das rund 56 Bytes pro Token. So kann man z.B. bei einem Token 
pro Abstand, nur schon für ein paar Abstände, schnell mal 56 mehr an 
Metadaten haben, als die eigentlichen Daten platz verbrauchen. O(1) an 
Speicher pro Token hin oder her, das ist eine massive Verschwendung an 
Arbeitsspeicher. Deshalb will ich die Metadaten in einer Komprimierten 
Form abspeichern, und dann nur jeweils die, die ich als nächstes 
Verarbeiten will, on-the-fly wieder entpacken.

Das Format dafür am Ende ist nicht wirklich das Problem, das kann ich 
mir schon selbst ausdenken. Aber um hier Platz zu sparen, brauche ich 
jedes Bit, das ich kriegen kann. Ein Format, dass Byte weise operiert, 
bringt mich hier nur begrenzt weiter, weil ich ja viele Token haben 
kann, die nur 1 Byte oder so beinhalten, und die will ich mit möglichst 
geringem Speicher overhead Speichern, aber so, dass ich das trotzdem 
noch Weiterverarbeiten kann.

# Frage

Ich will effizient & einfach auf einzelne Bits zugreifen. Ich bräuchte 
eine Abstraktion für eine Liste von Bits. Also lesen, schreiben, 
kopieren, verschieben, usw. von Bits, mit beliebigem Bitoffset. Am 
Anfang und Ende will ich auch mehr Bits anhängen können. Gibt es da eine 
gute C Library für so was? Oder falls ich das selbst machen muss, habt 
ihr Empfehlungen, wie man sowas einigermassen effizient hinbekommt?

[Voodoopriester (Gast)]

https://en.wikipedia.org/wiki/Bit_field

[Daniel A. (daniel-a)]

Voodoopriester schrieb:
> https://en.wikipedia.org/wiki/Bit_field

Das hilft bei diesem Anwendungsfall nicht weiter. Ich habe nicht vor, 
meine Datenstrukturen auf ganze Bytes zu alignenen. Ich suche eher 
sowas:

https://en.wikipedia.org/wiki/Bit_array

Da ist die Limitation auch nochmal erwähnt:
>The C programming language's bit fields, pseudo-objects found in structs with
> size equal to some number of bits, are in fact small bit arrays; they are
> limited in that they cannot span words.

[Voodoopriester (Gast)]

Ja stimmt, das meinte ich auch. Aber der Verwaltungsaufwand wird immer 
relativ hoch sein, so dass du nichts einsparst und das ganze nur unnötig 
komplex wird. Evt. kann man es auf Nibbleebene runterbrechen damit es 
passt.

Wenn du die Syntax anpassen kannst, dann eben so, dass man es einfacher 
implementieren kann wie bei der UPN.

[Rolf M. (rmagnus)]

Daniel A. schrieb:
> Dann wären das rund 56 Bytes pro Token. So kann man z.B. bei einem Token
> pro Abstand, nur schon für ein paar Abstände, schnell mal 56 mehr an
> Metadaten haben, als die eigentlichen Daten platz verbrauchen. O(1) an
> Speicher pro Token hin oder her, das ist eine massive Verschwendung an
> Arbeitsspeicher.

Kommt drauf an, wie groß deine Dateien sind. Wenn's mehrere Hundert MB 
sein können, kann man sich schon mal Gedanken darüber machen.

> Deshalb will ich die Metadaten in einer Komprimierten
> Form abspeichern, und dann nur jeweils die, die ich als nächstes
> Verarbeiten will, on-the-fly wieder entpacken.

Musst du denn alles auf einmal parsen? Vielleicht kannst du ja nur so 
viel parsen, wie du gerade brauchst, das dann verarbeiten, und dann zum 
nächsten weitergehen.

Daniel A. schrieb:
> Ich will effizient & einfach auf einzelne Bits zugreifen. Ich bräuchte
> eine Abstraktion für eine Liste von Bits. Also lesen, schreiben,
> kopieren, verschieben, usw. von Bits, mit beliebigem Bitoffset.

Aber wo willst du das bei deiner obigen Datenstruktur einsetzen? Die 
besteht ja fast nur aus Zeigern.

[Hannes J. (Firma: _⌨_) (pnuebergang)]

Du ließt ein Zahl und speicherst jede Ziffer einzeln in deiner Struktur 
ab? Ungeschickt.

Ansonsten, wenn der Hauptspeicher nicht reicht muss man halt auf der 
Festplatte speichern. Bei klassischen rotierenden Platten wird es 
deutlich langsamer. Bei SSD etwas weniger.

Wie du speicherst, ob z.B. sequenziell, mit einer Baum-Struktur, lieber 
direkt in einer Datenbank und welcher Art von Datenbank, ... ob mit 
fester oder variabler Record-Größe hängt davon ab wie du auf die Daten 
zugreifen möchtest.

[Daniel A. (daniel-a)]

Rolf M. schrieb:
>> Deshalb will ich die Metadaten in einer Komprimierten
>> Form abspeichern, und dann nur jeweils die, die ich als nächstes
>> Verarbeiten will, on-the-fly wieder entpacken.
>
> Musst du denn alles auf einmal parsen? Vielleicht kannst du ja nur so
> viel parsen, wie du gerade brauchst, das dann verarbeiten, und dann zum
> nächsten weitergehen.

Die Idee ist, das der root Token den gesamten Input matchen sollte. Ist 
das nicht der Fall, muss ich unter Umständen backtracken, bis eine 
Lösung gefunden ist, wo alles gematcht wird. Ähnliches kann es auch bei 
subtoken geben. Ich weiss also nicht unbedingt, ob alles richtig geparst 
ist, bis ich alles geparst habe.

Rolf M. schrieb:
> Daniel A. schrieb:
>> Ich will effizient & einfach auf einzelne Bits zugreifen. Ich bräuchte
>> eine Abstraktion für eine Liste von Bits. Also lesen, schreiben,
>> kopieren, verschieben, usw. von Bits, mit beliebigem Bitoffset.
>
> Aber wo willst du das bei deiner obigen Datenstruktur einsetzen? Die
> besteht ja fast nur aus Zeigern.

Das ganze ist eine Baumstruktur. Wenn ich anfange, darüber zu iterieren, 
muss ich zwangsweise ganz unten bei der Wurzel anfangen. Bei jedem Token 
kann ich zum  nächsten Token, zum parent Token, zum ersten child Token, 
oder zum letzten child Token gehen. Bei der Struktur oben habe ich dafür 
jeweils Pointer, aber es gibt auch andere Wege, das gleiche umzusetzen. 
Ich werde einen iterator und ein paar Funktionen definieren, um über den 
Baum zu zu navigieren, und eine Funktion, um die Informationen für den 
momentanen Token auszulesen. Irgendwas in die Richtung:

struct hlex_root {
  struct hlex_string mmap;
  const struct hlex_iterator* root;
};

hlex_it hlex_it_dup(const struct hlex_iterator* it, bool cut_off);
bool hlex_it_reset(hlex_it dst, const hlex_it src);
void hlex_it_free(hlex_it it);

struct hlex_token hlex_it_get(hlex_it it);
bool hlex_it_next(hlex_it it, bool allow_updown);
bool hlex_it_prev(hlex_it it, bool allow_updown);
bool hlex_it_parent(hlex_it it);
bool hlex_it_first_child(hlex_it it);
bool hlex_it_last_child(hlex_it it);

Die Reihenfolge der Token und der gematchten Inhalte ist ja die Selbe. 
Einige Informationen kann ich im Iteratorobjekt selbst vorhalten, und 
wären dem Traversieren des Baums updaten.

Die Namen der Token, sowie welche Subtoken und Label ein Token haben 
kann, ist für jeden Token bereits im vornherein bekannt. Und die Anzahl 
der möglichen Subtoken typen wird meistens vermutlich recht gering sein. 
Das kann ich zur Kompression nutzen. Ich habe mir bereits ein Format für 
das Kodieren der Zahlen ausgedacht:

/**
 * Custom reverse-readable variable length number encoding.
 * 
 * Format:
 * 1) 1 bits length, fixed. After that, a bit being 1 for numbers less than 4, 0 for larger numbers.
 * 2) After that, the next 8 bits become part of the number.
 * 3) If the remaining numerosity fits into these bits, a 0 bit follows, otherwise, a 1 bit.
 * 4) goto 2, if the number isn't fully encoded yet
 *
 * Number of bits needed for any number (ranges are inclusive):
 *       start        |         end          |       start       |         end         | bits | min bytes
 *                  0 -                    3 |               0x0 -                 0x3 |    3 |  1
 *                  4 -                 1027 |               0x4 -               0x403 |   12 |  2
 *               1028 -               263171 |             0x404 -             0x40403 |   21 |  3
 *             263172 -             67372035 |           0x40404 -           0x4040403 |   30 |  4
 *           67372036 -          17247241219 |         0x4040404 -         0x404040403 |   39 |  5
 *        17247241220 -        4415293752323 |       0x404040404 -       0x40404040403 |   48 |  6
 *      4415293752324 -     1130315200594947 |     0x40404040404 -     0x4040404040403 |   57 |  8
 *   1130315200594948 -   289360691352306691 |   0x4040404040404 -   0x404040404040403 |   66 |  9
 * 289360691352306692 - 74076336986190513155 | 0x404040404040404 - 0x40404040404040403 |   75 | 10
 *
 * Finding the start from the end (reading backwards) can be done as follows: 
 *  1) Take a bit.
 *  2.1) Is it 1? Skip the next 2 bits, now you're at the start.
 *  2.2) Is it 0? continue at 3.
 *  3) skip 8 bits
 *  4) Take a bit.
 *  5.1) Is it 1? goto 3.
 *  5.2) Is it 0? Skip the next 2 bits, now you're at the start.
 */
static int write_compressed_length(struct bitarray* dst, uint64_t number){
  if(number < 0x4){
    return write_bits_u(dst, number | 0x4, 3);
  }else if(number < 0x404){
    number -= 0x4;
  }else if(number < 0x40404){
    number -= 0x404;
  }else if(number < 0x4040404){
    number -= 0x40404;
  }else if(number < 0x404040404){
    number -= 0x4040404;
  }else if(number < 0x40404040404){
    number -= 0x404040404;
  }else if(number < 0x4040404040404){
    number -= 0x40404040404;
  }else if(number < 0x404040404040404){
    number -= 0x4040404040404;
  }else/* if(number < 0x40404040404040404)*/ { // 2**64 < 0x40404040404040404
    number -= 0x404040404040404;
  }
  write_bits_u(dst, number & 0x3, 3);
  do {
    if(write_bits_u(dst, number, 8))
      return -1;
    number <<= 8;
    if(write_bit(dst, number))
      return -1;
  } while(number);
  return 0;
}

Zusätzlich kann es Token geben, die nur einen Subtoken type haben 
können, und Subtoken, die nur in einem parent Token auftreten können, in 
den fällen kann ich mir jenachdem das explizite Codieren der Token 
sparen.

Erschwert wird das ganze aber dadurch, dass ich weiterhin in alle 
Richtungen über den Baum iterieren können will, ich muss also entweder 
gewisse Zusatzdaten im Baum vorhalten, oder im Iterator. Ich gehe davon 
aus, dass die Baume in der regel breiter als tief sind. Ich habe vor, 
den Anfang von jedem Level im Iterator festzuhalten. Für den Nachsten / 
Vorherigen Token hingegen, habe ich vor, in den Metadaten selbst genug 
Daten / struktur zu lassen, um diese rückwärts lesen zu können.

[Egon D. (Gast)]

Daniel A. schrieb:

> Ich bin gerade dabei etwas zwischen einem Parser und
> einem Lexer zu schreiben. [...]
>
> Daraus baue ich dann eine Baumstruktur auf,

Warum?

Soll heißen: Bei der Lösung genau welches Problems soll
Dir diese Baumstruktur helfen?


Nur als Beispiel: Mein Programm zur semi-numerischen
Berechnung von RLC-Filtern wandelt die Netzliste der
Schaltung in eine Formel um, die in umgekehrter
polnischer Notation (sic!) einfach als String gespeichert
wird.
Dieses RPN-"Programm" wird dann direkt von einem
Kellerautomaten ausgeführt, der die komplexe Wechselstrom-
rechnung beherrscht; dessen "Parser" für die RPN ist meiner
Erinnerung nach strunzdumm und verdient den Namen "Parser"
nicht. Keine Klammern, kein Baum, kein Stress.

[Sheeva P. (sheevaplug)]

Egon D. schrieb:
> Soll heißen: Bei der Lösung genau welches Problems soll
> Dir diese Baumstruktur helfen?

Was ist eigentlich ein Abstract Syntax Tree?

[Egon D. (Gast)]

Sheeva P. schrieb:

> Egon D. schrieb:
>> Soll heißen: Bei der Lösung genau welches
>> Problems soll Dir diese Baumstruktur helfen?
>
> Was ist eigentlich ein Abstract Syntax Tree?

???
Falsche Adresse.

Meine Frage an den TO bleibt weiterhin bestehen.

[Daniel A. (daniel-a)]

Egon D. schrieb:
> Warum?

Ich habe vor, eventuell mal später eine eigene Programmiersprache zu 
schreiben. Ich finde es wichtig, die Syntax explizit separat definiert 
zu haben. Aber ich finde bestehende Lexer und Parser ehrlich gesagt eher 
unpraktisch.

Wenn man sich z.B. lex/flex ansieht, dort gibt es noch keinen Kontext & 
keine hirarchie, die längsten matches werden einfach zu Token, nein 
nicht einmal das, was man bei nem match macht muss man selbst Coden. Mit 
Bison kann man auch abflogen von Token interpretieren, aber auch da muss 
man dann immer selbst gleich was Coden, was damit passieren soll. Auch 
bei vielen anderen Parsern (vor)verarbeitet man den Input oft gleich 
beim Parsen / parst Sachen stückchenweise. Das mag ja effizient sein, 
aber ich finde es ehrlich gesagt eher unschön und unpraktisch.

Deshalb mache ich meinen eigenen Lexer. Damit kann ich meine Syntax 
vollständig, simpel, und unabhängig vom eigentlichen Parser/Compiler 
definieren, und muss keinen extra Code für den Lexer -> Parser schritt 
schreiben. Was ich bekomme ist zwar nicht so high level wie ein 
richtiger AST - der Input wird ja nicht weiter/vor- verarbeitet, sondern 
nur halt unverändert auf die Token / Syntax gekappt, aber diese 
Datenstruktur ist trotzdem sehr einfach weiterverarbeitbar. Man kann 
daraus dann z.B. einen richtigen AST aufbauen. Oder man kann ihn sich 
ausgeben lassen, um die Syntax zu Debuggen. Ich könnte das Resultat auch 
in beliebigen anderen, mit anderen Programmen weiterverarbeitbaren 
Formaten, ausgeben.

Klar, am Ende muss ich auch irgendwann mal über den Baum gehen, und den 
weiterverarbeiten. Aber mir gefällt es halt einfach besser, einen 
simplen, vollständigen, Baum zu haben, und Tools, die ich bei 
verschiedenen mit meinem Lexer beschriebenen Sprachen verwenden kann. So 
einen praktischen, simplen, nachvollziehbaren, Zwischenzustand, haben 
andere Lexer / Parser, einfach nicht einfach so in der Form. Ich sehe 
schon lange vor dem Schreiben des finalen Parser/Interpreter/Compiler, 
ob die Syntax so passt, wie ich mir das gedacht habe.

Also warum das ganze?

Weil mir halt gerade danach ist, das so zu machen.

[Egon D. (Gast)]

Daniel A. schrieb:

> Egon D. schrieb:
>> Warum?
>
> Ich habe vor, eventuell mal später eine eigene
> Programmiersprache zu schreiben.

Ah, okay.
Dann habe ich Deine Beispiele fehlgedeutet; ich dachte,
es ginge in die Richtung Formelparser und Numerik.


> Wenn man sich z.B. lex/flex ansieht, [...]
> Das mag ja effizient sein, aber ich finde es ehrlich
> gesagt eher unschön und unpraktisch.

Nach meinem (sehr rudimentären) Verständnis liegt das
Problem darin, dass diese Generatoren das gesamte
Verhalten in einen einzigen großen Automaten quetschen
wollen. Das wird natürlich extrem unübersichtlich.


> Deshalb mache ich meinen eigenen Lexer. Damit kann ich
> meine Syntax vollständig, simpel, und unabhängig vom
> eigentlichen Parser/Compiler definieren, und muss keinen
> extra Code für den Lexer -> Parser schritt schreiben.
> Was ich bekomme ist zwar nicht so high level wie ein
> richtiger AST - der Input wird ja nicht weiter/vor-
> verarbeitet, sondern nur halt unverändert auf die
> Token / Syntax gekappt,

Hmm. Ich ahne GANZ dunkel, was Du machen willst, nur
verstehe ich nicht, wie das praktisch funktionieren soll.
Du kannst ja schlecht die einzelnen Zeichen des Input-
stromes auf Token mappen, bevor Du die Regeln definiert
hast, anhand derer man die Token erkennen kann.

Und eine Datenstruktur, mit der Du jedes beliebige
Mapping für jede beliebige definierbare formale
Sprache abbilden kannst, ... naja, das klingt sehr
nach der "Allgemeinen Theorie von Allem". Kann man
machen, scheint mir aber... ungünstig.


Was wäre, wenn man sich weniger auf die Datenstruktur
fokussiert, sondern die Verarbeitungsschritte zerlegt?

Ich stelle mir das ganze als eine Reihen-Parallel-
Schaltung von Filtern vor (vielleicht sollte man auch
nicht von "Filtern", sondern besser von "Demultiplexern"
sprechen).

Beispiel: Angenommen, in Deiner Sprache sollen sich
Newlines überall (in Kommentaren, in Strings und im
regulären Code) durch Backslash maskieren lassen. Also
programmierst Du einen Automaten mit einem Ein- und
einem Ausgang und zwei Zuständen, "standard" und
"backslash". Im Zustand "standard" werden alle ein-
laufenden Zeichen (bis auf den Backslash) einfach zum
Ausgang weitergereicht, und der Backslash ruft einen
Übergang zum Zustand "backslash" hervor, erzeugt aber
keinen Output.
Im Zustand "backslash" ruft ein newline keinen Output,
jedes andere Zeichen aber den Output eines Backslash,
gefolgt vom jeweiligen Zeichen hervor, und der Automat
wechselt wieder in den Zustand "standard".

Folge: Hinter diesem Automaten können keine maskierten
Newlines mehr auftreten, sie werden unterdrückt; alles
andere erscheint unverändert am Ausgang.

Angenommen, in Deiner Sprache soll es darüberhinaus
Kommentare, regulären Code und Strings geben. Also
schaltest Du zu dem Backslash-Newline-Filter einen
weiteren Automaten in Reihe, der drei Ausgänge und
drei Zustände kennt, nämlich "comment", "code" und
"string", und der sinngemäß genauso funktioniert wie
der erste.

Falls Du Dich nachträglich entschließt, die maskierte
Newlines nur aus dem eigentlichen Code herausfiltern
zu wollen, nicht aber aus Strings und Kommentaren,
musst Du lediglich die Verdrahtung der Bausteine
ändern, nicht deren innere Logik.

Fehlerbehandlung fehlt natürlich in meiner Idee noch,
außerdem wird man die letztlich gefundenen Token der
Reihenfolge im Input-Strom nach nummerieren wollen.


> So einen praktischen, simplen, nachvollziehbaren,
> Zwischenzustand, haben andere Lexer / Parser, einfach
> nicht einfach so in der Form.

Verstehe ich. Bietet mein Vorschlag aber auch. Du musst
ja nur mit dem Oszi prüfen, an welchem Ausgang ein
bestimmtes Symbol erscheint :)


> Weil mir halt gerade danach ist, das so zu machen.

Vollkommen okay. Ich wollte es wirklich nur wissen.

[Rolf M. (rmagnus)]

Daniel A. schrieb:
> Wenn man sich z.B. lex/flex ansieht, dort gibt es noch keinen Kontext &
> keine hirarchie, die längsten matches werden einfach zu Token, nein
> nicht einmal das, was man bei nem match macht muss man selbst Coden.

Ja natürlich. Woher soll flex denn die Bedeutung des gefundenen Tokens 
kennen?

> Mit Bison kann man auch abflogen von Token interpretieren, aber auch da
> muss man dann immer selbst gleich was Coden, was damit passieren soll.

Wenn du Lexer und Parser von Hand schreibst, musst du das doch auch tun, 
aber eben zusätzlich noch den Lexer und Parser schreiben.
Normalerweise nutzt man flex mit bison zusammen, so dass der Output des 
einen direkt in den anderen rein geht.

> Auch bei vielen anderen Parsern (vor)verarbeitet man den Input oft gleich
> beim Parsen / parst Sachen stückchenweise. Das mag ja effizient sein,
> aber ich finde es ehrlich gesagt eher unschön und unpraktisch.

Dann schau dir mal ANTLR an. Da wird ein Parsetree aufgebaut, den man 
dann im Anschluss z.B. mit einem visitor begutachtet. Man kann da 
prinzipiell zwar auch Code mit in die Regeln schreiben, aber das macht 
man dort eigentlich nur, wenn man für irgendwelche Besonderheiten der 
Sprache das Parsing selbst speziell anpassen muss. Die Auswertung 
erfolgt immer erst hinterher auf dem erzeugten Parsetree.
Allerdings kann ANTLR4 zwar für mehrere Ziel-Programmiersprachen Code 
generieren, aber C ist nicht dabei. In ANTLR3 ging das wohl noch.

[Sheeva P. (sheevaplug)]

Egon D. schrieb:
> Daniel A. schrieb:
>> Egon D. schrieb:
>>> Warum?
>> Ich habe vor, eventuell mal später eine eigene
>> Programmiersprache zu schreiben.
> Ah, okay.
> Dann habe ich Deine Beispiele fehlgedeutet; ich dachte,
> es ginge in die Richtung Formelparser und Numerik.

Wenn man mal selbst etwas in der Richtung entwickelt hat, erkennt man 
schnell, was Daniel vorhat. Deswegen auch meine Frage nach dem AST. ;-)

[Sheeva P. (sheevaplug)]

Daniel A. schrieb:
> Ich habe vor, eventuell mal später eine eigene Programmiersprache zu
> schreiben. Ich finde es wichtig, die Syntax explizit separat definiert
> zu haben. Aber ich finde bestehende Lexer und Parser ehrlich gesagt eher
> unpraktisch.

Naja, Du hast die existierenden Lexer und Parser für C angeschaut, also 
(f)lex, Bison und Co. Die sind deswegen etwas speziell, weil sie halt 
die Besonderheiten einer prozeduralen Sprache abbilden (müssen).

> Wenn man sich z.B. lex/flex ansieht, dort gibt es noch keinen Kontext &
> keine hirarchie, die längsten matches werden einfach zu Token, nein
> nicht einmal das, was man bei nem match macht muss man selbst Coden. Mit
> Bison kann man auch abflogen von Token interpretieren, aber auch da muss
> man dann immer selbst gleich was Coden, was damit passieren soll. Auch
> bei vielen anderen Parsern (vor)verarbeitet man den Input oft gleich
> beim Parsen / parst Sachen stückchenweise. Das mag ja effizient sein,
> aber ich finde es ehrlich gesagt eher unschön und unpraktisch.

Ist es auch. Moderne Parser/Lexer machen das auch etwas anders und geben 
Dir gleich einen AST zurück, das Du dann rekursiv verarbyten kannst. 
Dazu ein paar Beispiele wären die Schnittstellen zu dem Parser von 
Python, schau mal auf [1]. Deine EBNF könnte aber auch Python's Lark [2] 
verarbeiten. Ansonsten möchtest Du vielleicht mal bei Boost::Spirit 
schauen... ;-)

> Deshalb mache ich meinen eigenen Lexer.

räusper ;-)


[1] https://docs.python.org/3/library/parser.html
[2] https://lark-parser.readthedocs.io/en/latest/
[3] 
https://www.boost.org/doc/libs/1_77_0/libs/spirit/doc/html/index.html

[Daniel A. (daniel-a)]

ANTLR und Lark sind doch sehr nahe an dem, was ich wollte. Aber ANTLR 
ist in java geschrieben, da bin ich kein grosser Fan von. Lark ist in 
Python geschrieben, da habe ich nichts dagegen, vielleicht verwende ich 
das am ende.
Ich versuche mich aber am Anfang trotzdem noch an einem eigenen solchen 
Lexer / Parser, immerhin habe ich damit schon angefangen, wäre schade, 
das alles einfach weg zu werfen...

[Rolf M. (rmagnus)]

Daniel A. schrieb:
> ANTLR und Lark sind doch sehr nahe an dem, was ich wollte. Aber ANTLR
> ist in java geschrieben, da bin ich kein grosser Fan von.

Macht doch nichts. Du musst deshalb ja nicht selbst irgendwas in Java 
schreiben. Bei mir funktioniert es jedenfalls gut, und ich bin recht 
zufrieden damit.

> Lark ist in Python geschrieben, da habe ich nichts dagegen, vielleicht
> verwende ich das am ende.
> Ich versuche mich aber am Anfang trotzdem noch an einem eigenen solchen
> Lexer / Parser, immerhin habe ich damit schon angefangen, wäre schade,
> das alles einfach weg zu werfen...

Das ist ja auch mal eine nette Übung.