Institut für Informatik

Michael Wand
David Hartmann

Sommersemester 2020 • DIGITAL

Aufgabe Parsen von Mathematischen Ausdrücken

Wir werden im Folgenden einen Algorithmus entwickeln, der gegeben einer Menge von Operatoren mit Präzedenz (Operatorrangfolge) und Funktionen einen Binärbaum erstellt, der die Syntax der Zeichenkette widerspiegelt. Wenig überraschend ist es, dass bei der Übersetzung von Programmiersprachen ganz ähnliche Konzepte eine Rolle spielen.

Theoretische Vorüberlegungen — Bausteine für einen arithmetischen Parser

Als erstes möchten wir genauer verstehen wie ein einfacher Parsing-Algorithmus funktioniert. Dazu schauen wir uns einige kleinere Teilprobleme an, aus mit denen wir Schritt für Schritt (mithilfe von einigen Tipps) einen einfachen Parser für arithmetische Ausdrücke entwickeln.

Nach und nach fügen wir nun Features zu unserem Parser hinzu:

• Klammergebirge.
  Als erstes möchten wir prüfen, ob ein arithmetischer Ausdruck „wohlgeformt“ ist (also keine Syntaxfehler enthält, d.h., keine Abfolge von Zeichen, die keinen Sinn macht).
  Ein Teilproblem dabei ist, zu prüfen, ob die Klammern richtig gesetzt sind (alle geöffneten Klammern müssen auch wieder geschlossen werden; ungeöffnete Klammern kann man nicht schließen).
  Wir betrachten daher ein „Klammergebirge“ als Eingabe. Dies ist ein String der nur aus den beiden Zeichen „(“ und „)“ bestehen darf. Wir sollen nun prüfen, ob die Schachtelung der Klammern gültig ist.
  Die Schachtelung ist gültig, wenn sie dadurch entstanden sein könnte, bei einem wohlgeformten arithmetischen Ausdruck alle Zeichen außer den Klammern wegzulassen.
  Zum Beispiel sind „wohlgeformt“: ()(()) und ((()())(()()()))(())
  Nicht wohlgeformt wären z.B.: )(()), ((()())(()( und (())))
  Hinweis: Das Problem könnte man einfach mit Zählen lösen; das hilft uns später aber nicht weiter. Verwenden Sie daher jetzt schon einen Stack: Gehen Sie von links nach rechts durch die Eingabe und legen Sie auf dem Stack Teilergebnisse ab, die Teilbäumen entsprechen, die auf der bisher auf der linken Seite erkannt worden. Wenn diese noch nicht zu einem Gesamtbaum zusammengefasst werden konnten, liegen unter Umständen mehrere solche Teilergebnisse vor. Nach jedem Schritt nach rechts sollten Sie dann prüfen, wieviele Teilbäume sie schon zusammenbinden können, oder ob ein Fehler aufgetreten ist.
• Arithmetische Ausdrücke. Wir betrachten nun sehr einfache arithmetische Ausdrücke. Erlaubt sind wieder runde Klammern, die binären Operatoren +,-,*,/, sowie Zahlen mit einer einzelnen Ziffer (0,1,...,9). Erlaubt wäre also z.B.: 1+2+3 oder (1+2)*3+(4-7). Verboten wären dagegen 23+42, -4 (unäres Minus erlauben wir nicht) oder 2++, und natürlich auch falsche Klammerungen wie ((3+2). Leere Klammern machen auch keinen Sinn: ()+4 ist verboten.
  Überlegen Sie sich einen Algorithmus, der kontrolliert ob ein eingegebener String valide ist im Sinne der obigen Definition (also nur geklammerte Ausdrücke von den vier Grundrechenarten mit Zahlen, die aus einzelnen Ziffern bestehen).
  Hinweis 1: Verwenden Sie einen Stack für die Operatoren und die Klammern und einen zweiten Stack für alle anderen Symbole. Dies ist jedoch nur eine von vielen Möglichkeiten. Die Aufgabe kann auch mit nur einem Stack gelöst werden, falls Ihnen das eher liegt.
  Hinweis 2: Später sollen Sie während des Parsens eine Baumstruktur erstellen. Im Hinblick darauf bietet es sich an, Subterme zusammenzufassen und durch ein neues „Dummy-Term“-Element im Elemente-Stack zu ersetzen. (Den Operatorstack müssen sie bei der Ersetzung eventuell mit anpassen).
  Hinweis 3: Sehr Ähnlich ist der Shunting-Yard-Algorithmus konstruiert worden. Der Unterschied besteht darin, dass der Shunting-Yard-Algorithmus keinen Baum erstellt, sondern den String in die umgekehrte Polnische Notation umwandelt. Falls Sie einen Anstoß brauchen, können Sie also erst den Shunting-Yard-Algorithmus nachvollziehen und müssen dort lediglich den erstellten String durch einen Baum ersetzen.
  
  Bonus: Wie müssen wir den Algorithmus erweitern, so dass auch mehrstellige Zahlen (Kommas für Fließkommazahlen sind optional; brauchen wir im weiteren nicht unbedingt) erkannt werden? Wie können wir das unäre Minus handhaben?
• Erweitern Sie nun Ihren Algorithmus so, dass nicht (nur) ausgegeben wird, ob ein Ausdruck valide ist, sondern — wie in der Vorlesung gezeigt — einen Binärbaum erstellt, der den Ausdruck repräsentiert.
  Hinweis 1: Aus dem Dummy-Term wird ein Teilbaum.
  Hinweis 2: Achten Sie zuerst nicht darauf, dass die Operatoren geordnet sind (* bindet eigentlich stärker als +, etc.) und überlegen Sie insbesondere was (mit den Stacks) geschehen muss, wenn
  • eine schließende Klammer gefunden wird,
  • die Zeichenkette komplett durchlaufen wurde, aber noch Elemente auf den beiden Stacks liegen. Hinweis 3: Fügen Sie nun die nötige Funktionalität ein, die die Struktur des Baumes die Präzendenz von Operatoren berücksichtigt. Hierzu gibt man jedem Operator eine Ordnung; je höher diese Zahl, desto stärker bindet er. Typischerweise nimmt man hier: \[\text{ord}(\texttt{-}) = \text{ord}(\texttt{+}) < \text{ord(mod)} < \text{ord}(\texttt{/}) = \text{ord}(\texttt{*}) < \text{ord}(\texttt{^})\] Sie können jedoch auch eine strikte \(<\)-Ordnung annehmen (dies bedeutet minimal weniger Programmieraufwand). Wie muss Beispielsweise der Baum für a*(b+c) aussehen und wie muss der Baum für a*b+c aussehen?
• Nicht alle hintereinander ausgeführte Operatoren können beliebig geklammert werden (Assoziativgesetz, \(a+(b+c)=(a+b)+c\)).
  Ein Beispiel hierfür ist das Potenzieren: Hierbei handelt es sich um einen Rechtsassoziativen Operator, \(a^{b^c}=a^{(b^c)} \not= (a^b)^c\). Sie müssen nicht viel an Ihrem Algorithmus ändern, damit auch dies berücksichtigt wird.
  Hinweis: Überlegen Sie sich insbesondere Beispiele, die nicht nur das Potenzieren, sondern auch andere Operatoren enthält.