Backus-Naur-Form

Author: N43

Kommentare      Download

In dem Tutorial werde ich anhand einer Grammatik für natürliche und ganze Zahlen beschreiben, wie man die Backus-Naur-Form (BNF) und die erweiterte BNF (EBNF) verwendet.


1. Kurzer Hintergrund zur BNF

Die Backus Naur-Form wurde von Backus und Naur entworfen, um einen kompakteren Formalismus zum beschreiben von kontextfreien (Chomsky-2) Grammatiken zu haben. Entworfen wurde die BNF im Zusammenhang mit der Entwicklung der Sprache ALGOL 60. Später wurde die BNF zusätzlich erweitert, da sich manches noch nicht ganz geschickt
darstellen lies.


2. BNF

Regeln einer Grammatik wurden ursprünglich wie folgt geschrieben:



Mit dieser Regel kann das Nichtterminal entweder zum Terminal a, b oder c werden. Die BNF bietet für die kürzere Schreibweise das Symbol | an, was für oder steht. Aus den obigen Regeln wird dann eine einzige Regel:



Als Beispiel eine Grammatik für die natürlichen Zahlen:

Da die 0 bei den natürlichen Zahlen nicht dabei ist darf sie nicht an erster Stelle stehen. Dazu wurde eine Regel eingeführt, die für mindestens eine der Ziffern 1 bis 9 an erster Stelle sorgt. Außerdem hat jede Zahl mindestens eine Ziffer.



In der Grammatik ist Z das Startsymbol. Über die Regel wird die Möglichkeit zum Anhängen weiterer Ziffern (einschließlich der 0) gegeben.

Durch das Metasymbol | wurde bei der Grammatik viel Schreibarbeit gespart und man erkennt schneller, was die Grammatik definiert. Die erweiterte BNF liefert noch ein Symbol für optionale Wörter und eines für
Wiederholungen.

Steht ein Wort zwischen 2 eckigen Klammern, so kann es vorkommen muss aber nicht.



Durch diese Regel wird die obige Grammatik zu den ganzen Zahlen erweitert. Die 0 kann nur positiv sein. Alle anderen Zahlen können positiv und negativ sein.

Um eine beliebige Anzahl an Wiederholungen (auch 0-mal) zu kennzeichnen wurde das Metasymbol { } eingeführt.



Die Wörter dieser Grammatik bestehen aus einem a gefolgt von beliebig vielen b und einem abschließendem c. Bsp.: ac, abc, abbc, abbbc, ...

Auch mit dieser Regel kann man die obige Grammatik (der ganzen Zahlen) noch etwas kompakter schreiben.




3. Schluss

Genaugenommen ist die Angabe der obigen Grammatiken nicht vollständig. Darauf habe ich hier aber bewusst verzichtet, und mich nur auf die Metasymbole der (E)BNF konzentriert, um das Tutorial kurz zu halten.

Falls du Fragen zur (E)BNF oder Grammatiken hast kannst du diese im Forum oder einfach als Kommentar zu dem Tutorial stellen.

hallo(

hallo

Und wie würde man Operationen in die BNF einbauen, also quasi dass man Zahlen zeigen will, also alle, die man durch 2 teilen kann, quasi alle geraden, oder ist das nicht möglich?
Sorry bin im ersten Semester und mir macht das verstehen ein bissel Probleme, vllt ist ja jemand so lieb und kann mir das erklären, weil das für n Kurztest nächste woche wichtig sein könnte

Lg Judith