Formale Sprachen und Programmiersprachen
von
Michael Ziegenbalg
1. Einleitung
Programmiersprachen sind im Gegensatz zur Umgangssprache - welche auch als natürliche Sprache bezeichnet wird - keine Sprachen, die sich im Laufe der Zeit unter den gegebenen regionalen Besonderheiten entwickelt haben, sondern sie werden gewissermaßen ''konstruiert''. Trotzdem finden wir sehr viele Gemeinsamkeiten. Wie bei einer natürlichen Sprache kennen wir auch bei formalen Sprachen eine Grammatik, die die Syntax zur Bildung eines korrekten Satzes angibt. Ein Alphabet gibt uns den Zeichensatz an, in dem wir uns in unserer formalen Sprache ausdrücken,
Als Alphabet bezeichnen wir im Rahmen der Theorie formaler Sprachen eine endliche ( eventuell auch unendlichen) Menge von Symbolen., Buchstaben genannt, mit einer Ordnungsrelation
A= {a1, a2, a3, .... }
mit
a1 < a2 < a3 < ....
In der Regel werden nur endliche Alphabete betrachtet. Das lateinische Alphabet
{a,b,c,d ,..., z, A,B,C, ...., Z}
In den Fällen, in denen keine Ordnung vorliegt, dann ist das Alphabet nur ein Zeichenvorrat
Ein Wort w über einem Alphabet ist eine endliche Folge von Buchstaben des Alphabetes, die auch leer sein kann.
Das leere Wort bezeichnet man meist mit griechisch epsilon: , manchmal auch mit lambda: .
Mit A* bezeichnet man üblicherweise die Menge aller Wörter (einschließlich ) über dem Alphabet. Die Anzahl der Buchstaben in einem Alphabet bezeichnet man als die Länge l(w) = |w|:
Die wichtigsten Alphabete für Rechenanlagen sind der
ASCII-Code
und der
EBCDI-Code
Der ASCII-Code steht für American Standard Code for Information und ist insbesondere im PC-Markt und in UNIX-System weit verbreitet. Er verwendet zur Codierung einen 7-Bit Code zur Darstellung von Ziffern, Sonderzeichen und Buchstaben (groß und klein) in den Computern
Zeichen Dez. Hex. Binär
A 65 41 100 0001
B 66 42 100 0002
Mit einem 7-Bit-Code kann man 27 = 128 Zeichen darstellen.
Der EBCDI-Code steht für extended binary coded decimal interchange code, also erweiterter BCD-Code. Dieser Code nutzt zur Darstellung eines Zeichens ein Byte.
Zeichen Hex. Binär
A C1 1100 0001
B C2 1100 0002
Ein Byte wird in 2 Gruppen(Tetrade) von vier Binärziffern gruppiert
2. Sprachen
2. Künstliche Sprachen:
3. Spezifikationssprachen:
oder
Semantik