Tabulaturen parsen

Aus Informatik
Wechseln zu: Navigation, Suche

Entwickler bei diesem Projekt: Ingo Henkel und Rainer Thome

Die Idee

Tabulaturen sind eine Art der Notennotation für verschiedene Instrumente. Im Gegensatz zum normalen Notensystem wird die Tonlänge nicht durch die Note selbst gekennzeichnet sondern duch den Abstand zwischen den Noten. Wir dachten uns, ein Parser, der solche Tabulaturen überprüft und ein dazugehöriger Interpreter, der ein Abspielen der Tabulatur möglich macht, wäre ein sinnvolles Projekt(passt halt gerade so schön ins Thema). Aus diversen Gründen haben wir uns für das Schlagzeug als Instrument entschieden.

Kurze Einführung in die Notation

Beispiel

C |x---------------|----------------|
H |--x-x-x-x-x-x-x-|x-x-x-x-x-x-x-x-|
S |----o-------o---|----o-------o---|
B |o-------o-------|o-------o-------|
   1 + 2 + 3 + 4 +  1 + 2 + 3 + 4 + 
  • Jede Linie Steht für ein Instrument (z.b. C für das Crashbecken oder B für die Basstrommel)
  • ein '-' steht für eine 16tel Note
  • die Markierungen auf der jeweiligen Linie zeigen an wann welches Instrument gespielt werden muss.
  • '|' steht für die Trennung eines Taktes

Soviel zur Theorie nun zum Projekt

Ziele

  • Entwerfen eines Parsers und ggf eines Scanners zum Überprüfen der syntaktischen Korrektheit einer beliebigen Tabulatur
  • Entwerfen eines Interpreters zur Analyse der Tabulatur
  • Entwerfen eines Rahmenptrogramms das Scanner und Interpreter beinhaltet sowie die Möglichkeit zum Abspielen der Tabulatur gibt

Geplante Vorgehensweise

  • Erstellen einer Grammatik zum Problem - ABGESCHLOSSEN
  • Umsetzen der Grammatik in einem Scanner/Parser - ABGESCHLOSSEN
  • Entwerfen des Interpreters - ABGESCHLOSSEN
  • Designen des Rahmenprogramms - ABGESCHLOSSEN
  • Fertigstellen dieses Artikels - AUSSTEHEND

Entwicklung

Finden einer Grammatik zum Problem

Festlegen einiger Notationsregeln

Um eine eindeutgige Grammatik für komplette Tabulaturen herleiten zu können, müssen zunächst einige Notationsregeln für die zu verwendenden Textdateien festgelegt werden. Wir haben uns auf folgende geeinigt:

  • Jegliche Zusatzinformationen (z.b. Hinweise für den Leser, zu welchem Teil des Liedes der folgende Abschnitt gehört) sind mit "/" auszukommentieren
  • Das simulierte Drumkit wird auf ein Grundset beschränkt: 1 Bassdrum , 1 Snaredrum, 3 Tomtoms, ein Crash-Becken, ein Ride- Becken und eine Hi-Hat. Erweiterte Tabulaturen , die z.B. mit mehreren Crashbecken arbeiten, werden vom Programm nicht akzeptiert.
  • Informationen, die z.b. das Wiederholen einer gewissen Passage anzeigen, werden ignoriert
  • Die Reihenfolge der Instrumente im "Liniensystem" ist wie folgt festgelegt:
*1. Linie: Crashbecken(C,Cc)
*2. Linie: Ridebecken(R,Rd)
*3. Linie: Hi-Hat(H,HH)
*4.-6.L. : Tom-Toms(T1,T2,FT)
*7.Linie : Snaredrum(S,Sd)
*8.Linie : Bassdrum(B,bd)
  • Je nach Bedarf können einzelne Linien fehlen
  • Die zugelassenen Zeichen sind im Einzelnen:
 *Bassdrum: "o","O"
 *Snaredrum: "o","O",","f","g","r","u"
 *Tom-Toms: "o","O","f"
 *Becken: "x","X","g","b"

