Syntaxdiagramme und BNF

Um die Syntax (Aufbau) einer Programmiersprache präzise zu definieren, werden formale Notationen verwendet. Die beiden wichtigsten sind:

• Backus-Naur-Form (BNF): Textülle Notation mit Produktionsregeln.
• Syntaxdiagramme: Grafische Darstellung des gleichen Sachverhalts.

Beide beschreiben kontextfreie Grammatiken und definieren, welche Zeichenfolgen syntaktisch korrekt sind.

Die BNF wurde von John Backus und Peter Naur in den 1960er Jahren für die Beschreibung der Programmiersprache ALGOL 60 entwickelt.

Bestandteile:

• Nichtterminale (in spitzen Klammern): <bezeichner>, <ausdruck> – müssen weiter abgeleitet werden.
• Terminale: Konkrete Zeichen, die in der Sprache vorkommen (z. B. +, *, a, 0).
• ::= – „wird definiert als“
• | – Alternative („oder“)

Beispiel – Einfache arithmetische Ausdrücke:

<ausdruck>  ::= <term> | <ausdruck> "+" <term>
<term>      ::= <faktor> | <term> "*" <faktor>
<faktor>    ::= <zahl> | "(" <ausdruck> ")"
<zahl>      ::= <ziffer> | <zahl> <ziffer>
<ziffer>    ::= "0" | "1" | "2" | ... | "9"

Die EBNF erweitert die BNF um zusätzliche Operatoren für häufige Muster:

• {...} – Wiederholung (0 oder mehr Mal)
• [...] – Option (0 oder 1 Mal)
• (...) – Gruppierung

Beispiel in EBNF:

ausdruck = term { "+" term } .
term     = faktor { "*" faktor } .
faktor   = zahl | "(" ausdruck ")" .
zahl     = ziffer { ziffer } .
ziffer   = "0" | "1" | "2" | ... | "9" .

Die EBNF ist kompakter als die BNF und vermeidet viele rekursive Regeln.

Syntaxdiagramme (Railroad Diagrams) sind die grafische Äquivalenz zur BNF/EBNF. Regeln:

• Ovale/Kreise: Terminale Symbole (konkrete Zeichen).
• Rechtecke: Nichtterminale (verweisen auf andere Diagramme).
• Pfeile: Zeigen den erlaubten Weg durch das Diagramm.
• Verzweigungen: Alternativen (|).
• Schleifen (Rückpfeile): Wiederholungen ({...}).

Ein syntaktisch korrektes Wort entsteht, wenn man dem Diagramm von Eingang (links) zu Ausgang (rechts) folgen kann.

Beispiel für ausdruck = term { "+" term }:

Syntaxdiagramm "ausdruck":

  ---->[ term ]---+---->
                  |
                  +<---(+)<---[ term ]<---+

Man liest: Zuerst ein „term“, dann optional beliebig oft „+“ gefolgt von einem weiteren „term“.

Ein Parser ist ein Programm, das prüft, ob eine Eingabe der Grammatik entspricht, und dabei einen Syntaxbaum (Parse Tree) aufbaut:

• Top-down-Parser: Beginnt bei der Startregel und leitet die Eingabe ab (z. B. Recursive-Descent-Parser). Gut für EBNF-basierte Grammatiken.
• Bottom-up-Parser: Beginnt bei der Eingabe und reduziert sie zur Startregel (z. B. LR-Parser).

Der Syntaxbaum für den Ausdruck „3 + 4 * 2“:

        ausdruck
        /    \
      term    +    term
       |          /    \
     faktor    faktor  *  faktor
       |         |          |
       3         4          2

Abitur-Tipp: Im Abitur wird häufig eine BNF-Grammatik gegeben mit der Aufgabe, zu prüfen, ob ein bestimmter Ausdruck ableitbar ist, oder ein Syntaxdiagramm in BNF umzuwandeln (und umgekehrt). Übe die Ableitung von Ausdrücken wie „3 + 4 * 2“ Schritt für Schritt. Merke: Ovale = Terminale, Rechtecke = Nichtterminale, Rückpfeile = Wiederholung.