Inhaltsverzeichnis

Sprachbeschreibung

Noch von vorher… 

<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>              ::= ...
...

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. 

Σ* ist die Menge aller möglichen Wörter über Σ
(formale) Sprache über Alphabet Σ ist eine Teilmenge von Σ*

Syntaxdiagramme

Wege durch ein Syntaxdiagramm ergeben

Das Bild als PDF und als ODG zum Bearbeiten.

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

Bestandteile von Syntaxdiagrammen:

Ü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: 

(* 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 ? ;