Formale Sprachen

Eine formale Sprache L kann festgelegt werden durch eine Grammatik oder einen Automaten.

Ein Wort ist eine endliche Hintereinanderschreibung von Zeichen oder Symbolen.

Die Menge einer Sprache zugrunde liegenden Symbole wird Alphabet genannt und häufig mit \(\Sigma\) bezeichnet.

Die Programmiersprache C ist eine formale Sprache. Die Wörter sind die jeweiligen C-Programme. Das Alphabet von C sind die Schlüsselwörter und Zeichen.

Grammatik

Zur Beschreibung eignen sich formale Grammatiken mit Terminalsymbolen und Nichtterminalsymbolen.

Die erste anwendbare Regel ist ein Nichtterminalsymbol und das Ergebnis eines Ersetzungsvorgangs gilt nur dann als Wort der Sprache wenn es keine Nichtterminale mehr enthält.

Die Regeln heißen Produktionen

Beispiel:

Summe  -> Ziffer
Summe  -> Summe + Ziffer
Ziffer -> 1
Ziffer -> 2
Ziffer -> 3

Chomsky-Hierarchie

  • Typ-0 Grammatik

Rekursiv aufzählbar

Erkannt von Turingmaschine

  • Typ-1 Grammatik

Kontextsensitiv

Anders als bei kontextfreien Grammatiken können auf der linken Seite der Produktionen kontextsensitiver Grammatiken durchaus statt einzelner Symbole ganze Symbolfolgen stehen, sofern sie mindestens ein Nichtterminalsymbol enthalten.

Erkannt von einer nichtdeterministischen, linear beschränkten Turingmaschine

  • Typ-2 Grammatik

Kontextfrei

Auf der linken Seite muss genau ein Nichtterminalsymbol stehen.

Erkannt von einem nichtdertiministischen Kellerautomaten (NPDA)

Verwendet für die meisten Programmiersprachen

  • Typ-3 Reguläre Grammatik

Auf der rechten Seite genau ein Terminalsymbol und max ein weiteres Nichtterminalsymbol. Dessen Stellung muss einheitlich immer link oder rechts sein.

-> Linksreguläre / Rechtsreguläre Grammatik

Erkannt von einem endlichen Automaten. (Glaube mit Epsilon)

Können auch beschrieben werden durch Reguläre Ausdrücke

Sie werden häufig benutzt für Suchmuster oder die Lexikalische Struktur von Programmiersprachen