Frage zu Grammatik

happystudent

Hallo,

angenommen ich habe folgende Grammatik in BNF:

<expr>    ::= <expr><op><expr> |         (1)
              "("<expr><op><expr>")" |   (2)
              <const>                    (3)

<op>      ::= "+" | "-" | "*" | "/"

<const>   ::= "1" | "2" | ... | "9"

Mir geht es jetzt nich darum "ausgeschriebene" Ausdrücke (also strings) zu parsen, sondern nur ob jeder mathematische Ausdruck nach der Grammatik darstellbar ist oder nicht.

Wofür braucht man hier Regel Nummer (2)? Ist das nicht überflüssig hier die Klammern einzufügen?

Irgendwie fällt mir kein (Gegen-)Beispiel ein, wo man das brauchen würde. Wenn ich etwas habe wie:

2 * (5 - 1)

Dann kann ich das ja darstellen durch

*
 / \
2   -
   / \
  5   1

oder übersehe ich hier etwas?

SG1

Nein, das wäre

2 * 5 - 1

happystudent

SG1 schrieb:

Nein, das wäre
2 * 5 - 1

Das müsste schon das sein?

Um den Baum auszuwerten werte ich erst den Minus Knoten aus, da dessen Ergebnis gebraucht wird um den Mal-Knoten auszuwerten. Also entspricht der Baum 2 * (5 - 1) .

Ohne Klammern, also 2 * 5 - 1 wäre der Baum ja

-
   / \
  *   1 
 / \
2   5

, würde also anders aussehen.

SG1

Wieso redest Du jetzt von mathematischer Auswertung? Es geht doch um generierte Worte und Syntaxbäume!

happystudent schrieb:

*
 / \
2   -
   / \
  5   1

Da kommt keine einzige Klammer als Terminalsymbol vor - also kann das dazugehörige Wort auch keine Klammer enthalten!

SG1

Ah, ich ahne, wo die Verwirrung herkommt: Du redest von Syntaxbäumen, ich von Ableitungsbäumen (und mach die dann auch noch falsch).

Also: 2 * 5 - 1 hat zwei verschiedene Ableitungsbäume in Deiner Grammatik:

<expr>
     / | \
<expr> | |
 / | \ | |
 2 * 5 - 1

und

<expr>
 / | \
 | | <expr>
 | | / | \
 2 * 5 - 1

2 * ( 5 - 1 ) hat dagegen nur einen Ableitungsbaum:

<expr>
/ | \
| |  <expr>
| |  / /|\ \
| | / / | \ \
2 * ( 5 - 1 )

happystudent

SG1 schrieb:

Wieso redest Du jetzt von mathematischer Auswertung? Es geht doch um generierte Worte und Syntaxbäume!

...

Da kommt keine einzige Klammer als Terminalsymbol vor - also kann das dazugehörige Wort auch keine Klammer enthalten!

Also es ist so, mich interessiert das erzeugte Wort nicht wirklich.

Was ich eigentlich nur wissen will ist: Kann ich mit der oben genannten Grammatik jeden mathematischen Ausdruck (bestehend aus +-*/() und den Ziffern 1 bis 9) erzeugen, sodass der Baum ausgewertet das Ergebnis des entsprechenden Ausdrucks ergibt?

Die Klammern stehen dabei nur für die Auswertungsreihenfolge.

SG1

happystudent schrieb:

SG1 schrieb:

Wieso redest Du jetzt von mathematischer Auswertung? Es geht doch um generierte Worte und Syntaxbäume!

...

Da kommt keine einzige Klammer als Terminalsymbol vor - also kann das dazugehörige Wort auch keine Klammer enthalten!

Also es ist so, mich interessiert das erzeugte Wort nicht wirklich.

Das erzeugte Wort ist Dein Ausdruck. Ich glaub schon, dass der Dich interessiert

