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:
Alphabet: eine vorgegebene Menge von Symbolen (Zeichen), aus denen die sprachlichen Elemente aufgebaut sind.
Grammatik: Regeln, die angeben, auf welche Weise die Zeichen und Worte zusammenzufügen sind, um einen gültigen Satz zu erhalten.
Semantik: Bedeutung syntaktisch richtiger Zeichenkette.
Die Syntax einer Sprache wird durch die beiden Elemente Alphabet und Grammatik gebildet.1
2
3
1 Worte über dem Alphabet
2 syntaktisch richtige Worte
3 semantisch richtige Worte
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:
Menge der Terminalsymbole (Grundsymbole), der Zeichenvorrat, aus dem Worte der Sprache gebildet werden können.
Menge der Nonterminalsymbole (Hilfssymbole), sie stellen Platzhalter für diverse Wortmengen dar.
Menge der Produktionsregeln, mit denen festgelegt wird, wie gewisse Symbole durch Hilfs- oder Terminalsymbole ersetzt werden können.
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:
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.
kontextfreie Grammatik (Typ 2): links steht ebenfalls immer ein Hilfssymbol, rechts können beliebig kombiniert Terminal- und Hilfssymbole stehen.
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.
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:
ABNF
EBNF
BNF::= |
< >
[ ]
{ }
Erklärung der Metasymbole:
::= Definitionszeichen, trennt linken und rechten Regelteil
| “entweder-oder”-Zeichen, trennt die Ersatzmöglichkeiten
<, > Hilfsmittel zur Kennzeichnung der Hilfssymbole
{, } ein in diesen Klammern stehender Ausdruck kann einmal oder keinmal vorkommen
[, ] ein in eckigen Klammern stehender Ausdruck kann einmal oder keinmal vorkommen
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.
∑={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, ..
., Z, a, b, c, d, e, f, ..., _}
Φ={ <digit>, <letter>, <underscore>, <letter or digit>, <extra underscore>, <identifier>}
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>::= _
<letter or digit>::= <letter> | <digit>
<extra underscore>::= <underscore><letter or digit> | <letter or digit>
<identifier>::= <letter> | <identifier><extra 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
<identifier>::= <letter> {<extra underscore>}
Beispiel zur ABNF
Bei der ABNF kann das Hilfssymbol <extra underscore> entfallen.
<letter>, <digit>, <underscore> und <letter or digit> wie oben
<identifier>::= <letter> {[<underscore>] <letter or digit>}
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.
<identifier>
<identifier>
<extra und.>
<extra und.>
<digit>
<identifier>
<l or d>
<underscore>
<letter>
l
<identifier>
<extra und.>
n
<l or d>
t
<l or d>
_
2
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:
X
Hilfssymbol
<Name>::= <X>
Name:
Z
Y
Sequenz
<Name>::= <Y><Z>
Name:
A
Einfache Alternative
<Name>::= [<A>]
Name:
Z
B
A
Mehrfache Alternative
<Name>::= <A>|<B>|.
..|<Z>
Name:
A
Wiederholung (mind. Einmaliges Auftreten)
<Name>::= <X> {<X>}
Name:
A
Wiederholung
(auch keinmal)
<Name>::= {<X>}
Name:
Beispiel: vorzeichenlose Realzahl (PASCAL)
+
Ziffer
E
.
Ziffer
Ziffer
-
Zahl:
9
8
7
6
5
0
4
3
2
1
Ziffer:
Anwendungsmöglichkeiten
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.
SYNTAXDIAGRAMME UND BNF
zur Syntax-Beschreibung von Programmiersprachen
BNF = Backus-Naur-Form
Beschreibung in Textform
entspricht einer Grammatik
verschiedene Varianten:
BNF ..
... ALGOL
EBNF ...
PASCAL
ABNF ... ADA
Syntax-Diagramme:
graphische Darstellung
übersichtlicher als BNF
EBNF
erweiterte BNF
Meta-Zeichen:
< > ...
für Hilfssymbole
::= ... Definitions-Symbol
| ...
für Alternativen
--------------------------------------
{} ... für Wiederholungen
BEISPIEL: Namen in Pascal
<ident> ::= <letter> {<l_o_d>}
<l_o_d>::= <letter> | <digit>
<letter> ::= A|B| ...
|Z|a|b| ... |z
<digit> ::= 0|1|2| ...
|9
Ableitung
<ident> 1-> <letter> <l_o_d> <l_o_d>
3-> z <l_o_d> <l_o_d>
2-> z <digit> <l_o_d>
4-> z 3 <l_o_d>
2-> z 3 <letter>
3-> z 3 a
Ableitungsbaum
<ident>
<letter>
<l_o_d>
<l_o_d>
z
<digit>
3
<letters>
a
SYNTAX-DIAGRAMME
statt Hilfssymbol:
Terminalsymbole:
Beispiel:
ident:letter
l_o_d
l_o_d:letter
digit
digit:1
2
0
9
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
