erste Schritte zum Parser

[Antigo]

Hi,
bin heute auf einen Thread gestoßen wo jemand fragte wie man eine Rechnung in einem String berechnen kann. (Also '2+3/4' bspw). DIe Antwort war ein Mathe Parser und da ich etwas freizeit hatte hab ich mal angefangen einen zu entwickeln (ich weiss das es schon viele gibt, aber das hat denk ich mal noch keinen aufgehalten ;) ).

Ich hab einfach mal angefangen simple Rechnungen zu lösen, erstmal ohne Klammern. Rausgekommen ist folgendes:

Delphi-Quellcode:

//Rechnungen ohne Klammern lösen
function TForm1.simplecalc(s:string):double;
var i:integer;
foo1,foo2:double;
temp:string;
ps:TPositionen;
begin
  temp:=s;

  //Punkt vor Strichrechnung
  calcpos(temp,ps); //Positionen der Operatoren festellen
  i:=0;
  while (i < length(ps)) and
  ((pos('*',temp)>0) or (pos('/',temp)>0)) do begin
    if (temp[ps[i]]='*') or (temp[ps[i]]='/') then begin
      //erster Faktor
      if i=0 then foo1:=strtofloat(copy(temp,1,ps[i]-1))
      else foo1:=strtofloat(copy(temp,ps[i-1]+1,ps[i]-ps[i-1]-1));
      //zweiter
      if i=length(ps)-1 then foo2:=strtofloat(copy(temp,ps[i]+1,length(temp)))
      else foo2:=strtofloat(copy(temp,ps[i]+1,ps[i+1]-ps[i]-1));

      //ergebnis 
      if (temp[ps[i]]='*') then
      foo1:=foo1*foo2
      else foo1:=foo1/foo2;

      //an passender Stelle in den String einsetzen
      if i=0 then temp:=floattostr(foo1)+copy(temp,ps[i+1],length(temp))
      else if i=length(ps)-1 then temp:=copy(temp,1,ps[i-1])+floattostr(foo1)
      else temp:=copy(temp,1,ps[i-1])+floattostr(foo1)+copy(temp,ps[i+1],length(temp));

      showmessage(temp);
      
      calcpos(temp,ps);
     end;
     inc(i);
  end;

  //Additionen / Subtraktionen
  foo1:=strtofloat(copy(temp,1,ps[0]-1));
  for i:=0 to length(ps)-1 do begin
    if i=length(ps)-1 then
      foo2:=strtofloat(copy(temp,ps[i]+1,length(temp)))
        else foo2:=strtofloat(copy(temp,ps[i]+1,ps[i+1]-ps[i]-1));
    if temp[ps[i]]='+' then foo1:=foo1+foo2
    else foo1:=foo1-foo2;
  end;

  //Ergebnis (foo1) ausgeben
  showmessage(floattostr(foo1));

end;

das ganze funktioniert zumindest schonmal. Was ganz klar noch nicht funktioniert ist:
- Klammersetzung, aber das hab ich bereits geschrieben
- Negative Zahlen eingeben (Nach dem Motto 1+-3, aber das kann man noch relativ leicht abfangen indem man -- zu +; +- und -+ zu - und ++ zu + macht.

Ich würde mal gern eure Meinung zu meinem Ansatz hören. Ich denke mal es ist nicht der eleganteste, aber was hätte ich wie besser machen können? Ich würd mich über Feedback sehr freuen :)

edit: noch kurz zum algorithmus: ich gehe so vor, das ich in der Rechnung erst alle Produkte löse, so dass ich nachher nur noch additionen und subtraktion haben.
Aus 1*2+3*4+5*6 wir so erstmal 2+3*4+5*6 , dann 2+12+5*6 und dann 2+12+30 was dann im zweiten schritt zu 44 wird ;)

mfg
Antigo

[jfheins]

Ich denke einfach mal laut, dass die allermeisten Parser einen (Binär-)Baum verwenden, und es dafür sicher einen Grund gibt ;)

