Strukturierter Klartext zu Array mit Compiler oder Präprozessor???

[MB]

moin,

ich will einen sehr sehr sehr simplen Text Format in ein array umwandeln

der blaupausen Text:

	Einkaufsliste:
		[Obst]
		* Aepfel
		* Birnen
		* Bananen

		[Gemuese]
		* Kartoffeln
		* Zwiebeln

		Den Schluessel Nicht vergessen!

	Fund:
		* 3 Gang
		  * 2 Regal
		    * 8 Fach

	Wertetabelle:
		Fett							- 8,7
		Kohlenhydrate			- 80

rauskommen soll sowas ein 2 Dimensionales Hashmap mit unterschiedlichem Inhalt:

[
	[ "Einkaufsliste", [
		[ "Obst", [
			// Liste
			[
				[ 0, "Aepfel" ],
				[ 0, "Birne" ],
				[ 0, "Banane" ]
			]
		],
		[ "Gemuese", [
			// Liste
			[
				[ 0, "Kartoffeln" ],
				[ 0, "Zwiebeln" ]
			]
			// Text
			[
				[ "Den Schluessel Nicht vergessen!" ]
			]
		]
	],
	[ "Fund", [
		[ "", [
			// Liste
			[
				[ 0, "3 Gang" ],
				[ 1, "1 Regal" ],
				[ 2, "8 Fach" ]
			]
		]
	],
	[ "Wertetabelle", [
		[ "", [
			// Tabelle
			[
				[ "Fett", "8.7%" ],
				[ "kolenhydrate", "80%" ]
			]
		]
	]
]

Ich hab es seeehr statisch hinbekommen. Mein Script arbeitet maßgeblich mit mit Tabstopps und EOL, hat zur Überprüfung jeder Zeile gehäuft switch case verweise zu den funktionen die eine zeile funktionsspezifisch behandeln.

Ich möchte es besser, kompetenter machen und hab dazu den Begriffen Tokenizer Lexer und Parser überflogen eben was so ein Compiler eben tut. Aber ich bezweifle stark, das ich einen Compiler für die trivialeste Dinge, wie meine Einkaufsliste, benötige um daraus ein hashmap zu machen.

Ich benötige nur Theorie eines z.B. WYSIWYG-Editoren auf HTML Basis. Ist da win Präprozessor am Werk und wenn ja wie ist der Aufbau? Ähnlich wie bei Kompilern???

lgmb

[Rolf B]

Hallo MB,

Ich benötige nur Theorie eines z.B. WYSIWYG-Editoren auf HTML Basis.

Nein. Das ist kein WYSIWYG Editor. Es ist definitiv ein Parser.

Lexer und Parser sind nur die halbe Miete. Je nach Syntax der verwendeten Notation braucht es danach noch semantische Interpretation.

Man kann nun aufwändig eine EBNF-Grammatik formulieren, die deine "Sprache" definiert, und dafür dann einen Lexer und einen Parser bauen. Das geht, ich hab's auch mal angefangen, aber dann abgebrochen.

Denn bei Dir ist es einfacher. Das Zeilenende ist ein eindeutiger Trenner, und du hast genau 6 Zeilentypen: Level-1 Key, Level-2 Key, Text, Listenpunkt, Tabellenzeile.

Diese 6 Zeilentypen kannst Du recht gut mit Regexen erkennen und zerlegen. Das solltest Du im ersten Schritt tun, und basierend darauf ein Array aus Zeileninformationen erzeugen. Eine solche Zeileninformation besagt, was für ein Typ von Zeile das ist und welche relevanten Daten drinstehen (Key, Einrücktiefe bei Listen, Text-Array).

Dieser Programmteil sollte noch nichts von der weiteren Struktur der Einkaufsliste wissen. Er hat nur seine 3 oder 4 Regexe, die Level-1 Key, Level-2 Key, Liste und Text/Tabellenzeile erkennen. Text und Tabellenzeile sind im Prinzip nur an der Anzahl der Texte unterscheidbar, deswegen bietet sich da eine gemeinsame Regex an und du prüfst nur, wieviele tab-getrennte Texte du darin gefunden hast. Je nachdem, welche Regex getroffen hat (oder ob es eine Leerzeile war) baust Du die entsprechene Zeileninformation auf und schiebst sie in ein Array. Punkt!

Daraus baust Du ein Array aus Level-1 Einträgen auf. Ein solcher Eintrag besteht aus einem Key und einem Array aus Level-2 Einträgen. D.h. sobald Du einen neuen Level-1 Key findest, ist der Level-1 Eintrag, den Du gerade baust, fertig und Du beginnst einen neuen.

In einem Level-2 Eintrag musst Du unterscheiden. Du kannst - wenn dein Beispiel vollständig ist - eine Liste finden, eine Wertetabelle oder Text. D.h. du musst prüfen, ob Du einen dieser drei Zeilentypen hast. Eventuell musst Du, wenn Du eine Zeile analysierst, auch berücksichtigen, in welchem Typ von Gruppe Du bist. In einer Punkteliste? Hab ich noch gar keine Liste? Das kann einfach oder kompliziert sein, je nachdem, welche Varianten du erlauben willst.

Sicherlich sieht dein aktueller Code ähnlich aus, vermengt aber möglicherweise die Schritte 1 und 2 und verwendet vielleicht auch keine Regexe. Aber irgendwie muss die Programmstruktur die Struktur des Eingabedokuments wiederspiegeln, oder Du verwendest einen generischen Parser, der eine Grammatik vorgegeben bekommt. Dann ist die statische Struktur die Grammatik. Aber irgendwo muss die Definition der Struktur sein.

Du könntest Dich auch mal mit YAML beschäftigen. Das ist deiner Einkaufsliste sehr ähnlich, und für YAML gibt es fertige Interpreter, die daraus ein Objekt machen, welches Du dann in einen JSON-String umwandeln kannst.

Rolf

[MB]

moin,

ok schon mal echt herzlichen Dank zur Bstimmung meines Problemes! extrem blöderweise aber hat die Sprache keinen Regex - wird aber definitiv noch durch eine neuere Version kommen - und ich benötige diese lösung möglichst schnell aus meine fingern gesorgen.

Ich schätze ich muss das allein durchstehen, aber deinen Rat beherzigen und gern aufnehmen, was du gesagt hast. Den ansatz habe ich ja bereits hinter mir wie du weist 😉. Den source code werde ich auf GitHunb posten.

lgmb

[Rolf B]

Hallo MB,

okay, wenn Du keine Regex hast, dann musst Du die Zeilentypen eben von Hand erkennen. Das lässt sich ja durch Aufsuchen von :, *, [ und ] ganz gut machen.

Die Zweiteilung in "Zeileninfos bilden" und "Infos aggregieren" solltest Du auf jeden Fall einbauen.

Welche Sprache ist das? Eine selbstgemachte? Oder was bekanntes?

Ist das wirklich ein Einkaufszettel? Oder ist der nur ein Muster für das eigentliche Problem?

Spricht irgendwas gegen YAML? Einen Parser dafür gibt's für viele Sprachen.

Rolf

[MB]

moin,

okay, wenn Du keine Regex hast, dann musst Du die Zeilentypen eben von Hand erkennen. Das lässt sich ja durch Aufsuchen von :, *, [ und ] ganz gut machen.

so habe ich es ja gemacht

Die Zweiteilung in "Zeileninfos bilden" und "Infos aggregieren" solltest Du auf jeden Fall einbauen.

das ebenfalls

Welche Sprache ist das? Eine selbstgemachte? Oder was bekanntes?

eigentlich sind es Script Header Kommentare die blöderweise mehr oder weitaus weniger einer Syntax folgen. Das sind eben die, die ich hier im Thread vorgestellt habe. Es gibt bloderweise aber massive Abweichungen 😟.

Ist das wirklich ein Einkaufszettel? Oder ist der nur ein Muster für das eigentliche Problem?

Nur n Muster 😉

Spricht irgendwas gegen YAML? Einen Parser dafür gibt's für viele Sprachen.

Das hat @Raketenstartbeauftrakter auch vorgeschlagen. Aber mit meinen Begründungen eher nich 😕.

lgmb

[Rolf B]

Hallo MB,

Welche Sprache ist das? Eine selbstgemachte? Oder was bekanntes?

eigentlich sind es Script Header Kommentare

Nee, in welcher Sprache programmierst Du das? Bestimmt nicht mit Header Kommentaren...

Rolf

[MB]

moin,

Welche Sprache ist das? Eine selbstgemachte? Oder was bekanntes?

eigentlich sind es Script Header Kommentare

Nee, in welcher Sprache programmierst Du das? Bestimmt nicht mit Header Kommentaren...

Sry, habe ich vergessen zu erwähnen. Ich entwickle mit der proprietäre Scriptsprache von Bohemia Interactive Studios (BIS) mit der Bezeichnung SQF.

Mein Absicht ist eigentlich nicht für BIS gedacht aber ich entwickle…

1. zum Zeitvertreib…
2. ausfreude…
3. um mich zu profilieren egal in welchem Code
4. für die BIS community

ich hoffe zu verstehst meine Intension.

lgmb

[MB]

moin,

nebenbei bemerkt: Ein - oder DAS - Erzeugnis von BIS war damals der ausschlaggebende Grund dafür, warum ich so früh die Affinität (unteranderem über Editoren) zu Code entwickelt habe 😀.

lgmb

[Raktenstartbeauftragter]

Ich würde anno 2020 über YAML nachdenken.

[1unitedpower]

Ich möchte es besser, kompetenter machen und hab dazu den Begriffen Tokenizer Lexer und Parser überflogen eben was so ein Compiler eben tut.

Da warst du schon in der richtigen Ecke unterwegs. Einen richtigen Lexer brauchst du nicht, den braucht man eigentlich nur, wenn die Sprache, die man parsen will, auch Schlüsselwörter wie "if", "while" und "for" benutzt. Ein Compiler ist auch zu viel des Guten, du brauchst lediglich einen Parser.

Die Sprache, die du parsen möchtest, hat eine Besonderheit und ist deshalb auch nicht ganz so einfach zu behandeln, wie es den Anschein macht. Deine Sprache benutzt die Einrückungstiefe einer Zeile, um die Verschachtelungssruktur zu bestimmen. Die meisten Sprachen benutzen stattdessen Klammerpaare, wie "[]" oder "{}". In der Theorie sagt man, dass deine Sprache kontextsensitiv ist. Das macht das Parsen deutlich schwieriger. Da steckt also der Teufel in einem kleinen Detail.

Grundsätzlich ist es meistens eine gute Idee das Problem, vor dem man steht, erstmal extrem zu vereinfachen und dafür eine Lösung zu finden. Also, lass uns doch erstmal einen einfachen Parser schreiben, der aus einem Text mit Zeileneinrückung ein verschachteltes Array macht. Der Einfachheit halber ignorieren wir auch erstmal Leerzeilen und Zeilen, die nur Tabs enthalten.

Outline

Hier ist schonmal die grobe Rahmenstruktur für den Algorithmus, die Details müssen wir noch einfügen:

const TOKEN_TAB = "\t";
const TOKEN_NEWLINE = "\n";

const STATE_INDENTATION = 0;
const STATE_CONTENT = 1;

function parse(input) {
  let state = STATE_INDENTATION;
  // TODO 1
  for (let char of input) {
    switch (state) {
      case STATE_INDENTATION:
        switch (char) {
          case TOKEN_TAB:
            // TODO 2
            break;
          case TOKEN_NEWLINE:
            // TODO 3
            break;
          default:
            // TODO 4
            break;
        }
        break;
      case STATE_CONTENT:
        switch (char) {
          case TOKEN_TAB:
            // TODO 5
          case TOKEN_NEWLINE:
            // TODO 6
            break;
          default:
            // TODO 7
            break;
        }
        break;
    }
  }
  // TODO 8
}

• Der Algorithmus durchläuft die Eingabe Zeichen für Zeichen, dafür ist die Schleife da.
• Wir unterscheiden nun zwei Zustände: Haben wir in der aktuell zu lesenden Zeile schon ein Symbol gelesen, dass kein Tab ist? Denn wenn das der Fall ist, lesen wir gerade richtigen Textinhalt. Ansonsten ermitteln wir noch die Verschachtelungsstruktur. Für diese Fallunterscheidung ist das äußere switch-Statement gedacht.
• Je nachdem, ob es sich bei dem gerade gelesenen Zeichen um einen Zeilenumbruch, ein Tab oder einen anderen Buchstaben handelt, ist eine andere Reaktion notwendig. Dafür sind die inneren switch-Statements da.

Wir füllen jetzt nach und nach die Lücken.

Todo 1

In die Lücke 1 kommen diverse Hilfsvariablen, die unser Algorithmus zum Arbeiten braucht.

let lineDepth = 0;
let previousLineDepth = 0;
let buffer = "";
let list = [];
let stack = [list];

• Die Variable lineDepth speichert die Einrückungstiefe der aktuell zu lesenden Zeile. Am Anfang einer Zeile (also wenn wir ein Zeilenumbruch gelesen haben) setzen wir die Variable auf 0. Und wir erhöhren Sie dann um 1 für jedes Tab, das wir am Zeileanfang lesen.
• Die Variable previousLineDepth speichert die Einrückungstiefe der zuletzt gelesenen Zeile. Wenn wir die beiden Variablen vergleichen, wissen wir, ob wir uns auf der selben Verschachtelungsebene wie in der Zeile zuvor befinden, ob wir tiefer gehen müssen, oder ob wir wieder eine oder mehrere Ebenen rauf gehen müssen.
• Die Variable buffer speichert den Textinhalt der aktuellen Zeile ohne die führenden Tabs. Am Zeilenanfang löschen wir den Inhalt. Und nachdem wir alle führenden Tabs gelesen haben, hängen wir Zeichen um Zeichen an diesen Buffer.
• Die Variable list speichert die aktuelle Liste, die wir bearbeiten.
• Die Variable stack speichert unfertige Listen, die wir noch nicht bis zum Ende gelesen haben. Immer, wenn wir festellen, dass wir uns eine Einrückungsebene tiefer befinden als in der Zeile zuvor, dann fangen eine neue Liste an und legen sie auf den Stack. Falls wir umgekehrt feststellen, dass wir uns eine Einrückungsebene über der zuletzt gelesenen Zeile gefinden, dann können wir die aktuelle Liste abschließen. D.h. wir nehmen sie vom dem Stack und fügen sie der Liste darunter als ein Listenelement hinzu.

Dass ich diese Hilfsvariable brauche, wusste ich nicht von Anfang an. Das hat sich nach und nach ergeben, während ich mir um die einzelnen Fälle in den switch-Statements Gedanken gemacht habe. Deshalb war es wichtig erstmal den Rahmenalgorithmus vor mir zu sehen. Außerdem ist das nicht die einzige Wahl für Hilfsvariablen. Bspw. ist previousLineDepth eigentlich unnötig, weil die darin gespeicherte Information sich auch aus der Stack-Tiefe ableiten lässt. Ich fand es so aber besser verständlich, und hab die Hilfsvariable deshalb definiert.

TODO 2

Der Zustand STATE_INDENTATION sagt uns, dass wir uns noch am Zeilenanfang befinden. Das aktuell gelesene Symbol ist ein Tab. Was müssen wir also machen?

lineDepth += 1;
if (lineDepth > previousLineDepth) {
  list = [];
  stack.push(list);
}

• Wir erhöhen erstmal die aktuelle Einrückungstiefe um 1.
• Dann überprüfen wir, ob wir uns nun eine Ebene tiefer befinden als zuvor. Wenn ja, dann machen wir eine neue Arbeitsliste auf und legen Sie oben auf den Stack.

TODO 3

Der Zustand STATE_INDENTATION sagt uns, dass wir uns noch am Zeilenanfang befinden. Das aktuell gelesene Symbol ist ein Zeilenumbruch. Was müssen wir also machen?

throw new Error("Unexepcted newline.");

• Wie am Anfang geschrieben, wir ignorieren Leerzeilen und Zeilen, die nur aus Tabs bestehen. Wir produzieren deshalb nur einen Parse-Error.

TODO 4

Der Zustand STATE_INDENTATION sagt uns, dass wir uns noch am Zeilenanfang befinden. Das aktuell gelesene Symbol ist kein Sonderzeichen. Was müssen wir also machen?

while (lineDepth < previousLineDepth) {
  previousLineDepth -= 1;
  const finishedList = stack.pop();
  list = stack[stack.length - 1];
  list.push(finishedList);
}
buffer += char;
state = STATE_CONTENT;

• Wir überprüfen zunächst, ob wir uns eine oder mehrere Ebenen über der Einrückungsstufe der zuletzt gelesen Zeile befinden. Das heißt, ob wir eine Ebene abschließen können. Für jede zu schließende Ebene vermindern wir zunächst die Variable previousLineDepth, wir nehmen die oberste Liste vom Stack und fügen sie der Liste darunter als Listenelement hinzu. Die Variable previousLineDepth hat in diesem Zusammenhang einen irreführenden Namen. Sie speichert eigentlich nur Anzahl der noch nicht abgeschlossenen Ebenen.
• Anschließend fügen wir das gerade gelesen Zeichen dem Textbuffer hinzu.
• Schlussendlich wechseln wir den internen Zustand unseres Parsers. Wir ermitteln nun nicht mehr die Verschatelungsebene, sondern lesen Textinhalt.

TOOD 5 und TODO 7

Der Zustand STATE_CONTENT sagt uns, dass wir Textinhalt lesen. Das aktuell gelesene Symbol ist kein Zeilenumburch. Beachte, dass ein Tab in der Zeilenmitte auch kein Sonderzeichen ist. Wir können die Fälle 5 und 7 deshalb gleich behandeln. Was müssen wir also machen?

buffer += char;

Wir fügen das atuell gelesene Zeichen dem Textbuffer hinzu, ansonsten müssen wir nichts unternehmen.

TODO 6

Der Zustand STATE_CONTENT sagt uns, dass wir Textinhalt lesen. Das aktuell gelesene Symbol ist ein Zeilenumburch. Was müssen wir also machen?

previousLineDepth = lineDepth;
lineDepth = 0;
list.push(buffer);
buffer = "";
state = STATE_INDENTATION;

• Wir setzen die Einrückungstiefe der vorherigen Zeile auf die Einrückungstiefe der aktuellen Zeile.
• Wir setzen die Einrückungstiefe der aktuellen Zeile zurück auf 0.
• Wir fügen den Textbuffer der aktuellen Arbeitsliste hinzu und löschen den Textbuffer.
• Wir wechseln wieder in den STATE_INDENTATION-Zustand.

TODO 8

Wir sind nun den gesamten Eingabe-String durchlaufen. Wir müssen jetzt noch gucken, welche Hilfsvariablen noch unfertige Teilresultate erhalten und die zusammensetzen.

list.push(buffer);
while (1 < stack.length) {
  const finishedList = stack.pop();
  list = stack[stack.length - 1];
  list.push(finishedList);
}
return stack.pop();

• Wir führen nochmal die gleichen Schritte aus, die auch bei einem Zeilumbruch anfallen. Auf diese Weise schließen wir alle noch offenen Ebenen ab.
• Schlussendlich liegt unser Endergebnis als einziges Element auf dem Stack. Das geben wir jetzt zurück.

Zusammenfassung

Den kompletten Algorithmus findest du inkl. einiger Tests auch bei Stackblitz. Da fehlen natürlich noch etliche Details, die in deinem ursprünglichen Format vorgesehen waren, aber hier vernachlässigt werden. Ich würde an deiner Stelle damit beginnen, das Handling für Leerzeilen hinzuzufügen. Ich habe mir hier nur den kontextsenstiven Teil deines Problems rausgepickt, habe aber an andere Stelle im Forum auch schon über kontextfreie Parser geschrieben.

[MB]

moin,

Ich möchte es besser, kompetenter machen und hab dazu den Begriffen Tokenizer Lexer und Parser überflogen eben was so ein Compiler eben tut.

Da warst du schon in der richtigen Ecke unterwegs.

perfekt 😀

Einen richtigen Lexer brauchst du nicht […] du brauchst lediglich einen Parser.

ok?

[…]. Deine Sprache benutzt die Einrückungstiefe einer Zeile. […] In der Theorie sagt man, dass deine Sprache kontextsensitiv ist.

euer wissen möchte ich gerne haben 😕.

[…] Das macht das Parsen deutlich schwieriger.

Das was ich als beispiel geschrieben habe habe ich schon geparset, aber unschön und nicht gegliedert.

Grundsätzlich ist es meistens eine gute Idee das Problem, vor dem man steht, erstmal extrem zu vereinfachen und dafür eine Lösung zu finden. […]

Dann hatte ich wohl nix falsches im sinn gehabt 😉. Genauso habe ich es gemacht, aber mich nur mit der zweiten einrücktungstiefe beschränkt. Hilfsvariablen benötige ich keine, da ich das alles über eine rekursive funktion gelöst hab, die nichts zurück gibt und einen string extern behandelt. So kann man bis ins n-te hinein verschachteln. Ich weis aber nicht ob's gut ist 😕.

[…]. Ich würde an deiner Stelle damit beginnen, das Handling für Leerzeilen hinzuzufügen.

Ich müsste zunächst alle anderen non-printable characters ansehen

<end>
--->Title:<end>
--->--->-.listpoint<end>
<end>
--->--->Definition:--->{--->*}Description<end>
<end>
--->--->collum.1--->{--->*}-.collum.2<end>
<end>

Legende

• . steht für Leerzeichen
• <end> steht für Zeilenumbruch
• ---> steht für Tabulator
• [character*] steht für Zeichen n mal

Ich habe mir hier nur den kontextsenstiven Teil deines Problems rausgepickt, habe aber an andere Stelle im Forum auch schon über kontextfreie Parser geschrieben.

schaue ich mir sehr gern an - aber heute, nicht gestern 😉.

lgmb

[MB]

moin,

Ich möchte es besser, kompetenter machen und hab dazu den Begriffen Tokenizer Lexer und Parser überflogen eben was so ein Compiler eben tut.

Da warst du schon in der richtigen Ecke unterwegs. Einen richtigen Lexer brauchst du nicht, den braucht man eigentlich nur, wenn die Sprache, die man parsen will, auch Schlüsselwörter wie "if", "while" und "for" benutzt.

Ich hab jetzt ne konzeptionelle Idee von Tokenizer und Parser. Melde mich hoffentlich mit meinem sehr trivialen Parser im SQF Format auf GitHub wieder 😉.

lgmb