Parser: Überladene 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 "a-b" als auch "a*(-b)" 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".
Und dann können bestimmte Datentypen noch implizit in andere umgewandelt werden. Das bedeutet, wenn ich ein Gleitkommazahl-Plus definiere: 1,2 + 3,4 = 4,6 dann kann ich dieses + auch für Ganzzahlen benutzen: 1 + 2 wird dank impliziter Datentypumwandlung zu 1,0 + 2,0 = 3,0.
Das bedeutet wenn ich z.B 5 Datentypen habe könnte ein einziger Operator aus 5 + 5 + 5^2 = 35 Ü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 Op Op Op 1 = (((1 Op) Op) Op 1) oder (1 Op (Op (Op 1))) oder ((1 Op) Op (Op 1))
Und dummerweise entstehen auch Möglichkeiten wie:
(1 Op) (Op (Op 1)) die dann zu einem Fehler führen

Ich habe mir überlegt, dass zur Auswahl des Operators in erster Linie der Datentyp entscheiden sollte (und nicht der Rang). Angenommen ich definiere String-Plus (String + String = String) und ein Int-Plus (Int + Int = Int) wobei das String-Plus einen höheren Rang hat als das Int-Plus. Dann würde wenn der Rang entscheidet sobald das +Zeichen auftaucht immer das String-Plus verwendet werden und z.B 1+2 würde zu einem Fehler führen.

Und genau das macht das ganze so schwer (bzw. unmöglich?).
Meine Grundvoraussetzung ist eine klammerlose Reihe von Operatoren und Zahlen (alles andere wurde im Schritt zuvor zu Zahlen reduziert).
Also z.B: Op Op Op 1 Op Op Op 2 Op Op Op (das ist zwar kein praktikables Beispiel aber durchaus ein korrektes, selbst wenn Op immer für denselben Operator steht)

Ein großes Problem hier ist, dass ein Operator nicht zwingend nur einen Typ benutzt. Es ist z.B auch ein solcher Operator möglich: Int Op Boolean = String.
Das bedeutet wenn ich folgenden Ausdruck habe
Op 1 Op
habe ich schon ein Problem.
angenommen Op 1 ist definiert als Op Int = Float und 1 Op als Int Op = Int. Dann wäre es von den Datentypen her sinnvoller ich rechne Op (1 Op) statt (Op 1) Op.

Und erst richtig unüberschaubar wird es bei vorherigem Beispiel Op Op Op 1 Op Op Op 2 Op Op Op.
Mein einziger Ansatz um die passendsten Datentypen herauszufinden ist es alle Möglichkeiten auszuprobieren. Aber das kann ich wegen der Effizienz nicht machen. Allein bei der Rechnung 1+2+3+4+5+6+7+8+9+0+1 würde ich hier ordentliche Probleme bekommen, da das Plus alleine schon 7 Überladungen hat und bei 10 Plus macht das 7^10 = 282.475.249 Möglichkeiten. Das bedeutet mit dieser Möglichkeit könnte man nicht einmal 11 Zahlen addieren!

Nochmal zusammengefasst:
Ich habe einen Audruck wie "Op Op Op 1 Op Op Op 2 Op Op Op". Ein Operator kann beliebig überladen werden mit beliebigen Rängen. Und ich habe keine Ahnung wie ich hierbei vorgehen soll.

Ich würde mich wirklich über jede Idee freuen!

Grüße
blablab

Noch etwas: Der Parser hat den Delphi-Parser zum Vorbild. Das bedeutet, sobald eine Entscheidungsmöglichkeit entsteht möchte ich es möglichst gleich wie der Delphi-Parser behandeln.

[Namenloser]

Ich weiß nicht, ob ich es ganz richtig verstanden habe, aber ich bin der Meinung, dass ein Operator immer die gleiche Priorität haben sollte, unabhängig von den Datentypen. Sonst wird es nämlich nicht nur haarig zu implementieren, sondern auch irgendwann schwer nachzuvollziehen. Außerdem erschließt sich mir der Sinn nicht wirklich, die Priorität vom Datentyp abhängig zu machen; ich kenne auch keine dynamisch typisierte Sprache, die das so macht.

Wenn man es so macht, dass ein Operator immer die gleiche Priorität hat, ist es doch eigentlich einfach: Beim Parsen kümmert man sich erst mal gar nicht um die Datentypen sondern baut erst mal nur einen abstrakten Baum auf. Im nächsten Schritt arbeitet man diesen dann ab, und beachtet dabei die Typen. Das geht im einfachsten Fall mit einer case-Anweisung und damit in konstanter Laufzeit.