Was die Klammern angeht: Die könntest du vielleicht rekursiv lösen: Einfach zuerst alle eingeklammerten Terme suchen, und diese dann (rekursiv) auswerten ;)

[Antigo]

ich hab leider keine ahnung wie ich so einen Binärbaum umsetzen soll. IM Prinzip wird da aber doch auch nciht viel anders gemacht als ich es tue.

Und das mit den Klammern wollte ich auch ungefähr so lösen. Also bis zur untersten "KLammerebene" gehen, wo also nur noch addition/subtraktion/multiplikation/division zu machen ist, und das ergebnis davon dann halt rückwikend einsetzen. Dafür würde sich eine rekusrive Prozedur natürlich anbieten. Wie ich das dann konkret umsetz muss ich noch schauen, ich finde es immer schwer rekursiv zu denken/zu programmieren, auch wenn das Ergebnis dann meist genial einfach ist...

[alzaimar]

Wird dein Ansatz auch mit Klammern auskommen? Ich denke nicht.

So ein Parser richtig zu implementieren ist gar nicht mal so einfach. Schwer ist es allerdings auch nicht, wenn man weiss, wie man es richtig machen muss.

Dazu musst du wissen, das ein Parser eine 'Sprache' erkennt und syntaktisch analysiert. In Deinem Fall heißt die Sprache "Terme" oder "mathematische Ausdrücke".

Jede Sprache besteht aus Wörtern, oder Dingern, oder wie auch immer man das nennt. Auf Englisch heißen die Dinger "Token". Bei den mathematischen Ausdrücken sind die Token (oder eben Wörter): ( ) + - / * Zahl.

So, der Parser... was hab ich gesagt? ... genauer gesagt erkennt der Parser einen Satz einer Sprache. Und jeder Satz benötigt ein Satzende. Also definieren wir noch ein extra Wort "Ende des mathematischen Ausdruckes" oder einfach nur '$'.

Jetzt haben wir die Wörter, fehlt noch die Sprache. Damit man die einfach und formal korrekt definieren kann, haben sich Informatiker eine Notation ausgedacht, die BNF oder "Backus-Naur-Form".

Wenn Du eine Sprache in EBNF (steht im Wiki-Artikel) beschreiben kannst, dann bekommst Du vermutlich auch sehr einfach einen super funktionierenden Parser hin. Kurz erweitert hast du dann auch den Syntax-Baum.

[Hawkeye219]

Ein schöner Einstieg in die faszinierende Welt des Compilerbaus ist die Artikelreihe Let's Build a Compiler von Jack Crenshaw.

Gruß Hawkeye

[Antigo]

hmm naja ich denke schon das mein Ansatz auch irgendwie mit Klammern auskommen wird, aber die Betonung liegt auf irgendwie. Besondern elegant würde das wohl nicht werden ;)

Den Syntax Baum verstehe ich grundsätzlich, aber nicht wie ich damit arbeite. Im Prinzip ist das ja nur eine Darstellungsart von dem was ich machen will.

Naja ich werd dann wohl erstmal die letzten 2 Klausuren diese Woche hinter mich bringen und mir das ganze dann nochmal näher anschauen. Das Projekt Parser Bau scheint nichts für mal eben zwischendurch zu sein ;)

danke auf jedenf all schonmal für die hinweise.

edit:
Let's Build a Compiler scheint interessant zu sein. Aber auch nix für mal eben grade ^^ Ich werd mir das aber wenn die Klausuren vorrüber sind mal zu gemüte führen. Vielen Dank für den Tipp :)

[Antigo]

ich muss leider sagen, dass ich mit dem Tutorial nicht so wirklich zurecht komme. Das es auf englisch ist, ist ja noch ok, aber das assembler zeug verwirrt mich irgendwie. Ausserdem muss man nach guter alter Pascal Manier beim lesen des Codes ständig hin und her springen, da die Prozeduren chronoligsch angeordnet sien müssen...

Kennt jemand eine andere gute EInführung? SOnst muss ich mir doch weiter selber den kopf zerbrechen... ;)