Kleines Nachschlagewerk Informatik
Formale Sprachen
Worum geht es?
Formale Sprachen zeichnen sich dadurch aus, dass es klare Regeln für deren Bildung gibt. Zum Beispiel brauchen Programmiersprachen diese klaren Regeln, da Compiler sie sonst nicht verarbeiten könnten.

Die Regeln zur Bildung einer Sprache (also die Grammatik) kann man verschieden darstellen. Zum einen gibt es Produktionsregeln. Anschaulicher sind Syntaxdiagramme. Aber auch Automaten, die auf das Erkennen eines Wortes hin entworfen wurden, lassen sich angeben. Alle darstellungsformen lassen sich ineinander überführen.

Neben den Regeln für die Erzeugung muss natürlich auch ein Alphabet definiert werden.

Formale Sprachen lassen sich genau wie Automaten einordnen. Man wird sehen, dass die Ordnung der Sprachen und die Ordnung der Automaten zueinander passend ist.
Produktionsregeln
Egal, ob man Wörter einer Sprache erzeugen oder eine Sprache testen will, man braucht Regeln, welche die Grammatik beschreiben. Diese Regeln können je nach Sprache unterschiedlich komplex sein, aber eines zeichnet sie alle aus: Man kann die Grammatik durch Produktionsregeln beschreiben.

Produktionsregeln werden immer nach dem gleichen Muster gebildet: Man ersetzt schrittweise Nichtterminalsymbole durch Terminalsymbole. Begonnen wird mit dem Nichtterminalsymbol S, dem Startsymbol. Dieses Ersetzen geschieht so lange, bis nur noch Terminalsymbole im Ausdruck vorhanden sind. Dabei kann die Ersetzung eines Nichtterminalsymbols durch mehrere Kombinationen aus Terminal- und Nichtterminalsymbolen erfolgen.

Wie diese Regeln aussehen, wird bei den verschiedenen Sprachen gezeigt. Vereinbarung ist noch, dass man Terminalsymbole mit kleinen, Nichtterminalsymbole mit großen Buchstaben beschreibt.

Syntaxdiagramme
Syntaxdiagramme sind die grafische Darstellung einer Grammatik. Die Produktionsregeln sind oft recht abstrakt, Syntaxdiagramme sind dagegen - da es Bilder sind - zugänglicher.

Aber auch hier erfolgt die Beschreibung der Grammatik durch Ersetzungsregeln. Mit diesen kann man nicht nur - wie eben erwähnt - die Ersetzungsregeln beschreiben, sie unterstützen auch den Planungsprozess. Das Vorgehen ist der Planung eines Algorithmus - also schrittweise immer konkreter werden - nicht unähnlich.





Das obige Beispiel zeigt, wie eine ganze Zahl dargestellt wird. Das NTS ganze Zahl wird in ganze Zahl bzw. das TS 0 zerlegt. Die ganze Zahl wiederum besteht evtl. aus einem Vorzeichen, einer Ziffer ungleich 0 und evtl. weiteren Ziffern, die auch 0 sein können und sich beliebig oft wiederholen dürfen.
Backus-Naur-Form
Die Backus-Naur-Form ist - wenn man das Prinzip der Ersetzung von Nichtterminalsymbolen verstanden hat - nur noch eine Formalität. In ihr werden Nichtterminalsymbole spitz geklammert. Eine Alternative kennzeichnet man mit einem senkrechten Strich. Beschreiben lassen sich damit jedoch nur reguläre und kontextfreie Sprachen.

Wiederholungen und Optionen sieht die Backus-Naur-Form nicht vor. Nimmt man das Beispiel der ganzen Zahl, so sieht die Deklaration in BNF so aus:


      <GanzeZahl> ::= <ZahlMitVorzeichen> | <ZahlOhneVorzeichen>
      <ZahlMitVorzeichen> ::= <Vorzeichen><ZahlOhneVorzeichen>
      <Vorzeichen> ::= + | -
      <ZahlOhneVorzeichen> ::= <ZifferOhneNull>|<ZifferOhneNull><RestZiffern>
      <RestZiffern> ::= <Ziffer> | <Ziffer><RestZiffern>
      <ZifferOhneNull> ::= 1|2|3|4|5|6|7|8|9
      <Ziffer> ::= 0|1|2|3|4|5|6|7|8|9
            


Rekursionen sind möglich. Das Nichtterminalsymbol der linken Seite kann also auf der rechten Seite wieder vorkommen.
Erweiterte Backus-Naur-Form
Man hat an obigem Beispiel gesehen, dass Wiederholungen und Optionen, so wie man sie aus den Syntaxdiagrammen kennt, sinnvoll wären. Deshalb wurde die BNF erweitert.

Das Beispiel der ganzen Zahl sieht nun so aus:

      <GanzeZahl> ::= [<Vorzeichen>]<ZifferOhneNull>{<Ziffer>}
      <Vorzeichen> ::= + | -
      <ZifferOhneNull> ::= 1|2|3|4|5|6|7|8|9
      <Ziffer> ::= 0|1|2|3|4|5|6|7|8|9
            
Oftmals werden in der EBNF die Nichtterminalsymbole ohne spitze Klammern geschrieben.