Erweiterte Backus-Naur-Form

Wenn du eine Programmiersprache lernst, merkst du schnell: Nicht jede Zeichenfolge ist erlaubt. x = 5 kann passen, aber = x 5 sieht für den Computer falsch aus. Damit ein Computer solche Formen prüfen kann, braucht er genaue Regeln. Die Erweiterte Backus-Naur-Form ist eine Schreibweise für genau solche Regeln.

Deine Lernziele

• Du verstehst, wofür EBNF benutzt wird.
• Du erkennst konkrete Zeichen und Regel-Namen in einer Sprachbeschreibung.
• Du liest Auswahl, Reihenfolge, optionale Teile und Wiederholungen.
• Du unterscheidest erlaubte Form von Bedeutung.

Wozu braucht man EBNF?

In der Informatik beschreibt Syntax die erlaubte äußere Form einer Zeichenfolge. Bei Programmen heißt das: Die Syntax sagt, ob der Programmtext richtig aufgebaut ist.

EBNF steht für Erweiterte Backus-Naur-Form. Sie ist eine genaue Schreibweise für Syntaxregeln. Mit ihr kann man beschreiben, welche Zeichenfolgen zu einer formalen Sprache gehören. Eine formale Sprache ist eine Sprache mit festgelegten Regeln, zum Beispiel eine Programmiersprache oder eine kleine Rechensprache.

Definition

EBNF ist eine formale Schreibweise für Syntaxregeln. Sie beschreibt, welche Zeichenfolgen in einer Sprache erlaubt sind.

Beispiel

Stell dir eine Mini-Sprache für Rechnungen vor.

Erlaubt: Zahl Rechenzeichen Zahl

Beispiele: 3 plus 4 8 mal 2

Nicht erlaubt: plus 3 4 3 4 plus

Die EBNF würde hier nicht ausrechnen, was 3 plus 4 ergibt. Sie würde nur festlegen, welche Form erlaubt ist.

Merke

EBNF prüft die Form. Sie erklärt noch nicht die Bedeutung und berechnet kein Ergebnis.

Bausteine einer EBNF-Regel

Eine EBNF-Regel arbeitet mit zwei Arten von Symbolen. Das ist wie bei einem Bauplan: Manche Teile sieht man später wirklich, andere sind nur Namen für Baugruppen.

Ein Terminalsymbol ist ein Zeichen oder Wort, das in der fertigen Sprache wirklich vorkommt. In EBNF stehen Terminalsymbole oft in Anführungszeichen, zum Beispiel "0", "+" oder "BEGIN".

Ein Nichtterminalsymbol ist ein Name für etwas, das noch durch Regeln erklärt wird. Zum Beispiel kann Ziffer ein Nichtterminalsymbol sein.

Eine Produktionsregel erklärt ein Nichtterminalsymbol. Links steht der Name. Rechts steht, woraus dieser Baustein bestehen darf.

Beispiel

Ziffer = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Links steht das Nichtterminalsymbol: Ziffer

Rechts stehen Terminalsymbole: "0", "1", "2" und so weiter

Die Regel sagt: Eine Ziffer darf eines dieser Zeichen sein.

Gut zu wissen

Viele EBNF-Schreibweisen beenden eine Regel mit einem Semikolon. Manche Schulmaterialien nutzen einen Punkt oder andere Zeichen. Wichtig ist, dass du innerhalb einer Aufgabe eine Schreibweise einheitlich verwendest.

Alternativen und Folgen lesen

Oft gibt es mehrere erlaubte Möglichkeiten. Eine Ziffer kann 0 oder 1 oder 2 sein. In EBNF nennt man so eine Auswahl eine Alternative.

Eine Alternative ist eine Auswahl zwischen mehreren erlaubten Formen. Häufig trennt der senkrechte Strich | die Möglichkeiten.

Eine Folge bedeutet: Die Teile müssen nacheinander kommen. In vielen EBNF-Varianten trennt ein Komma die Teile einer Folge.

Beispiel

Vorzeichen = "+" | "-" ;

Diese Regel sagt: Ein Vorzeichen ist entweder plus oder minus.

ZweistelligeZahl = Ziffer, Ziffer ;

Diese Regel sagt: Eine zweistellige Zahl besteht aus zwei Ziffern hintereinander.

Bei einer Alternative wählst du eine Möglichkeit. Bei einer Folge müssen alle Teile in der angegebenen Reihenfolge vorkommen.

Beispiel

Regel: AmpelFarbe = "rot" | "gelb" | "gruen" ;

Erlaubt: rot gelb gruen

Nicht erlaubt: rot gelb

Regel: DatumKurz = Tag, ".", Monat ;

Erlaubt: 12.04 03.11

Nicht erlaubt: .1204

