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 number enthält;
- interface Number wird implementiert von
- class MultiDigitNumber, die als Klassenvariable eine Number und eine Digit erhält und
- class SingleDigitNumber, die als Klassenvariable ein Digit enthält;
- interface Digit wird implementiert von class DigitOne, class DigitTwo, class DigitThree, class DigitFour, class DigitFive, class DigitSix, class DigitSeven, class DigitEight und class DigitNine.