Angereicherte Backus-Naur-Form

kompakte formale Metasprache für kontextfreie Grammatiken

Die angereicherte Backus-Naur-Form (ABNF, englisch augmented BNF) ist eine Variante der Backus-Naur-Form-Metasprache zur Beschreibung von Syntax-Notationen. Sie wurde ursprünglich als RFC 2234[1] zur eindeutigen Spezifikation von RFC-Internet-Standards der IETF entwickelt und eignet sich zur syntaktischen Festlegung von technischen Sprachen und Protokollen.

Entstehung

Bearbeiten

Während der Entstehung der RFC-Standards entstand die Notwendigkeit, die benötigten Syntaxbeschreibungen durch eine standardisierte BNF-Variante darzustellen. Der Standard RFC 2234[1] vereinheitlichte die leicht abweichenden Varianten in den bisher erschienenen RFC-Standards. Neuere RFC-Standards brauchten nun keine Definition der verwendeten Metasprache mehr zu enthalten. Stattdessen reichte ein Verweis auf RFC 2234 aus.

Das Dokument enthält eine Selbstdefinition der ABNF-Syntax. Darin wird ABNF mithilfe der ABNF-Notation ausgedrückt.

Nachfolgeversionen

Bearbeiten

Später lösten die korrigierten Ausgaben RFC 4234,[2] RFC 5234[3] und RFC 7405[4] die erste Version ab.

Eigenschaften

Bearbeiten

Die ABNF-Notation baut auf der BNF auf, die auch hier geltenden Grundlagen der BNF können dort entnommen werden.

Die Erweiterungen zur BNF bestehen aus einer modifizierten Namensgebung von Regeln, Wiederholungen, Alternativen, Wertebereichen und einem Satz vordefinierter Basisregeln. Sie erlauben eine komfortablere und ausdrucksstärkere Formulierung der zu beschreibenden Strukturen. Der Schwerpunkt der Ausdrucksmittel ist für die Definition von Zeichenketten gedacht. Es wurden bewusst Mechanismen definiert, die eine bestimmte Kodierung voraussetzen (z. B. ASCII). Werden z. B. Zeichencodes oder Bereiche verwendet, so sind diese Definitionen abhängig von der ursprünglich zugrunde gelegten Zeichenkodierung, und müssen in der Regel für andere Zeichenkodierungen angepasst werden.

Kommentare

Bearbeiten

Ein Semikolon (;) leitet den Kommentar ein. Der Kommentartext folgt und reicht bis zum nächsten Zeilenende (Zeilenkommentar). Mehrzeilige Kommentare erfordern ein Semikolon je Zeile.

Terminalsymbole

Bearbeiten

Terminalsymbole sind die Werte, aus denen die Regeldefinitionen letztlich aufgebaut sind. Zu den Terminalsymbolen gehören:

  • wörtliche Zeichenketten ohne Unterscheidung zwischen Groß- und Kleinschreibung. Sie werden in doppelte Anführungszeichen " gesetzt. Sie können auch explizit mit dem Präfix %i gekennzeichnet werden. Wird das Anführungszeichen in der Zeichenkette benötigt, so muss die Zeichenkette mit einem Zeichencode für das Anführungszeichen als Sequenz ausgedrückt werden. Beispiel: "PROGRAM"
  • wörtliche Zeichenketten, bei denen Groß- und Kleinschreibung beachtet werden muss. Sie werden durch das Präfix %s gekennzeichnet. Beispiel: %s"GROSSklein"
  • Zeichencodes in
    • dezimaler Darstellung: das Präfix %d kennzeichnet das verwendete Dezimalsystem. Beispiel: %d13 für das Zeichen mit dem Codewert 13 (das ist im ASCII das Zeichen Carriage Return, kurz CR)
    • sedezimaler (auch hexadezimaler) Darstellung: das Präfix %x kennzeichnet das verwendete Sedezimalsystem. Beispiel: %x0d für das Zeichen mit dem Codewert 13.
    • binärer Darstellung: das Präfix %b kennzeichnet hierbei die Verwendung des Binärsystems. Beispiel: %b00001101 für das Zeichen mit dem Codewert 13.
  • Sequenzen (oder Ketten) von Zeichencodes: Sie bestehen aus einem Zeichencode und beliebig vielen Anhängen für Folgezeichen bestehend jeweils aus Punkt . und einer Zahl ohne %-Präfix. Sequenzen waren vor der Einführung der %s-Zeichenketten die einzige Möglichkeit, Zeichenketten mit festgelegter Groß- und Kleinschreibung anzugeben. Beispiel: %d13.10 für die Zeichenfolge Wagenrücklauf (englisch CR) und Zeilenvorschub (englisch LF) im ASCII.

