\heading{Formale Darstellung der Noteneingabesprache} Eingabeverfahren, die f"ur den Computer geeignet sein sollen, m"ussen eine streng formalisierte "au\3ere Form haben, um Mehrdeutigkeiten bez"uglich der Bedeutung zu vermeiden. Solche \Ev\ geh"oren zur Klasse der formalen Sprachen, deren Syntax in den meisten F"allen mit Hilfe sogenannter Regelgrammatiken definiert werden kann. \abs Auch bei der hier entwickelten Noteneingabesprache kann die Theorie der formalen Sprachen zugrunde gelegt werden. Ihre Syntax wird durch die \BNF, mit der \kf e \G en beschrieben werden k"onnen, dargestellt. Doch bevor die Syntax der Eingabesprache definiert wird, sollen die theoretischen Grundlagen dieser Darstellungsweise geschaffen werden. Deshalb folgt eine kurze Einf"uhrung in formale Sprachen und \kf e \G en \lit{\Zima}, \lit{\Peters}. \abschnitt\abschnitt \centerline{\bf 2.1 Theoretische Grundlagen} \abschnitt\abschnitt \subheading{2.1.1 Formale Sprachen} Um den oben erw"ahnten Begriff der formalen Sprache zu er\-kl"a\-ren, sind zun"achst einige andere Definitionen n"otig. \absatz \subheading{Definition} Eine nichtleere endliche Menge $\Sigma=\{a_1,a_2,\ldots,a_n\}$, $n\ge 1$, hei\3t (endliches) \de{Alphabet} und die $a_i$, $1\le i\le n$ sind die Zeichen oder Symbole des Alphabets $\Sigma$. \absatz Diese Zeichen lassen sich nach folgender Vorschrift zu W"ortern zusammensetzen. \abs \subheading{Definition} Sei $\Sigma=\{a_1,\ldots,a_n\}$, $n\ge 1$. Dann hei\3t die endliche Folge $$x=a_{i_{\ssize 1}}\cdots a_{i_{\ssize r}}\;, \q r\ge 0\;,\q 1\le i_j\le n\;, \q j\in \lbrack 1,r\rbrack$$ \de{Wort} "uber dem Alphabet $\Sigma$. Dabei ist $r$ die L"ange des Wortes und wird geschrieben als $|x|=r$. Falls $r=0$, so ist $x$ gleich dem leeren Wort $\epsilon$. Die Menge aller Worte "uber $\Sigma$ wird mit $\Sigma^*$ bezeichnet und $\Sigma^+=\Sigma^*\setminus \{\epsilon\}$ ist die Menge aller Worte "uber dem Alphabet $\Sigma$ ohne das leere Wort. \absatz Auf der Menge aller W"orter ist eine Verkn"upfung, die Konkatenation, wie folgt definiert. \abs \subheading{Definition} Seien $x=a_{i_{\ssize 1}}\cdots a_{i_{\ssize r}}$ und $y=a_{k_{\ssize 1}}\cdots a_{k_{\ssize s}}$ zwei Worte "uber dem Alphabet $\Sigma$. Dann wird das Wort $z=a_{i_{\ssize 1}}\cdots a_{i_{\ssize r}}a_{k_{\ssize 1}} \cdots a_{k_{\ssize s}}$ als \de{Konkatenation} oder \de{Produkt} von $x$ und $y$ bezeichnet und $z$ wird geschrieben als $z=xy$. \absatz Mit den definierten Begriffen k"onnen nun formale Sprachen eingef"uhrt werden. \abs \subheading{Definition} Eine \de{(formale) Sprache} "uber dem Alphabet $\Sigma$ ist eine beliebige Menge $L\subseteq \Sigma^*$. \abschnitt Es stellt sich die Frage, wie die Sprache $L$ spezifiziert werden kann und wie die Elemente dieser Menge beschrieben werden k"onnen. Die Beantwortung h"angt davon ab, ob die Sprache $L$ endlich oder nicht endlich ist. Handelt es sich bei $L$ um eine endliche Wortmenge, so k"onnen die Elemente aufgez"ahlt werden. Falls $L$ jedoch nicht endlich ist, mu\3 eine endliche Beschreibung der Sprache gefunden werden. Bei dieser Beschreibung soll auf nat"urliche Sprachen verzichtet und formale Methoden angewandt werden, um Mehrdeutigkeiten zu vermeiden. Es gibt verschiedene Hilfsmittel, um solch eine Beschreibung zu erhalten. \abs Eine der gebr"auchlichsten Methoden zur Beschreibung formaler Sprachen sind die Regelgrammatiken, die je nach M"achtigkeit verschiedene Klassen formaler Sprachen definieren. Die geeignetste Regelgrammatik zur Darstellung von Eingabesprachen, wie sie bei der Aufgabenstellung dieser Arbeit vorkommen, sind die \kf en \G en. Sie erfassen weite Teile der Syntax dieser Eingabesprachen. \abschnitt\abschnitt \subheading{2.1.2 Kontext--freie Grammatiken} Es folgen nun einige Definitionen zu \kf en \G en und Sprachen. \absatz \subheading{Definition} Eine \de{\kf e \G\ } ist ein Quadrupel $G=(N,\Sigma,P,S)$, wobei $N$ die endliche Menge der \de{Nichtterminalsymbole} und $\Sigma$ die endliche Menge der \de{Terminalsymbole} ist. Es soll $N\cap\Sigma=\emptyset$ gelten. Die endliche Menge $\Gamma=N\cup \Sigma$ wird als \de{Gesamtalphabet} bezeichnet. $P\subseteq N\times\Gamma^*$ ist die Menge der Regeln oder \de{Produktionen}. $P$ ist eine endliche Menge. $(A,v)\in P$ hei\3t eine Regel f"ur $A$ und wird in der Form $A\longrightarrow v$ geschrieben. $S\in N$ hei\3t \de{Startsymbol}. \absatz Produktionsregeln aus $P$ lassen sich hintereinander ausf"uhren. Dies f"uhrt zu folgender Definition \abs \subheading{Definition} Sei $G=(N,\Sigma,P,S)$ eine \kf e \G\ und $w,w_0\in \Gamma^*$. Dann hei\3t $w$ aus $w_0$ \de{ableitbar} bez"uglich $P$, wenn es eine Folge $w_1,w_2,\ldots,w_m\in \Gamma^*$ gibt, mit $w_m=w$ und folgender Eigenschaft:\abs F"ur jedes $i=1,\ldots, m$ gibt es eine Regel $(A_i,v_i)\in P$ und W"orter $x_i, y_i\in\Gamma^*$, so da\3 gilt: $$w_{i-1}=x_iA_iy_i\qq\hbox{und}\qq w_i=x_iv_iy_i\;.$$ Die Folge $w_i$, $i=0,\ldots, m$, hei\3t \de{Ableitung} der L"ange $m$ und wird in der Gestalt $$w_0\longrightarrow w_1\longrightarrow \ldots \longrightarrow w_m=w$$ als solche angedeutet. Die Tatsache, da\3 es eine Ableitung von $w$ aus $w_0$ in $P$ gibt, wird durch $w_0\abl^P w$ notiert. \abs Mit einer \kf en \G\ lassen sich W"orter erzeugen. Ausgehend vom Startsymbol $S$ k"onnen nach Belieben Produktionsregeln der Grammatik angewandt werden. Eine Produktion ersetzt jeweils ein Nichtterminalsymbol durch ein Element aus der Menge $N\cup\Sigma$. Terminalsymbole k"onnen nicht ersetzt werden. Der Ableitungsvorgang terminiert sp"atestens dann, wenn das Wort nur noch Symbole aus dem Terminalalphabet enth"alt. Er endet auch, wenn f"ur ein Nichtterminalzeichen keine Produktion existiert. Die bei einer Ableitung entstandenen W"orter, die nur Terminalsymbole enthalten, hei\3en \de{Terminalw"orter} oder S"atze. Sie geh"oren zur Menge $\Sigma^*$. Die Menge aller von einer \kf en \G\ erzeugten Terminalw"orter bilden die zu der \G\ geh"orende \kf e Sprache. \absatz \subheading{Definition} Eine formale Sprache $L\subseteq \Sigma^*$ hei\3t \de{\kf} genau dann, wenn es eine \kf e \G\ $G=(N,\Sigma,P,S)$ gibt, f"ur die $$L=L(G):=\{w\,\mid\,w\in\Sigma^*\hbox{ und } S\abl^P w\}$$ gilt. \abs \subheading{Beispiel} Sei $G_1=(\{S,T\}, \{a,b\}, \{S\to aT|Ta|\epsilon, T\to Sb|bS\}, S)$ eine kontext--freie Grammatik. Die verschiedenen Produktionen f"ur ein Nichtterminalsymbol werden "ublicherweise zu einer Regel zusammengefa\3t und durch einen senkrechten Strich getrennt. $T\to Sb|bS$ bedeutet also $T\to Sb$ oder $T\to bS$. Es gibt zum Beispiel folgende Ableitungen: $$S\longrightarrow aT\longrightarrow aSb\longrightarrow ab$$ oder $$S\longrightarrow Ta\longrightarrow Sba\longrightarrow aTba \longrightarrow aSbba\longrightarrow abba\;.$$ Die W"orter $ab$ bzw. $abba$ sind Terminalworte. \abschnitt Sei im folgenden $G=(N,\Sigma,P,S)$ eine \kf e \G, $w\in\Sigma^*$ und $L(G)$ die von $G$ erzeugte \kf e Sprache. \abs Im Zusammenhang mit \kf en \G en und Sprachen stellt sich die Frage, ob die Syntax der erzeugten Sprache korrekt ist. Deshalb sind drei Probleme, auf die im folgenden n"aher eingegangen wird, von besonderem Interesse: \item{---} "Aquivalenz von Grammatiken, \item{---} Entscheidbarkeit "uber die Zugeh"origkeit eines Wortes zu der von der Grammatik $G$ erzeugten Sprache $L(G)$, \item{---} Eindeutigkeit der Ableitung f"ur ein Wort $w\in L(G)$. \abs Auf diese drei Punkte wird nun n"aher eingegangen. \abschnitt\abschnitt \subheading{2.1.3 "Aquivalenz \kf er \G en} Es kann sein, da\3 eine \kf e \G\ in ihren Alphabeten Zeichen enth"alt, f"ur die es keine Ableitungen gibt oder die in den Terminalw"ortern der erzeugten Sprache nicht vorkommen. Auch die Menge der Produktionen kann nutzlose Regeln enthalten, die zur Erzeugung der Sprache, also der Terminalw"orter, nicht beitragen. \abs Es w"are sicherlich w"unschenswert, wenn diese redundanten beziehungsweise nutzlosen Zeichen und Regeln aus der \kf en \G\ entfernt werden k"onnten, ohne da\3 sich die \G\ wesentlich "andert. Dies geht, indem folgende Einschr"ankungen gemacht werden: (1) das Startsymbol kommt nur auf der linken Seite einer Ableitung auf, (2) keine Regel f"uhrt nur zum leeren Wort, (3) kein Nichtterminalsymbol wird in ein Nichtterminalsymbol abgeleitet und (4) jede Ableitung f"uhrt zu einem Terminalwort. Auf welche Art ein Grammatik dahingehend abge"andert werden kann, da\3 sie diese Bedingungen erf"ullt, wird im Anschlu\3 an die Definition der "Aquivalenz geschildert. \absatz \subheading{Definition} Zwei \kf e \G en $G=(N,\Sigma,P,S)$ und $G'=(N',\Sigma',P',S')$ hei\3en \de{"aqui\-va\-lent} genau dann, wenn $L(G)=L(G')$; \dh, wenn die beiden \G en die gleiche Sprache erzeugen. \abschnitt Der folgende Algorithmus "uberf"uhrt die \kf e Grammatik $G$ in eine \kf e Grammatik $G'$, die die obigen Bedingungen erf"ullt und "aquivalent zu $G$ ist. Die Grammatik $G'$ wird \de{reduziert} genannt. F"ur eine ausf"uhrlichere Beschreibung des Algorithmus sei auf \lit{\Zima} oder \lit{\Peters} verwiesen. \abs Eine \kf e \G\ $G=(N,\Sigma,P,S)$ kann durch folgende Schritte reduziert werden: \abs \item{1.} Das Startsymbol $S$ soll nicht auf der rechten Seite einer Ableitung vorkommen, \dh in $A\longrightarrow v$, $A\in N$, $v\in\Gamma^*$, tritt $S$ nicht in $v$ auf. Diese Bedingung kann erf"ullt werden durch Einf"uhrung eines neuen Startsymbols $S'$ und der Hinzunahme der Regel $S'\longrightarrow S$. $N'$ ist dann $N\cup\{S'\}$. \item{2.} Die Produktionen sollen \de{$\epsilon$--frei} sein, \dh keine Regel soll die Form $C\longrightarrow \epsilon$, $C\in N$, haben. Sei $v\in\Gamma^*$ und das Nichtterminalsymbol $C$ kommt in $v$ vor. Dann kann zu jeder Regel $A\longrightarrow v$, $A\in N$, eine Produktion $A\longrightarrow w$, $w\in\Gamma^*$, hinzugef"ugt werden. Diese entsteht aus $A\longrightarrow v$, indem in $w$ alle $C$ durch $\epsilon$ ersetzt werden. Die Regel $C\longrightarrow \epsilon$ kann dann eliminiert werden. \item{3.} Die Menge der Produktionen enth"alt keine \de{single production}, also keine Regel der Form $A\longrightarrow B$ mit $A,B\in N$. Dazu werden alle Produktionen $C\longrightarrow x$, $x\in\Sigma$ betrachtet. Nun wird f"ur alle $A$ mit $ A\longrightarrow B$ und alle $ C\longrightarrow x$ "uberpr"uft, ob eine Ableitung $A\abl^P C$ existiert. Falls es so eine Ableitung gibt, wird $A\longrightarrow x$ als neue Regel hinzugenommen und die Regel $A\longrightarrow B$ entfernt. \item{4.} Jede abgeschlossene Ableitung soll zu einem Terminalwort f"uhren. Das bedeutet, da\3 es immer eine Ableitung $S\abl^P vAw\abl^P vuw$ mit $v,w,u\in\Sigma^*$, $A\in N$, gibt. Dies kann erreicht werden, indem alle Nichtterminalzeichen aus dem Nichtterminalalphabet $N$ gestrichen werden, aus denen kein Terminalwort abgeleitet werden kann. Au\3erdem werden alle nichterreichbaren Symbole aus den Alphabeten gestrichen. \abs Die durch obigen Proze\3 entstandene \kf e \G\ $G'=(N',\Sigma',P',S')$ ist "aquivalent zu der \kf en \G\ $G$, \dh $L(G')=L(G)$ (Beweis siehe \lit{\Zima}, \lit{\Peters}). Mit der \G\ $G'$ kann die Sprache $L$ ohne unn"otige bzw. redundante Ableitungen erzeugt werden. Au\3erdem wird mit jeder vollst"andigen Ableitung ein Terminalwort erreicht. Ein Ziel wird es demnach sein, zur Erzeugung einer Sprache eine reduzierte \kf e \G\ zu benutzen. \abschnitt Im folgenden sei die \kf e \G\ $G=(N,\Sigma,P,S)$ laut obigen Vereinbarungen eine reduzierte Grammatik. \abschnitt\abschnitt \subheading{2.1.4 Entscheidbarkeit} Immer dann, wenn die Syntax einer Sprache "uberpr"uft werden soll, stellt sich die Frage nach der Zugeh"origkeit eines Wortes zu dieser Sprache. Eine syntaktisch korrekte Sprache enth"alt nur W"orter, die durch die zugeh"orige Grammatik erzeugt wurden. Deshalb ist es f"ur die Syntaxanalyse wichtig, entscheiden zu k"onnen, ob ein Wort zu der von einer Grammatik erzeugten Sprache geh"ort oder nicht. Falls diese Frage f"ur ein Wort entschieden werden kann, so mu\3 als n"achster Schritt eine Ableitung f"ur dieses Wort gefunden werden -- vorausgesetzt, das Wort geh"ort zu der Sprache. Anhand der gefundenen Ableitung f"ur ein Wort $x$ kann seine syntaktische Struktur erkannt werden. \absatz \subheading{Definition} Eine Sprache $L\subseteq \Sigma^*$ mit der Eigenschaft, da\3 f"ur jedes Wort $v\in\Sigma^*$ entschieden werden kann, ob $v\in L$ oder $v\notin L$, hei\3t \de{entscheidbar}. \absatz Jede \kf e Sprache ist entscheidbar (siehe \lit{\Peters} oder \lit{\Zima}). Das bedeutet, da\3 in jedem Fall festgestellt werden kann, ob ein Wort durch die Grammatik erzeugt wird und damit zu der Sprache geh"ort. Im Zusammenhang mit der Entscheidbarkeit \kf er Sprachen werden Verfahren angegeben, mit denen eine Ableitung f"ur ein Terminalwort gefunden werden kann. Verfahren zum systematischen Aufsuchen einer Ableitung zu einer gegebenen Grammatik $G$ und einem gegebenen Wort $w\in \Sigma^*$ werden \de{Syntax--Anlayse--Verfahren} genannt. \abs Bei der Konstruktion einer zu $w$ geh"orenden Ableitung k"onnen zwei prinzipiell verschiedene Wege eingeschlagen werden: Einerseits kann von den Terminalzeichen, die das Wort $w$ bilden, ausgegangen und versucht werden, das Startsymbol $S$ zu erreichen (``bottom--up--Analyse''). Andererseits kann die Konstruktion einer Ableitung mit dem Startsymbol begonnen werden, um auf diesen Weg das Terminalwort $w$ zu erreichen (``top--down--Analyse''). \abs W"ahrend einer Analyse mu\3 h"aufig zwischen mehreren Regeln gew"ahlt werden, weil es f"ur ein Nichtterminalsymbol verschiedene Produktionen geben kann und es oft nicht absehbar ist, ob die eine oder die andere Regel zum gew"unschten Ergebnis f"uhrt. Dies zeigt das folgende Beispiel. \absatz \subheading{Beispiel} Sei $G$ eine \kf e \G\ mit $\Sigma=\{a,+,*,(,)\}$, $N=\{S\}$, \par $P=\{S\to S+S/S*S/(S)/a\}$ und dem Startsymbol $S$. Dann kann der Ausdruck $a+a*a$ mit verschiedenen Ableitungen erreicht werden: $$S\to S+S\to S+S*S\to a+S\to a+a*S\to a+a*a$$ oder $$S\to S+S\to a+S\to a+S*S\to a+a*S\to a+a*a\,.$$ \absatz Es kann auch sein, da\3 durch die Wahl einer ungeeigneten Regel die Anlayse vor Erreichen des Startsymbols $S$ bzw. des Terminalworts $w$ terminiert. Dann mu\3 die Ableitung bis zu der mehrdeutigen Stelle r"uckg"angig gemacht werden (``back--tracking'') und von dort aus wieder mit der Analyse begonnen werden. Allerdings werden die Bem"uhungen dahingehen, solche Sackgassen zu vermeiden und m"oglichst effiziente Analysealgorithmen zu verwenden. \abs Verfahren, die solche Analysealgorithmen f"ur \kf e Sprachen automatisch generieren, sind die $LL(1)$-- und die $LALR(1)$--Analyse. Die Besprechung dieser Analyseverfahren w"urde hier zu weit f"uhren, deshalb sei an dieser Stelle wiederum auf \lit{\Zima} verwiesen. \absatz Es ist noch zu sagen, da\3 diese Analysestrategien ausschlie\3lich auf eindeutige \G en anwendbar sind. Darum schlie\3t an dieser Stelle eine kurze Zusammenfassung "uber den Eindeutigkeitsbegriff \kf er \G en an. \abschnitt\abschnitt \subheading{2.1.5 Eindeutigkeit} Bevor Aussagen zur Eindeutigkeit einer \kf en \G\ gemacht werden k"onnen, m"ussen einige Vereinbarungen "uber Ableitungen getroffen werden. Um daf"ur einen anschaulichen Hintergrund zu haben, werden die Ableitungen durch sogenannte Ableitungsb"aume graphisch dargestellt. \absatz \subheading{Definition} Sei $G$ eine \kf e \G\ und $w\in L(G)\subseteq\Sigma^*$. Ein \de{Ableitungsbaum von $w$ in $G$} ist ein Baum mit den Eigenschaften: \item{---} Die Wurzel hat die Marke $S$. \item{---} Alle mit Nichtterminalzeichen $A$ markierten Knoten haben Nachfolger; sind f"ur einen mit $A$ markierten Knoten die Nachfolger mit $v_1,\ldots, v_n\in\Gamma$ markiert, dann enth"alt $G$ die Regel $A\longrightarrow v_1\cdots v_n$. \item{---} Die Marken der Bl"atter ergeben von links nach rechts gelesen das Wort $w$. \absatz Zu einer Ableitung $S\abl^P w$ mit $S\longrightarrow w_1\longrightarrow w_2\longrightarrow \cdots \longrightarrow w_m=w$, $w\in L(G)$, kann nach folgenden Regeln ein \de{Ableitungsbaum} zusammengef"ugt werden: \par \item{1.} Zu jeder Regel $A\longrightarrow v_1\cdots v_n\in P$ mit $v_i\in \Gamma$, $1\le i\le n$, wird der zugeh"orige \de{Regelbaum} \par % \input mdocpic1 % \item{ } gebildet. \item{2.} Nun wird der Ableitungsbaum f"ur $S\abl^P w$ begonnen, indem der Regelbaum zur Regel $S\longrightarrow w_1$ erstellt wird. \item{3.} Sei $w_i=xAy$, $1\le i