Für alle, die mit den Einzelnen Teilinstrumenten nichts anfangen können, hier eine kleine Hilfe:

P.S.: Herr Höpping, wie kann ich Bilder intern verlinken ohne dass sie direkt im Artikel angezeigt werden? Schaut mal hier nach

Die Grammatik

\ G \ = \ \{ \ N \ , \ T \ , \ P \ , \ S \ \}
\ N \ = \ \{ \ Q \ , \ Z \ , \ C \ , \ R \ , \ H \ , \ T_1 \ , \ T_2 \ , \ F \ , \ S \ , \ B \ , \ CL \ , \ TL \ , \ SL \ , \ BL \ ,
\ CT \ , \ TT \ , \ ST \ , \ BT \ , \ CZ \ , \ TZ \ , \ SZ \ , \ BZ \ \}
\ T \ = \ \{ \ X \ , \ x \ , \ O \ , \ o \ , \ - \ , \ g \ , \ b \ , \ f \ , \ r \ , \ u \ , \ | \ \}
\ P \ = \ \{ ( \ Q \rightarrow Z \ | \ Z \ Q \ ), \ ( \ Z \rightarrow C \ R \ H \ T_1 \ T_2 \ F \ S \ B \ ),
( \ C \rightarrow CL \ ), \ ( \ R \rightarrow CL \ ), \ ( \ H \rightarrow CL \ ),
( \ T_1 \rightarrow TL \ ), \ ( \ T_2 \rightarrow TL \ ), \ ( \ F \rightarrow TL \ ), \ ( \ S \rightarrow SL \ ), \ ( \ B \rightarrow BL \ ),
( \ CL \rightarrow CT \ | \ CT|CL \ ), \ ( \ TL \rightarrow TT \ | \ TT|TL \ ),
( \ SL \rightarrow ST \ | \ ST|SL \ ), \ ( \ BL \rightarrow BT \ | \ BT|BL \ ),
( \ CT \rightarrow CZ \ *16 \ ), \ ( \ TT \rightarrow TZ \ *16 \ ), \ ( \ ST \rightarrow SZ \ *16 \ ), \  ( \ BT \rightarrow BZ \ *16 \ ),
( \ CZ \rightarrow X \ | \ x \ | \ g \ | \ b \ | \ - \ ), \ ( \ TZ \rightarrow O \ | \ o \ | \ f \ | \ - \ ),
( \ SZ \rightarrow O \ | \ o \ | \ g \ | \ f \ | \ r \ | \ u \ | \ - \ ), \ ( \ BZ \rightarrow O \ | \ o \ | \ - \ ) \ \}
\ S \ = \ Q

Anmerkungen

  1. Das Zeichen " | " wird hier sowohl als Pipe in den Regeln wie auch als Terminal verwendet. Um Verwechslungen zu vermeiden, wird es nur als Pipe gewertet, wenn es von 2 Leerzeichen links und rechts begleitet wird, ansonsten gilt es als Terminal, also als Taktstrich.
  2. Die Produktionen von CT, TT, ST und BT werden jeweils in das entsprechende Nichtterminal " *16 " überführt. Dies bedeutet lediglich, dass das folgende Nichtterminal 16 mal folgt. Auf eine vollständige Notation wurde hier aus Platzgründen verzichtet.

Legende

Q  : Tabulatur
Z  : Zeile
C  : Crashbecken / Crash-Cymbal
R  : Ridebecken  / Ride-Cymbal
H  : HiHat
T1 : Kleines Tom / Tom 1
T2 : Großes Tom  / Tom 2
F  : Floortom    / Standtom
S  : Snaredrum   / Kleine Trommel
B  : Bassdrum    / Basstrommel
CL : Cymbal-Line
TL : Tom-Line
SL : Snare-Line
BL : Bass-Line
CT : Cymbal-Takt
TT : Tom-Takt
ST : Snare-Takt
BT : Bass-Takt
CZ : Cymbal-Zeichen
TZ : Tom-Zeichen
SZ : Snare-Zeichen
BZ : Bass-Zeichen


