Formale Sprachen sind künstliche Sprachen, die es Computern ermöglichen, Daten und Informationen zu verarbeiten. Eine formale Sprache L besteht aus einer Menge von Wörtern, die wiederum aus Zeichen des Alphabets ∑  der Sprache bestehen. 

Das Alphabet  ist hierbei die Menge der Zeichen, die in einem Wort  benutzt werden dürfen, wie zum Beispiel die Buchstaben von A bis Z und Umlaute im deutschen Alphabet.

Formale Sprachen werden durch Grammatiken erzeugt.

Zu diesem Thema finden sich viele gute Einführungen u.a. sei hier die sehr informative Seite von Studyflix E-Learning empfohlen (www.studyflix.de), auf deren Inhalte hier stellenweise Bezug genommen wird.

Grammatiken

Nichtterminale Symbole können durch andere Symbole ersetzt werden, während terminale Symbole unveränderlich sind. Das heißt, man erkennt die Symbole an sogenannten Produktionsregeln. Diese Regeln beschreiben, aus welchen Zeichen welche anderen Zeichen entstehen können.

Formale Grammatiken beschreiben und erzeugen durch Symbole und Regeln formale Sprachen. Die Regeln definieren dabei, wie neue Symbole aus bereits bestehenden entstehen können. Bei den Symbolen unterscheidet man zwischen terminalen und nichtterminalen:

Man unterscheidet Grammatiken anhand der möglichen Einschränkungen ihrer Produktionsregeln. Die sogenannte Chomsky-Hierarchie stellt eine Hierarchie von Klassen formaler Grammatiken dar, welche formale Sprachen erzeugen. Darin werden vier verschiedene Arten von Typ-0 bis Typ-3 unterschieden, wobei Typ-0 die Sprache überhaupt nicht einschränkt, während Typ-3 die Grammatik sehr stark einschränkt.

Die Typ-0-Grammatik wird auch Chomsky-Grammatik oder Phasenstrukturgrammatik genannt. Allgemein kann man sagen, dass alle formalen Grammatiken mindestens vom Typ-0 sind, da hier keine Einschränkungen gestellt werden. Es kann also aus jedem Wort ein beliebiges anderes Wort entstehen.

Typ-1-Grammatiken, auch kontextsensitive Grammatiken genannt. Sie erweitern die Typ-0-Grammatik um eine Längenbeschränkung. Diese Beschränkung sagt aus, dass bei einer Produktionsregel  immer gelten muss, dass die Länge von  mindestens der Länge von  entspricht. Es gibt eine einzige Ausnahme: aus einem Symbol S darf das leere Wort  gebildet werden.

Typ-2 Grammatiken (kontextfreie Grammatiken), sind zusätzlich dadurch eingeschränkt, dass jede Regel der Grammatik auf der linken Seite genau ein nichtterminales Symbol, und auf der rechten Seite eine beliebige Kombination aus terminalen und nichtterminalen Symbolen enthalten muss. Die Kombination muss hierbei immer mindestens ein Element enthalten.

Typ-3-Grammatiken, auch reguläre Grammatiken genannt. Sie sind im Vergleich zu Typ-2-Grammatiken zusätzlich dadurch eingeschränkt, dass auf der rechten Seite der Produktionsregeln genau ein Terminalsymbol sein muss und optional ein Nichtterminalsymbol sein kann. Je nachdem, auf welcher Seite des Terminalsymbols das nichtterminale Symbol ist, spricht man von einer linksregulären oder einer rechtsregulären Grammatik. Typ-3-Grammatiken erzeugen die regulären Sprachen und werden von Endlichen Automaten erkannt.

Reguläre Grammatiken und Endliche Automaten

Die Reguläre Grammatik stellt eine Typ 3 Grammatik der Chomsky-Hierarchie dar und erzeugt reguläre Sprachen. Es ist ein 4-Tupel, bestehend aus der Menge der Terminalsymbole, der Nichtterminale und der Produktionen, sowie einem Startsymbol.

Die Grammatik wird über dieses 4-Tupel erzeugt:

N ist dabei die Menge der Nichtterminale oder auch Variablen und wird mit Großbuchstaben bezeichnet.

T ist die Menge der Terminalsymbole in Kleinbuchstaben.

