xscDevBlog – LastSharp & Co.

Einen wichtigen Schritt haben wir an dieser Stelle bereits hinter uns: Der hier beschriebene Lexer verwandelt eine Eingabesequenz wie “1+3*(4-2)”  in eine Liste von Tokens mit Typ und Wert:

zahl        :    1
operator    :    +
zahl        :    3
operator    :    *
open        :    (
zahl        :    4
operator    :    -
zahl        :    2
close       :    )

Damit haben wir eine maschinenlesbare Repräsentation des gewünschten Ausdrucks – allerdings keine Garantie dafür, dass dieser syntaktisch korrekt ist. Ebensowenig kann eine Maschine, die diese Liste nun vorgelegt bekommt, “einfach mal so” den Wert des Ausdrucks berechnen, da ihr Informationen zur Auswertungsreihenfolge fehlen. (Wenn 1+3 zuerst berechnet wird, lautet das Ergebnis 8, wenn 3*(4-2) zuerst berechnet wird, lautet es 7.)

Wir brauchen also eine Darstellung unseres Ausdrucks, die bezüglich der Reihenfolge der Auswertung eindeutig ist und eine Maschine, die diese erstellt  – und wie könnte es anders sein: auch dieses Problem wurde bereits einmal gelöst.

Wandeln wir also auf den Spuren von Edsger W. Dijkstra.

Reverse Polish Notation

Der polnische Mathematiker Jan Łukasiewicz entwickelte etwa 1920 die sog. Polnische Notation für arithmetische Ausdrücke, die sich dadurch auszeichnete, dass jedem Operator (“+”, “-”, …) direkt seine Operanden (Zahlen oder weitere arithmetische Ausdrücke) folgten. Durch diese Präfixnotation ergibt sich die Möglichkeit, auf Klammern, Kommas, etc… verzichten zu können, wenn man weiß, wie viele Operanden ein Operator benötigt:

1+2+3         ==>        + 1 + 2 3           (auch: + + 1 2 3)
1+3*(4-2)     ==>        + 1 * 3 - 4 2
(3+4)*(4*3-1) ==>        * + 3 4 - * 4 3 1

Anhand des letzten Beispiels will ich die Auswertung so eines Ausdrucks beschreiben. Das Prinzip ist: “Werte den Ausdruck, der nur Zahlen als Operanden hat, als nächstes aus!”

   * + 3 4 - * 4 3 1        |   Das + bezieht sich auf 3 und 4!
=  * 7     - * 4 3 1        |   Das * bezieht sich auf 4 und 3!
=  * 7     - 12    1        |   Das - bezieht sich auf 12 und 1!
=  * 7     11               |   Das * bezieht sich auf 7 und 11!
=  77

Wie bereits erwähnt, funktioniert so eine Auswertung nur, wenn man weiß, wie viele Operanden/Parameter ein Operator/eine Funktion benötigt. Deswegen haben wir uns bei der Entwicklung des Lexers auch die Mühe gemacht, diese Information immer irgendwie bei der Hand zu haben.

Was Dijkstra nun gemacht hat, war, aus der Präfix- eine Postfixnotation zu machen, die sog. Reverse Polish Notation (RPN). Hier stehen nun alle Operanden vor dem Operator zu dem sie gehören:

1+2+3         ==>        1 2 3 + +          (auch: 1 2 + 3 +)
1+3*(4-2)     ==>        1 3 4 2 - * +
(3+4)*(4*3-1) ==>        3 4 + 4 3 * 1 - *

Sowohl Polish Notation als auch Reverse Polish Notation beschreiben (unter der Voraussetzung, dass man die Anzahl der Parameter/Operanden kennt) eine eindeutige Auswertungsreihenfolge. Bei der letztlichen Auswertung ist die RPN aber ihrem Vorfahren in Bezug auf Speicherverbrauch und Verständlichkeit dann doch voraus. Die Regel: “Wenn ein Operator auftaucht, werte ihn aus!”

