BNF UND SYNTAXDIAGRAMME

BNF und Syntaxdiagramme

Allgemeines

Aufbau von Sprachen

BNF und Syntaxdiagramme werden verwendet, um die Syntax einer Sprache darzustellen und graphisch zu veranschaulichen. Mit ihnen können entweder Worte erzeugt oder die Korrektheit vorhandener Ausdrücke überprüft werden. Dazu müssen sie über eine sogenannte Metasprache verfügen. Nachstehend die Erklärung der verschiedenen Begriffe.

Sprachen sind durch folgenden Aufbau gekennzeichnet:

l Alphabet: eine vorgegebene Menge von Symbolen (Zeichen), aus denen die sprachlichen Elemente aufgebaut sind.

l Grammatik: Regeln, die angeben, auf welche Weise die Zeichen und Worte zusammenzufügen sind, um einen gültigen Satz zu erhalten.

l Semantik: Bedeutung syntaktisch richtiger Zeichenkette.

Die Syntax einer Sprache wird durch die beiden Elemente Alphabet und Grammatik gebildet.

Grammatiken

Die Grammatik einer Sprache kann nicht durch sie selbst beschrieben werden, es wird eine "Über-Sprache" benötigt. Die Sprache zum Beschreiben der sogenannten Objektsprache wird als Metasprache bezeichnet.

Eine Grammatik beinhaltet folgende Angaben:

l Menge der Terminalsymbole (Grundsymbole), der Zeichenvorrat, aus dem Worte der Sprache gebildet werden können.

l Menge der Nonterminalsymbole (Hilfssymbole), sie stellen Platzhalter für diverse Wortmengen dar.

l Menge der Produktionsregeln, mit denen festgelegt wird, wie gewisse Symbole durch Hilfs- oder Terminalsymbole ersetzt werden können.

l ein Startsymbol ( aus der Menge der Hilfssymbole).

Daraus ergibt sich, daß ein Wort über dem Alphabet genau dann zur Sprache gehört, wenn es ausgehend vom Startsymbol unter Anwendung der Produktionsregeln erzeugt werden kann.

Die Grammatik G einer Sprache läßt sich als mathematisches System G=(Φ,Σ,P,S) festlegen. Φ ist die Menge der Hilfs-, ∑ die Menge der Terminalsymbole, P die Menge der Regeln und S das Startsymbol.

Grammatiken lassen sich aufgrund der Struktur der Produktionsregeln in vier verschiedene Typen einteilen. Der Typ der Grammatik bestimmt die Mächtigkeit der von ihr erzeugten Sprache. Die vier Typen sind nach Chomsky folgendermaßen aufgebaut, wobei die reguläre Grammatik die einfachste, die allgemeine die koplexeste Grammatik ist:

l reguläre Grammatik (Typ 3): auf der linken Seite einer Regel steht genau ein Hilfssymbol, auf der rechten nur ein Terminalsymbol, oder ein Terminal- gefolgt von einem Hilfssymbol.

l kontextfreie Grammatik (Typ 2): links steht ebenfalls immer ein Hilfssymbol, rechts können beliebig kombiniert Terminal- und Hilfssymbole stehen.

l kontextsensitive Grammatik (Typ 1): auf der linken Seite sind zusätzlich zum Hilfs- auch Terminalsymbole gestattet, welche als Kontext bezeichnet werden; rechts bleibt der Kontext unverändert erhalten, das Nonterminalsymbol kann beliebig ersetzt werden.

l allgemeine Regelgrammatik (Typ 0): sowie links als auch rechts sind beliebige Kombinationen von Terminal- und Nonterminalsymbolen gestattet.

Backus-Naur-Form (BNF)

Anwendung und Formen der BNF

Die BNF wurde entwickelt, um die Syntax von Programmiersprachen zu definieren. Sie beschreibt kontextfreie Grammatiken in Textform. Weiterentwicklungen sind die erweiterte BNF (EBNF) und die allgemeine BNF (ABNF). Sie unterscheiden sich nur durch zusätzliche Metysymbole. Metysymbole der einzelnen Darstellungsformen sind:

Beispiel zur BNF

In ADA müssen <identifier> (Bezeichner) mit einem Buchstaben beginnen, danach können Buchstaben sowie Zahlen kommen, die zusätzlich durch einen Unterstrich getrennt werden können.

S=<identifier>

Produktionsregeln:

<digit>::= 0|1|2|3|4|5|6|7|8|9

<letter>::= A|B|C|D|E|F|G|H|I|J|K|L|M|

<underscore>::= _

Ein richtiges <identifier> wird nun erstellt, indem folgende Schritte angewandt werden:

Ausgangspunkt ist Startsymbol

die diesem Hilfssymbol zugeordnete Produktionsregel suchen (ist die Regel, bei der das Hilfssymbol auf der linken Seite steht)

eine Alternative dieser Regel wählen

mit den Hilfssymbolen dieser Alternative die beiden vorhergehenden Punkte wiederholen, bis nur noch Terminalsymbole vorhanden sind

Beispiel zur EBNF

Die Produktionsregeln des oben angeführten Beispieles würden sich bei der EBNF wie folgt ändern:

<letter>, <digit>, <underscore>, <letter or digit> und <extra underscore> wie oben

Beispiel zur ABNF

Bei der ABNF kann das Hilfssymbol <extra underscore> entfallen.

<letter>, <digit>, <underscore> und <letter or digit> wie oben

Ableitungsbaum

Ein Ableitungsbaum visualisiert die Anwendung der Regeln auf eine Zeichenkette und hilft so, die Korrektheit der Syntax zu überprüfen. Die Wurzel des Baumes ist das Startsymbol, die Knoten stellen die einzelnen Hilfssymbole dar und die Blätter die Grundsymbole.

Als Beispiel wird ein Ableitungsbaum der Zeichenfolge "Int_2" mit Anwendung der in Punkt 2.2 angeführten Regeln dargestellt.

Syntaxdiagramme

Zusammenhang zwischen Syntaxdiagrammen und BNF

Syntaxdiagramme sind durch die graphische Darstellung wesentlich übersichtlicher als eine BNF. Ein Diagramm entspricht immer einer Produktionsregel von einem Hilfssymbol. Der Zusammenhang von BNF und Syntaxdiagrammen ist:

Anwendung

Regel der BNF

Element im Diagramm

Hans

Terminalsymbol

<Name>::= Hans

Name:

Hilfssymbol

Name:

Sequenz

Name:

Einfache Alternative

<Name>::= [<A>]

Name:

Mehrfache Alternative

Name:

Wiederholung (mind. Einmaliges Auftreten)

Name:

Wiederholung

(auch keinmal)

<Name>::=

Name:

Beispiel: vorzeichenlose Realzahl (PASCAL)

Ziffer

Zahl:

Synthese: Die Generierung von gültigen Sprachelementen; am Eingang des Startdiagramms folgt man der Pfeilrichtung - bei Verzweigung nach Bedarf - und "entnimmt" die erhaltenen Terminalsymbole. Kommt man auf ein rechteckiges Feld, wird das dort bezeichnete Diagramm eingesetzt. Sobald der Ausgang erreicht wird, ist ein zulässiges Sprachelement gebildet.

Analyse: Aufgrund einer vorgegebenen Zeichenfolge wird entschieden, ob diese eine Sprachelement darstellt. Dazu müssen beim Durchlaufen des entsprechenden Diagramms die Zeichen der Reihe nach gefunden werden. Gelingt es, den Ausgang zu erreichen, ist die Zeichenkette syntaktisch richtig.