S ist das Startsymbol und als Variable in N enthalten. P ist schließlich die Menge der Produktionsregeln.

Die Definition beschreibt somit zum einen die Grundelemente der Sprache, also Terminalsymbole, die beispielsweise bei Programmiersprachen für Schlüsselworte stehen. Aus diesen können dann Sätze zusammengestellt werden, die auf Produktionsregeln, bzw. Konstruktionsregeln basieren.

Beispiel

Reguläre Grammatiken erzeugen reguläre Sprachen, deshalb gibt es für jede reguläre Sprache immer mindestens eine reguläre Grammatik. Zur besseren Verständlichkeit betrachten wir die folgende Sprache als „Reguläre Grammatik Beispiel“:

   

Sie enthält alle Wörter, die mit einem bis n Nullen beginnen und mit keiner oder einer geraden Anzahl Einsen enden. Wenn man diese Sprache auf eine wie eben beschriebene reguläre Grammatik zurückführen kann, dann ist sie regulär.

Gestartet wird mit dem Startsymbol S. Dabei wird versucht zunächst das kleinstmögliche Wort zu bilden. Das wäre einfach Null.

Mit der ersten Produktionsregel „S wird umgewandelt in Null“ bekommt man genau dieses Wort.

Man benötigt aber eine Möglichkeit mehr als eine 0 zu erzeugen. Das gelingt, indem an die Null einfach erneut das Startsymbol angefügt wird:

Nachdem eine Null erzeugt wird, befindet man sich wieder in S und kann dadurch so viele beliebige Nullen erschaffen. Im nächsten Schritt muss man das Wort entweder beenden oder mit den Einsen anfangen. Dabei kann man die Produktionsregel einfach erweitern:

S wird umgewandelt in Null S oder 1 S oder Epsilon.

Doch Vorsicht! Mit dieser Regel kann man das leere Wort   erzeugen. Oder eines, das direkt mit einer 1 beginnt: . Beides darf in dieser Sprache aber nicht passieren. Deshalb muss zwischen dem Teil des Wortes, das Nullen enthält und dem Rest unterschieden werden. Dafür braucht man eine weitere Variable.

Mit dieser Regel können viele Nullen erschafft werden, dabei muss aber mindestens eine erzeugt werden, bevor man sich dem nächsten Teil des Wortes in B widmen kann. Von B aus beendet man entweder mit Epsilon oder erzeugt Einsen.

Wenn das Wort Einsen besitzt, müssen diese in gerader Anzahl vorhanden sein. Dies wird mit einer Schleife erreicht:

Dabei gelangt man von B mit einer 1 nach C und von dort mit einer weiteren 1 nach B zurück. Die Produktionsregeln erzeugen nun die beschriebene Sprache.

Endliche Automaten

Grundsätzlich gibt es für jede reguläre Grammatik einen zugehörigen deterministischen Automaten. Dieser wird durch einen nichtdeterministischen endlichen Automaten erstellt, indem aus den Nichtterminalsymbolen ein Zustand erstellt wird und zusätzlich aus jeder Konstruktionsregel einen Übergang erzeugt.

Im Gegenzug gibt es natürlich auch in jedem deterministischem endlichen Automaten eine reguläre Grammatik. Allgemein gilt: Jede Sprache, die endliche Automaten akzeptieren, wird von einer regulären Grammatik erzeugt.

Deterministische endliche Automaten (DEA)

Deterministische endliche Automaten – kurz DEA (Informatik) oder DFA (Englisch: deterministic finite state machine)– sind endlichen Automaten . Gibt man nun eine Eingabe, wobei nur Zeichen enthalten sein können, die im Eingabealphabet stehen, in den Automaten ein, dann passiert für jede Eingabe ein Zustandsübergang. Hierbei gilt, dass ein determinisitischer endlicher Automat immer eindeutig ist, bei welcher Eingabe welcher Zustandsübergang ausgeführt wird.

