Stefan Röttger

Das wichtigste Werkzeug zum Bau eines Compilers ist die Erweiterte Backus Naur Form (EBNF).

Die EBNF ist eine Metasprache zur formalen Beschreibung der sogenannten Syntax von regulären Programmiersprachen wie C oder Pascal. Sie wurde ursprünglich von Niklaus Wirth als Erweiterung der Backus Naur Form (BNF) zur Darstellung der Syntax der Programmiersprache Pascal eingeführt.

Mit der Syntax ist die Abfolge von Schlüsselwörtern (Token) gemeint. Eine Abfolge von Schlüsselwörtern nenn man auch Satz. Typischerweise hängt die Abfolge von den vorangegangenen Schlüsselwörtern ab, d.h. dass nicht alle möglichen Abfolgen erlaubt sind.

Mit der EBNF wird nun festgelegt, welche Abfolgen erlaubt sind und welche nicht:

Die erlaubte Reihenfolge der Schlüsselworter in einem Satz strikt identisch mit der Reihenfolge in der EBNF Definition. Zusätzlich benutzt EBNF die Metazeichen [] {} | () , um eine alternative Reihenfolge der Sprachschlüsselwörter festzulegen.

• [ wort ... ] bedeutet, dass ein wort (oder mehrere) optional vorkommen kann.
• { wort ... } bedeutet, dass ein wort (oder mehrere) beliebig oft vorkommen kann (inkl. keinmal)
• wort1 | wort2 bedeutet, dass eine von zwei Varianten, d.h. wort1 oder wort2, vorkommen kann.
• Zur Gruppierung von Worten benutzt man runde Klammern: ( wort1 wort2 ... )

Um Mehrdeutigkeiten zwischen Schlüsselwörtern und Metazeichen zu vermeiden setzt man häufig die betreffenden Schlüsselwörter in Anführungszeichen.

Jede so definierte Abfolge von Wörtern nennt man Regel. Jede Regel hat einen Namen:

regel_name ::= Abfolge

oder einfach

regel_name = Abfolge

Ein Regelname kann in anderen Regeln als Abkürzung für die zugehörige Wortfolge eingesetzt werden. Wenn im umgekehrten Fall der Regelname durch die zugeordnete Wortfolge ersetzt wird, nennt man dies Ableitung.

Daher nennt man die obigen Regeln auch Ableitungsregeln und man sagt, dass ein Satz formal korrekt ist, wenn er sich mit Hilfe der Ableitungsregeln erzeugen läßt. Die Summe der Ableitungsregeln nennt man Grammatik.

Ein Programm, welches einen bestimmten Satz anhand einer Grammatik ableitet und auf Korrektheit überprüft nennt man Parser. Der Parser ist der zentrale Bestandteil eines Compilers.

← Intro | ● | EBNF Beispiel →