Formale Sprache

Eine formale Sprache ist eine Sprache, die nicht der Kommunikation dient, sondern zur Definition von Korrektheit in Informatiksystemen. Mit formalen Sprachen wird z.B. die Syntax von Programmiersprachen festgelegt, damit diese von einem Compiler überprüft werden können. Auch technische Spezifikationen wie der Aufbau von E-Mail-Adressen oder URLs werden mit formalen Sprachen festgelegt.

Grundbegriffe

Die Elemente einer formalen Sprache nennt man Wörter und deren Bestandteile Symbole. Alle Symbole einer Sprache bilden deren Alphabet.

Symbole können alles Mögliche sein: Buchstaben, Zahlen, Zeichen oder auch Zeichenketten.

Beispiele

• Eine Sprache, die römische Zahlen beschreibt, hat das Alphabet $\lbrace {\textrm {I}},{\textrm {V}},{\textrm {X}},{\textrm {L}},{\textrm {C}},{\textrm {D}},{\textrm {M}}\rbrace$ und enthält Wörter wie ${\textrm {XLII}}$ oder ${\textrm {MMXXIII}}$.
• Eine Sprache, die chemische Verbindungen beschreibt, könnte das Alphabet $\lbrace {\textrm {H}},{\textrm {He}},{\textrm {Li}},{\textrm {Be}},\dots ,{\textrm {Ts}},{\textrm {Og}},{}_{0},{}_{1},{}_{2},{}_{3},{}_{4},{}_{5},{}_{6},{}_{7},{}_{8},{}_{9}\rbrace$ haben und enthält Wörter wie ${\ce {PuF6}}$ oder ${\ce {C169719H270466N45688O52238S911}}$.

Grammatik

Nicht alle Wörter, die aus den Symbolen eines Alphabets gebildet werden können, sind auch in der Sprache enhalten. Zum Beispiel können aus dem Alphabet für römische Zahlen auch Wörter wie ${\textrm {MIMIMI}}$ gebildet werden, die keine gültigen römischen Zahlen darstellen. Denn zu einer Sprache gehören auch Regeln zur Bildung der Wörter. Diese Regeln fasst man zu einer Grammatik zusammen.

Beispiel

<RoemischeZahl> ::= <Tausender> <Hunderter> <Zehner> <Einer>
<Tausender>     ::= M <Tausender> | ε
<Hunderter>     ::= C | CC | CCC | CD | D | DC | DCC | DCCC | CM | ε
<Zehner>        ::= X | XX | XXX | XL | L | LX | LXX | LXXX | XC | ε
<Einer>         ::= I | II | III | IV | V | VI | VII | VIII | IX | ε

Diese Regeln bedeuten Folgendes:

1. Eine <RoemischeZahl> besteht aus einer <Tausender>-, einer <Hunderter>-, einer <Zehner>- und einer <Einer>-Stelle in dieser Reihenfolge.
2. Die <Tausender>-Stelle ist entweder leer – dafür steht das ε – oder besteht aus einem M, gefolgt von noch mehr <Tausender>n, die aber auch leer sein dürfen. Der senkrechte Strich | trennt zwei Alternativen.
3. Die <Hunderter>-Stelle ist entweder ein C, ein CC, ... ein CM oder leer.
4. Die <Zehner> und die <Einer> funktionieren genau wie die Hunderter.

Syntax

Syntaxelement	Erläuterung
<Symbol>	Dies nennt man Nichtterminalsymbol, dieses muss noch weiter durch die Anwendung von Regeln abgeleitet werden, bis irgendwann ein Wort entstanden ist, das keine Nichtterminalsymbole mehr enthält.
Sekt | Selters	Der senkrechte Strich trennt zwei Optionen, von denen nur eine gewählt werden kann.
ε	ε steht für das leere Symbol, das Nichts.
<A> ::= ???	Ersetze <A> durch ???

Ableitung von Wörtern aus den Regeln

Durch wiederholte Anwendung der Regeln einer Grammatik kann aus einem Nichtterminalsymbol ein vollständiges Wort abgeleitet werden, das keine Nichtterminalsymbole mehr enthält, z.B. aus dem Nichtterminalsymbol <RoemischeZahl> das Wort MMXXIII.

Ableitungsschritt von...		... nach...	Angewandte Regel
<RoemischeZahl>	→	<Tausender><Hunderter><Zehner><Einer>	<RoemischeZahl> ::= <T><H><Z><E>
<Tausender><Hunderter><Zehner><Einer>	→	M<Tausender><Hunderter><Zehner><Einer>	<Tausender> ::= M<Tausender>
M<Tausender><Hunderter><Zehner><Einer>	→	MM<Tausender><Hunderter><Zehner><Einer>	<Tausender> ::= M<Tausender>
MM<Tausender><Hunderter><Zehner><Einer>	→	MM<Hunderter><Zehner><Einer>	<Tausender> ::= ε
MM<Hunderter><Zehner><Einer>	→	MM<Zehner><Einer>	<Hunderter> ::= ε
MM<Zehner><Einer>	→	MMXX<Einer>	<Zehner> ::= XX
MMXX<Einer>	→	MMXXIII	<Einer> ::= III

Die Reihenfolge dieser Ableitungsschritte ist nicht fest, man hätte auch zuerst die <Einer> zu III ableiten können.

Zur Visualisierung der Ableitung zeichnet man Ableitungsbäume:

Die letztendlich abgeleiteten Terminalsymbole stehen dann unten in den Blättern des Baumes.

Zum Weiterlesen

• Sprachbeschreibungen mit Grammatiken bei inf-schule.de 🇩🇪