Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 42

Backus-Naur-Form BNF

Nach den einfachen Mustern der regulären Ausdrücke werden wir nun einen Formalismus vorstellen, der eine einfache Festlegung der Syntax von Kunstsprachen ermöglicht, wie sie etwa Programmiersprachen darstellen. Die Backus-Naur-Form (kurz BNF) ist benannt nach den Autoren des ursprünglichen Vorschlags und wird insbesondere zur Festlegung der Syntax von Programmiersprachen genutzt.

Eine Beschreibung einer Syntax in BNF besteht aus Ersetzungsregeln der folgenden Form:

linkeSeite ::= rechteSeite

Die linkeSeite ist ein Name für ein zu definierendes Konzept, also eines Satzbausteines. In einer Programmiersprachendefinition könnte ein derartiges Konzept etwa den Namen Schleife haben. Die rechteSeite gibt nun eine Definition an, die die Form einer Liste von Sequenzen aus Konstanten und anderen, ebenfalls definierten Konzepten (eventuell einschließlich dem zu definierenden!) hat. Die Listenelemente bilden Alternativen und sind durch das Symbol | getrennt.

Wir erläutern diese Festlegungen an einem einfachen Beispiel. Es handelt sich wieder um die Bezeichner in einer Programmiersprache, die wir ja bereits mittels regulärer Ausdrücke beschrieben hatten.

Ziffer	::=	1|2|3|4|5|6|7|8|9|0
Buchstabe	::=	a|b|c| … |z
Zeichenkette	::=	Buchstabe|Ziffer|BuchstabeZeichenkette|ZifferZeichenkette
Bezeichner	::=	Buchstabe|BuchstabeZeichenkette

Nichtterminalsymbole und Terminalsymbole

Für derartige Definitionen haben sich bestimmte Sprechweisen etabliert. Die definierten Konzepte, die in die Klammern eingeschlossen sind, werden als Nichtterminalsymbole bezeichnet in Abgrenzung zu den Konstanten, die Terminalsymbole genannt werden. Die Bezeichnung basiert darauf, dass bei diesen Symbolen die Ersetzung mittels Regeln endet (»terminiert«).