BNF und EBNF


Die regulären Ausdrücke gehen in ihrer Mächtigkeit nicht über die regulären Sprachen, also die Sprachklasse 3 hinaus; in der Praxis ist jedoch auch die Klasse 2 von großer Bedeutung, daher benötigen wir weitere Mechanismen.

Der Chomsky-Formalismus hat nur ein einziges Metazeichen, den Pfeil ; für die Terminal- und Nichtterminalsymbole braucht er je ein eigenes Alphabet. Für die automatische Verarbeitung ist er daher kaum geeignet; anders ist es mit den folgenden Mechanismen:

BNF (Backus-Naur-Formalismus) wurde ca. 1959 zur Notation der (kontextfreien) Grammatikregeln für die Programmiersprache ALGOL 60 eingeführt:

EBNF (Erweiterter Backus-Naur-Formalismus) ist eine bequeme Erweiterung von BNF,  wenn auch mit etwas anderen Konventionen:

Die Syntax der meisten Programmiersprachen wird heutzutage meist mittels EBNF definiert; daneben gibt es oft noch Syntaxdiagramme zur Veranschaulichung, die sich jedoch zur automatischen Verarbeitung nicht eignen.

Als Beispiel für EBNF folgen hier die Regeln für den zulässigen Aufbau regulärer Ausdrücke:

R =  |  A  |  "(" R ")"  |  R "|" R  |  R "*"  .
dabei haben wir die Menge A der Grundzeichen als bekannt und gegeben vorausgesetzt.

Mit BNF bzw. EBNF beschreiben wir kontextfreie Grammatiken  in einer Form, die für die automatische Verarbeitung geeignet ist; es gibt Parser-Generatoren, die dies mit Vorteil ausnutzen, um automatisch ein Erkennungsverfahren zu generieren. Nicht für alle Grammatiken der Klasse 2 ist dies möglich, aber für eine praktisch ausreichend große Teilmenge davon.

Auch die Regeln für das EBNF-Format selbst lassen sich wiederum in EBNF angeben! Damit kann man einen Parsergenerator schrittweise aufbauen: ein Prototyp braucht nur die Grammatik der EBNF selbst zu verstehen; mit seiner Hilfe lassen sich dann mächtigere Versionen generieren. Diese Methode, genannt Bootstrap, kann den Gesamtaufwand erheblich reduzieren (wir haben vor einigen Jahren, neben der Compilerbau-Vorlesung, einen Generator auf diese Art innerhalb von 3 Wochen geschrieben).


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36