Namensregeln

Bearbeiten

Namen für Definitionen dürfen die Zeichen A–Z, a–z, 0–9 und das Minuszeichen - enthalten, wobei das erste Zeichen ein Buchstabe sein muss. Im Vergleich zur BNF sind keine spitzen Klammern < > um Namen notwendig; sie sind jedoch aus Kompatibilitätsgründen möglich. Die Definition einer Regel beginnt mit dem Namen und einem Gleichzeichen =. Sie wird solange fortgesetzt, bis keine Folgezeile mehr mit erweiterter Einrückung angetroffen wird.

  Regel1 = Regelbestandteil1
    Regelbestandteil2
    Regelbestandteil3
  Regel2 = 

Eine Ausnahme betrifft die inkrementelle Alternative (siehe unten). Sie erweitert eine schon vorhandene Definition.

Bereiche

Bearbeiten

Bereiche stellen eine Menge von Zeichen dar, deren Codewerte in dem angegebenen Bereich liegen. Sie sind eine spezielle Form von Alternativen. Der Bereich wird durch die Codewerte an den Grenzen des Bereichs gebildet. Beide Werte sind mit einem Minuszeichen - verbunden, das Präfix für das verwendete Zahlensystem ist nur bei der ersten Zahl angegeben. Zum Beispiel wird hiermit der Bereich der sedezimalen Zeichenkodes 0x30 bis 0x39 (oder dezimal 48 bis 57) festgelegt. Dies entspricht im gebräuchlichen Zeichenkode ASCII den Ziffern '0', '1' usw. bis '9':

         Ziffer      =  %x3039

entspricht der Alternative

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

Wiederholungen

Bearbeiten

Angaben zu Wiederholungen werden vor den Ausdruck gesetzt und können ein Minimum und/oder ein Maximum der Vorkommen enthalten. Die explizite Form ist <Minimum>*<Maximum>, wobei ein fehlendes Minimum als 0 (nicht vorhanden) und ein fehlendes Maximum als Unendlich (unbegrenztes Vorkommen) genommen wird. Eine exakte Anzahl von n Wiederholungen wird durch die einzelne Zahl n ausgedrückt.

  beliebighaeufig    = *meinWert
  genau-dreimal      = 3allergutenDinge
  mindestens-zweimal = 2*abzweidabei
  hoechstens-drei    = *3Versuchefrei
  ein-bis-zwei       = 1*2Vornamen

Gruppen dienen der eindeutigen Vorrangdefinition bei zusammengesetzten Ausdrücken und werden durch runde Klammern ( und ) gebildet.

  Ausdruck1          = (To be) / (not to be)
  Ausdruck2          =  To (be / not) to be

Das erste Beispiel bildet die Alternativen „To be“ und „not to be“.

Im zweiten Beispiel wird eine Sequenz gebildet aus „To“, dann entweder „be“ oder „not“, und dann „to be“, also „To be to be“ oder „To not to be“.

Sequenzen

Bearbeiten

