BNF: Term und Expression

[burli]

Ich lese mich gerade in das Thema BNF ein und bin etwas unschlüssig über die Definition der Begriffe "Term" und "Expression". Laut Wikipedia ist ein Term ein "sinnvoller Ausdruck".

Wie ist dann zum Beispiel folgendes zu interpretieren?

Code: Alles auswählen

expr ::= term | term + expr

[BlackJack]

@burli: Das kannst Du nicht wirklich nur an den Bedeutungen der Worte fest machen. Da fehlt ja jetzt noch etwas. Man möchte bei Grammatiken oft gewisse Eigenschaften haben, zum Beispiel da drin auch gleich den Operator-Vorrang festlegen, Rechts- oder Linksassoziativität ausdrücken, oder mit einem Token vorausschauend eindeutig halten, und dann muss man die komplizierter schreiben als man das intuitiv machen würde und „Zwischenschritte” einführen. Und denen muss man dann natürlich Namen geben.

[burli]

Ich weiß, dass es nicht vollständig ist. Es geht erstmal um die Grundlagen. Zum Beispiel für einfache Formeln

(1+3)*(4+5)

Dafür ist in dem Beispiel folgendes definiert:

Code: Alles auswählen

expr ::= term | term + expr
term ::= factor | factor * term
factor ::= number | (expr)

Ein Faktor ist ein Operand einer Multiplikation (oder Division). Der Begriff Term taucht in der BNF Lektüre immer im Zusammenhang mit der Addition auf. Aber entweder bin ich jetzt völlig auf dem Holzweg oder diese Beispiele sind Blödsinn.

[deets]

Du bist auf dem Holzweg.

Die Beispiele sind eine Standardkonstruktion fuer arithmetische Ausdruecke mit Addition und Multiplikation, vobei letztere Praezedenz vor ersterer hat.

Und "das Thema BNF" und "Term und Expression" haben eigentlich nichts miteinander zu tun, bei Grammatiken im allgemeinen spricht man von Terminalen und Nicht-Terminalen. Expr und Term sind spezifisch fuer deine konkrete Grammatik.

[burli]

Die Beispiele sind eine Standardkonstruktion fuer arithmetische Ausdruecke mit Addition und Multiplikation.

Nach BNF Regeln eigentlich nichtmal das. Bei BNF werden Non Terminals eigentlich in <> gesetzt.

[deets]

Das habe ich voellig vergessen. Aber es aendert ja auch nix - in dem Moment, wo etwas in einer rechten Seite als Name auf einer linken auftaucht, ist es ja implizit ein nicht-terminal. Und fuer die Betrachtung hier jetzt ja auch nicht weiter relevant, wie da die exakte Nomenklatur ist. Andere machen's durch gross/kleinschreibung, und dritte durch Anfuehrungszeichen um Terminale.

Deine Verstaendnisprobleme ruehren aber doch nicht daher, oder?

[BlackJack]

@burli: Du hast da eigentlich doch Terminale drin, es sei denn Du definierst +, *, und die Klammern noch mal als Nicht-Terminale die einfach nur für das jeweilige Zeichen als Terminal stehen.

Schreiben wir das Beispiel mal ohne `term` und `factor`:

Code: Alles auswählen

expr ::= number | '(' expr ')' | expr op expr
op ::= '+' | '*'

Diese Grammatik hat zwei Probleme:

1. Eine Endlosrekursion weil eine der Alternativen von `expr` wieder mit `expr` beginnt.
2. Man kann damit Syntaxbäume aus Ausdrücken erstellen, bei denen die „Punkt vor Strich”-Regel aus der Mathematik nicht mehr gilt.

[burli]

@burli: Du hast da eigentlich doch Terminale drin, es sei denn Du definierst +, *, und die Klammern noch mal als Nicht-Terminale die einfach nur für das jeweilige Zeichen als Terminal stehen.

Ich denke, so weit hab ich BNF schon verstanden. IMHO müsste es heißen

Code: Alles auswählen

<expr> ::= <term> | <term> + <expr>

, da expr und term ja Non Terminals sind, oder liege ich da auch falsch? Gut, je nach dem, ob man nach BNF, EBNF oder was auch immer geht. In dem Text wurde aber auf BNF hingewiesen.

[burli]

Deine Verstaendnisprobleme ruehren aber doch nicht daher, oder?

Nein, mein Problem ist es eigentlich, eine entsprechende Definition für die Begriffe term, expression oder factor zu finden.

