Parser verstehen

Leute kann mir einer in kurzen Sätzen erklären was jetzt genau ein Parser macht um z.B. sowas zu berechnen?

2 + 4 * 7

Ich verstehe die Beschreibungen im Internet nicht mit diesen Bäumen und dies und das. Kann man nicht in einfachen Sätzen sagen wie so ein Programm vorgeht?
Ist das wirklich so kombliziert?

virtuell Realisticer

jorg schrieb:

Leute kann mir einer in kurzen Sätzen erklären was jetzt genau ein Parser macht um z.B. sowas zu berechnen?

2 + 4 * 7

Ich verstehe die Beschreibungen im Internet nicht mit diesen Bäumen und dies und das. Kann man nicht in einfachen Sätzen sagen wie so ein Programm vorgeht?
Ist das wirklich so kombliziert?

Nun, dein obiger Term ist in der sogenannten Infix-Schreibweise. Man koennte
nun z. B. hingehen und ihn in die Postfix-Schreibweise umwandeln:

2 4 + 7 *

und nun kann man hieraus schoen einen Baum erstellen, der dann z. B. folgenden
Aufbau hat:

(*)
   /   \
 (7)   (+)
      /   \
    (2)   (4)

Zu beachten ist hier, dass hier _keine_ Operatorenprioritaet beachtet wird.
Entweder man setzt voraus, dass der Term vollstaendig geklammert sein muss, oder
man hat entsprechend mehr arbeit und muss die Klammerung selbst vornehmen.

Dann sieht der Term nach Bearbeitung so aus:

(2 + (4 * 7))

und wird entsprechend in Postfix-Schreibweise umgewandelt:

2 4 7 * +

Daraus ergibt sich dann folgender Baum:

(+)
   /   \
 (2)   (*)
      /   \
    (4)   (7)

Jeder Op und jede Zahl kann man als Knoten ansehen. Beinhaltet ein Knoten eine
Zahl, so weisst du, dass keine weiteren Operanten ausgewertet werden muessen.
Handelt es sich bei einem Knoten um einen mathematischen Operator, so hast du
immer zwei Teilausdruecke, links und rechts vom Operator. Natuerlich kann ein
Teilausdruck mit einem weiteren Operator beginnen (siehe letzten Baum oben).
Das heisst, du laeufst erst diesen Knoten ab, solange, bis du mit einem Ergebnis
zurueckkommst, das der, in diesem Beispiel, Operator + mit der Zahl 2
verrechnen kann.

Hoffe ich hab das nicht zu umstaendlich erklaert. Das Prinzip sollte aber, denke
ich, klar geworden sein.

mfg
v R

(*) 
   /   \ 
 (7)   (+) 
      /   \ 
    (2)   (4)

Wenn ich diesen Baum jetzt folge. Kommt der Multiplikator, der Zeiger geht weiter auf Addition. Und weiter auf dir 4 und gleich auf die 2. Das macht 6 und Multipliziert das mit 7.

Das ist doch falsch? Oder habe ich einen Denkfehler?

Jester

virtuell Realisticer schrieb:

Man koennte
nun z. B. hingehen und ihn in die Postfix-Schreibweise umwandeln:

2 4 + 7 *

Nein.

Ich lese mal Deinen Ausdruck:

2 -> auf den Stack
4 -> auf den Stack
+ -> zwei Operanden vom Stack holen, addieren, Ergebnis 6 auf den Stack
7 -> auf den Stack
* -> zwei Operanden vom Stack, multiplizieren, Ergebnis 42 auf den Stack

2+4*7 ist aber als 2 + (4*7) = 30 zu lesen.

Der korrekte Postfix-Ausdruck lautet:

2 4 7 * +

MfG Jester

Jester

jorg: wenn man die Postfix-Notation richtig aufstellt kommt man mit vRs Weg dann auf den korrekten Baum und dann funktioniert auch alles.

virtuell Realisticer

Jester schrieb:

virtuell Realisticer schrieb:

Man koennte
nun z. B. hingehen und ihn in die Postfix-Schreibweise umwandeln:

2 4 + 7 *

Nein.

Ich lese mal Deinen Ausdruck:

2 -> auf den Stack
4 -> auf den Stack
+ -> zwei Operanden vom Stack holen, addieren, Ergebnis 6 auf den Stack
7 -> auf den Stack
* -> zwei Operanden vom Stack, multiplizieren, Ergebnis 42 auf den Stack

2+4*7 ist aber als 2 + (4*7) = 30 zu lesen.

Der korrekte Postfix-Ausdruck lautet:

2 4 7 * +

MfG Jester

Du hast meinen Beitrag nicht ganz gelesen, das habe ich naemlich geschrieben

mfg
v R

Jester

Stimmt, ändert aber nichts daran, daß die zitierte Aussage falsch ist.
Was Du angegeben hast ist nicht die Postfix-Schreibweise des Ausdrucks.

virtuell Realisticer

Jester schrieb:

Stimmt, ändert aber nichts daran, daß die zitierte Aussage falsch ist.
Was Du angegeben hast ist nicht die Postfix-Schreibweise des Ausdrucks.

Das stimmt auch mal wieder

mfg
v R

Bashar

jorg schrieb:

Leute kann mir einer in kurzen Sätzen erklären was jetzt genau ein Parser macht um z.B. sowas zu berechnen?

2 + 4 * 7

Kommt drauf an, welchen Parseralgorithmus du meinst. Da gibt es einige ...

Bashar schrieb:

jorg schrieb:

Leute kann mir einer in kurzen Sätzen erklären was jetzt genau ein Parser macht um z.B. sowas zu berechnen?

2 + 4 * 7

Kommt drauf an, welchen Parseralgorithmus du meinst. Da gibt es einige ...

arrrggggg, und da kommst du damit das es mehrere gibt. Ja welche? Gibt es welche die für bestimmte Sachen besser geeignet sind?

z.B. dieser Parser für Programmiersprache, dieser Parser für Anwendungen ect...

Bashar

Das hängt von der Grammatik ab, also nur indirekt von der Anwendung. Aber ich glaube nicht, dass es Sinn hat, das jetzt auszubreiten. Du solltest mal sagen, was genau du an einem bestimmten Script nicht verstehst.

Th

Wenn du Parser wirklich verstehen willst, dann schau dir mal die BNF (Backus-Naur-Form) Notation bzw. die EBNF (extended) an.

Aus jeder kontextfreien Grammatik (die meisten einfachen Programmiersprachen gehören dazu) läßt sich nämlich ein (E)BNF-Ausdruck erstellen, den man dann 1:1 in Code umsetzen kann.

Also erlich gesagt wollte ich schon immer mal eine eigene Scriptsprache programmieren.

Nun ich habe vor einer Weile damit angefangen. Was ich bis jetzt habe ist ein art Parser der einen String parsen kann.

So ist z.B. Kein Problem für mich so was zu analysieren: FunktionName(10,2.4)

Ich kann also die Werte 10 und 2.4 rauslesen.

Oder ein anderes Beispiel:

LoadBitmap("bitmap.bmp") Ist auch kein Problem dem Parser beizubringen das bei LoadBitmap er nur einen Text einlesen soll.

Jetzt will ich aber entlich das er rechnet.

Danach kommen Varibale ect...

Es ist ein Hobbyprojekt und ich arbeite immer wenn ich Zeit finde. Doch entweder habe ich zur Zeit keinen klaren Kopf oder das Thema ist zu kombliziert.

Naja, danke für die Tipps cu.