Bei Sequenzen werden alle aufgereihten Ausdrücke genau so erwartet wie angegeben. Sequenzen werden einfach durch Aneinanderreihung von Ausdrücken (getrennt mit Leerraum) gebildet.

  Sequenz            = Eins nach dem Anderen

Optionale Sequenzen

Bearbeiten

Optionale Sequenzen können einmal vorhanden sein, müssen es aber nicht. Sie werden durch eckige Klammern [ und ] gebildet. Die folgenden Idiome sind gleichwertig:

[optionalerAusdruck]
*1optionalerAusdruck
0*1optionalerAusdruck

Alternativen

Bearbeiten

Bei Alternativen kann nur genau eine der aufgeführten Varianten vorhanden sein. Alternativen werden mit Solidus bzw. Schrägstrich / getrennt aufgelistet.

  Auswahl            = Sein / Nichtsein

Inkrementelle Alternativen

Vorhandene Definitionen können inkrementell mit Alternativen erweitert werden. Damit sind dezentrale Definitionen möglich, was allerdings zu Lasten der Übersichtlichkeit gehen kann, falls die Bestandteile einer Definition weit voneinander entfernt stehen. Der Name der Regel muss mit =/ wiederholt werden.

  Status             = Ja
    Status             =/ Nein
    Status             =/ WeissNicht

entspricht

  Status             = Ja / Nein / WeissNicht

Vorrangfestlegung

Bearbeiten

Bei zusammengesetzten Ausdrücken gilt die folgende Bearbeitungsreihenfolge:

  • Namen, Zeichenketten, Terminale
  • Kommentare
  • Bereiche
  • Wiederholungen
  • Gruppen und optionale Sequenzen
  • Sequenzen
  • Alternativen

Der RFC-Standard empfiehlt das Setzen von Gruppen zur eindeutigen Vorrangfestlegung bei gemischten Ausdrücken mit Sequenzen und Alternativen.

Vordefinierte Regeln

Bearbeiten

Häufig gebrauchte Definitionen werden als core rules schon vordefiniert. Sie umfassen allgemeine Klassen wie Ziffern, Buchstaben und Leerräume.

vordefinierte Regeln in ABNF[5]
Regel = Definition Kommentar POSIX Zeichenklasse in der C-locale
ALPHA = %x41-5A / %x61-7A ; Groß- und Kleinbuchstaben A–Z bzw. a–z in ASCII [:alpha:]
BIT = "0" / "1" ; Die Werte eines Bits
CHAR = %x01-7F ; jedes 7-bit US-ASCII Zeichen, bis auf das NUL-Zeichen
CR = %x0D ; Wagenrücklauf (englisch carriage return)
CRLF = CR LF ; Internet standard für Zeilenumbruch
CTL = %x00-1F / %x7F ; Kontrollzeichen [:cntrl:]
DIGIT = %x30-39 ; Die Ziffern des Dezimalsystems 0-9 [:digit:]
DQUOTE = %x22 ; " (Anführungszeichen, engl. Double Quote)
HEXDIG = DIGIT / "A" / "B" / "C" / "D" / "E" / "F" ; Die Ziffern des Sedezimalsystems [:xdigit:]
HTAB = %x09 ; Horizontal-Tabulatorzeichen
LF = %x0A ; Zeilenvorschub (englisch linefeed)
LWSP = *(WSP / CRLF WSP) ; linearer Leerraum (nach Zeilenenden)
OCTET = %x00-FF ; 8-bit-Daten
SP = %x20 ; Leerzeichen (englisch space)
VCHAR = %x21-7E ; sicht- und druckbare Zeichen [:graph:]
WSP = SP / HTAB ; Leerraum (englisch white space)

Beispiel

Bearbeiten

