In der Informatik wird zwischen verschiedenen Darstellungsebenen von Termen unterschieden. Der gleiche Term kann auf unterschiedliche Weise dargestellt werden und verschiedene Terme können zu demselben Wert ausgewertet werden. Die Darstellung eines Terms wird als seine Syntax bezeichnet, der Wert zu dem er ausgewertet wird, als seine Semantik. Zum Beispiel sind 1 + 2 und 2 + 1 zwei verschiedene Terme mit derselben Semantik. Im folgenden werden wir sehen, dass auch ein und derselbe Term mit unterschiedlicher Syntax dargestellt werden kann.
Eine Möglichkeit, Terme auf unterschiedliche Weise darzustellen, ist es, Klammern zu schreiben, die bereits durch Präzedenzregeln implizit vorgegeben sind. Zum Beispiel sind 3 + math.sqrt(x**2 + 1) und 3 + math.sqrt((x**2)+1) der gleiche Term, da Potenzierung (**) stärker bindet als Addition (+), die zusätzlichen Klammern an der Termstruktur also nichts ändern. Durch vollständige Klammerung kann die Struktur eines Terms ohne Hilfe von Präzedenzregeln eindeutig kenntlich gemacht werden. Eine andere Möglichkeit sind sogenannte Termbäume, wie der folgende, der den obigen Term repräsentiert:
Hier stehen Funktionssymbole oberhalb ihrer Argumente und die Klammerung ist durch die Baumstruktur kenntlich gemacht1.
In Python werden Funktionsnamen wie math.sqrt vor ihren Argumenten notiert (Präfix-Notation) und zweistellige Operatoren wie + werden zwischen ihren Argumenten notiert (Infix-Notation).
Wir können auch Operatoren in Präfix-Notation schreiben:
+(3,math.sqrt(+(**(x,2),1)))
Wenn die Stelligkeit (also die Anzahl der Argumente) aller Funktions- und Operator-Symbole eindeutig festgelegt ist, können wir alle Klammern weglassen, ohne dass die Termstruktur dadurch verloren geht:
+ 3 math.sqrt + ** x 2 1
Da wir die Stelligkeiten aller Funktions- und Operator-Symbole kennen, können wir den zu dieser Darstellung gehörigen Termbaum eindeutig rekonstruieren. Wir können auch umgekehrt die Präfix-Notation aus dem Termbaum ableiten, indem wir zuerst die Wurzel des Baums notieren und dann mit den Argumenten genauso verfahren. Wir notieren also danach die Wurzel des Teilbaums für das erste Argument, dann dessen Argumente und so weiter. Wenn dieser Teilbaum abgearbeitet ist, verfahren wir entsprechend mit den weiteren Argumenten.
Analog zur Präfix-Notation wird auch die Postfix-Notation betrachtet. Diese kann aus dem Termbaum abgeleitet werden, indem die Wurzel jedes Teilbaums nicht vor sondern nach den zugehörigen Argumenten notiert wird. Für das obige Beispiel ergibt sich:
3 x 2 ** 1 + math.sqrt +
Genau wie aus der Präfix-Notation kann auch aus der Postfix-Notation der zugehörige Termbaum anhand der Stelligkeiten rekonstruiert werden.
Die (wie bei der Präfix-Notation) klammerfrei eindeutige Darstellung ist nur ein Vorteil der Postfix-Notation. Der eigentliche Grund für die Relevanz der Postfix-Notation ist, dass sie sich besonders gut eignet, um Terme mit Hilfe einer sogenannten Stackmaschine auszuwerten. Bevor wir uns dem dieser Auswertung zu Grunde liegenden Mechanismus widmen, lernen wir jedoch unsere ersten Datenstrukturen kennen.
In der Informatik wachsen Bäume von oben nach unten. ↩︎