Also habe ich versucht, einen Taschenrechner mit dem Parser von Scala zu schreiben, und es hat Spaß gemacht, mit der Ausnahme, dass ich festgestellt habe, dass die Operatorassoziativität verkehrt ist, und dass ich meine Grammatik rekursiv mache, obwohl sie völlig eindeutig ist ein Stapelüberlauf.

Zur Verdeutlichung, wenn ich eine Regel habe wie: def subtrahiere: Parser [Int] = num ~ "-" ~ addiere {x => x._1._1 - x._2}, dann ergibt sich die Bewertung 7 - 4 - 3 6 statt 0.

Die Art und Weise, wie ich dies implementiert habe, besteht darin, dass ich einen Binärbaum zusammensetze, in dem Operatoren Nicht-Blattknoten und Blattknoten Zahlen sind. Die Art, wie ich den Baum auswerte, ist left child (Operator) right child. Wenn ich den Baum für 7 - 4 - 5 konstruiere, möchte ich, dass er so aussieht:

-
-   5
7   4   NULL   NULL

wo - die Wurzel ist, sind seine Kinder - und 5, und die Kinder des zweiten sind 7 und 4.

Der einzige Baum, den ich leicht konstruieren kann, ist

-
7   -
NULL   NULL   4   5

Das ist anders und nicht das, was ich will.

Grundsätzlich ist die einfache Klammerung 7 - (4 - 5), während ich (7 - 4) - 5 möchte.

Wie kann ich das hacken? Ich habe das Gefühl, dass ich in der Lage sein sollte, einen Taschenrechner mit der korrekten Priorität eines Operators zu schreiben. Sollte ich zuerst alles mit einem Token versehen und dann meine Token umkehren? Ist es für mich in Ordnung, meinen Baum einfach umzudrehen, indem ich alle linken Kinder der rechten Kinder zum rechten Kind des Elternteils des rechten Kindes mache und das Elternteil zum linken Kind des ex-rechten Kindes mache? Auf den ersten Blick scheint es gut zu sein, aber ich habe nicht wirklich tief darüber nachgedacht. Ich habe das Gefühl, es muss nur einen Fall geben, den ich vermisse.

Mein Eindruck ist, dass ich nur mit den Scala-Parsern einen LL-Parser erstellen kann. Wenn Sie einen anderen Weg kennen, sagen Sie es mir bitte!