AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Wie am besten Parsen?

Ein Thema von malo · begonnen am 30. Apr 2005 · letzter Beitrag vom 28. Nov 2005
Antwort Antwort
Seite 5 von 5   « Erste     345
Benutzerbild von Ultimator
Ultimator

Registriert seit: 17. Feb 2004
Ort: Coburg
1.860 Beiträge
 
FreePascal / Lazarus
 
#41

Re: Wie am besten Parsen?

  Alt 23. Nov 2005, 21:16
Das war schön ausführlich und gut erklärt, danke alzaimar
Allerdings sollte es nur ein kleiner Matheparser werden, ohne "Sprachfeatures" oder sowas *g*
Ich hab mir schon Routinen geschrieben, die mir eben true zurückgeben, wenn ein Zeichen ein Punkt-Operator, ein Strich-Operator oder so ist.
Außerdem wird ein Term bereits ordentlich zerlegt,
aus
Code:
45*(60-18)+382/(+102)-3^897
zerlegt er also
Code:
45  *  (  60  -  18  ) +  382  /  (  +  102  ) -  3  ^  897
Das klappt soweit schon ganz gut

Ich denke, wenn ich auf eine "(" stoße, schaue ich, ob dahinter ein "-" ist mit einer anschließenden Zahl, und dann wieder die ")", dann speichere ich die negative Zahl in der Klammer in eine Variable, sehe dann, was nach der Klammer für ein Rechenzeichen kommt (speicher ich in einen eigenen Variablen-Typen, der u.A. auch "KeinOperator" enthält), danach hol ich mir die andere Zahl und "verwurste" die beiden per Operator. OK, es gibt natürliuch auch den Fall, dass die Zahl in der Klammer die hintere der beiden zu verwurstenden Zahlen ist, aber das seh ich ja daran, ob in meiner Operator-Variable "KeinOperator" oder was anderes gespeichert ist
Denkt ihr, das wäre ein guter funktionierender Ansatz?
Performance spielt erstmal keine Rolle
Julian J. Pracht
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#42

Re: Wie am besten Parsen?

  Alt 23. Nov 2005, 21:28
Wenn Du mein Rezept nimmst, dann ergeben sich alle Sonderfälle automatisch. Versuch das mal. 'Nur' einen Matheparser kann man auch mit einem Stack schreiben, auf den man so lange die Zahlen raufschiebt, bis man auf einen 'schwächeren' Operator trifft (oder so ähnlich)
Die Reihenfolge ist (Starke zuerst): */ +- () <EOF>, */ ist stärker als +-, das ist stärker als () das ist stärker als EOF.

3+4*5: 3 push + push 4 push * push 5 push <ENDE> (stack = 5 * 4 + 3)
<Ende> ist schwächer als der letzte Operator (*) also 5*4 ausrechnen und auf den Stack. Stack = 20 + 3. <Ende> ist schwächer als + also weiter rechnen und fertig.

4*5+3: 4 push * push 5 push + ist schwächer als *, der oberste Operator, also 4*5 ausrechnen. Kein schwächerer Operator mehr auf dem Stack, also weitermachen. + push 3 push <Ende> ist schwächer als +, also ausrechnen. Ergebnis wieder 23 (oh Wunder!)

Probier das mal, das ist recht kompakt.

[edit] ob ein operator (+-) ein Vorzeichen ist, oder nicht, wird vom Token links vom Operator gesteuert. Wenn das letzte Token eine Zahl war, dann ist der Operator KEIN Vorzeichen, sonst schon.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Ultimator
Ultimator

Registriert seit: 17. Feb 2004
Ort: Coburg
1.860 Beiträge
 
FreePascal / Lazarus
 
#43

Re: Wie am besten Parsen?

  Alt 23. Nov 2005, 21:36
Ja, das klingt auch plausibel und vor allem verständlich
Zitat von alzaimar:
[edit] ob ein operator (+-) ein Vorzeichen ist, oder nicht, wird vom Token links vom Operator gesteuert. Wenn das letzte Token eine Zahl war, dann ist der Operator KEIN Vorzeichen, sonst schon.
Danke! Endlich hat mal jemand das in Worte gefasst, worüber ich schon tagelang überleg (eigentlich peinlich )
Wird schon klappen
Julian J. Pracht
  Mit Zitat antworten Zitat
Benutzerbild von Ultimator
Ultimator

Registriert seit: 17. Feb 2004
Ort: Coburg
1.860 Beiträge
 
FreePascal / Lazarus
 
#44

Re: Wie am besten Parsen?

  Alt 27. Nov 2005, 01:54
So, jetz muss ich nochmal was fragen
Ich pushe ja solang, bis ich auf einen schwächeren Operator komme.
Angenommen, ich hab

