Treffer: Ein Ausflug in den Compilerbau. : Syntaktische Analyse und Berechnung arithmetischer Ausdrücke.

Aus der Einleitung: Der Compilerbau ist ein (aufgrund der komplexen Materie) in der Schule vernachlässigtes Teilgebiet der praktischen Informatik, obwohl sich viele Berührungspunkte zu anderen Themen aufzeigen lassen: Zur theoretischen Informatik (insbesondere zu den formalen Sprachen und Grammatiken), zur Mathematik und schließlich zu Datenstrukturen (insbesondere zu Listen, Stapeln und Bäumen). Ausgangspunkt der Unterrichtsreihe war ein in JAVA programmierter Taschenrechner, der im Rahmen einer Reihe zur Algorithmik an eine Mathematikbibliothek angebunden war. Die Schüler hatten darin einige Algorithmen (Quadratwurzel, trigonometrische Funktionen, Exponentialfunktion etc.) numerisch oder rekursiv implementiert. Beim Vergleich mit einem realen Taschenrechner kam dann die Frage auf, wie man die Klammerrechnung realisieren könne. Meinen Einwand, das sei gar nicht so einfach, ließen die Schüler nicht gelten, sodass ich mir diesbezüglich Gedanken machen musste. Im Folgenden wird zunächst der Aufbau (vereinfachter) arithmetischer Ausdrücke untersucht und durch Regeln beschrieben. Es erweist sich als günstig, den Begriff der "formalen Sprache" und der (hier: kontextfreien) "Grammatik" einzuführen. Zur Syntaxprüfung wird das Verfahren des "rekursiven Abstiegs" erarbeitet und in JAVA implementiert. Zwecks Auswertung arithmetischer Ausdrücke werden diese zunächst in Postfix-Notation übersetzt, um sie klammerfrei zu machen und dann mithilfe eines Kellerspeichers berechnet.
From the introduction (translation): Compiler building is a neglected branch of Practical Computer Sciences, although many points of contact to other topics can be demonstrated: to Theoretical Computer Science (particularly to formal languages and grammars), to mathematics, and finally to data structures (particularly to lists, stacks, and trees). The starting point of the teaching unit was a pocket calculator programmed in JAVA that was linked to a mathematics library within the framework of a teaching unit on algorithms. The students had some algorithms (square root, trigonometric functions, exponential functions etc.) implemented, numerically or recursively. When doing a comparison with a real calculator the question arose how to carry out calculations with parenthetical expressions. In the following, the structure of (simplified) arithmetic terms is examined and described by rules. It turns out to be convenient to introduce the concept of "formal language" and (here: context-free) "grammar". For checking the syntax, the procedure of "recursive descent" is developed and implemented in JAVA. Arithmetic terms are first translated into postfix notation, to write them without parantheses, and then calculated with a push-down stack.