Erweiterte Backus - Naur - Form (EBNF)
Aus Informatik
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. Für die EBNF gelten die folgenden Regeln:
Terminalsymbole werden ohne, Nichtterminalsymbole mit spitzen Klammern 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 | <AA>b
Optionale Wiederholung
Kann ein Teil der rechten Seite einer Produktionsregel (auch evtl. null-mal) wiederholt werden, so wird er in geschweifte Klammern eingeschlossen.
<Optionale Wiederholung> ::= {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
Notiere die Grammatik aus Aufgabe 3 der Übungen zu Formale Sprachen und Grammatiken in EBNF-Form.
Aufgabe 2
Beschreibe 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> ::= <unsigned number> | <sign><unsigned number>
<sign> ::= + | -
<unsigned number> ::= <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 | ...
- Ändere die Grammatik so ab, dass den Substantiven die richtigen Artikel zugeordnet werden.
- Schreibe ein Programm (Delphi, Prolog), welches zufallsgesteuert Sätze der Sprache ausgibt.
Aufgabe 5
Entwickle ein Frage-und-Antwort-Spiel zur Aufgabe 4.
Einzugeben ist eine Frage (z.B. "SITZT DER FAULE MANN IN DER WOHNUNG?"); diese wird auf syntaktische Korrektheit untersucht; es wird eine Antwort ausgegeben (z.B. "NEIN; DER FAULE MANN LÄUFT IN DEN WALD!").
