Así que he estado tratando de escribir una calculadora con el analizador de Scala, y ha sido divertido, excepto que descubrí que la asociatividad del operador es al revés, y que cuando trato de hacer que mi gramática sea recursiva a la izquierda, aunque es completamente inequívoca, obtengo una pila se desborda.

Para aclarar, si tengo una regla como: def resta: Parser [Int] = num ~ "-" ~ add {x => x._1._1 - x._2} luego evaluar 7 - 4 - 3 resulta ser 6 en lugar de 0.

La forma en que implementé esto es que estoy componiendo un árbol binario donde los operadores son nodos sin hojas y los nodos con hojas son números. La forma en que evalúo el árbol es niño izquierdo (operador) niño derecho. Cuando construyo el árbol para 7 - 4 - 5, me gustaría verlo como:

-
-   5
7   4   NULL   NULL

donde - es la raíz, sus hijos son - y 5, y los hijos de los segundos son 7 y 4.

Sin embargo, el único árbol que puedo construir fácilmente es

-
7   -
NULL   NULL   4   5

Lo que es diferente, y no lo que yo quiero.

Básicamente, la paréntesis fácil es 7 - (4 - 5) mientras que quiero (7 - 4) - 5.

¿Cómo puedo hackear esto? Siento que debería poder escribir una calculadora con la prioridad de operador correcta independientemente. ¿Debo tokenizar todo primero y luego invertir mis fichas? ¿Es correcto para mí simplemente voltear mi árbol tomando a todos los hijos abandonados de los niños de la derecha y haciéndolos el hijo correcto del padre del niño de la derecha y haciendo que el padre sea el hijo de la izquierda del ex hijo de la derecha? Parece bueno en una primera aproximación, pero realmente no lo he pensado demasiado. Siento que debe haber algún caso que me falte.

Mi impresión es que solo puedo hacer un analizador de LL con los analizadores de scala. Si sabes de otra manera, por favor dímelo!