diff options
Diffstat (limited to 'macros/mtex/documentation/mdoc2.tex')
-rw-r--r-- | macros/mtex/documentation/mdoc2.tex | 1206 |
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 |