Edit:
Noch mal bezüglich:

Zitat:

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

Das eine nennt man linksassoziativ und das andere rechtsassoziativ. Das ist auch wieder eine reine Frage der Definition, genau wie die Operatorenrangfolge. In der Mathematik sind z.B. Subtraktion und Division linksassoziativ, aber Potenzen rechtsassoziativ.

[Bjoerk]

Das nennt sich unäres Minus (muß man besonders behandeln), z.B. einen gesonderten Operator vergeben. Das unäre Plus kann man rauslöschen.

[blablab]

@NamenLozer:

Ich hab mir das auch nochmal überlegt und das klingt wirklich sinnvoll. Denn wie du sagst, auch für den Benutzer ist es wahrscheinlich eher verwirrend wenn ein String-Plus einen höheren Rang hat als ein Int-Plus, denn das +Zeichen ist ja beides mal gleich. Und außerdem erwartet man ja auch, dass ein Operator mit einem höheren Rang eher verwendet wird als einer mit einem niedrigerem Rang. Das bedeutet wenn ich ein Int-Plus und ein Float-Plus definiere und dem Float-Plus einen höheren Rang gebe, dann kann ich das Int-Plus gar nicht mehr verwenden, da automatisch immer das Float-Plus mit impliziter Datentypumwandlung benutzt wird. Es scheint also wirklich sinnvoll zu sein bei gleichen Argumenten (ich hab das argLeft, argRight und argBoth genannt) auch nur gleiche Ränge zu erlauben.

Was ich mir nur noch nicht sicher bin ist, ob ich bei unterschiedlichen Argumenten (argLeft, argRight und argBoth) auch unterschiedliche Ränge verlangen soll. Denn wenn nicht, dann sollte ich wahrscheinlich eine eigene Rangfolge zwischen argLeft, argRight und argBoth festlegen. Wäre das sinnvoll z.B zuerst argRight dann argBoth und dann argLeft zu nehmen? Das entspräche dann der Reihenfolge von links nach rechts: Wenn ich also !5! habe wobei Fakultät und Subfakultät denselben Rang haben, dann würde (!5)! gerechnet werden, da man es wahrscheinlich auch so von links nach rechts lesen würde.
Oder gibt es hier eine andere, sinnvollere Variante?

Wegen links- und rechtsassoziativ: Ich mach vorerst alles linksassoziativ. Ob ich das nur wegen den blöden Potenzen noch einführe, muss ich mir dann später nochmal überlegen...

[Namenloser]

Also Wolfram Alpha klammert so: !4!4!!4! = !(4!) * 4!! * 4!

Fakultät hat also höhere Priorität als Subfakultät.

[Furtbichler]

Also, für eine Parser ist das doch sehr einfach:

Code:

<Term><Op><Term>
<Term> ::= <OptionalSign><Term> | <Constant>

Ergo ist das 1. '-' ein Operator und alles was danach folgt, ein Vorzeichen. Der Tokenizer liefert eh nur 'OpMinus' und weiß nicht (und ist ihm auch egal), ob es sich um ein Vorzeichen oder einen Operator handelt.

Anders als bei '--' und '++' Operatoren, da macht der Tokenizer ein Lookahead, weswegen 'a---b' funktioniert (und kompiliert), aber 'a----b' nicht (Syntaxfehler).

Zurück zum Thema: Definiere deine Sprache einfach so, wie Du es gerne hättest, denn ein Parser -richtig programmiert- setzt nur die Grammatik um. Verwende keine eigenen Gedanken, dann hast Du auch keine Probleme mit dem Teil.

[blablab]

@Furtbichler:
aber das funktioniert z.B dafür nicht: 1!+2

Edit:
Dank NamenLozer hab ich momentan gar keine offene Frage mehr.
Dadurch, dass ich überladene Operatoren mit gleichen Argumentpositionen aber unterschiedlichen Prioritäten nicht mehr zulasse, hat sich die Problemstellung komplett geändert. Ich muss es jetzt erst einmal ausprobieren...

[Memnarch]

In erster Linie eher nen Parserproblem oder nicht?
Namenloozer hat das schon gut erklärt.

Um an meinem Compiler zu arbeiten habe ich folgendes durchgelesen:
http://compilers.iecc.com/crenshaw/

vielleicht ganz informativ

[blablab]

Vielen Dank für eure Antworten!
So wie es aussieht war die zusätzliche Einschränkung alles was ich brauchte, also danke NamenLozer!
Und Respekt dafür, dass ihr durch meine verwirrende Texte durchgestiegen seid