summaryrefslogtreecommitdiff
path: root/macros/mtex/documentation/mdoc2.tex
diff options
context:
space:
mode:
Diffstat (limited to 'macros/mtex/documentation/mdoc2.tex')
-rw-r--r--macros/mtex/documentation/mdoc2.tex1206
1 files changed, 1206 insertions, 0 deletions
diff --git a/macros/mtex/documentation/mdoc2.tex b/macros/mtex/documentation/mdoc2.tex
new file mode 100644
index 0000000000..5cbcf78290
--- /dev/null
+++ b/macros/mtex/documentation/mdoc2.tex
@@ -0,0 +1,1206 @@
+\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<m$, $x,y\in\Gamma^*$, $A\in N$ und
+$w_{i+1}=xvy$, $v\in \Gamma^*$. Der "Ubergang von $w_i$ nach
+$w_{i+1}$ wird durch die Anwendung der Regel
+$A\longrightarrow v$ bewirkt.
+Im Ableitungsbaum wird
+der Knoten $A\in N$ durch den Regelbaum f"ur die Regel
+$A\longrightarrow v$ ersetzt.
+Jeder Ableitungsschritt kann an den
+Bl"attern des Baumes von links nach rechts abgelesen werden.
+\abs
+Auf diese Weise kann f"ur jedes Wort $w$ ein Ableitungsbaum konstruiert
+werden.
+Der umgekehrte Vorgang ist ebenfalls m"oglich.
+Zu einem Ableitungsbaum eines Wortes $w$ k"onnen Ableitungen
+gefunden werden; dabei kann es sein, da\3 es zu einem Ableitungsbaum
+verschiedene Ableitungen gibt. Deswegen wird jedem Ableitungsbaum eine
+ausgezeichnete Ableitung zugeordnet.
+\absatz
+\subheading{Definition}
+Eine Ableitung
+$S\longrightarrow w_1\longrightarrow\cdots\longrightarrow w_m=w$ hei\3t
+\de{Linksableitung} genau dann, wenn bei jedem "Ubergang
+$w_{i}=xAy\longrightarrow xvy$ mit
+$w_i,y,v\in\Gamma^*$,
+$A\in N$, stets $x\in\Sigma^*$ gilt.
+Analog dazu kann auch die \de{Rechtsableitung} definiert werden.
+\abs
+Jeder Linksableitung von $w$ entspricht genau ein Ableitungsbaum und
+umgekehrt. Au\3erdem besitzt jedes Wort einer Sprache
+eine Linksableitung.
+\abs
+Es ist m"oglich, da\3 es zu einem Wort mehrere
+Linksableitungen gibt, also auch mehrere Ableitungsb"aume. Aus
+diesem Grund ist es sinnvoll, folgende Vereinbarung zu treffen:
+\absatz
+\subheading{Definition}
+Eine \kf e \G\ $G$ hei\3t \de{eindeutig} genau dann, wenn f"ur jedes
+$w\in L(G)$ nur eine Linksableitung existiert. Andernfalls hei\3t $G$
+\de{mehrdeutig}.
+\abs
+\subheading{Definition}
+Eine \kf e Sprache $L\subseteq \Sigma^*$ hei\3t \de{eindeutig} genau
+dann, wenn es eine eindeutige \kf e \G\
+f"ur $L$ gibt. Andernfalls hei\3t
+$L$ \de{mehrdeutig}.
+\abs
+Es liegt auf der Hand, da\3 Eingabesprachen f"ur den Computer eindeutig
+sein sollten, schon allein aus dem Grund, da\3 die semantische
+Eindeutigkeit sonst nicht gew"ahrleistet werden kann.
+\abschnitt
+Zum Abschlu\3 dieses Abschnitts sei darauf hingewiesen, da\3
+sich die praktische Anwendung der \kf en \G en von der Theorie
+unterscheidet.
+Mit \kf en \G en k"onnen weite Teile der Syntax von
+Eingabe-- oder Programmiersprachen erfa\3t werden. Allerdings
+m"ussen zus"atzlich zu den Regeln des Produk\-tionssystems $P$ noch
+weitere Vorschriften gemacht werden, bei denen es sich dann nicht
+mehr um \kf e Regeln handelt. Diese Zusatzregeln sind meist n"otig,
+um Eingaben zu vermeiden, die semantisch
+keinen Sinn ergeben, aber aus den
+Produktionsregeln der \G\ ableitbar sind.
+\abs
+Trotzdem kann mit \kf en \G en zun"achst die "au\3ere
+Struktur der Sprachen, die beschrieben werden m"ussen,
+festgelegt werden.
+Auch der Aufbau der hier erarbeiteten
+Eingabesprache f"ur Musikst"ucke, die
+zur Automatisierung des Notensatzes benutzt werden soll,
+kann mit Hilfe obiger Theorie behandelt werden.
+\abschnitt
+\abschnitt
+\goodbreak
+\centerline{\bf 2.2 Die Syntax der Noteneingabesprache in \BNF}
+\abschnitt
+In diesem Abschnitt soll die Syntax der Noteneingabesprache,
+die f"ur eine Anwendung mit dem Computer entwickelt worden ist und
+und deshalb zur Klasse der formalen Sprache geh"ort, dargestellt
+werden.
+Eine formale Sprache kann durch eine \kf e \G\ erzeugt werden, deren
+Produktionsregeln den syntaktischen Aufbau der Sprache
+beschreiben. Die entwickelte Noteneingabesprache kann ebenfalls
+durch eine \kf e \G\ generiert werden.
+Zur Beschreibung dieser \kf en \G\ wird aus mehreren Gr"unden
+die standardm"a\3ig benutzte
+\BNF\ gew"ahlt.
+Zum einen bietet die \BNF\ die M"oglichkeit,
+die Nichtterminalzeichen mnemotechnisch zu benennen, was die
+Erkennung ihrer Bedeutung innerhalb der Sprache und daher
+das Verst"andnis erleichtert. Au\3erdem k"onnen die Nichtterminal%-
+symbole in den Produktionsregeln von den Terminalsymbolen durch die
+die Art ihrer Darstellung unterschieden werden. Die Menge der
+Terminal-- bzw. Nichtterminalzeichen m"ussen demnach nicht gesondert
+aufgef"uhrt werden, was vor allem bei sehr umfangreichen \G en\
+von Vorteil ist.
+\abs
+Bevor der syntaktische Aufbau der Eingabesprache mit Hilfe der
+\BNF\ dargestellt wird, soll diese anhand
+eines Beispiels
+erl"autert werden.
+\abschnitt\abschnitt
+\subheading{2.2.1 Die \BNF}
+Zur Backus--Naur--Form
+geh"ort ein Qua\-dru\-pel
+$(N,\Sigma,P,S)$. Die Nichtterminalsymbole
+werden mnemotechnisch benannt
+und in spitze Klammern eingeschlossen. Statt dem Ableitungspfeil wird
+das Zeichen
+$::=$ zum Anschreiben der Produktionen benutzt.
+Bei Auftreten des Zeichens wird
+das Nichtterminalsymbol auf der linken Seite durch die rechte
+Seite genauer erkl"art. Wie bei Produktionsregeln von \G en "ublich,
+werden bei der \BNF\ die verschiedenen M"oglichkeiten einer
+Ableitung f"ur ein Nichtterminalzeichen durch einen senkrechten Strich
+voneinander getrennt.
+\abs
+Zum besseren Verst"andnis wird nun ein Beispiel f"ur eine
+\kf e \G\ in
+\BNF\ gegeben und nach ihren Regeln eine Ableitung konstruiert.
+\absatz
+\subheading{Beispiel}
+Sei
+$G=(N,\Sigma,P,S)$ eine \kf e \G\ mit\par
+$N=\{$\nl{name},\nl{letter},\nl{alphanum},\nl{numeral},$\}$,
+$\Sigma=\{\hbox{B,E,I,S,P,L,1,2,3}\}$,
+$S=$\nl{name} und $P$ enth"alt die Produktionen
+\item{ }
+\nl{name}::=\nl{alphanum}\T\nl{alphanum}\nl{name},
+\item{ }
+\nl{alphanum}::=\nl{letter}\T\nl{numeral},
+\item{ }
+\nl{letter}::=B\T E\T I\T S\T P\T L,
+\item{ }
+\nl{numeral}::=1\T2\T3.
+\abs
+W"orter der von $G$ erzeugten Sprache sind \zB BEISPIEL22, B11LE,
+1322 oder BSP1.
+Zur Veranschaulichung wird die Linksableitung, dargestellt als
+Ableitung und Ableitungsbaum, f"ur das Terminalwort BSP1 konstruiert.
+$$\align \nm{name}
+&=\nm{alphanum}\nm{name}\\
+&=\nm{letter}\nm{name}\\
+&={\bf B}\nm{name}\\
+&={\bf B}\nm{alphanum}\nm{name}\\
+&={\bf B}\nm{letter}\nm{name}\\
+&={\bf BS}\nm{name}\\
+&={\bf BS}\nm{alphanum}\nm{name}\\
+&={\bf BS}\nm{letter}\nm{name}\\
+&={\bf BSP}\nm{name}\\
+&={\bf BSP}\nm{alphanum}\\
+&={\bf BSP}\nm{numeral}\\
+&={\bf BSP1}\endalign$$
+Der Ableitungsbaum f"ur die Linksableitung hat folgende Gestalt:
+\par
+{
+\def\HB#1{\hbox to 3cm{\hfil$#1$\hfil}}
+\def\Hb#1{\hbox to 1.5cm{\hfil$#1$\hfil}}
+\centerline{ \HB{\nm{name}} }
+\centerline{ \Hb{\swarrow} \Hb{\searrow} }
+\centerline{ \HB{\nm{alphanum}} \HB{\nm{name}} }
+\centerline{ \Hb{\swarrow} \Hb{} \Hb{\swarrow} \Hb{\searrow} }
+\centerline{ \HB{\nm{letter}} \HB{\nm{alphanum}} \HB{\nm{name}} }
+\centerline{ \Hb{\swarrow} \Hb{} \Hb{\swarrow} \Hb{}
+ \Hb{\swarrow} \Hb{\searrow} }
+\centerline{ \HB{\bf B} \HB{\nm{letter}} \HB{\nm{alphanum}} \HB{\nm{name}} }
+\centerline{ \Hb{} \Hb{\swarrow} \Hb{} \Hb{\swarrow} \Hb{} \Hb{\swarrow} }
+\centerline{ \HB{\bf S} \HB{\nm{letter}} \HB{\nm{alphanum}} }
+\centerline{ \Hb{} \Hb{\swarrow} \Hb{} \Hb{\swarrow} }
+\centerline{ \HB{\bf P} \HB{\nm{numeral}} }
+\centerline{ \Hb{} \Hb{\swarrow} }
+\centerline{ \HB{\bf 1} }
+}
+
+Im Anschlu\3 daran kann nun
+mit Hilfe der \BNF\ die Syntax der Noteneingabesprache
+beschrieben werden. Diese wird
+zusammen mit
+Erl"auterungen zu den Pro\-duktions\-regeln und ihrer Bedeutung
+f"ur die Sprache
+im n"achsten Abschnitt geliefert.
+\abschnitt\abschnitt
+\subheading{2.2.2 Syntaxbeschreibung in \BNF}
+Die Grammatik, die die Syntax der Eingabesprache beschreibt, ist eine
+nach den Gesichtspunkten aus 2.1.3 reduzierte \G. Das bedeutet,
+da\3 sie $\epsilon$--frei ist, keine single production enth"alt und da\3
+das
+Startsymbol nur einmal vorkommt, und zwar auf der linken Seite. Des
+weiteren gibt es f"ur jedes Nichtterminalsymbol eine Ableitung, die
+zu einem Terminalwort f"uhrt und es gibt keine nicht\-erreichbaren
+Nichtterminal-- bzw. Terminalzeichen. Die Elemente der erzeugten Sprache,
+also die Terminalw"orter, sind Eingaben f"ur den Computer und
+beschreiben ein Musikst"uck.
+\absatz
+Die Grammatik wird haupts"achlich durch ihre Produktionsregeln
+charakterisiert. Dabei wird die Vereinbarung getroffen, da\3 die
+Nichtterminal-- und Terminalzeichen durch die Art der Notation in den
+Ableitungsregeln kenntlich gemacht werden.
+Es soll gelten:
+\item{---}
+$S=\nm{music input}$
+\item{---}
+$N$ enth"alt alle metalinguistischen Variablen, das sind die
+in spitzen Klammern eingeschlossenen Zeichenfolgen.
+\item{---}
+$\Sigma$ besteht aus allen fett gedruckten Symbolen. Das k"onnen
+auch Zeichenfolgen sein.\abs
+Die Menge $P$ der Produktionsregeln, die die Noteneingabesprache
+vollst"andig erzeugen, soll im folgenden erl"autert werden.
+Allerdings wird aus Gr"unden der besseren Lesbarkeit
+darauf verzichtet, die Vorschriften f"ur
+Linksableitungen genau zu befolgen.
+Bei aufeinanderfolgenden Regeln wird also nicht immer das am weitesten
+links stehende Nichtterminalsymbol der vorhergehenden Regel erkl"art.
+Stattdessen wird eine Vorgehensweise gew"ahlt, die den Kontext der
+einzelnen Produktionsregeln verdeutlichen soll. Dazu werden die Regeln
+zu verschiedenen Abschnitten zusammengefa\3t, wobei ein Abschnitt solche
+Produktionen f"ur Nichtterminalzeichen enth"alt, die sinngem"a\3
+zusammengeh"oren. Diese Methode f"uhrt zu einer Unterteilung in
+sechs Abschnitte, die in Anlehnung an die Notation von
+Musikst"ucken in Notenschrift entstanden sind.
+Bevor auf die Beschreibung der Produktionsregeln eingegangen wird,
+soll zun"achst zum Verst"andnis der gew"ahlten Unterteilung
+der Aufbau einer Partitur in groben Z"ugen dargestellt werden.
+\abs
+Zu Anfang eines Musikst"ucks
+stehen "ublicherweise Angaben zum Komponisten
+und dem Titel, bei Vokalmusik werden diese erg"anzt durch Informationen
+"uber den Dichter. Danach wird, der Art des zu notierenden Musikwerks
+entsprechend, die Anzahl der erforderlichen Notenliniensysteme
+festgelegt, in die der Melodieverlauf der einzelnen Stimmen der
+Partitur in Notenschrift geschrieben wird.
+Ein Notenliniensystem besteht
+aus f"unf Linien, in die die Notenschriftzeichen eingeordnet werden.
+Zur Niederschrift mehrstimmiger Musikst"ucke werden mehrere
+Notenliniensysteme benutzt, die untereinander geschrieben
+und durch eine geschweifte Klammer auf der linken Seite zu sogenannten
+Akkoladen zusammengefa\3t werden (siehe \lit{\Ziegen}).
+Im folgenden wird statt Notenliniensystem
+auch der Begriff System benutzt.
+\abs
+Ein einzelnes Notenliniensystem kann grob in zwei Teile gegliedert
+werden. Der erste Teil enth"alt die Angaben, die f"ur die gesamte
+Melodie des Systems G"ultigkeit haben und die zu Beginn jeder
+zu dem System geh"orenden Notenzeile stehen. Mit den einleitenden
+Angaben wird durch den Notenschl"ussel und die Tonart eine Aussage
+"uber die genaue Tonh"ohe der Melodie gemacht, der Rhythmus
+und eventuell Tempo und Tonst"arke festgelegt \lit{\Ziegen}.
+Der zweite Teil eines Systems beschreibt den Melodieverlauf, der
+haupts"achlich mit Hilfe von Noten, Versetzungszeichen, Pausen
+und Taktstrichen notiert wird. Zus"atzlich werden f"ur erl"auternde
+Angaben Sonderzeichen oder Text benutzt.
+In einem einzelnen System d"urfen entweder ein--
+oder zweistimmige St"ucke notiert werden, die
+f"ur Vokalmusik noch mit einem
+Liedtext versehen werden k"onnen.
+\par
+Bei der Notation des Melodieverlaufs bilden die ben"otigten
+Notenschriftzeichen in vielen F"allen wiederum Einheiten,
+die dadurch zustande kommen, da\3 die Notenschriftzeichen
+miteinander verbunden werden, wie \zB mit Balken oder B"ogen.
+Es kann also zwischen einzelnen und kombinierten Notenschriftzeichen
+unterschieden werden.
+\abs
+Die Produktionsregeln der \G\ werden nun entsprechend
+der von ihnen erzeugten Sprachelemente aufgegliedert, wobei die oben
+beschriebene Strukturierung zugrunde gelegt wird.
+Je nachdem, zu welchem Abschnitt sie geh"oren,
+beschreiben sie dann folgende Teile einer Partitur:
+\item{---}
+Eigenschaften, die eine Aussage "uber die Art
+des Musikwerks machen,
+\item{---}
+Melodieverlauf eines Systems,
+\item{---}
+einleitende Angaben, die f"ur ein
+System G"ultigkeit haben,
+\item{---}
+elementare Notenschriftzeichen,
+\item{---}
+Notengruppen, die von Notenschriftzeichen gebildet werden, und
+\item{---}
+sonstige Zeichen und Zeichenketten, wie sie f"ur schriftliche
+Anmerkungen ben"otigt werden.
+\abs
+Ausf"uhrliche Erkl"arungen zu den dort zusammengefa\3ten
+Produktionsregeln werden im folgenden gegeben.
+Doch zuvor noch eine allgemeine Erkl"arung. Manche Regeln der Eingabe%
+sprache legen die Reihenfolge, in der die Angaben gemacht werden
+m"ussen, nicht fest.
+Diese Daten k"onnen also beliebig aufeinanderfolgen,
+wie es zum Beispiel bei \nl{preliminary data} erlaubt ist
+(siehe 2.2.2, Abschnitt 1).
+In solchen F"allen wird das "Ubereinkommen getroffen, da\3 bei
+mehrfachen sich eventuell widersprechenden Angaben mit gleichem
+Informationsgehalt die zuletzt eingegeben gilt. F"ur Linksableitungen
+ist das die, die am weitesten rechts steht.
+\abschnitt
+\subheading{1) Beschreibung der Art der Partitur}\abs
+\def\T{\ |\ }
+Dieser Abschnitt enth"alt die Produktionsregeln,
+mit denen
+die Art des Musikst"ucks bestimmt werden kann und die die
+Notenliniensysteme erzeugen, in die anschlie\3end der Melodieverlauf
+eingetragen wird.
+Durch einige der hier aufgef"uhrten Regeln wird
+die Anzahl der zur Notation des Musikst"ucks ben"otigten Systeme
+und der Inhalt eines Systems
+festgelegt. Andere bieten die M"oglichkeit, die Angaben, die f"ur
+die Dauer eines Systems gelten und zu Beginn jeder Zeile des Systems
+notiert werden, zu erzeugen. Die Regeln, die zur Generierung der
+"Uberschriften einer Partitur ben"otigt werden, sind ebenfalls
+in diesem Abschnitt aufgef"uhrt.
+Anfang und Ende eines Musikst"ucks m"ussen besonders gekennzeichnet
+werden. Das ist vor allem deshalb n"otig, um
+eine Noteneingabe innerhalb einer normalen Texteingabe von dieser
+abzuheben. Damit k"onnen Partituren gemeinsam
+mit Texten eingegeben und verarbeitet werden.
+\abs
+{\tabskip0pt plus1fill
+\halign to\hsize{\hfill$#{}$%
+\tabskip0pt&$#$\hfill\tabskip0pt plus 1fill\cr
+\nm{music input} ::=& \nm{begin} \nm{piece} \nm{end}\cr
+\nm{begin} ::=& {\hbox{\bf!!}} \T \bs{\bf beginsong}\cr
+\nm{piece} ::=& \nm{several system} \T \nm{system} \T \nm{heading}
+\nm{piece}\cr
+\nm{several system} ::=& \bs{\bf system}
+ \lk\nm{system}\rk \T\cr
+&\bs{\bf system}
+ \lk\nm{system}\rk
+\nm{several system}\cr
+\nm{system} ::=& \nm{block} \T \nm{preliminary data} \nm{block}\cr
+\nm{block} ::=& \nm{melody} \T \nm{two} \T \nm{vocal}\cr
+\nm{two} ::=& \bs{\bf two}\lk\nm{melody}\rk \lk%
+ \nm{melody}\rk\cr
+\nm{vocal} ::=& \bs{\bf vocal}\lk\nm{melody}\rk \lk%
+ \nm{songtext}\rk \T
+\bs{\bf vocal}\lk\nm{two}\rk \lk%
+ \nm{songtext}\rk\cr
+\nm{preliminary data} ::=& \nm{voice} \T \nm{clef} \T \nm{signature} \T
+\nm{metre} \T
+ \nm{explanation} \T \cr
+&\nm{preliminary data} \nm{preliminary data}\cr
+\nm{heading} ::=& \bs{\bf title}\lk\nm{text}\rk \T
+ \bs{\bf poet}\lk\nm{text}\rk \T
+ \bs{\bf composer}\lk\nm{text}\rk\cr
+\nm{end} ::=& {\hbox{\bf!!}} \T \bs{\bf endsong}\cr
+}}
+\abs
+Die Eingabe eines Musikst"ucks beginnt und endet mit \nl{begin} bzw.
+\nl{end}, wobei entweder das Terminalzeichen {\bf!!} oder
+\bs{\bf beginsong} bzw. \bs{\bf endsong} benutzt werden kann.
+\par
+Mit \nl{piece} kann entschieden werden, ob ein System oder mehrere
+Systeme eingegeben werden sollen. Falls mehrere Systeme eingegeben
+werden, so werden diese hintereinander eingegeben. Dabei zeigt das
+Terminalwort \bs{\bf system} den Beginn eines weiteren Systems an.
+Zus"atzlich besteht mit \nl{heading} die M"oglichkeit, "Uberschriften
+einzugeben.\par
+In einem System \nl{system} k"onnen unterschiedliche St"ucke notiert
+werden. Diese Wahl findet mit \nl{block} statt.
+Einerseits kann es sich bei der Eingabe um eine einstimmige
+Melodie \nl{melody} handeln.
+Eine andere M"oglichkeit ist, da\3 zwei Stimmen in
+einem System dargestellt werden. Dazu wird \nl{two} benutzt. Die
+dritte M"oglichkeit, n"amlich die Eingabe eines Liedes, geschieht
+mit \nl{vocal}. \par
+Einem System k"onnen durch \nl{preliminary data} einleitende
+Angaben wie Instrumentenstimmen, Notenschl"ussel, Tonart, Taktart
+und Tempoangaben vorangestellt sein.
+\abschnitt
+\subheading{2) Beschreibung des Melodieverlaufs}
+\abs
+Die folgenden Produktionsregeln erzeugen den
+Melodieverlauf jeweils einer Stimme und den eventuell vorhandenen
+Liedtext.
+Die Melodie wird charakterisiert durch einfache Notenschriftzeichen wie
+Noten, Pausen,
+Vorzeichen und Taktunterteilungen. Die Regeln f"ur diese einfachen
+Zeichen werden in 4) erl"autert.
+Diese Zeichen k"onnen je nach Anordnung
+in Gruppen zusammengefa\3t werden, wie es in Abschnitt 5) beschrieben
+wird. Zus"atzlich kann eine Melodie
+schriftliche Erl"auterungen in Form eines Textes enthalten.
+\abs
+{\tabskip0pt plus1fill
+\halign to\hsize{\hfill$#{}$%
+\tabskip0pt&$#$\hfill\tabskip0pt plus 1fill\cr
+\nm{melody} ::=& \nm{primitives} \T \nm{group} \T \nm{change} \T
+ \nm{explanation}\cr
+\nm{primitives} ::=& \nm{note} \T \nm{rest} \T
+\nm{caesura} \T \nm{barline} \T\cr
+ & \nm{primitives} \nm{primitives}\cr
+\nm{group} ::=& \nm{simple nested group} \T
+ \nm{mismatched group} \T \cr
+ & \nm{articulation group} \T \nm{group} \nm{group}\cr
+\nm{change} ::=& \nm{clef} \T \nm{signature} \T \nm{metre} \T \nm{change}
+ \nm{change}\cr
+\nm{songtext} ::=& \nm{text} \T \nm{place}\nm{text} \T
+\nm{omission} \T
+\nm{songtext} \nm{songtext}\cr
+\nm{articulation group} ::=
+& \bs{\bf stac} \nm{melody} \bs{\bf noaccent} \T\cr
+& \bs{\bf staccatissimo} \nm{melody} \bs{\bf noaccent} \T\cr
+& \bs{\bf tenuto} \nm{melody} \bs{\bf noaccent}\cr
+}}
+\abs
+Der Melodieverlauf wird in \nl{melody} beschrieben. Die Melodie ist eine
+Anordnung von \nl{primitives}, \nl{group},
+\nl{change} und \nl{explanation}.
+\par
+Dabei handelt es sich bei \nl{primitives} um die Grundbausteine wie
+Noten, Pausen, Atemzeichen und Taktstriche.
+\par
+In \nl{group} werden alle Notengruppen beschrieben. Das sind
+\nl{primitives}, die mit Balken, Bogen oder Notenh"alse zu einer
+Einheit zusammengefa\3t werden. Unterschieden wird zwischen
+\nl{simple nested group}, \nl{mismatched group} und
+\nl{articulation group}.
+\nl{simple nested group}
+ist eine Gruppe, in der die \nl{primi\-tives} entweder
+mit einem Balken oder einem Bogen oder einem Notenhals verbunden sind.
+Gleichzeitig ist die
+M"oglichkeit gegeben, solche Gruppen ineinanderzuschachteln.
+\par
+Bei einer Noteneingabe kommt es sehr oft vor, da\3 solche Gruppen nicht
+``korrekt'' ineinandergeschachtelt sind, \dh es k"onnen
+"Uberschneidungen vorkommen.
+Eine Gruppe kann innerhalb
+einer anderen aufh"oren, obwohl sie au\3erhalb dieser Gruppe
+begonnen wurde. Dieser Fall ist mit \nl{mismatched group} abgedeckt.
+Auf diese beiden
+Notengruppen wird weiter unten in 5) genauer eingegangen.
+\par
+Mit \nl{articulation group} k"onnen Noten mit Akzentuierungen
+versehen werden. Dabei zeigen die Terminalw"orter
+\bs{\bf stac}, \bs{\bf staccatissimo} und \bs{\bf tenuto} jeweils
+den Beginn, das Terminalwort \bs{\bf noaccent} das Ende der
+Gruppe an. F"ur jede Note, die innerhalb dieser Gruppe vorkommt, gilt
+dann die Akzentuierung.
+\par
+Weiterhin kann w"ahrend des Melodieverlaufs ein Wechsel von
+Takt-- bzw. Tonart oder ein "Ubergang zu einem anderen Notenschl"ussel
+erfolgen. Dies wird mit \nl{change} bewerkstelligt.\par
+\nl{songtext} tritt in der Ableitung nur auf,
+wenn mit \nl{vocal} Vokalmusik
+eingegeben werden soll. Solch eine Textunterlage besteht aus W"ortern und
+dem Auslassungszeichen \nl{omission}. Dieses Zeichen ist n"otig,
+weil jeder Note eine Textsilbe zugeordnet werden soll. Das Auslassungs%
+zeichen wird benutzt, wenn es zu einer Note keinen Text gibt.
+Die Silben werden durch Leerzeichen voneinander getrennt und
+k"onnen mit einer Positionsangabe versehen werden,
+die allerdings nur f"ur
+die folgende Silbe gilt.
+Falls
+mehrere Noten f"ur eine Silbe ben"otigt werden, so m"ussen nach der
+Silbe entsprechend der Anzahl der Noten diese Auslassungszeichen
+eingef"ugt werden.\par
+\abschnitt
+\subheading{3) Beschreibung der einleitenden Angaben,
+zus"atzliche Anmerkungen}
+\abs
+Dieser Teil der Menge der Produktionsregeln erzeugt die
+oben erw"ahnten einleitenden Angaben, die f"ur
+das gesamte System gelten und zu Beginn jeder Zeile eines Systems
+stehen.
+Dazu geh"oren Instrumentenstimme,
+Notenschl"ussel, Vorzeichnung, Taktart, Tempo und Tonst"arke.
+\abs
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+{\tabskip0pt plus1fill
+\halign to\hsize{\hfill$#{}$%
+\tabskip0pt&$#$\hfill\tabskip0pt plus 1fill\cr
+\nm{voice} ::=& \bs{\bf voice}\lk\nm{text}\rk\cr
+\nm{clef} ::=& \bs{\bf treble} \T \bs{\bf bass} \T \bs{\bf baritone} \T
+ \bs{\bf alto} \T \bs{\bf mezzo} \T \bs{\bf soprano} \T
+ \bs{\bf tenor} \cr
+\nm{signature} ::=& \bs{\bf signature}\lk\nm{several accid}\rk \T
+ \nm{sign}\cr
+\nm{several accid} ::=& \nm{accid} \T \nm{accid} \nm{several accid}\cr
+\nm{accid} ::=& \nm{accidental} \nm{simple note} \T
+\nm{octave} \nm{accidental}
+ \nm{simple note} \T \cr
+ &\nm{accidental} \nm{octave} \nm{simple note}\cr
+\nm{sign} ::=&
+\bs{\bf C} \T \bs{\bf G} \T \bs{\bf D} \T \bs{\bf A} \T \bs{\bf E}
+ \T \bs{\bf H} \T \bs{\bf Fis} \T
+ \bs{\bf Cis} \T \cr
+ &\bs{\bf a} \T \bs{\bf e} \T
+\bs{\bf h} \T \bs{\bf fis} \T
+\bs{\bf cis} \T \bs{\bf gis} \T \bs{\bf dis} \T
+\bs{\bf ais} \T \cr
+&\bs{\bf Ces} \T
+\bs{\bf Ges} \T \bs{\bf Des} \T \bs{\bf As} \T
+ \bs{\bf Es} \T \bs{\bf B} \T
+ \bs{\bf F} \T \cr
+ &\bs{\bf as} \T \bs{\bf es} \T
+ \bs{\bf b} \T \bs{\bf f} \T \bs{\bf c} \T \bs{\bf g} \T \bs{\bf d}\cr
+\nm{metre} ::=& \bs{\bf meter}\lk\nm{number}\slash\nm{number}\rk \T
+\bs{\bf allabreve}
+ \T \bs{\bf hC} \T \bs{\bf dC}\cr
+\nm{explanation} ::=& \bs{\bf text}\lk\nm{text}\rk \T
+ \bs{\bf text}\lk\nm{place} \nm{text}\rk \T\cr
+ &\nm{recital} \T
+ \lk\nm{place} \nm{recital}\rk \cr
+\nm{place} ::=& \bs{\bf\us} \T
+\bs{\bf\us l} \T \bs{\bf\us c} \T \bs{\bf\us r} \T
+\bs{\bf\us n} \T \bs{\bf\us v} \T \bs{\hbox{\bf\os\ }} \T
+ \bs{\hbox{\bf\os\ l}} \T
+ \bs{\hbox{\bf\os\ c}} \T
+\bs{\hbox{\bf\os\ r}} \T \bs{\hbox{\bf\os\ n}}\cr
+\nm{recital} ::=&
+\bs{\bf dacapo} \T \bs{\bf dalsegno} \T
+ \bs{\bf unisono} \T \bs{\bf cantusfirmus} \T
+ \bs{\bf crescendo} \T\cr
+& \bs{\bf decrescendo} \T \bs{\bf diminuendo} \T
+ \bs{\bf forte} \T \bs{\bf fortissimo} \T\cr
+& \bs{\bf fortissimoposs} \T \bs{\bf mezzoforte} \T
+ \bs{\bf mezzopiano} \T \bs{\bf piano} \T\cr
+& \bs{\bf pianissimo} \T
+ \bs{\bf pianissimoposs} \T
+ \bs{\bf fortepiano} \T \bs{\bf forzato} \T\cr
+& \bs{\bf rinforzando} \T \bs{\bf sforzato} \T
+ \bs{\bf sforz} \T \bs{\bf decr} \T \bs{\bf rallentando} \T\cr
+& \bs{\bf ritardando} \T \bs{\bf ritenuto} \T
+ \bs{\bf tr} \T \bs{\bf staccato} \T
+\bs{\bf fine} \T
+ \bs{\bf tacet}
+\cr}}
+\abs
+Einleitende Angaben, die zu einem System gemacht werden k"onnen,
+werden in \nl{preliminary data} beschrieben. Die Instrumentenstimme
+kann mit \nl{voice} durch das Terminalzeichen \bs{\bf voice} eingegeben
+werden, wobei auf das Schl"usselwort in Klammern der Name der
+Instrumentenstimme folgen mu\3. \par
+Eine andere m"ogliche Angabe betrifft den Notenschl"ussel. Dabei
+f"uhrt die Variable \nl{clef} zu einem Terminalzeichen, denn die
+Notenschl"ussel werden durch Schl"usselw"orter angegeben.\par
+In der Regel f"ur \nl{signature} wird erkl"art, wie die Tonart eingegeben
+werden kann. Daf"ur gibt es zwei M"oglichkeiten. Entweder
+wird die Tonart durch ein Schl"usselwort aus der Regel f"ur
+\nl{sign} beschrieben oder durch die expliziten Angaben der
+jeweiligen Vorzeichen. Dies geschieht durch die Eingabe der Tonh"ohe,
+auf die das Vorzeichen Einflu\3 nehmen soll, und dem gew"unschten
+Vorzeichen.\par
+Die Taktart \nl{metre} wird durch das Schl"usselwort \bs{\bf meter} und
+der Taktart eingegeben. Abk"urzende Notationen f"ur
+Taktarten aus der Mensuralnotation wie allabreve k"onnen durch
+die entsprechenden Schl"usselw"orter
+erreicht werden.\par
+Die letzte einleitende Angabe, die m"oglich ist, kann eine
+schriftliche Erkl"arung \zB zum Tempo oder der Tonst"arke
+des Musikst"ucks sein. Dazu wird in \nl{explanation} die
+erl"auternde Angabe in geschweifte Klammern geschrieben, der das
+Schl"usselwort \bs{\bf text} vorangeht. Mit \nl{place} kann
+bestimmt werden, wohin der Text geschrieben werden soll: ober-- oder
+unterhalb des Notenliniensystems (\bs{\bf\os\ }, \bs{\bf\us}),
+links-- oder rechtsb"undig ({\bf l, r}),
+zentriert ({\bf c})
+oder so, da\3 die Breite des darunterstehenden
+Notenschriftzeichens
+der Breite des schriftlichen Hinweises nicht angepa\3t wird ({\bf n}).
+Anmerkungen, die unterhalb der Notenzeile stehen, stehen eigentlich
+in der f"ur Liedtexte vorgesehenen Zeile. Mit {\bf v} k"onnen sie
+direkt unter die Notenzeile gesetzt werden.
+\par
+Der Gebrauch von \nl{recital} bietet die M"oglichkeit, oft vorkommende
+Vortragsbezeichnungen oder Angaben zum Tempo bzw. zur Betonung
+mit Hilfe einer Kontrollsequenz einzuf"ugen. Die genaue
+Erkl"arung, durch was diese Kontrollw"orter bei der Ausgabe
+ersetzt werden, kann in 3.4 gefunden werden.
+\abschnitt
+\subheading{4) Beschreibung der Grundbausteine f"ur einen Takt}\abs
+Mit den folgenden Produktionsregeln k"onnen die elementaren
+Zeichen der Notenschrift wie Noten, Pausen, Versetzungszeichen
+und Taktstriche generiert werden.
+\abs
+{\tabskip0pt plus1fill
+\halign to\hsize{\hfill$#{}$%
+\tabskip0pt&$#$\hfill\tabskip0pt plus 1fill\cr
+\nm{note} ::=& \nm{simple note} \T
+\nm{note specification} \nm{simple note}\cr
+\nm{simple note} ::=& {\bf c} \T {\bf d} \T {\bf e} \T {\bf f}
+\T {\bf g} \T {\bf a} \T {\bf h} \cr
+\nm{note specification} ::=&
+\nm{octave} \T \nm{accidental} \T
+\nm{duration} \T\cr
+&\nm{punctuation} \T
+ \nm{note specification}
+ \nm{note specification}
+\cr
+\nm{octave} ::=& {\hbox{\bf,}} \T {\hbox{\bf{,,}}} \T
+{\hbox{\bf{,,,}}} \T {\hbox{\bf `}}
+\T {\hbox{\bf{`}{`}}} \T
+{\hbox{\bf{{`}{`}{`}}}} \T
+{\hbox{\bf{{`}{`}{`}{`}}}} \cr
+\nm{accidental} ::=& {\bf x} \T {\bf{xx}} \T {\bf{b}} \T {\bf{bb}} \T
+{\bf{n}}\cr
+\nm{duration} ::=& {\bf 1} \T
+{\bf 2} \T {\bf 4} \T {\bf 8} \T {\bf 6} \T {\bf 3} \T {\bf 5}
+\T {\bf 7} \cr
+\nm{punctuation} ::=& \nm{dot} \T
+\nm{dot} \nm{punctuation} \cr
+\nm{dot} ::=& {\hbox{\bf.}}\cr
+\nm{rest} ::=& \nm{rest specification} {\bf p} \T {\bf{p}} \cr
+\nm{rest specification} ::=& \nm{duration} \T
+\nm{punctuation} \T \cr
+&\nm{rest specification}
+ \nm{rest specification}\cr
+\nm{caesura} ::=& {\bf 0p}\cr
+\nm{barline} ::=& \strich\ \T\ \strich\strich\ \T
+\ \gleich\ \T\ \strich\strich\dpkt\ \T
+\ \dpkt\strich\strich\ \T\ \dpkt\strich\strich\dpkt
+\cr}}
+\abs
+Eine Note, dargestellt
+durch \nl{note}, besteht entweder aus \nl{simple note} oder
+\nl{simple note} versehen mit der \nl{note specification}. Dabei
+gibt \nl{simple note} den Notennamen an, \nl{note specification} n"ahere
+Angaben zur Oktavlage, Vorzeichen und Tondauer.
+Die Oktave kann mit einem der m"oglichen Terminalzeichen f"ur
+\nl{octave} eingegeben werden und das Vorzeichen wird durch die
+Anwendung der Regel f"ur
+\nl{accidental} beschrieben. Die Tondauer ist eine der m"oglichen
+Produktionen f"ur \nl{duration}, eventuell zusammen mit einer
+Punktierung, die mit \nl{punctuation} dargestellt wird.
+\par
+Pausen werden mit \nl{rest} analog zu \nl{note} abgeleitet. Das
+Atemzeichen \nl{caesura}
+gilt als Pause mit der Dauer 0, da es keinen Einflu\3 auf
+den Takt hat. \par
+Zur Einteilung eines Taktes werden noch die verschiedenen Taktstriche
+ben"otigt. Die Terminalzeichen daf"ur werden durch Anwendung der
+Regel f"ur \nl{barline} erreicht.
+\abschnitt
+\subheading{5) Beschreibung der Notengruppen}\abs
+Die hier beschriebenen Regeln generieren alle Arten von
+Notengruppierungen. Auf diese Weise werden die
+einfachen Notenschriftzeichen wie Noten, Pausen und Vorzeichen,
+die in Abschnitt 4) beschrieben werden,
+zu Einheiten zusammengefa\3t.
+Das ist \zB der Fall bei Verbalkungen und Ligaturen.
+\abs
+{\tabskip0pt plus1fill
+\halign to\hsize{\hfill$#{}$%
+\tabskip0pt&$#$\hfill\tabskip0pt plus 1fill\cr
+\nm{simple nested group} ::=& \bs{\bf beam}\lk%
+\nm{nested group}\rk \T
+ \bs{\bf slur}\lk\nm{nested group}\rk \T\cr
+ &\bs{\bf cresc}\lk\nm{nested group}\rk \T
+ \bs{\bf descresc}\lk\nm{nested group}\rk\cr
+ &\bs{\bf chord}\lk\nm{several notes}\rk \cr
+\nm{nested group} ::=& \nm{primitives} \T \nm{explanation} \T
+\nm{change} \T \cr
+&\nm{simple nested group} \T \nm{articulation group} \T\cr
+&\nm{nested group} \nm{nested group}\cr
+\nm{mismatched group} ::=& \bs{\bf group}\lk\nm{primitives}\rk
+ \nm{special group} \T\cr
+ &\bs{\bf group}\lk\nm{chord}\rk \nm{special group}\cr
+\nm{special group} ::=& \bs{\bf gslur}\lk\nm{sign number}\rk \T
+ \bs{\bf gbeam}\lk\nm{sign number}\rk \cr
+ &\bs{\bf gcresc}\lk\nm{sign number}\rk \T
+ \bs{\bf gdecresc}\lk\nm{sign number}\rk \cr
+ &\nm{special group}\nm{special group}\cr
+\nm{chord} ::=& \bs{\bf chord}\lk%
+\nm{several notes}\rk \T \nm{chord} \nm{chord}\cr
+\nm{several notes} ::=& \nm{note} \T \nm{note} \nm{several notes}\cr
+\nm{sign number} ::=& \nm{number} {\hbox{\bf-}} \nm{number} \T
+\nm{sign number} {\bf,} \nm{number} {\hbox{\bf-}} \nm{number}
+\cr}}
+\abs
+Die Unterschiede der einzelnen Notengruppen wurden schon in 2)
+erl"autert. In \nl{simple nested group}
+gibt das jeweilige Schl"usselwort an, um
+welche Art von Gruppe es sich handelt. \bs{\bf beam} gibt Anweisung,
+die folgende \nl{nested group} zu verbalken, \bs{\bf slur} spannt einen
+Bogen "uber die Gruppe, \bs{\bf cresc} bzw. \bs{\bf decresc} steht
+f"ur crescendo bzw. decrescendo. Bis auf \nl{chord} k"onnen die
+Gruppen von \nl{primitives} gebildet werden. Mit \nl{chord}
+werden die in \nl{several notes} notierten Noten zu einem
+Akkord verbunden. Au\3er Noten d"urfen in \nl{several notes}
+keine anderen Zeichen vorkommen.
+Au\3erdem erlaubt es
+das Nichtterminalsymbol \nl{simple nested group}, die eben
+beschriebenen Gruppen ineinanderzuschachteln. Diese Regel ergibt aber
+nur ``korrekt'' geschachtelte Gruppen, also solche, die sich
+nicht gegenseitig "uberlappen.
+Ein Beispiel f"ur eine Eingabe mit \nl{simple nested group} w"are
+$$\hbox{\bf \ks{slur}\{\ks{beam} \{8`a bh n{`}{`}c\}\}}\;.$$
+\par
+\vskip-0.5cm
+{\universal
+\hsize9.5cm
+\parindent6cm
+\nointerlineskip\beginsong
+\vio\C
+\group{\\{\a3}\\{\b4\a4}\\{\n5\a5}}{\\{3}\\{4}\\{5}}\lbeam13\uslur13\go
+\hfill\hbox{}\endsong}
+\vskip-0.6cm\abs
+Falls dies nicht der Fall ist,
+mu\3 die Gruppe mit Hilfe des Nichtterminalzeichens
+\nl{mismatched group} hergeleitet werden. Daf"ur stehen hinter dem
+Schl"usselwort \bs{\bf group} die \nl{primitives},
+die die Gruppe bilden.
+Diese Angaben werden gefolgt von der Variablen \nl{special group}.
+Sie gibt durch die Stellennummer der Notenschriftzeichen
+an, welche Zeichen wie
+verbunden werden:
+$$\hbox{\ks{group}{\bf \{b4.`a 8a g ba\} \ks{gslur}\{1-2\}
+\ks{gbeam}\{2-4\}}}$$
+\vskip-.5cm
+\par
+{\hsize10cm\parindent5.5cm
+\universal\nointerlineskip\beginsong
+\vio\C%
+\group{\\{\b3\v3\.1}\\{\a3}\\{\a2}\\{\b3\a3}}
+{\\{3}\\{3}\\{2}\\{3}}\ubeam24\lslur12\go
+\hfill\hbox{}\endsong}
+\vskip-0.6cm\abs
+\abschnitt
+\subheading{6) Zeichen und Zeichenketten}\abs
+Abschnitt 6) enth"alt die Produktionsregeln, die zur Erzeugung
+der schriftlichen Er\-l"au\-terungen notwendig sind. Schriftlich bedeutet
+hier, da\3 es sich um Angaben handelt, die mit Hilfe von
+normalen Text gemacht werden.
+\abs
+{\tabskip0pt plus1fill
+\halign to\hsize{\hfill$#{}$%
+\tabskip0pt&$#$\hfill\tabskip0pt plus 1fill\cr
+\nm{word} ::=& \nm{letter} \T \nm{digit} \T \nm{letter} \nm{word} \T
+\nm{digit} \nm{word}\cr
+\nm{letter} ::=& {\bf a} \T
+{\bf b} \T {\bf c} \T {\bf d} \T {\bf e} \T {\bf f} \T {\bf g}
+\T {\bf h} \T {\bf i} \T {\bf j} \T {\bf k} \T {\bf l}
+\T {\bf m} \cr
+&\T {\bf n} \T {\bf o} \T {\bf p} \T {\bf q} \T {\bf r}
+\T {\bf s} \T {\bf t} \T {\bf u} \T {\bf v} \T {\bf w} \T {\bf x}
+\T {\bf y} \T {\bf z} \T\cr
+&{\bf A} \T {\bf B} \T {\bf C} \T {\bf D}
+\T {\bf E} \T {\bf F} \T {\bf G} \T {\bf H} \T {\bf I} \T {\bf J}
+\T {\bf K} \T {\bf L} \T {\bf M} \T\cr
+&{\bf N} \T {\bf O} \T {\bf P}
+\T {\bf Q} \T {\bf R} \T {\bf S} \T {\bf T} \T {\bf U} \T {\bf V}
+\T {\bf W} \T {\bf X} \T {\bf Y} \T {\bf Z}\cr
+\nm{digit} ::=& {\bf 0} \T {\bf 1} \T
+{\bf 2} \T {\bf 3} \T {\bf 4} \T {\bf 5} \T {\bf 6} \T {\bf 7}
+\T {\bf 8} \T {\bf 9}\cr
+\nm{number} ::=& \nm{digit} \T \nm{digit} \nm{number}\cr
+\nm{text} ::=& \nm{word} \T \nm{special character} \T
+ \nm{text} \nm{text}\cr
+\nm{special character} ::=&\ {\hbox{\bf,}}\ \T\ {\hbox{\bf;}}\ \T
+ \ {\hbox{\bf.}}\ \T\ {\hbox{\bf!}}\ \T
+ \ {\hbox{\bf?}}\ \T\ {\blank}\ \T
+ \ {\hbox{\bf*}}\ \T\ {\hbox{\bf+}}\ \T
+ \ {\hbox{\bf-}}\ \T\ {\hbox{\bf`}}\ \T
+ \ {\hbox{\bf'}}\ \T\ \bs\ \T\ {\hbox{\~\ }}\cr
+\nm{omission} ::=&\slash
+\cr}}
+\abs
+W"orter, die in der Syntax mit \nl{word} bezeichnet werden, sind
+eine Folge von Buchstaben und Zahlen. \nl{number} beschreibt eine
+beliebige positive Zahl.\par
+Aus \nl{word} und \nl{special character} wird eine beliebige
+Zeichenkette \nl{text} gebildet.\par
+Die Bedeutung von \nl{omission}, dem Auslassungszeichen, wurde
+in 2) schon erw"ahnt, als \nl{songtext} erkl"art wurde.
+\abschnitt
+%
+%
+Eine
+andere gebr"auchliche Methode zur Darstellung von Produktionsregeln
+einer \kf en \G\ sind sogenannte Syntaxdiagramme. Aus diesem Grund
+wird in
+Anhang C
+das Regelsystem der \G\ f"ur die Noteneingabesprache
+der Vollst"andigkeit halber mit Hilfe der Syntaxdiagramme
+veranschaulicht.
+\abschnitt
+\abschnitt
+Nachdem in diesem Kapitel die Syntax der Noteneingabesprache mit Hilfe
+einer \kf en \G\ beschrieben wurde, wird nun ein Leitfaden f"ur die
+Anwendung der Eingabesprache gegeben.
+In dieser Anleitung wird die Bedeutung und Handhabung der
+Terminalsymbole erl"autert. Dabei wird es sich nicht vermeiden lassen,
+da\3 zu den \kf en Regeln der Syntaxbeschreibung einige Anweisungen
+hinzukommen, die nicht mehr \kf\ sind. Diese sind n"otig, um
+Mehrdeutigkeiten oder Fehler bei der "Ubersetzung auszuschlie\3en. Das
+Thema des n"achsten Kapitels ist also weniger die Syntax als die
+Semantik der Eingabesprache.
+\vfill\eject