====== Sprachbeschreibung ======


Noch von vorher...
----

  * [[Kellerautomat]]: Automat um Kellerspeicher erweitert; kann Kontextfreie Sprachen erkennen
  * kontextfreie Sprachen: Sprachen, die durch eine kontextfreie Grammatik erzeugt werden
  * kontextfreie Grammatik: kontextsensitive Grammatik, bei der genau ein Nichtterminal durch Nichtterminale und/oder Terminale ersetzt wird; Bsp: BNF
  * BNF: Backus-Naur-Form; Metasprache zur Definition kontextfreier Grammatiken; Bsp. aus Wikipedia:
<code BNF>
<Programm>               ::= 'PROGRAM' <Bezeichner> 'BEGIN' <Satzfolge> 'END' .
<Bezeichner>             ::= <Buchstabe> <Restbezeichner>
<Restbezeichner>         ::= | <Buchstabe oder Ziffer> <Restbezeichner>
<Buchstabe oder Ziffer>  ::= <Buchstabe> | <Ziffer>
<Buchstabe>              ::= A | B | C | D | ... | Z | a | b | ... | z   *)
<Ziffer>                 ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<Satzfolge>              ::= ...
...
</code>
  * EBNF: Erweiterte BNF; alles aus EBNF lässt sich auch mit BNF darstellen; EBNF ist nur besser lesbar und kürzer


----



Grammatiken, Syntaxdiagramme, reguläre Ausdrücke
endliche Automaten

Beispiel: Eingabe einer E-Mail-Adresse; Überprüfung auf Korrektheit; Was heießt korrekt?; Aufbau nach RFC 2822 (Requests for Comments - seit 7. April 1969); 

Die Menge der korrekt gebildeten E-Mail-Adressen ist eine formale Sprache bestehend aus: Alphabet -> Wort -> Sprache (Alle gültigen Worte)

Alphabet (stark vereinfacht): 
  Σ={a, b, c, ., @}
Wort: Hintereinanderreihung endlicher vieler Zeichen aus dem Alphabet. 
<file>Σ* ist die Menge aller möglichen Wörter über Σ</file>
<file>(formale) Sprache über Alphabet Σ ist eine Teilmenge von Σ*</file>


==== Syntaxdiagramme ====

Wege durch ein Syntaxdiagramm ergeben
  * einen Buchstaben
  * ein Wort
  * einen korrekten Namen:  Name -> Buchstabe [->b->] -> Buchstabe [->c->] ->
  * eine Domainangabe
  * eine korrekte E-Mail-Adresse
  * ...


{{:informatik-buch:theoretische_informatik:syntaxdiagramme.png?600|}}

Das Bild {{:informatik-buch:theoretische_informatik:syntaxdiagramme.pdf|als PDF}}
und
{{:informatik-buch:theoretische_informatik:syntaxdiagramme.odg|als ODG}} zum Bearbeiten.

Nun kann man an Hand der Syntaxdiagramme die Korrektheit von E-Mail-Adressen oder Domainangaben prüfen.


Bestandteile von Syntaxdiagrammen:
  * Terminalsymbole : Bestandteile des Alphabets zum Aufbau des jeweiligen Konstrukts (z.B. @ und .)
  * Nichtterminalsymbole: Mit Hilfe weiterer Syntaxdiagramme schon beschriebene Einheiten, die ebenfalls dem Aufbau des Konstruktes dienen. (z.B Name oder Domainangabe)

==== Übersetzung der Syntaxdiagramme in Produktionsregeln ====

Die Produktionen (Regeln) zu E-Mail-Adressen mit vereinfachtem Alphabet
| Buchstabe         | B -> a \\ B -> b \\ B -> c |
| Name                | N -> B \\ N -> NB |
| Domainangabe  | V -> N \\ V -> V.N \\ H -> BB  \\ D -> V.H |
| E-Mail-Adresse  | A -> N \\ A -> A.N \\ E -> A@D |


==== Die Ableitung ====
(auch Worterzeugung) eines Worts durch die Produktionsregeln entspricht einem Weg durch die Syntaxdiagramme.
Z.B.:

  E -> A@D -> A.N@D -> A.N@V.H -> A.N.N@V.H -> A.N.N@V.N.H -> N.N.N@V.N.H -> N.N.N@N.N.H -> ... -> a.cba.ac@adda.a.ca



==== Grammatikbegriff ====
^ Eine Grammatik besteht aus ^ Beispiel ^
| einer endlichen nichtleeren Menge T von Terminalsymbolen, | T = {a, b, c, ., @} |
| einer endlichen nichtleeren Menge N von Nichtterminalsymbolen, | N = {E, D, N, B, A, H, V} |
| einer endlichen Menge P vpn Produktionen (Regeln) und | P = {B -> a, B -> b, ..., E -> A@D} |
| einem Startsymbol S∈N. | E |
Kurz:
^  G = ( T, N, P, S)  ^


==== Sprache zur Grammatik ====
Eine Grammatik G = {T, N, P, S} erzeugt eine Sprache 
^ L(G) ^
über dem Alphabet T. L(G) ist dabei die Menge der Wörter über T, die vom Startsymbol S mit Hilfe der Produktionen aus P abgeleitet werden können.


==== Die Backus-Naur-Schreibweise ====
ist eine Kurzschreibweise für Produktionen. Gibt man eine Grammatik in Backus-Naur-Form an, nutzt man meist die Abkürzung BNF.
Beispiel:
^ Normalform ^ BNF ^
| B-> a \\  B -> b \\  B -> c \\    N -> B \\  N -> BN \\    H -> .N \\  H -> .NH \\    D -> NH \\    E -> N@D | B -> ''a|b|c'' \\ \\ \\ N -> ''B | BN'' \\ \\  H -> ''.N | .NH'' \\ \\  D -> ''NH'' \\  E -> ''N@D'' |


==== Die EBNF ====
ist eine Erweiterung der BNF. Sie erlaubt einfachere optionale Elemente und Wiederholung von Elementen. Sie kann nicht mehr sondern lediglich einfacher dasselbe darstellen. Beispiel aus Wikipedia:
<code>
(* ein einfaches Beispiel in EBNF − Wikipedia *)
Programm = 'PROGRAM' Bezeichner 
           'BEGIN' 
           { Zuweisung [";"] } 
           'END' "." ;
Bezeichner = Buchstabe { ( Buchstabe | Ziffer ) } ;
Zahl = [ "-" ] Ziffer { Ziffer } ;
String = '"' { AlleZeichen − '"'} '"' ;
Zuweisung = Bezeichner ":=" ( Zahl | 
                              Bezeichner |
                              String ) ;
Buchstabe = "A" | "B" | "C" | "D" | "E" | "F" | "G"
          | "H" | "I" | "J" | "K" | "L" | "M" | "N"
          | "O" | "P" | "Q" | "R" | "S" | "T" | "U"
          | "V" | "W" | "X" | "Y" | "Z" ;
Ziffer = "0" | "1" | "2" | "3" | "4" | "5" | "6" 
       | "7" | "8" | "9" ;
AlleZeichen = ? alle sichtbaren Zeichen ? ;
</code>