Merke

Der Strich bedeutet meist: eine dieser Möglichkeiten. Eine Folge bedeutet: diese Teile nacheinander.

Optionen und Wiederholungen

Manche Teile dürfen vorkommen, müssen aber nicht. Denke an ein Minuszeichen vor einer Zahl: 5 ist möglich, -5 auch. Das Minuszeichen ist dann optional.

Eine Option ist ein Teil, der nullmal oder einmal vorkommen darf. In EBNF stehen Optionen oft in eckigen Klammern.

Beispiel

Vereinfachte Regel: ZahlMitMoeglichemMinus = [ "-" ], Ziffer, { Ziffer } ;

Der Teil [ "-" ] ist optional.

Erlaubt: 7 -7 42 -123

Nicht erlaubt: --7

Diese Regel ist bewusst einfach. Sie erlaubt auch Schreibweisen wie 007. Für echte Programmiersprachen würde man führende Nullen meist genauer regeln.

Eine Wiederholung ist ein Teil, der nullmal, einmal oder mehrmals vorkommen darf. In EBNF stehen Wiederholungen oft in geschweiften Klammern.

Beispiel

Zahl = Ziffer, { Ziffer } ;

Erlaubt: 4 19 805 123456

Die erste Ziffer ist Pflicht. Die Wiederholung danach darf auch leer bleiben. Darum ist auch 4 erlaubt.

Merke

Option heißt: höchstens einmal. Wiederholung heißt: beliebig oft, auch gar nicht.

Gruppierung und BNF

Bei längeren Regeln musst du manchmal Teile zusammenfassen. Sonst ist unklar, worauf sich eine Auswahl oder Wiederholung bezieht.

Eine Gruppierung fasst mehrere Teile zu einer Einheit zusammen. In EBNF nutzt man dafür häufig runde Klammern.

Beispiel

Faktor = Zahl | "(", Ausdruck, ")" ;

Diese Regel sagt: Ein Faktor ist entweder eine Zahl oder ein Ausdruck in Klammern.

Erlaubt: 7 (3+4)

Nicht erlaubt: 3+4)

Eine Gruppierung kann auch mit Wiederholung kombiniert werden.

Beispiel

Bezeichner = Buchstabe, { Buchstabe | Ziffer } ;

Ein Bezeichner beginnt mit einem Buchstaben. Danach dürfen beliebig viele Buchstaben oder Ziffern kommen.

Erlaubt: A x2 Name42

Nicht erlaubt: 2Name Name-42

BNF steht für Backus-Naur-Form. Das ist eine ältere Grundform für solche Syntaxregeln. EBNF erweitert diese Schreibweise. Besonders Optionen, Wiederholungen und Gruppierungen lassen sich in EBNF oft kürzer und lesbarer ausdrücken.

Gut zu wissen

EBNF ist nicht grundsätzlich mächtiger als BNF. Was du in EBNF beschreibst, kann man meistens auch in BNF beschreiben. Es wird dort nur oft länger.

Syntax ist nicht Semantik

Wenn eine Zeichenfolge zur Grammatik passt, ist sie syntaktisch korrekt. Das heißt aber noch nicht, dass sie inhaltlich sinnvoll ist.

Semantik bedeutet die Bedeutung eines Ausdrucks oder Programms. EBNF beschreibt normalerweise nicht die Semantik. Sie sagt also nicht, was ein Programm beim Ausführen tut.

Beispiel

Regel: Zuweisung = Name, "=", Wert ;

Syntaktisch passend: alter = 14 punkte = 900

Vielleicht syntaktisch passend, aber inhaltlich fraglich: alter = blau

Die Form kann stimmen. Die Bedeutung muss trotzdem extra geprüft werden.

Das ist wie bei einem deutschen Satz. „Der Stein trinkt Tee“ ist grammatisch aufgebaut. Inhaltlich ist der Satz aber merkwürdig. Syntax und Bedeutung sind also zwei verschiedene Fragen.

Merke

EBNF beantwortet: Ist die Form erlaubt? Semantik beantwortet: Was bedeutet es?

Zusammenfassung

EBNF ist eine kompakte Schreibweise für Syntaxregeln. Du nutzt sie, um festzulegen, welche Zeichenfolgen zu einer formalen Sprache gehören.

Terminalsymbole stehen wirklich in der Sprache. Nichtterminalsymbole sind Namen für Bausteine, die durch Produktionsregeln erklärt werden. Alternativen erlauben mehrere Möglichkeiten. Folgen ordnen Bausteine nacheinander an.

Optionen dürfen fehlen oder einmal vorkommen. Wiederholungen dürfen beliebig oft vorkommen, auch nullmal. Gruppierungen machen längere Regeln übersichtlich und eindeutig.