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