7-3/(5-4*2)
push 3 push - push 8 push / [is ja stärker als -] push (
Jetz hab ich die Klammer-Auf gepusht, also muss ich mich um den Teil in der Klammer kümmern.
Muss ich da jetzt immernoch weiter pushen, bis ich die Klammer-Zu gepusht hab?

Das mit den Klammern versteh ich noch nicht ganz, wenn du das bitte nochmal erklären könntest?

Könnte man das eventuell in eine rekursive Funktion packen, die dem nächsten Aufruf einfach immer nur den nächst-tieferen Klammerterm zum ausrechnen übergibt?
Julian J. Pracht
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#45

Re: Wie am besten Parsen?

  Alt 27. Nov 2005, 09:18
Die Klammern musst Du gesondert betrachten. Bei '(' wird auf den Stack gepackt und bei einem ')' der Stack bis zum '(' aufgelöst. Rekursiv muss da Nichts sein. Das ist ja grad das Lustige an der Methode. Ich vermute mal, Du wirst den Operatoren Werte zuweisen. Stärker ist der, dessen Wert größer ist. Sollte das nicht mit den Klammern genauso gehen? Eine '(' stoppt das Auflösen des Stacks für alle Operatoren, mit Ausnahme des ')'. Das ')' löst den Stack bis zum '(' auf und entfernt ds '(' dann.

Beispiel:
2/(3*4+5)
2 push / push ( push 3 push * 4 push + ...ausrechnen 3*4-> 12 push. der Operator auf dem Stack ist das '('=STOP, nicht mehr weitermachen
auf dem Stack ist jetzt 2 / ( 12+, also weitermachen.
5 push )...Auflösen bis zum (', also 12+5=17 : Stack = 2/(17. Top-Operator ist jetzt '(', wir haben ein ')', also weg damit. Stack = 2/17.
Nächstes Token zu Pushen: <End of Input>... Also 2/17 ausrechnen und fertig.

Die Reduzieren des Stacks geht immer nur soweit, bis der oberste Operator ein '(' ist. Der Einzige, der ein '(' eliminieren kann, ist ein ')'.

Der Stack enthält also zu jedem Zeitpunkt nur die Teile des bisher abgearbeiteten Ausdruckes, der infolge der Punkt-Vor-Strich- und der Klammer-Regeln noch nicht ausgerechnet werden konnten. Er wird jeweils zum frühest möglichen Zeitpunkt reduziert, d.h. die obersten Elemente ausgerechnet (und damit der Stack ja verkleinert). Damit werden auch Klammerebenen automatisch richtig behandelt, denn ein ')' bewirkt nur, das Alles, was 'rechts' von dem letzten '(' steht, reduziert, d.h. ausgerechnet, wird.

Mich würde der Code interessieren, wenn es läuft.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Ultimator
Ultimator

Registriert seit: 17. Feb 2004
Ort: Coburg
1.860 Beiträge
 
FreePascal / Lazarus
 
#46

Re: Wie am besten Parsen?

  Alt 27. Nov 2005, 13:58
*Groschen fall*
Danke, jetz hab ichs endlich verstanden
Den Code kriegst du ganz bestimmt, hast ja auch viel dazu beigetragen
Aja: Bisher misst der Parser gerade mal 160 Zeilen.
Außerdem getrennte Tokenize-, Parse- und Lösungs-Funktionen, damit man nicht mehr machen muss als nötig, wenn man den Term einmal "getokenized" hat. Bin richtig stolz auf mich

Das stellt jetzt eigentlich kein Problem mehr dar, allerdings hab ich gestern rausgefunden, dass die Sache mit den Vorzeichen beim ^-Operator noch nicht ganz klappt, wegen der Sache mit -3^2 = -(3^2) = -9. Da muss ich erst nochmal schauen, wie da die Regel mit den Vorzeichen definiert ist.

Achja, noch was *g*
Angenommen, ich hab 6+5*(-3)-4
Dann muss ich das doch so machen:
push 6 push + push * push ( push -3 push ) usw.
Nachdem ich die ) gepusht hab, weiß ich ja, dass ( der letzte Operator war.
Tu ich da 3mal pop ausführen, um dann die -3 zu pushen?
Julian J. Pracht
  Mit Zitat antworten Zitat
Nils_13

Registriert seit: 15. Nov 2004
2.647 Beiträge
 
#47

Re: Wie am besten Parsen?

  Alt 28. Nov 2005, 15:05
Der Parser von c.wuensch hat einen Fehler: Wenn ich
diesen Code habe:
Delphi-Quellcode:
PROGRAM Testprojekt;
VAR realx, a, b: integer;
Procedure proc;
  begin
    b := abc
  end;

BEGIN
  a := cdefg;
  x := hijklmnop;
  Writeln (x); readln (y)
END.
und ich verwandle das erste VAR (unter PROGRAM), und parse und vorher PROGRAM in ROGRAM verwandelt habe, dann kommt mir der Parser mit zwei Fehlern, statt einem an:
Code:
"PROGRAM" erwartet !
Anweisungsteil erwartet !
Damit dieser Fehler nicht auftritt, muss der ürbsprüngliche Code
(
Delphi-Quellcode:
If Programm Then ...
Else ... ;
)
durch
Delphi-Quellcode:
  If Programm Then
  begin
   Form1.errormemo.Clear;
  end
  Else
  begin
    ShowMessage('Fehler im Programm');
  end;
ersetzt werden
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:59 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz