Erweiterte Backus - Naur - Form (EBNF)

Aus Informatik
Wechseln zu: Navigation, Suche

Die Erweiterte Backus-Naur-Form ist eine sehr häufig benutzte Form zur Definition von Grammatiken, die den Syntaxdiagrammen und Ersetzungsregeln gleichwertig ist. Sie ähnelt sehr der bisher benutzten Schreibweise bei den Produktionen, hat aber den Vorteil, dass sie einfacher maschinenlesbar ist. Die EBNF ist eine Erweiterung der BNF (Backus-Naur-Form) und ist standardisiert. Gelegentlich findet man andere Defineitionen für eine EBNF (siehe auch hier).

Für die EBNF gelten die folgenden Regeln:

Terminalsymbole werden in Anführungszeichen dargestellt, Nichtterminalsymbole werden "einfach" geschrieben.

Terminalsymbole: "a", "b", "c", "1", "+", ...
Nichtterminalsymbole: A, BEGIN, vorzeichen, ...

Die linke und die rechte Seite einer Produktionsregel werden statt durch einen Pfeil durch das Zeichen "::=" getrennt

A ::= "b"

Alternative

Kann ein Nichtterminalsymbol durch mehrere Symbolfolgen ersetzt werden, dann werden diese auf der rechten Seite durch senkrechte Striche getrennt, die dem ODER entsprechen.

Alternative ::= "b" | "c" | "d"

Optionale Wiederholung

Kann ein Teil der rechten Seite einer Produktionsregel (auch evtl. null-mal) wiederholt werden, so wird er in geschweifte Klammern eingeschlossen.

OptionaleWiederholung ::= {"a"}

Option

Darf ein Teil einer Produktionsregel optional (also nicht zwingend) vorkommen, so wird dieser wie folgt in eckigen Klammern eingeschlossen:

Option ::= [-,+] 123456

Das Vorzeichen ist optional. Die Definition ist äquivalent zu

Option ::=  123456 | +123456 | -123456

Gruppierung

Kann ein Teil einer Produktionsregel verschiedene Optionen haben, aber muss zwingend auftreten so wird er in runden Klammern eingeschlossen.

 Gruppierung ::= "a", ("a" | "b")

Nach dem ersten "a" MUSS entweder ein weiteres "a" oder ein "b" folgen. Die Definition ist äquivalent zu

 Gruppierung ::= "aa" | "ab"

Übungsaufgaben zu EBNF

Aufgabe 1

Notieren Sie die Grammatik aus Aufgabe 3 der Übungen zu Formale Sprachen und Grammatiken in EBNF-Form.



Aufgabe 2

Beschreiben Sie die Regeln zur Darstellung von Gleitkommazahlen (real) in EBNF-Form.



Aufgabe 3

Gesucht ist ein Automat, der aus mehreren Teilautomaten besteht. Er soll in einen Endzustand übergehen, wenn er eine Konstantendeklaration in vereinfachter Pascal-Syntax erhält, die der folgenden Syntax entspricht:

CONSTANT ::= unsignedNumber | sign, unsignedNumber
sign ::= "+" | "-"
unsignedNumber ::= digit, {digit}
digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"



Aufgabe 4

satz          ::= nominalgruppe, verbalgruppe
nominalgruppe ::= artikel, attribut, substantiv
verbalgruppe  ::= verb | verb, nominalgruppe
artikel       ::= "DER" | "DIE" | "DAS"
attribut      ::= "ALTE" | "FAULE" | "SCHNELLE" | "KLUGE" | ...
substantiv    ::= "MANN" | "FRAU" | "HUND" | ...
verb          ::= "GEHT" | "SINGT" | "BELLT" | ...
  • Entwerfen Sie ein Syntaxdiagramm, welches diese Grammatik abbildet.
  • Änderen Sie die Grammatik so ab, dass den Substantiven die richtigen Artikel zugeordnet werden.