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

[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.