Parser: Operatoren

[blablab]

Hallo!

Ich programmiere gerade an einem Parser und ich stehe bei den überladenen Operatoren ziemlich auf dem Schlauch. Zum Beispiel der Operator "-" ist ja normalerweise überladen: Sowohl "1-1" als auch "1*(-1)" ist möglich. Beim ersten hab ich Argumente auf beiden Seiten und beim zweiten nur eins auf der rechten Seite. Ein anderes Beispiel wäre "x!" und "!x" (Fakultät und Subfakultät). Theoretisch sind also überladene Operatoren möglich, die alle drei Möglichkeiten ausschöpfen: Argument links, rechts und auch auf beiden Seiten.
Dazu kommt noch dass Operatoren wegen dem Datentyp überladen sein können, zB "True and False = False" und "1 and 3 = 1".
Das bedeutet wenn ich 2 Datentypen habe könnte ein einziger Operator aus 6 Überladungen bestehen! Und jede Überladung könnte ihren eigenen Rang haben (mit Rang meine ich die Rangfolge von Operatoren wie z.B "Punkt vor Strich").

Angenommen ich habe nur solche Psycho-Operatoren (davon muss ich ja ausgehen wenn ich ein fehlerfreies Programm haben möchte), wie soll ich dann vorgehen???

1 A A A 1 = (((1 A) A) A 1) oder (1 A (A (A 1))) oder ((1 A) A (A 1))
Und dummerweise entstehen auch Möglichkeiten wie:
(1 A) (A (A 1)) die dann zu einem Fehler führen

Das bedeutet mein erstes Problem ist es erst einmal herauszufinden ob es überhaupt eine gültige Lösung gibt. Und dann stellt sich die Frage welche davon unter Berücksichtigung des Rangs die korrekte ist.

Ich weiß leider nicht mal wirklich wo ich hier anfangen soll. Könnt ihr mir vielleicht weiterhelfen?

Grüße
blablab

[Furtbichler]

Ich glaube, Du bringst da etwas durcheinander.

Das Minus ist einerseits Operator, andererseits Vorzeichen. Da kann man nichts mißverstehen: A-B ist eindeutig, A--B auch. Der Tokeinzer liefert dir eh nur 'MINUS', weil er das Symbol erkannt hat. der Rest ergibt sich aus der Grammatik.

Beim Ausrufungszeichen defnierst Du, welche Bindung (links, rechts) stärker ist.

Allerdings gibt es Mehrdeutigkeiten, z.B. bei Pascal des 'dangling else' Problem

[idefix2]

Hallo!

Die Rangfolge der Operatoren ist doch definiert. Bei gleichem Rang ist definiert, ob von links nach rechts oder von rechts nach links abgearbeitet wird.

Das Scannen erledigst mit Hilfe einer Reihe von wechselseitig rekursiven boolean functions, z.B. A1,A2,A3, etc., wobei A1 alle Teilausdrücke der Form
o1 x
x o1
x o1 y
erkennt, dabei sind x und y entweder elementare Operanden, oder Klammerausdrücke, oder Teilausdrücke, die von der Funtion A2 erkannt werden, o1 ist ein beiebiger Operator der Rangstufe 1. Normalerweise sollten sich auf einer gegebenen Rangstufe allerdings nur unäre oder nur binäre Operanden befinden.

Der Gesamtausdruck wird an A1 zum Scannen übergeben.

A1 sucht je nach vorgegebener Richtung von rechts oder von links den ersten Operator mit Rangstufe 1, teilt an der Stelle den Gesamtausdruck in zwei Teile und wendet auf jeden Teilausdruck wieder die Prozedur A1 an. Findest Du beim Scannen Klammern, dann wird der Bereich zwischen den Klammern auf dieser Rekursionsstufe natürlich nicht gescannt, sondern als ein Operand betrachtet und auf den Inhalt zwischen den Klammern wieder A1 angewendet. Findet A1 keinen Operator mit Rangstufe 1, dann übergibt A1 den ganzen Ausdruck an A2. Liefert A2 für einen Teilausdruck false, dann sucht A1 nach einem weiteren Operator der Rangstufe 1 und versucht dort erneut, den Ausdruck zu teilen.