Wir benötigen hierbei einen Stack, der die Zwischenergebnisse speichert und der diese bei Auftreten eines Operators zur Berechnung zur Verfügung stellt.

----------------------------------------------------------------------------------
Eingabe            | Stack    |  Kommentar
----------------------------------------------------------------------------------
3 4 + 4 3 * 1 - *  |          |  Beginn des Algorithmus
4 + 4 3 * 1 - *    | 3        |  Zahl (3): auf den Stack!
+ 4 3 * 1 - *      | 3 4      |  Zahl (4): auf den Stack!
4 3 * 1 - *        | 7        |  Operator (+): hole 3 und 4, berechne, speichere
3 * 1 - *          | 7 4      |  Zahl (4): auf den Stack!
* 1 - *            | 7 4 3    |  Zahl (3): auf den Stack!
1 - *              | 7 12     |  Operator (*): hole 4 und 3, berechne, speichere
- *                | 7 12 1   |  Zahl (1): auf den Stack!
*                  | 7 11     |  Operator (-): hole 12 und 1, berechne, speichere
                   | 77       |  Operator (*): hole 7 und 11, berechne, speichere
                   | 77       |  Eingabe leer, Ergebnis auf Stack.

Dies umzusetzen ist kein großes Problem und spricht in jedem Fall für die Reverse Polish Notation als Darstellung eines auszuwertenden Ausdrucks. Und dann wäre da noch die kleine, aber feine Tatsache, dass es einen Algorithmus gibt, der die Umwandlung “normaler” (Infix-)Ausdrücke (à la “1+2*f(3)”) in diese Notation vornimmt.

Der Shunting-Yard-Algorithmus

Der Shunting-Yard-Algorithmus (zu deutsch: Rangierbahnhofalgorithmus) ist eine ebenfalls von Dijkstra entwickelte Methode zur Umwandlung von Infix-Ausdrücken in Postfix-Notation. Sein Name kommt daher, dass seine Funktionsweise den Abläufen in einem Rangierbahnhof entspricht: alle terminalen Symbole (z.B. Zahlen, Variablen, …) sind Waren und Güter, die von Zügen (den nichtterminalen Symbolen wie Operatoren und Funktionen) mitgenommen werden müssen.

Die folgende Animation zeigt (vereinfacht) das Prinzip des Algorithmus. Er basiert darauf, dass in der Zugwarteschlange immer der Zug mit der höchsten Priorität (in der Realität z.B. die Geschwindigkeit) ganz vorne steht. Will sich ein langsamerer Zug einreihen, müssen also zuerst alle schnelleren Züge losgefahren sein. (Jeder Zug kann beliebig viele Waren transportieren und nimmt beim Abfahren alle verfügbaren mit! Es kann also auch passieren, dass ein Zug leer losfährt.)

Übertragen auf die Reverse Polish Notation: Die Operationen mit der niedrigsten Priorität werden zuletzt ausgeführt, entsprechen also den langsamsten Zügen. Mit ein wenig Überlegung sieht man, dass der Algorithmus also genau das Ergebnis liefern wird, was wir haben wollen!

Die Waren-Schlange kann übrigens in der letztlichen Implementierung entfallen, wenn man alle Waren einfach direkt zum Ausgang schiebt und immer nur den Zug voranstellt, der sie mitnehmen soll.

Hinzu kommt noch die Behandlung von Klammern und Trennsymbolen (z.B Kommas). Ich möchte den Algorithmus hier nicht im Detail aufschreiben, da der zugehörige Wikipedia-Artikel (englisch) eine genaue Beschreibung enthält.

Wichtig ist:

• Der Algorithmus kann Operatoren, Terminalsymbole, Klammern, Trennzeichen und Funktionen verarbeiten, d.h. wenn wir spezielle Konstrukte haben (z.B. “def x=a*(b-1)”) müssen wir diese erst in Funktionsform bringen. (z.B. “definition(x, a*(b-1))”)
• Der Algorithmus hat eine Laufzeit in O(n), d.h. er ist vergleichsweise effizient.

