1. Sprachen u. Grammatik u. BNF u. Syntaxdiagramm

Thema 1: Sprachen und Grammatiken, BNF, Syntaxdiagramm

1. Formale Sprachen

• Definition: Eine formale Sprache ist eine Menge von Zeichenketten (Strings), die aus einem bestimmten Alphabet gebildet werden und durch definierte Regeln beschrieben werden.

• Alphabet (Σ): Eine endliche Menge von Symbolen, z.B. Σ = {a, b}.

• Wörter: Endliche Sequenzen von Symbolen aus dem Alphabet, z.B. "abba".

• Sprache (L): Eine Menge von Wörtern, z.B. L = {"a", "ab", "abb"}.

2. Grammatiken

• Definition: Eine Grammatik beschreibt, wie gültige Wörter einer Sprache gebildet werden.

• Bestandteile einer Grammatik (G):

  • N (Nichtterminalsymbole): Platzhalter für Symbolfolgen (z.B. S, A, B).

  • Σ (Terminalsymbole): Endsymbole der Sprache (z.B. a, b).

  • P (Produktionsregeln): Regeln zur Erzeugung von Symbolfolgen (z.B. S → aSb | ε).

  • S (Startsymbol): Das Symbol, von dem aus die Ableitung beginnt.

Beispiel:

• Grammatik G = ({S}, {a, b}, P, S) mit P = {S → aSb | ε}

• Diese Grammatik erzeugt die Sprache: L = {"", "ab", "aabb", "aaabbb", ...} (symmetrische Wörter mit gleich vielen a und b).

3. Backus-Naur-Form (BNF)

• Definition: Eine Notation zur formalen Beschreibung der Syntax von Programmiersprachen und Grammatiken.

• Syntax:

  • ::= → Definiert eine Produktionsregel (z.B. <A> ::= a | b)
  • | → Alternativen (ODER-Verknüpfung), z.B. a | b bedeutet „a oder b“

Beispiel:

• BNF zur Beschreibung von einfachen arithmetischen Ausdrücken:

  <expr> ::= <term> | <term> + <expr>
  <term> ::= <factor> | <factor> * <term>
  <factor> ::= ( <expr> ) | number
  

• Erklärung: Ein Ausdruck <expr> kann ein Term <term> sein oder ein Term plus ein weiterer Ausdruck.

3.1 Erweiterte EBNF-Symbole:

Symbol	Bedeutung	Beispiel	Erklärung
{ }	Wiederholung (0 oder mehr)	{ a }	Beliebig viele a (auch 0-mal möglich)
[ ]	Optional (0 oder 1-mal)	[ b ]	b kann vorkommen, muss aber nicht
( )	Gruppierung	( a | b ) c
+	Mindestens einmal wiederholen	a+ (in manchen Varianten)	a muss mindestens einmal vorkommen
?	Optional (wie [ ] in EBNF)	b? (in manchen Varianten)	b ist optional

Beispiele für EBNF-Regeln:

1. Wiederholung ({ }):

   <digit> ::= { 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

   → Beliebig viele Ziffern, z.B. 123, 4567, oder auch nichts (0-mal).

2. Optional ([ ]):

   <sign> ::= [ + | - ]

   → Ein optionales Plus- oder Minuszeichen, z.B. +5, -10, oder einfach 42.

3. Kombination von Wiederholung und Optional:

   <identifier> ::= letter { letter | digit } [ "_" { letter | digit } ]

   → Definiert ein Identifier:

   • Beginnt mit einem Buchstaben
   • Gefolgt von beliebigen Buchstaben/Ziffern
   • Optional kann ein Unterstrich mit weiteren Buchstaben/Ziffern folgen
   • Beispiele: x1, var_name, count123
   • Gruppierung (( )):

   <expr> ::= ( <term> "+" <term> ) | ( <term> "-" <term> )

   → Ein Ausdruck ist entweder term + term oder term - term.

   4. Syntaxdiagramme (Railroad Diagrams)

4. Definition: Grafische Darstellung von BNF-Regeln zur besseren Visualisierung.

5. Elemente:

   • Ovale oder Rechtecke für Terminalsymbole.

   • Pfeile für den Ablauf.

   • Schleifen für Wiederholungen.

Beispiel:

• Syntaxdiagramm für <expr> ::= <term> | <term> + <expr>

  • Start → <term> → (+) → <expr> (mit einer Schleife für wiederholte Additionen).

5. Wichtige Konzepte und Anwendungen

• Warum wichtig?

  • Grundlegend für die Definition von Programmiersprachen.

  • Wird in Compilern, Parsern und zur Syntaxanalyse verwendet.

• Typische Prüfungsaufgaben:

  • Umwandlung von Grammatiken in BNF.

  • Erstellen von Syntaxdiagrammen.

  • Ableitung von Wörtern mit gegebenen Produktionsregeln.

  Beispielaufgaben:

1. Umwandlung von Grammatiken in BNF

Gegeben:

A → bCDe | cDCd
C → abA
D → ab[C]

BNF-Form:

<A> ::= b <C> <D> e | c <D> <C> d
<C> ::= a b <A>
<D> ::= a b [<C>]

2. Erstellen von Syntaxdiagrammen 3.1 Erstellen von BNF aus Syntaxdiagramm 3.2 Ableitung von Wörtern mit gegebenen Produktionsregeln