Die Arbeitsweise eines DEA ist hierbei so simpel wie genial: Nehmen wir an, es liegt ein Eingabewort vor, das nur aus Zeichen des Eingabealphabets besteht. Der Automat startet nun in seinem Startzustand, den wir hier nennen. Nun liest der Automat das erste Zeichen des Wortes ein, wodurch sich der Zustand des Automaten ändert. Dafür brauchen wir die Übergangsfunktion: Der Automat betrachtet den aktuellen Zustand und das eingelesene Zeichen. Er erfährt durch die Übergangsfunktion den neuen Zustand, beziehungsweise den Folgezustand. Dies geschieht so lange, bis das Wort vollständig eingelesen ist. Befindet sich der Automat nun in einem Endzustand, dann wird das Eingabewort akzeptiert. Ist der Automat jedoch in einem normalen Zustand, wird das Wort verworfen.

Beispiel-Anwendung

Als Beispiel soll ein Automat entwickelt werden, mit dessen Hilfe Telefon-Nummern erkannt werden sollen. Da es sich um ein einfaches Beispiel handeln soll, wird hierbei auf das erkennen internationaler Nummern verzichtet. Korrekte Telefon-Nummern sollen von folgendem Aufbau sein:

Die Nummer beginnt mit einer „0“  gefolgt von beliebiger Ziffer aus der Folge 1..9 , der dann wieder Ziffern aus 0…9 folgen können. Anschliessend folgt ein „/“ gefolgt von einer beliebigen Ziffer 1..9 der dann beliebig viele Ziffern von 0 …9 folgen dürfen.

Ein entsorgender endlicher Automat hat dann folgende Gestalt:

Ein wesentlicher Vorgang von EA ist das man diese sehr effizient in Programmcode überführen kann. Im folgenden ist das am Beispiel der Telefon-Nummern Erkennung dargestellt:

In der Sprache C existiert ein Konstrukt das als Zeiger oder Pointer bezeichnet wird. Zeiger repräsentieren eine besondere Art von Variablen. Ihr Inhalt ist eigentlich nebensächlich. Viel interessanter ist, dass sie auf andere Variablen zeigen können. Man betrachtet also nicht die Zeigervariable selbst, sondern über die Zeigervariable auf den Inhalt einer anderen Variablen.

Diese Indirektion ist nicht ganz leicht zu verstehen und bietet auch bei erfahrenen Programmieren immer wieder Anlass zur Verwirrung. Aus diesem Grund soll im folgenden Beitrag die Funktionsweise eines Zeigers erklärt werden.

Variablen

Eine Variable wird zum speichern von Informationen verwendet. Sie muss üblicherweise deklariert werden. D.h. man ordnet ihr einen eindeutigen Namen und einen Datentyp zu. Diese Informationen werden vom Compiler dann in einer sogenannten Symboltabelle abgelegt und verwaltet.

Nachdem man beispielsweise folgende Deklaration gemacht hat:

int myVar;

Wird in der Symboltabelle folgender Eintrag vorgenommen:

Bei diesem Vorgang fordert der Compiler vom Speichermanagement des Systems eine Adresse an, wo die damit zusammenhängenden Informationen dann gespeichert werden. Diese Speicheradresse wird als I-Wert bezeichnet, und gibt an, wo sich die Variable im Speicher befindet also (I-Wert = Standort).

Wenn wir einer Variablen nun einen konkreten Wert zuweisen, navigieren wir direkt zum Speicherort der Variablen im Speicher (dem I-Wert) und aktualisieren den Speicher an dieser Adresse mit dem neuen Wert. Die Daten, die tatsächlich im Speicher gespeichert sind, werden als R-Wert (R-Wert = Registerwert ) bezeichnet. Die Anzahl der dazu benötigten Speicherplätze hängt massgeblich vom Typ der Variablen ab.

Zeiger

Nachdem wir uns nun mit den Variablen und ihrer Funktionsweise vertraut sind, können wir uns dem Zeiger-Konstrukt zu wenden. Einfach ausgedrückt ist ein Zeiger nichts anderes als eine Variable, die auf die Speicheradresse einer anderen Variablen verweist. 

Unter Verwendung der soeben erlernten Terminologie ist ein Zeiger somit eine Variable, deren R-Wert der I-Wert einer anderen Variablen ist.

Die Deklaration einer Zeiger-Variable ist recht einfach. Um eine Zeigervariable zu definieren, wird zunächst der Typ angegeben, auf den der Zeiger zugreifen kann. Es folgt ein Stern und dann der Name der Variablen:

int *myPointer;