Wenn nach der Rekursion nichts übrigbleibt, hast Du automatisch das einzige richtige Ergebnis. Diese Vorgangsweise ist natürlich in keiner Weise optimiert, aber dafür leicht zu implementieren.

@ Furtbichler:
Vom Standpunkt eines Parsers gesehen ist ein Vorzeichen genauso ein Operator wie alle anderen, eben ein unärer Operator. Normalerweise haben unäre Operatoren die höchste Priorität, das ist aber Definitionssache und müsste nicht sein.
Eine unären Operator erkannt der Scanner daran, dass im Ausdruck auf einer der beiden Seiten kein Operand, sondern nichts oder ein Operator steht (Ein Operand kann natürlich auch ein Teilausdruck sein, der mit einem Operator endet).
Echte Mehrdeutigkeiten gibt es insofern nicht, als ihre Auflösung durch die Vorgabe einer Auswertungsrichtung gegeben ist.

[Furtbichler]

Zitat:

Zitat von idefix2 (Beitrag 1161647)

@ Furtbichler:
Vom Standpunkt eines Parsers gesehen ist ein Vorzeichen genauso ein Operator wie alle anderen, eben ein unärer Operator.

Diese Aussage verstehe ich nicht. Vom Standpunkt des Parsers ist ein Operator kein Vorzeichen. Das Token ist das gleiche, aber im Kontext eines Terms wird das Token MINUS als Operator erkannt. Während des Parsens eines Wertes dagegen als Vorzeichen. Mit "Look ahead ist da nichts.

Zitat:

Eine unären Operator erkannt der Scanner daran, dass im Ausdruck auf einer der beiden Seiten kein Operand,

Der Scanner erkennt hier nichts, er macht kein Look ahead. Er unterscheidet zwischen terminalen und nicht terminalen Symbolen und liefert Token. Hier ist ein '-' ein MINUS, egal in welchem Kontext.

Durch spezielle Zeichen des Alphabets kann es sein, das ein Look Ahead durchgeführt werden muss.

Bei Pascal z.B. betrifft dies den '.' (wie in 7.1) und '..' (wie in [1..2]). Beim erkennen eines '.' muss das nächste Zeichen geprüft werden, um zu entscheiden, ob sich im Eingabestream um ein DOT oder ein DOTDOT-Symbol (=Token) handelt.

Zitat:

Echte Mehrdeutigkeiten gibt es insofern nicht, als ihre auflösung durch die Vorgabe einer Auswertungsrichtung gegeben ist.

Grammatikalisch schon, siehe 'dangling else'. Dort kann die Grammatik als solche keine Eindeutigkeit liefern. Das macht die Implementierung des Parsers.

[idefix2]

Zitat:

Vom Standpunkt des Parsers ist ein Operator kein Vorzeichen

Nimm statt -1 einfach -x. dann ist - kein Vorzwichen, sondern ein unärer Operator.

[Medium]

Zitat:

Zitat von Furtbichler (Beitrag 1161650)

Bei Pascal z.B. betrifft dies den '.' (wie in 7.1) und '..' (wie in [1..2]).

Beim rekursiven parsen in einen Grammatikbaum (Term von aussen nach innen) weiss der Parser, dass er eine eckige Klammer betreten hat wenn er deren Inhalt weiter zerlegt, und kann entsprechend andere Regeln anwenden, die in diesem Fall z.B. das Look-Ahead unnötig machen (keine Floats in Mengen zulässig).
Die gleiche Vorgehensweise erlaubt auch das Behandeln von "-". Nehme ich den Term "2--X" finde ich zuerst das erste "-", und gehe in die Rekursion mit "2" und "-X" als Restterme. Schalte ich meinem Tokenizer ein einfaches

Delphi-Quellcode:

if TermString[1] = '-' then TermString := '0'+TermString;

vor, kann ich das Vorzeichen wie ein ganz normales Minus behandeln.

[Bjoerk]

Bei der Division funzt das allerdings nicht: 2/-3 <> 2/0-3

Wenn du als Grundlage den Parser von Joachim Mohr benutzt, da habe ich das seinerzeit eingearbeitet.

