Parser: Operatoren

[Medium]

Doch das geht prima, weil man den "/" eher erkennt als das "-" (Punktrechnung vor Strichrechnung).

So in etwa:

Delphi-Quellcode:

function Parse(s: String): TParseTreeNode;
begin  
  if s[1] = '-' then s := '0'+s;
  if FindToken('*', s) then
    result := TParseTreeNode.Create(opMul, Parse(PartBeforeToken('*', s)), Parse(PartAfterToken('*', s)))
  else
  if FindToken('/', s) then
    result := TParseTreeNode.Create(opDiv, Parse(PartBeforeToken('*', s)), Parse(PartAfterToken('*', s)))
  else
  if FindToken('+', s) then
    result := TParseTreeNode.Create(opAdd, Parse(PartBeforeToken('*', s)), Parse(PartAfterToken('*', s)))
  else
  if FindToken('-', s) then
    result := TParseTreeNode.Create(opSub, Parse(PartBeforeToken('*', s)), Parse(PartAfterToken('*', s)))
  else
  begin
    try
      result := TParseTreeNode.Create(opConst, StrToFloat(s));
    except
      raise Exception.Create('Grammar Error');
    end;
  end;
end;

Alles was oben im if-then-else-Wurm Steht bindet stärker.

Was die Bools angeht, so habe ich die bei mir nicht separat implementiert, sondern nutze ganz normale Zahlenwerte (0 und 1), womit die Operatoren in den selben Ablauf passen. Verliert etwas Typsicherheit, klappt aber wie ne eins.

[Namenloser]

Hmm, aber dein Parser sucht „aktiv“ nach Tokens mithilfe von Pos() bzw. einer ähnlichen Funktion, oder? Normalerweise baut man Parser doch als State-Machine auf – dachte ich zumindest (ich habe es jedenfalls immer so gemacht – bin aber auch (noch) kein Informatiker). Wenn man mit einer State-Machine arbeitet, arbeitet man sich ja zeichenweise durch den String, d.h. man kennt an sich ja nur das aktuelle Zeichen und den Zustand des Automaten, weiß aber nicht, was danach kommt (das wäre sonst ein Look-Ahead). [edit]D.h. man kann nicht einfach den ersten Punkt-Operator (*, /) suchen und mitten in den String rein springen und ihn zerteilen Quatsch, aber:[/edit] (und sobald Klammern vorkommen, müsste der Ansatz eigentlich auch versagen).

Aber im Falle des Minus ist der Fall doch eigentlich klar:

1. Das Minus ist ein Operator, wenn davor ein Bezeichner oder eine Zahl steht.
2. Das Minus ist ein Vorzeichen, wenn davor ein Operator oder eine Klammer steht.
3. Mehrere aufeinanderfolgende Vorzeichen werden zu einem einzigen Vorzeichen verschmolzen (je nachdem ob gerade oder ungerade Anzahl).

Zumindest sind diese Regeln bei Parsern so üblich... in der Mathematik ist es ja normalerweise nicht erlaubt, dass Operatoren oder mehrere Vorzeichen aufeinander folgen...

Bei Fakultät und Subfakultät müsste es so ähnlich sein.

Solche Regeln muss man eben finden/festlegen.

Auch wie die interne Klammerung aussieht (um dein Beispiel zu nehmen „(((1 A) A) A 1) oder (1 A (A (A 1)))“) ist von vornherein festgelegt – darum muss sich dein Parser also gar nicht kümmern. Ist deine Sprache linksassoziativ, gilt „(((1 A) A) A 1)“, ist sie rechtsassoziativ, gilt „(1 A (A (A 1)))“.

[Bjoerk]

Zitat von Medium:

Doch das geht prima, weil man den "/" eher erkennt als das "-" (Punktrechnung vor Strichrechnung).

Vorausgesetzt, du macht die Klammern zuerst. Bei (2+3)/(4+5) muß der Parser zuerst die Additionen durchführen.

[Medium]

Ja, er sucht mittels Pos(), also aktiv. Zudem gibt mir mein FindToken() den ersten Operator zurück, der nicht in Klammern steht, jap. Wird kein OP ausserhalb von Klammern gefunden, fällt meine If-Then-Wurst in einen Zweig if (s[1] = '(') and (s[High(s)] = ')') then result := Parse(copy(s, 2, Length(s)-2)); durch.

Ich hab mit der Technik jetzt ziemlich alle trivialen Dinge abgedeckt: "Normale" Operatoren (^,*,/,+,-), Funktionen mit 1-3 Parametern (sin(), cos(), ...), logische Operatoren (and, or, not, ...) sowie das Vorzeichenminus, Klammerung und Operatorenrang wie in der Mathematik üblich, wobei ich logischen Operatoren noch Vorrang vor diesen gewähre. (Dort ist sogar der ternäre Operator in Form eines IfThen() dabei.)
Unäre Operatoren wären leicht umzusetzen, wenn diese Zeichen dann von Variablen- und Konstantenbezeichnern als Bestandteil ausgeschlossen würden - fände man einen solchen, wird alles bis zum nächsten Operator als Argument aufgefasst, oder via Klammerung eindeutig gemacht. Ähnlich ließe sich mit unären Postfix-Operatoren verfahren, nur eben in die andere Richtung.

Dass dieses Vorgehen nicht unbedingt einem reinen sprachtheoretischen Lexer entspricht stimmt, jedoch ist es schlank, übersichtlich, recht intuitiv und wartbar (auch nach 6-7 Jahren noch, ich hab nämlich die Boolschen OPs erst letzte Woche nachgerüstst, auf einem Stand, den ich zuletzt 2006 gesehen habe glaube ich). Schmankerl sind registrierbare Konstanten und Variablen, letztere als Pointer auf eine Delphi-Variable, so dass sie zur Laufzeit geändert werden können, ohne den String neu parsen zu müssen. Zudem werden alle konstanten Teile des Baumes vorab gelöst und als Konstanten-Blatt eingefügt, so dass diese in dem Fall auch nicht immer wieder erneut aufgelöst werden müssen. Ergo: Das Teil ist sogar richtig flott, gerade bei wiederholter Ausführung der gleichen Formel mit unterschiedlichen Variableninhalten.

Für eine allgemeine, formale Grammatik mag das ggf. nicht taugen. Für logische und mathematische Terme war mir das bisher der angenehmste und universellste Ansatz, der zudem zu einer günstigen Datenstruktur führt.