Backus-Naur-Form

Backus Naur Form einfach erklärt

Nichtterminalsymbole in der Backus-Naur-Form stehen für Kategorien von Zeichenketten, die durch Anwendung der Produktionsregeln erzeugt werden können. Terminalsymbole sind die eigentlichen Zeichen der Sprache, die nicht weiter zerlegt werden können. Währenddessen bestimmen die Produktionsregeln, wie aus bestimmten Nichtterminalen Terminalzeichen oder andere Nichtterminale erzeugt werden können. Die Anwendung dieser Regeln ermöglicht die Konstruktion und Analyse von gültigen Zeichenketten in einer gegebenen Sprache.

Backus-Naur-Form Definition

Number := Digit | Number Digit
Digit := 0 | 1 | ... | 9

Anwendung der Backus-Naur-Form in der Informatik

Backus Naur Form in theoretischer Informatik

Praktische Anwendungsbeispiele in theoretischer Informatik

Expr := '(' Expr ')' | ε

Tree := 'Node(' Tree ',' Tree ')' | 'Leaf'

Erweiterte Backus Naur Form: Definition und Unterschied

Erweiterte Backus Naur Form vs Standard Backus Naur Form

Die Standard Backus-Naur-Form und die Erweiterte Backus-Naur-Form dienen dem gleichen Zweck: Sie repräsentieren die Syntax von Sprachen und Datenstrukturen. Allerdings bietet die EBNF durch ihre erweiterten Funktionen mehr Flexibilität und Präzision. Einige wesentliche Unterschiede und Erweiterungen zwischen BNF und EBNF sind:

Die EBNF erlaubt reguläre Ausdrücke für Terminale, was bedeutet, dass eine Gruppe von Zeichen, die auf eine bestimmte Weise kombiniert wird, als eine Einheit identifiziert und manipuliert werden kann.

Mit der EBNF kann optionaler und wiederholender Code einfacher dargestellt werden, was die Modellierung von Sprachebenen und -konstrukten unterstützt, die sonst schwierig auszudrücken wären.

Die EBNF ermöglicht Gruppierung von Symbolen, was dazu beiträgt, komplexe Syntaxstrukturen einfach und übersichtlich zu definieren. Vergleichen wir BNF und EBNF genauer mit Hilfe der folgenden Tabelle:

Beispiele für die Anwendung der erweiterten Backus Naur Form

List = Element, {",", Element}
Element = letter , {letter}

List = Element, {",", Element} ;
Element = letter {letter} ;

OptionalElem = "BEGIN", ["MIDDLE"], "END" ;

Backus-Naur-Form in verschiedenen Programmiersprachen

Backus Naur Form Python: Anwendung und Beispiele

von Text, der in menschenlesbaren Sprachen verfasst ist. Wir können ein vereinfachtes Beispiel betrachten, um das Konzept besser zu verstehen. Nehmen wir an, du möchtest einen Parser in Python schreiben, der einfache arithmetische Ausdrücke versteht. Folgende BNF könnte als Ausgangspunkt dienen:

Expression := Term { "+" Term }
Term       := Factor { "*" Factor }
Factor     := Number | "(" Expression ")"
Number     := Digit { Digit }
Digit      := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Entschlüsselung der Backus Naur Form in Python

def parse_number(s):
    digits = []
    while s and s[0].isdigit():
        digits.append(s[0])
        s = s[1:]
    return "".join(digits), s

Backus Naur Form Java: Implementierung und Praktische Anwendung

Interpretation der Backus Naur Form in Java

An dieser Stelle lohnt es sich, das Parsing in Java genauer anzuschauen. Wie in Python durchläuft der Parser den Eingabestring von links nach rechts und versucht, die BNF-Regeln der Reihe nach zu erfüllen. Bei der Interpretation der Backus-Naur-Form in Java kommen jedoch einige Besonderheiten des Java-Paradigmas zum Tragen. Zum Beispiel wird in Java typischerweise ein iterativer Ansatz anstelle eines rekursiven Ansatzes gewählt. Ein weiterer Unterschied besteht darin, dass in Java Interfaces verwendet werden, um die Syntaxregeln zu definieren, die der Parser verarbeiten soll. Diese Interfaces werden dann von konkreten Klassen implementiert, die das Verhalten des Parsers bestimmen.

public class BNFParser {
    // ...

    public Term parseTerm(String s) {
        Factor firstFactor = parseFactor(s);
        // ...
        if (/* we have "*" followed by another factor */) {
            Term term = new Term();
            term.addFactor(firstFactor);
            term.addFactor(parseFactor(s));
            return term;
        }
    }

    public Factor parseFactor(String s) {
        // ...
    }

    // ...
}