Der Scanner

Der Scanner hat kaum etwas zu tun, da die vorliegenden Textfiles schon direkt parsbar sind(Zeichen für Zeichen). Er führt lediglich folgende Tokens für die Zuordnung der einzelnen Lines zu den Instrumenten ein:

  • Crashbecken(in der Tabulatur deklariert durch C,Cc oder CC): C
  • Ridebecken(deklariert durch R,Rd oder RD): R;
  • Hi-Hat(H,Hh,HH): H
  • Tom 1 (T1,t): 1
  • Tom 2 (T2,T): 2
  • Floortom(F,Ft,FT): F
  • Snare(S,Sd,SD): S
  • Base(B,Bd,BD): B


Der Parser

Anmerkung: Während der Implementierung des Parsers wurden einige Änderungen an der Ausgangsgrammatik vorgenommen. So fallen zum Beispiel alle "X-line"-Nichtterminale weg.

Der Parser ist von der grundstruktur her ein RDP - Parser, der jedoch an einigen Stellen auf Schleifen zurückgreift.

Der Parser durchläuft solange die Quelldatei und überprüft sie auf einzelne "Zeilen", bis das Ende der Datei erreicht ist.

 Prozedur Parse
 begin
 //**********Beginn des Parsingvorgangs********************************
     correct:=true;
     zeilepos:=0;
     while zeilepos <= input.Count-2 do begin  //wiederholung für beliebig viele Zeilen
     if correct then zeile    //aufruf der Prozedur Zeile
     else zeilepos := input.Count;  //abbruchflag für falsche Tabulatur
   end;
  result:=Correct;
end;

Die Prozedur Zeile ruft jetzt nacheinander die 8 Prozeduren für die Einzelinstrumente des Schlagzeugs auf. eine Zeile besteht im Idealfall aus 8 Einzellinien, von denen einzelne Wegfallen dürfen. Es werden zunächst alle Prozeduren aufgerufen, sollte jedoch eine Zeile fehlen, rechnet der Parser dies nicht als Fehler an (L-->CL|nichts...). Ausnahme: Um Missverständnisse zu vermeiden, muss immer eine Bassline angegeben werden)

 procedure zeile;
 begin
   crash;
   if correct then ride;  //solange kein Fehler entdeckt wurde, arbeitet
   if correct then hihat;  der Parser weiter
   if correct then tom1;
   if correct then tom2;
   if correct then floortom;
   if correct then snare;
   if correct then bass;
 end;

Die folgende Prozedur für die Bassdrum steht stellvertretend für alle oben auftauchenden Unterprozeduren. die Prozeduren sind strukturell identisch.


 procedure bass;
 begin
 zunächst wird geürpft, ob das Ende der Datei erreicht ist. Ansonsten wird 
 die Zeile geparst.
  if zeilepos <= input.count-2 then begin   
     s:=input.Strings[zeilepos];    //zuweisung der Zeile an einen String
   
 //die folngende Selektion stellt sicher, dass die Reihenfolge der Instrumente eingehalten wird,
  d.h. die Linie für die Bassdrum darf z.B. nicht
 über der für die Snaredrum stehen (Styleguide ;) )
   
     if (s[1] in ['C','R','H','1','2','F','S']) then  begin
       correct:=false;
       Mistake.Zeile:=zeilepos;   //Merken der Zeile, in der der Fehler 
                                    passiert ist
     end
     else
     if (s[1]= 'B') then begin   //überprüfen des 1. Zeichens
       while i < length(s) do     //Solange nicht am Ende des Strings,                                 
         Basstakt;                Aufrufen der Taktprozedur
   
 Am Ende des Strings muss ein Pipe stehen,ansonsten wird die Tabulatur 
  als falsch gewertet        
       if s[i] <> '|' then begin                               
         correct:=false;
         mistake.Zeichen:=i;
       end;
       inc(Zeilepos);   //Hochzählens des Zeigers auf die aktuelle Zeile
     end;
  end;
 end;