Der Typbezeichner (in diesem Fall int) muss mit dem Datentyp der Variablen übereinstimmen, mit der der Zeiger verwendet werden soll. Das Sternchen zeigt dem Compiler an, dass myPointer ein Zeiger ist. Da Leerzeichen in C keine Rolle spielen, kann das Sternchen an einer beliebigen Stelle zwischen dem Typbezeichner und dem Namen der Zeigervariablen platziert werden, so dass manchmal auch Folgendes angezeigt wird: int * myPointer, int * myPointer usw.

Ein Zeiger, der definiert ist, aber nicht auf irgendetwas zeigt, ist für sich genommen ein ziemlich sinnloser Zeiger. Um auf die Speicheradresse einer anderen Variablen zu verweisen, müssen wir dem Zeiger natürlich die Speicheradresse dieser Variablen zuweisen.

Dazu wird der sogenannte „Adress-of-Operator &“ verwendet. Um unseren neuen Zeiger auf den Speicherort unserer Werttypvariablen myVar zu richten, rufen wir einfach die folgende Anweisung auf:

myPointer = &myVar;

Dies vervollständigt den im vorherigen Diagramm gezeigten Link und wird als Referenzierung bezeichnet . Aus dem gleichen Grund wird der Adressoperator (&) auch als „Referenzierungsoperator“ bezeichnet.

Beispiel mit der Arduino IDE

Machen wir ein Beispiel für das, was wir bisher besprochen haben in der Arduino IDE :

void setup() {
  Serial.begin(9600);
  
  int myVar = 10;  // Initialize a variable.
  
  Serial.print("myVar's lvalue: ");
  Serial.println((long) &myVar, DEC);  // Grab myVar's lvalue
  Serial.print("myVar's rvalue: ");
  Serial.println(myVar, DEC);
  Serial.println();
  
  int *myPointer;   // Declare your pointer.
  myPointer = &myVar; //Assign myVar's memory address to pointer.
  
  Serial.print("myPointer's lvalue: ");
  Serial.println((long) &myPointer, DEC);  //myPointer's lvalue
  Serial.print("myPointer's rvalue: ");
  Serial.println((long) myPointer, DEC);  //myPointer's rvalue
}

void loop() {
}

Als Ergebnis erhalten wir auf dem Monitor folgende Ausgabe:

De-Referenzierung

Wir haben gerade gesehen, dass ein Zeiger auf eine Stelle im Speicher verweisen kann, indem er diesem Zeiger die Speicheradresse einer Variablen mit dem Referenzoperator (&) zuweist.

Wir können noch einen Schritt weiter gehen und den an dieser Speicheradresse gespeicherten tatsächlichen Wert erhalten, indem wir den Zeiger dereferenzieren. Dies wird auch als Indirektion bezeichnet und erfolgt über den Indirektionsoperator (*) mit Ihrem Zeiger.

*myPointer = 5; // Go to memory addressed stored in myPointer's rvalue (myVar's lvalue)
                //  and place the value 5 in that memory address.

Wir erweitern das obige Programm und erhalten folgendes Ergebnis:

void setup() {
  Serial.begin(9600);
  int myVar = 10;
  
  Serial.print("myVar's lvalue: ");
  Serial.println((long) &myVar, DEC);
  Serial.print("myVar's rvalue: ");
  Serial.println(myVar, DEC);
  Serial.println();
  
  int *myPointer;
  myPointer = &myVar;
  
  Serial.print("myPointer's lvalue: ");
  Serial.println((long) &myPointer, DEC);
  Serial.print("myPointer's rvalue: ");
  Serial.println((long) myPointer, DEC);
  Serial.println();

  *myPointer = 5;  //THIS IS OUR DEREFRENCING ADDITION.
  Serial.println("-----------------------");
  Serial.println("Updating *myPointer = 5");
  Serial.println();

  Serial.print("myPointer's lvalue: ");
  Serial.println((long) &myPointer, DEC);
  Serial.print("myPointer's rvalue: ");
  Serial.println((long) myPointer, DEC);
  Serial.println();

  Serial.print("myVar's lvalue: ");
  Serial.println((long) &myVar, DEC);
  Serial.print("myVar's rvalue: ");
  Serial.println(myVar, DEC);
  Serial.println();
}
void loop() {
}