TI2—Kapitel 6.6

6.6 Einen Parser in Java implementieren

Den vollständigen Quelltext, den wir in der Vorlesung geschrieben haben, finden Sie in der Datei ArithmeticGrammar.java.

Ich möchte nun eine kontextfreie Grammatik für arithmetische Ausdrücke der Form ((31+402)*83) entwerfen. Der Einfachheit halber bestehe ich auf strenger Klammerung, so wäre (2*(1+2+3)) zum Beispiel nicht erlaubt. Unsere Grammatik soll allgemeine Dezimalzahlen darstellen können. Das Alphabet ist somit $\Sigma = \{\texttt{0},\texttt{1},\texttt{2},\texttt{3},\texttt{4}, \texttt{5},\texttt{6},\texttt{7},\texttt{8},\texttt{9}, \texttt{+},\texttt{*},\texttt{(},\texttt{)}\}$. Die Produktionsregeln sind:

\begin{align*} E&\rightarrow N \tag{JustNumber} \\ E&\rightarrow \texttt{(}E \texttt{+} E\texttt{)} \tag{Sum} \\ E&\rightarrow \texttt{(}E \texttt{*} E\texttt{)} \tag{Product}\\ N&\rightarrow D \tag{SingleDigit} \\ N&\rightarrow ND \tag{NumberDigit} \\ D&\rightarrow \texttt{0}\ | \ \texttt{1}\ | \ \texttt{2}\ | \ \texttt{3}\ | \ \texttt{4}\ | \ \texttt{5}\ | \ \texttt{6}\ | \ \texttt{7}\ | \ \texttt{8}\ | \ \texttt{9} \end{align*}

Die Nichtterminale sind also $E$ (Expression), $N$ (Number) und $D$ (Digit). Wir haben auch den einzelnen Produktionen Namen gegeben, bis auf die der Form $D \rightarrow i$. Was soll nun unser Parser tun? Er soll, gegeben ein Eingabewort $w \in L$, den Ableitungsbaum konstruieren, für ((31+402)*83) also

Wie wir diesen Baum in Java repräsentieren, darüber sprechen wir in einer Minute. Zuerst aber: wir wollen mit diesem Baum etwas Sinnvolles tun. Zum Beispiel auswerten, so dass am Ende eine Zahl rauskommt, im obigen Beispiel also $(31 + 402) \cdot 83 = 35939$. Oder den Ausdruck umformen von Infix-Notation zu Präfixnotation, also(* (+ 31 402) 83). All dies wird sehr einfach sein, sobald wir den Ableitungsbaum als Datenstruktur vorliegen haben.

Eine Datenstruktur für Ableitungsbäume

Für meine Implementierung in Java erschaffe ich für jedes Nichtterminal $X$ ein Interface und für jede Produktionsregel $X \rightarrow \alpha$ eine Klasse, die das Interface $X$ implementiert und $\alpha$ als Klassenvariable enthält.

interface Expression wird implementiert von
- class Sum, die als Klassenvariable Exrepssion e1, e2 enthält,
- class Product, die als Klassenvariable Exrepssion e1, e2 enthält,
- class JustNumber, die als Klassenvariable nur eine Number numberenthält;
interface Number wird implementiert von
- class MultiDigitNumber, die als Klassenvariable eineNumber und eine Digit erhält und
- class SingleDigitNumber, die als Klassenvariable ein Digitenthält;
interface Digit wird implementiert vonclass DigitOne,class DigitTwo,class DigitThree,class DigitFour,class DigitFive,class DigitSix,class DigitSeven,class DigitEight undclass DigitNine.

In unserem Anwendungsfall hat jedes Interface eine Methodepublic int toInt(). Interface Expression hat zusätzlich noch die Methode String toPrefixNotation(). Ich schreibe auch ein Über-Interface ParseObject, das alle Interfaces zusammenfasst. Um uns das Debugging zu erleichtern, überschreibe ich in jeder Klasse die Methodepublic String toString().