Zur Demonstration wird die Beispielsprachdefinition der EBNF-Variante auf ABNF adaptiert. Sie erlaubt Programme mit einfachen Zuweisungen.

 ; ein Beispiel in ABNF - analog zum Beispiel der EBNF-Wikipediaseite
 Programm = "PROGRAM" Bezeichner
            "BEGIN"
            *( Zuweisung ";" )
            "END."
 Zuweisung = Bezeichner ":=" ( Zahl /
                               Bezeichner /
                               String )
 Bezeichner = Buchstabe *( Buchstabe / Ziffer )
 Zahl = [ "-" ] 1*Ziffer
 String = %x22 *( %x20-21 / %x23-7E ) %x22 ; "beliebige sichtbare Zeichen ausser doppelten Anführungszeichen"
 Buchstabe = %x41-5A ; Bereich der Zeichen von "A" bis "Z"
 Ziffer = DIGIT      ; alle Ziffern
 AlleZeichen = VCHAR ; alle sicht- und druckbaren Zeichen (wird hier nicht verwendet)

Das folgende willkürliche Programm passt zu der oben gegebenen Definition.

 PROGRAM WERTESETZEN
 BEGIN
   A:=-1234;
   B:=A;
   BEZEICHNER:="";
   C:=BEZEICHNER;
   R2D2:="Piep";
   RESULTAT:="Erfolg";
 END.

Vergleich mit der EBNF

Bearbeiten

Zur Orientierung sind hier die Unterschiede zwischen ABNF und EBNF[6] tabellarisch aufgeführt.

Eigenschaftenvergleich
In ABNF vorhanden In EBNF vorhanden In EBNF verwendete Zeichen
Bereiche
Zeichencodes
inkrementelle Alternativen
Wiederholungen mit Minimum und Maximum
Zeilenkommentar Blockkommentar (**)
Alternatives „Anführungszeichen“ '
Ausnahmen (englisch exceptions) -
Optionale Wiederholung {}
Explizites Terminatorzeichen ;
Spezielle Sequenz ??

Beide Notationen erlauben den gleichen Umfang an Syntaxdefinitionen.

Siehe auch

Bearbeiten
Bearbeiten
  • tools.ietf.org Tools des IETF
  • tools.ietf.org ABNF-Tools des IETF: Parsergeneratoren und Validation (englisch) nicht mehr auf aktuellem Stand (März 2016)
  • github.com/fenner/bap ‘bap’ ist ein open source ABNF-Parsergenerator.
  • bortzmeyer.org ‘eustathius’ ist ein open source Toolset zum Parsen von ABNF und Generieren von Beispielprogrammen.
  • quut.com/abnfgen ‘abnfgen’ ist ein open source Generator von Beispielprogrammen nach vorgegebener ABNF-Syntax.
  • a-k-r.org/abnf ‘ABNF’ ist ein open source Ruby Modul, das ABNF-Syntax in reguläre Ausdrücke konvertiert.
  • coasttocoastresearch.com ‘apg’ ist ein open source ABNF-Parsergenerator (für C/C++/Java/JavaScript).
  • vinegen.com/metabbs ein ABNF-Parsergenerator von VineGen (closed source).

Einzelnachweise

Bearbeiten
  1. a b D. Crocker, P. Overell: RFC 2234 – Augmented BNF for Syntax Specifications: ABNF. (überholt, englisch).
  2. D. Crocker, P. Overell: RFC 4234 – Augmented BNF for Syntax Specifications: ABNF. (überholt, englisch).
  3. D. Crocker, P. Overell: RFC 5234 – Augmented BNF for Syntax Specifications: ABNF. (englisch).
  4. P. Kyzivat: RFC 7405 – Case-Sensitive String Support in ABNF. (englisch).
  5. D. Crocker, P. Overell: RFC 5234 – Augmented BNF for Syntax Specifications: ABNF. Anhang B.1: Core Rules. (englisch).
  6. ISO/IEC 14977 : 1996(E). ISO Standard zu EBNF (1st Edition). ISO Komitee, abgerufen am 25. August 2011 (englisch).