Reverse Polish Notation vs. Syntaxbaum

Eine weitere Möglichkeit, die Ausführungsreihenfolge eindeutig festzulegen, ist das Erstellen eines Syntaxbaumes. Für den Ausdruck “1+2*sqrt(e)” hat dieser z.B. die folgende Form:

               operator : +
              /            \
        integer : 1     operator : *
                       /            \
                  integer : 2   function : sqrt
                                     |
                                constant : e

Die Auswertung erfolgt von unten nach oben, d.h. bei der letztlichen Berechnung würden folgende Schritte ausgeführt:

e                 => 2.71
sqrt(2.71)        => 1.65
2                 => 2
2 * 1.65          => 3.3
1                 => 1
1 + 3.3           => 4.3

Das besondere ist, das jeder Syntaxbaum sehr einfach in Reverse Polish Notation umgewandelt werden kann und jede RPN ebenso einfach in einen Syntaxbaum.

Für erstere Umwandlung durchläuft man den Baum als Post-Order-Traversierung, d.h. man schreibt ausgehend von der Wurzel zuerst die Post-Order-Notation der Kindknoten auf und hängt anschließend den Wert der Wurzel daran an.

Für die entgegensetzte Transformation tut man so, als würde man die RPN-Notation auswerten (siehe oben!), aber anstatt auf dem Stack Zwischenergebnisse zu speichern, sichert man dort die Teilbäume:

-----------------------------------------------------------------------------------
Eingabe            | Stack           |  Kommentar
-----------------------------------------------------------------------------------
3 4 + 4 3 * 1 - *  |                     |  Beginn des Algorithmus
4 + 4 3 * 1 - *    | 3                   |  Zahl (3): Blatt auf den Stack!
+ 4 3 * 1 - *      | 3 4                 |  Zahl (4): Blatt auf den Stack!
4 3 * 1 - *        | +(3,4)              |  Operator (+): hole Blätter, bilde Baum
3 * 1 - *          | +(3,4) 4            |  Zahl (4): Blatt auf den Stack!
* 1 - *            | +(3,4) 4 3          |  Zahl (3): Blatt auf den Stack!
1 - *              | +(3,4) *(4,3)       |  Operator (*): hole Blätter, bilde Baum
- *                | +(3,4) *(4,3) 1     |  Zahl (1): Blatt auf den Stack!
*                  | +(3,4) -(*(4,3), 1) |  Operator (-): hole Blatt/Teilbaum, bilde Baum
[...]

Ergebnis: *(+(3,4), -(*(4,3), 1))

Ich hoffe die Baumnotation “Wurzel(Teilbaum1, Teilbaum2, …)” ist verständlich.

Es gibt hierzu noch eine weitere wichtige Anmerkung:
Jeder Algorithmus, der die Reverse Polish Notation eines Ausdrucks erstellen kann, kann so modifiziert werden, dass er einen Syntaxbaum erstellt und jeder Algorithmus, der einen Syntaxbaum erstellt, kann auch die RPN eines Ausdrucks erstellen!

Beide Darstellungen sind also gleichwertig in der Funktionalität, der Syntaxbaum benötigt jedoch mehr Speicherplatz, außerdem ist eine Auswertung des Baumes auf rekursivem Weg ebenfalls nicht gerade resourcenschonend.

Fazit

Auch wenn die Reverse Polish Notation eines Ausdrucks Verarbeitungsvorteile mit sich bringt, erschwert sie die Untersuchung der Eingabe auf syntaktische Korrektheit (vor allem Typkorrektheit!). Unser Parser muss also intern einen Syntaxbaum erstellen, diesen überprüfen und anschließend die RPN des Ausdrucks ausgeben. Damit dürften wir auf der sicheren Seite sein.

Nur: Was ist eigentlich Syntax?

Inhalt

1. Einführung: Ein Abenteuer in Teilen
2. Der Lexer
3. Grundlagen des Parsens
4. Syntax