[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:

Zitat von Medium (Beitrag 1161759)

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

Delphi-Quellcode:

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.

[Furtbichler]

Zitat:

Zitat von Medium (Beitrag 1161670)

Zitat:

Zitat von Furtbichler (Beitrag 1161650)

Bei Pascal z.B. betrifft dies den '.' (wie in 7.1) und '..' (wie in [1..2]).

Beim rekursiven parsen in einen Grammatikbaum (Term von aussen nach innen) weiss der Parser, dass er eine eckige Klammer betreten

Na ja. Widerspricht ja nicht dem, was ich geschrieben habe. Du kannst '..' als zwei Zeichen des Alphabets für die Programmiersprache Delphi ansehen, oder als ein Zeichen, entsprechend '(*', '*)' etc. Ich habe das immer als ein Zeichen interpretiert. Aber Scanner und Tokenizer arbeiten so. Z.B. bei C#:

a) int i=j++-++x; // geht
b) int i=j+++++x; // geht nicht

Bei A liefert der Tokenizer: id(int) id(i) symbol(assignment) id(j) symbol(plusplus) symbol(minus) symbol(plusplus) id(x)
Bei B liefert der Tokenizer: id(int) id(i) symbol(assignment) id(j) symbol(plusplus) symbol(plusplus) symbol(plus) id(x)

Würde der Parser das erkennen, wären beide Zeilen kompilierbar. Aber nur die erste Zeile funzt, eben weil der Scanner so blöd ist, und im Fall B die ersten zwei Plus-Paare erkennt. Probier's mal aus.

Zitat:

Zitat von NamenLozer (Beitrag 1161761)

Hmm, aber dein Parser sucht ...

Ein Parser sicht nicht, ein Parser erkennt nur. Algorithmisch gesehen liefert ein Parser die Antwort auf die Frage: 'Ist diese Zeichenkette ein Satz aus der Grammatik G?'. Den Vorgang des Erkennens kann man nutzen, um einen Syntaxbaum aufzuspannen, über den dann das Compilat erzeugt wird. Algorithmisch gesehen wird jedoch nur ein Satz der Sprache 'A' (Delphi) in einen Satz der Sprache 'B' (Assembler) überführt. Das der Maschinencode semantisch äquivalent zum Quellcode ist, ist Glücksache.

Zitat:

Aber im Falle des Minus ist der Fall doch eigentlich klar:
...
Zumindest sind diese Regeln bei Parsern so üblich...

Diese 'Regeln' ergeben sich implizit über die Grammatik. Für deine letzte Regel ist aber der Tokenizer zuständig;

Zitat:

in der Mathematik ist es ja normalerweise nicht erlaubt, dass Operatoren oder mehrere Vorzeichen aufeinander folgen...

Nein, was ist denn daran nicht erlaubt? "a = 1+-+-+-+-+-2;

Zitat:

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

Das ergibt sich aus deiner Grammatik.

[idefix2]

Zitat:

Nein, was ist denn daran nicht erlaubt? "a = 1+-+-+-+-+-2;

Was ist bitte daran erlaubt?

Zitat:

Das der Maschinencode semantisch äquivalent zum Quellcode ist, ist Glücksache.

Programmieren ist doch generell Glückssache :)

[Memnarch]

In meinem Compiler habe ich rekursives parsen eingebaut. Undzwar wie folgt:

(von oberer zu unterer schicht, niedrigstes level bindet am stärksten):

releation := expression (relop Expression)
expression := Term (+- Term)*
term := factor (*/ Factor)*
factor := Var|Constant|Function call| '(' relation ')'

wenn ich bei Factor vor meinem wert ein '-' finde, weiß ich es ist ein vorzeichen. Die funktionen liefern übrigens bei mir einen Datentyp zurück. So kann ich ich typensicherheit verfolgen :stupid:


edit @idefix: ich glaib dieses operator gewurschtel ist von delphi erlaubt, finde ich perönlich nicht so schön

[himitsu]

Zitat:

Zitat von Memnarch (Beitrag 1162057)

edit @idefix: ich glaib dieses operator gewurschtel ist von delphi erlaubt, finde ich perönlich nicht so schön

Meinst du das

Delphi-Quellcode:

1+-+-+-+-+-2

?

Wenn man klammern setzt, dann läßt sich erkennen, daß es damit eigentlich keine Probleme geben sollte.

Delphi-Quellcode:

1+(-(+(-(+(-(+(-(+(-2)))))))))

Man könnte aber auch einfach die Plus/Minus zählen und entsprechend handeln.
So mach ich das in meinem Billigparser.