Ein Faktor ist in der Mathematik ein Operand für eine Multiplikation, aber Expression und Term sind eigentlich recht ähnlich.

[deets]

Du kommst da vom falschen Ende her. Und mit Verlaub - so viel Unkenntnis in diesem Bereich macht deine Kritik an pyparsing und seinem vermeintlichen Mangel an Dokumentation noch deutlich fragwuerdiger. Denn offensichtlich brauchst du eine Einfuehrung in die Syntaxanalyse. Ist ja ok. Aber deine Unkenntnis in diesem Bereich dann dafuer spezialisierten Tools anzulasten? Finde ich unfair.

Wie dem auch sei.

Worum es hier geht, hat BlackJack schon angedeutet: es geht nicht um sauber definierte Begriffe aus der Mathematik. In der ist ja wohl auch kaum der Zugriff zB auf Objekt-Attribute zu finden, wie es einen in einer Programmiersprache interessiert.

Sondern um grammatikalische Regeln, welche dir einen Ausdruck zerlegen in einen dazugehoerigen abstrakten Syntax Baum oder etwas aehnliches. Und da muss man - je nach Parser - unterschiedliche Klimmzuege machen, um das gewuenschte Ergebnis zu erreichen.

In einer Programmiersprachen-Grammatik ist eine expression ueblicherweise etwas ,das einen Wert liefert. Und dann faengt man an, sich von oben nach unten (im Sinne einer Operator-Praezedenz) herabzuarbeiten. Dazu benutzt man dann Nicht-Terminale um Teilausdruecke bzw. Knoten im Baum zu bezeichnen, und so kommt man dann bis nach ganz "unten".

Du kannst das ganze auch erstmal umgekehrt betrachten: Du benutzt deine Regeln, um einen Ausdruck zu "produzieren". Dann wird das vielleicht etwas klarerer:

Nehmen wir mal diese "BNF":

Code: Alles auswählen

<expr> ::= <term> | <term> + <expr>
<term> ::= <faktor> | <faktor> * <term>
<factor> :: = <number> | "(" <expr> ")"
<number> ::= "0" | "1"

Dann kannst du daraus jetzt einen Ausdruck produzieren:

Code: Alles auswählen

<expr> -> <term> + <expr> -> <faktor> + <expr> -> <number> + <expr> -> 0 + <expr> -> 0 + <faktor> * <term> -> 0 + <number> * <term> -> 0 + 1 * <term> -> 0 + 1 * <factor> -> 0 + 1 * ( <expr> ) -> 0 + 1 * ( <term>) -> 0 + 1 * (<faktor>) -> 0 + 1 * ( <number> ) -> 0 + 1 * ( 0 )

Und ein Parser ist nun ein Stueck code, das genau diese Produktionen umgekehrt durchfuehrt, und dir aus einzelnen Tokens (den Terminalen) eine Ableitung aus der Grammatik liefert.

[burli]

Worum es hier geht, hat BlackJack schon angedeutet: es geht nicht um sauber definierte Begriffe aus der Mathematik. In der ist ja wohl auch kaum der Zugriff zB auf Objekt-Attribute zu finden, wie es einen in einer Programmiersprache interessiert.

Sondern um grammatikalische Regeln, welche dir einen Ausdruck zerlegen in einen dazugehoerigen abstrakten Syntax Baum oder etwas aehnliches. Und da muss man - je nach Parser - unterschiedliche Klimmzuege machen, um das gewuenschte Ergebnis zu erreichen.

Vielleicht werfe ich Grammatik und Mathematik durcheinander. Vielleicht beziehe ich mich zu stark auf die Mathematik, weil es sich bei dem Beispiel um die Auflösung von mathematischen Ausdrücken geht.

[sma]

Nach BNF Regeln eigentlich nichtmal das. Bei BNF werden Non Terminals eigentlich in <> gesetzt.

Ich denke nicht, dass es die eine feste Syntaxform für BNF gibt. RFC 2234 bzw. 4234 bzw. 5234 beschreibt z.B. einen Vorschlag, wo keine <> vorkommen. Gerne werden auch Terminal-Symbole in " eingeschlossen - in Anlehnung an Wirths EBNF glaube ich. Ich habe auch schon gesehen, dass GROSSBUCHSTABEN benutzt werden und Nicht-Terminal-Symbole dann mit einem Kleinbuchstaben anfangen. Oder man schreibt diese zur Unterscheidung kursiv.

Letztlich muss man immer definieren, wie die Syntax ist. Netterweise kann man BNF-Syntax in sich selbst beschreiben

