Termparser

Als Internetnutzer sind wir heute gewohnt, dass eine Internetseite grafisch ansprechend und oft so gestaltet ist, dass es Möglichkeiten zu Interaktion gibt. Den Quellcode, der das ermöglicht kannst du dir ansehen, wenn du auf einer Internetseite mit der rechten Maustaste auf eine leere Stelle der Seite klickst und dann Seitenquelltext anzeigen auswählst. In dem Fenster, welches sich dann öffnet, siehst du eine Mischung aus HTML, CSS und JavaScript. Dieser Text wird vom Server an deinen PC geschickt und der Browser (Firefox, Edge, Chrome, Opera,...) übersetzt die Texte in eine ansprechend aussehende Internetseite.

Das ist eine der Hauptaufgaben des Internetbrowsers. Er liest einen Text ein, erkennt darin Anweisungen, wertet diese aus und stellt damit die Internetseite dar. Diesen Vorgang nennt man PARSING (= analysieren).

Wie die Analyse eines Textes durch den Computer erfolgt, soll in diesem Projekt am Beispiel eines mathematischen Terms gezeigt werden. Ein mathematischer Term ist kurz und das Ergebnis kannst du selbst nachrechnen. Die Analyse des Quellcodes einer Internetseite ist wesentlich komplexer, aber wenn du dieses Projekt durchdenkst, bekommst du eine Idee, wie Texte in Anweisungen für den Computer übersetzt werden können.


Schritt 1: Übersetzung des Terms in die Mathematik

Eine mathematischer Term wie 3 + 2 * (286-12) wird berechnet, indem mathematische Regeln angewendet werden. Aus der 5. Klasse kennst du z.B. die grundlegende Rechenregel: Zuerst Klammer, dann Potenz, dann Punkt, dann Strich und dann von links nach rechts. Ein Computer kennt das alles nicht. Ihm muss das beigebracht werden. Dazu wird der Text eingelesen und in einem ersten Schritt in mathematische Symbole übersetzt. 3 ist eine Zahl, +, * und - sind mathematische Operatoren. ( ist eine öffnende/linke Klammer und ) ist eine schließende/rechte Klammer.


Schritt 2: Übertragung des Terms in eine Datenstruktur

Nachdem die einzelnen Zeichen einen mathematischen Sinn bekommen haben, müssen die Rechenregeln angewendet werden. Der Computer versteht solche Regeln nicht und kann diese auch nicht selbstständig anwenden. Deswegen stellt man den Term so genial dar, dass der Computer immer nur eine einzige Rechnung ausführen muss.

Den Algorithmus zu Übertragung eines Terms in eine für einen Computer berechenbare Datenstruktur hat sich der niederländische Informatiker Edsger W. Dijkstra ausgedacht. Da die Funktionsweise des Algorithmus an einen Rangierbahnhof erinnert, wird dieser auch Shunting-yard-Algorithmus genannt.

Der Algorithmus im Pseudo-Code:

Stack mit LIFO-Prinzip und Ausgabe-Queue anlegen.
SOLANGE Tokens verfügbar sind:
    Token einlesen.
    WENN Token IST-Zahl:
        Token ZU Ausgabe.
    ENDEWENN
    WENN Token IST-Funktion:
        Token ZU Stack.
    ENDEWENN
    WENN Token IST-Argumenttrennzeichen:
        BIS Stack-Spitze IST öffnende-Klammer:
            Stack-Spitze ZU Ausgabe.
            FEHLER-BEI Stack IST-LEER:
                GRUND (1) Ein falsch platziertes Argumenttrennzeichen.
                GRUND (2) Der schließenden Klammer geht keine öffnende voraus.
            ENDEFEHLER
        ENDEBIS
    ENDEWENN
    WENN Token IST-Operator
        SOLANGE Stack IST-NICHT-LEER UND Stack-Spitze IST Operator UND Token IST-linksassoziativ UND Präzedenz von Token IST-KLEINER Präzedenz von Stack-Spitze
            Stack-Spitze ZU Ausgabe.
        ENDESOLANGE
        Token ZU Stack.
    ENDEWENN
    WENN Token IST öffnende-Klammer:
        Token ZU Stack.
    ENDEWENN
    WENN Token IST schließende-Klammer:
        BIS Stack-Spitze IST öffnende-Klammer:
            FEHLER-BEI Stack IST-LEER:
                GRUND (1) Der schließenden Klammer geht keine öffnende voraus.
            ENDEFEHLER
            Stack-Spitze ZU Ausgabe.
        ENDEBIS
        Stack-Spitze (öffnende-Klammer) entfernen
        WENN Stack-Spitze IST-Funktion:
            Stack-Spitze ZU Ausgabe.
        ENDEWENN
    ENDEWENN
ENDESOLANGE
BIS Stack IST-LEER:
    FEHLER-BEI Stack-Spitze IST öffnende-Klammer:
        GRUND (1) Es gibt mehr öffnende als schließende Klammern.
    ENDEFEHLER
    Stack-Spitze ZU Ausgabe.
ENDEBIS

Quelle: Shunting-yard-Algorithmus

Über diesen Algorithmus könntest du jetzt lange nachdenken. Aber tröste dich, der Autor dieses Algorithmus gilt als einer der Väter moderner strukturierter Programmiersprachen.


Schritt 3: Berechnung des Ergebnisses

Der Abstrakte-Syntax-Baum, in den der Term übertragen wird und den du dir mit Hilfe des folgenden Programms ansehen kannst, erinnert dich vielleicht an die Termbäume aus dem Mathematikunterricht. Dort konnte dein Gehirn das Ergebnis berechnen, jetzt muss das dem Computer beigebracht werden.

Der Quellcode dazu ist:

var berechne = function(asb) {
    var ergebnis;

    switch(asb.token) {
        case '+':
            ergebnis = parseFloat(berechne(asb.linkerKindKnoten)) + parseFloat(berechne(asb.rechterKindKnoten));
            break;
        case '*':
            ergebnis = parseFloat(berechne(asb.linkerKindKnoten)) * parseFloat(berechne(asb.rechterKindKnoten));
            break;  
        case '-':
            ergebnis = parseFloat(berechne(asb.linkerKindKnoten)) - parseFloat(berechne(asb.rechterKindKnoten));
            break;
        case '/':
            ergebnis = parseFloat(berechne(asb.linkerKindKnoten)) / parseFloat(berechne(asb.rechterKindKnoten));
            break;
        case '^':
            ergebnis = Math.pow(parseFloat(berechne(asb.linkerKindKnoten)), parseFloat(berechne(asb.rechterKindKnoten)));
            break;
        case 'sin':
            ergebnis = Math.sin(parseFloat(berechne(asb.rechterKindKnoten)));
            break;
        case 'cos':
            ergebnis = Math.cos(parseFloat(berechne(asb.rechterKindKnoten)));
            break;          
        default:
            ergebnis = parseFloat(asb.token);
    }
    return ergebnis;
}

Wie du siehst, wird in dieser Funktion berechne die eigene Funktion berechne aufgerufen. Diese Programmiermethode nennt man rekursive Programmierung. Im Internet oder im Informatikunterricht der Oberstufe lernst du mehr darüber.


Der Termparser

Der Quellcode für den Termparser basiert auf der Arbeit: Parsing math expressions with JavaScript, 06.01.2018 (07.00 Uhr) von Shalvah A.

In einem neuen Fenster starten: Wellenmaschine