Das erste Plus Der erste Operator ist die Rechenoperator
und die +/- danach sind das Vorzeichen.
* alle Plus (Vorzeichen) werden stur ignoriert (da eh ohne Wirkung)
* die Minus werden gezählt ... bei einer ungeraden Anzahl ist es ein "-" und bei einer geraden Anzahl ein ignorierbares "+".

Delphi-Quellcode:

1+(-+-+-+-+-2)

ergibt dann ein

Delphi-Quellcode:

1+(-- -- -2)

, also

Delphi-Quellcode:

1+(-2)

:)

[Memnarch]

Zitat:

Zitat von himitsu (Beitrag 1162063)

Delphi-Quellcode:

1+(-+-+-+-+-2)

ergibt dann ein

Delphi-Quellcode:

1+(-- -- -2)

, also

Delphi-Quellcode:

1+(-2)

:)

Also ein

Delphi-Quellcode:

 1-2

:P
Ja die operatoren schlange macht vielleicht 'sinn' aber sie ist extrem hässlich und zum glück vernab jeglicher praktischer verwendung.

[Iwo Asnet]

Zitat:

Zitat von idefix2 (Beitrag 1161809)

Zitat:

Nein, was ist denn daran nicht erlaubt? "a = 1+-+-+-+-+-2;

Was ist bitte daran erlaubt?

Der Ausdruck. Versuche es selbst. In der Mathematik ist es problemlos möglich, und ich sehe keinen Grund (außer vielleicht einem ästhetischen), dies nicht zuzulassen. Bei ersetzenden Skriptsprachen (z.B. TeX) ist es sogar existentiell, das ein solcher Ausdruck keine Probleme bereitet. Ich kann mir auch vorstellen, das Codegeneratoren viel komplexer sein müssten, wären redundante Vorzeichen nicht erlaubt.

Zitat:

Zitat von Memnarch (Beitrag 1162057)

releation := expression (relop Expression)
expression := Term (+- Term)*
term := factor (*/ Factor)*
factor := Var|Constant|Function call| '(' relation ')'
wenn ich bei Factor vor meinem wert ein '-' finde, weiß ich es ist ein vorzeichen

Ich sehe das Vorzeichen in deiner Grammatik nicht. Dann muss dein Parser auch nichts 'wissen'. Parser sind -wie Du sicherlich schon herausgefunden hast- strutzdämlich, wissen gar nichts und machen doch alles richtig.

[Namenloser]

Zitat:

Zitat von himitsu (Beitrag 1162063)

Zitat:

Zitat von Memnarch (Beitrag 1162057)

edit @idefix: ich glaib dieses operator gewurschtel ist von delphi erlaubt, finde ich perönlich nicht so schön

Meinst du das

Delphi-Quellcode:

1+-+-+-+-+-2

?

Wenn man klammern setzt, dann läßt sich erkennen, daß es damit eigentlich keine Probleme geben sollte.

Delphi-Quellcode:

1+(-(+(-(+(-(+(-(+(-2)))))))))

Das Problem ist aber, dass die Klammern nicht da sind. In der Mathematik ist nur die Schreibweise mit Klammern erlaubt, nicht ohne. Genau so ist z.B. 5*-2 auch nicht erlaubt, sondern es muss 5*(-2) heißen. Ich habe es mir auch nicht ausgedacht, aber es ist nun mal so festgelegt. Wenn du das in der Schule so schreibst, wird dir das als Fehler angestrichen.

Bei Computern ist das in der Regel anders, aber das liegt daran, dass Informatiker halt manchmal ihre eigenen Regeln und Konventionen aufstellen und sich nicht an die aus der Mathematik halten. Z.B. ist ja auch der Ursprung des Koordinatensystems beim Computer meist links oben, während er sich in der Mathematik normalerweise links unten befindet.

Zitat:

Zitat von Iwo Asnet (Beitrag 1162074)

Ich kann mir auch vorstellen, das Codegeneratoren viel komplexer sein müssten, wären redundante Vorzeichen nicht erlaubt.

Genau das wird wohl der Grund sein. Es hätte einfach keinen Vorteil, eine Aneinanderreihung von Vorzeichen zu verbieten, sondern würde nur den Code komplizierter machen. Aber deshalb ist es in der Mathematik noch lange nicht erlaubt...