Stefan

[sma]

Die Begriffe "expr", "term" und "factor" für das angegebene Beispiel haben sich einfach eingebürgert. Man hätte auch "foo", "bar" und "baz" benutzen können. Ein Faktor ist einfach ein Teil einer Multiplikation und Term eigentlich ein beliebiger mathematischer Ausdruck, in diesem Fall aber als additiver Term gemeint. Und Ausdruck ist eben was sehr generelles. "term" hat NICHTS mit einem Terminal-Symbol (oder Nicht-Terminal-Symbol) zu tun.

Auf der linken Seite einer Grammatik-Regel können durchaus auch Nicht-Terminal-Symbole stehen, nur ist das dann keine kontextfreie Grammatik mehr und man ignoriert sie daher fast immer im Compilerbau der Informatik.

Und eine Regel "foo = foo op foo" kann sowohl links- als auch rechts-rekursiv sein. Das ist nicht an sich falsch. Man kann IIRC jede links-rekursive Grammatik-Regel in eine gleichwertige rechts-rekursive umwandeln und umgekehrt. Für Menschen sind häufig links-rekursive Regeln einfacher lesbar, doch die sind Gift für einen handgeschriebenen "recursive descent" Parser und die Klasse der LL-Parsergeneratoren (z.B. antlr), die man recht einfach bauen kann. Yacc oder Bison sind LALR-Parsergeneratoren, die wiederum links-rekursive Regeln benötigen. Diese galten lange Zeit als effizienter, weil sie statt mit rekursiven Funktionen über Zustandsautomaten funktionieren, die aber recht komplex zu konstruieren sind - daher ja überhaupt Programme, die derartige Parser automatisch erzeugen können. Heutzutage ist es aber normal, dass ein Parser komplett im Hauptspeicher übersetzt und es ist kein Problem, wenn er einige Dutzend oder Hundert Funktionsaufrufe schachtelt. Das sind wenige MB RAM, die da für den Stack benötigt werden und die Zeiten, wo vielleicht 10 verschachtelte Unterprogrammsprünge bei 4 KB RAM für ein Fortran-Programm zur Verfügung standen, sind vorbei. Die dritte Klasse von Parsergeneratoren sind PEG-Parser wie z.B. pyparsing. Auch diese können prinzipiell nicht mit Links-Rekursion umgehen, allerdings kann man für alle praktischen Fälle mit viel RAM hier schummeln, wie ein Paper gezeigt hat. Ein moderner PEG-Parser kann daher auch links-rekursive Regeln verarbeiten.

Noch mal zurück zu der Frage, wie man "expr", "term" oder "factor" definiert. Die Antwort ist simpel: Durch das, was auf der rechten Seite steht. Es sind nur Namen, die nur für einen Menschen Bedeutung haben, nicht für den Computer. Es gibt keine festgelegte Standardbedeutung.

Stefan

[deets]

Ich fand auch Earley-Parser wie sie mit SPARK fuer Python zur Verfuegung stehen ziemlich nett - die kommen naemlich mit allen kontextfreien Grammatiken klar - zum Preis von O(n**3) wenn's sehr bloede laeuft, aber da muss man schon was sehr pathologisches bauen.

[burli]

Es sind nur Namen, die nur für einen Menschen Bedeutung haben, nicht für den Computer. Es gibt keine festgelegte Standardbedeutung.

Ok, dass war mir soweit schon klar. Für den Computer bzw den Parser ist das alles ein Blabla. Es ging mir ja auch darum zu verstehen, was sich die Menschen dabei gedacht haben, als sie diese Begriffe gewählt haben.

[deets]

Es sind nur Namen, die nur für einen Menschen Bedeutung haben, nicht für den Computer. Es gibt keine festgelegte Standardbedeutung.

Ok, dass war mir soweit schon klar. Für den Computer bzw den Parser ist das alles ein Blabla. Es ging mir ja auch darum zu verstehen, was sich die Menschen dabei gedacht haben, als sie diese Begriffe gewählt haben.

Das, was dir schon mehrfach gesagt wurde: eine Definition von Ausdruecken fuer Infix-Operation unter Beruecksichtigung von

- Assoziativitaet (links)
- Praezedenz der Operatoren (* vor +)
- Einfuehrung von geklammerten Teilausdruecken zur disambiguierung.

Mal dir halt mal die von mir gegebene Produktionskette als Baum auf, oder versuch halt umgekehrt einen simplen Ausdruck mal auf Papier "durchzuparsen".