Eine Linie kann aus beliebig vielen Takten bestehen, jeder Takt besteht aus genau 16 Zeichen(16-tel-Noten). Jeder Takt wird durch einen Taktstrich getrennt. Die Basstaktprozedur steht wieder stellvertretend für alle Taktprozeduren.

 procedure basstakt;
 var j: integer;
  begin
    If s[i] = '|' then begin   //Abprüfen des Trennpipes
     inc(i);                  //springen ins nächste Zeichen
     For j:=1 To 16 Do       //überprüfen der 16 Einzelzeichen eines Taktes
   
      If i < length(s) then  
   //  ist das aktuelle Zeichen zugelassen?
        If not (s[i] in ['O','o','-']) then begin   
          correct:= false;
          mistake.Zeichen:=i-2;
        end
        Else
          Inc(i)  // wenn zugelassen, erhöhen des Zeichenpointers
      else begin
        correct:=false;
        mistake.Zeichen:=length(S);
      end;
  end
  else  begin
    correct:=false;
    mistake.Zeichen:=i;
  end;
  if not correct then i:=length(s);  //wenn nicht korrekt, setzen des 
  Pointers auf das Ende der Zeile, sonst Endlosschleife =) 
 end;

Der Interpreter

Die Einzelnen Zeilen werden nun in Qeues geladen, um dann nachher Spaltenweise abgearbeitet werden zu können. Anzumerken ist, dass, um die Tabulatur korrekt abzuspielen, für jedes Instrument, wenn es gerade nicht gespielt wird, Dummys in die Queues geladen werden müssen. Auch dann, wenn ein Instrument in einzelnen Zeilen nicht vorhanden war. Näheres dazu in der Präsentation. Aus Zeit- und Lustgründen stelle ich nur noch den (gottseidank auskommentierten ) Quellcode für das Füllen der Queues rein ^^


 procedure Tinterpreter.fillqueues(input: Tstringlist);
   var i, j: integer; 
     s: string;
 const
    e = '-';
 begin

' '

 {Zum abspielen der Tabulatur wird jedem Instrument eine Queue zugewiesen, in
 dem die Informationen Zeile für Zeile stehen.wird ein Instrument zeitweise
 nicht genutzt, so wird ein Dummy(konstante E = '-')eingeführt, so dass am Ende
 alle Queues gleichlang sind.}
 i:= 0;
 while input.Count >= i+1 do    {durchlaufen des Eingangstextes Zeilenweise
 wenn alle instrumente geprüft sind, wird wieder mit dem Crashbecken angefangen
 zum Ende des Dokumentes. }
 begin
   s:=input.strings[i];
 ' '
   // Crash
 ' '
   {findet der Interpreter ein C, so wird diese Zeile der Queue für das
   Crashbecken hinzugefügt}
   if s[1] = 'C' then begin
     for j:=2 to length(s) do begin
       if s[j] <> '|' then  //Herrauslassen der Takttrennstriche
         cq.push(s[j]);
     end;
     Inc(i);            //wenn ein C gefunden wurde in nächste Zeile springen
     If i+1 <= input.Count Then   // und, sofern nicht das Ende der  Zeile erreicht
       s:=input.strings[i];  //ist, einen neuen String zuweisen
   end
   else           {findet er in der Zeile kein Crash, so kann er sich sicher sein,
   dass für diesen Zeilenblock kein Crash gibt. der Queue wird entsprechend
 der Länge der Zeile mit Dummyelementen gefüllt. man springt NICHT in die
   nächste Zeile }
     for j:=1 to (length(s)-(2+(round((length(s)-2)/17)))) do
       cq.Push(e);
 ' '
 {ist die vorliegende Zeile kein Crashbecken, wird solange auf andere
 instrumente ensprechend der festgelegten Reihenfolge (C,R,H,t,T,F,S,B) überprüft,
 bis  das ensprechende INstrument gefunden ist. Danach in die nächste Zeile springen.}



Den vollständigen Parser,Scanner und Interpreter kann man in den Demnächst hier Downzuloadenden Quelldateien nachlesen.