Was ich eigentlich nur wissen will ist: Kann ich mit der oben genannten Grammatik jeden mathematischen Ausdruck (bestehend aus +-*/() und den Ziffern 1 bis 9) erzeugen, sodass der Baum ausgewertet das Ergebnis des entsprechenden Ausdrucks ergibt?

Die Klammern stehen dabei nur für die Auswertungsreihenfolge.

Naja, was heisst "nur"? Kannst Du sie weglassen? Dann brauchst Du auch Regel (2) nicht. Sonst schon.

happystudent

SG1 schrieb:

Also: 2 * 5 - 1 hat zwei verschiedene Ableitungsbäume in Deiner Grammatik:

...

2 * ( 5 - 1 ) hat dagegen nur einen Ableitungsbaum:

Ah ok, das stimmt. Wobei einer ja ausreicht, oder gibt es auch Fälle wo das nicht so wäre?

SG1 schrieb:

Naja, was heisst "nur"? Kannst Du sie weglassen? Dann brauchst Du auch Regel (2) nicht. Sonst schon.

Also mir wäre nur wichtig dass trotzdem jeder mathematische Ausdruck irgendwie damit repräsentiert (also berechnet) werden kann. Das ist ja dann auch ohne die Regel (2) gegeben, so wie ich dich verstehe?

SG1

happystudent schrieb:

SG1 schrieb:

Also: 2 * 5 - 1 hat zwei verschiedene Ableitungsbäume in Deiner Grammatik:

...

2 * ( 5 - 1 ) hat dagegen nur einen Ableitungsbaum:

Ah ok, das stimmt. Wobei einer ja ausreicht, oder gibt es auch Fälle wo das nicht so wäre?

richtig.

SG1 schrieb:

Naja, was heisst "nur"? Kannst Du sie weglassen? Dann brauchst Du auch Regel (2) nicht. Sonst schon.

Also mir wäre nur wichtig dass trotzdem jeder mathematische Ausdruck irgendwie damit repräsentiert (also berechnet) werden kann. Das ist ja dann auch ohne die Regel (2) gegeben, so wie ich dich verstehe?

Ohne Klammern kannst Du halt keine Ausdrücke mit Klammern bilden.

happystudent

[quote="SG1"]
richtig./quote]

SG1 schrieb:

Ohne Klammern kannst Du halt keine Ausdrücke mit Klammern bilden.

Aber ich kann doch eben schon Ausdrücke mit Klammern bilden?

Ein Baum wie

*
 / \
2   -
   / \
  5   1

ist doch äquivalent zu 2 * (5 - 1) ... oder steh ich jetzt auf dem Schlauch?

SG1

Als Syntaxbaum, ja. Aber nur, weil Du einen Syntaxbaum hinmalen kannst, heisst das doch noch lange nicht, dass Du den Ausdruck aus Deiner BNF bilden kannst!

die Grammatik ist dazu zu, zu beschreiben, wie Texte bzw. in deinem Fall Formeln auszusehen haben.
In der Mathematik ist es wichtig, die Auswertereihenfolge vorgeben zu können, denn 2*3+4 != 2*(3+4).

Welche Mittel hast du hierfür?
Wenn du Formeln mit Papier und Bleistift notierst, verwendest du Klammern, um diese Reihenfolge vorzugeben. Daher brauchst du unbedingt Klammern in deiner Grammatik!

Zeichnest du hingegen einen Syntaxbaum auf, so brauchst du keine Klammern. Du hast aber weiterhin die Möglichkeit, die Auswertereihenfolge zu definieren! Wie? Indem du Terme, die möglichst früh ausgewertet werden sollen, möglichst weit "unten" (also in der Nähe der Blätter des Baums) einbaust.

Wie du siehst ist die Bedeutung der Auswertereihenfolge die selbe geblieben, was sich geändert hat ist wie diese "codiert" wird.

EOP

SG1 schrieb:

Ohne Klammern kannst Du halt keine Ausdrücke mit Klammern bilden.

Hahaha, das leuchtet selbst mir ein.