Associatividade do operador usando analisadores Scala

Então, eu tenho tentado escrever uma calculadora com o analisador de Scala, e tem sido divertido, exceto que eu descobri que a associatividade do operador está atrasada, e que quando eu tento deixar minha gramática de esquerda recursiva, mesmo que seja completamente inequívoca, um estouro de pilha.

Para esclarecer, se eu tiver uma regra como: def subtrair: Parser [Int] = num ~ "-" ~ add {x => x._1._1 - x._2} então avaliar 7 - 4 - 3 vem a ser 6 em vez de 0.

A maneira que eu realmente implementei isso é que eu estou compondo uma árvore binária onde os operadores são nós não-folha, e os nós folha são números. A maneira como eu avalio a árvore é deixada filho filho (operador) direito. Ao construir a árvore para 7 - 4 - 5, o que eu gostaria que parecesse é:

-
-   5
7   4   NULL   NULL

onde - é a raiz, seus filhos são - e 5, e os filhos do segundo são 7 e 4.

No entanto, a única árvore que consigo construir é

-
7   -
NULL   NULL   4   5

o que é diferente, e não o que eu quero.

Basicamente, o parêntese fácil é 7 - (4 - 5) enquanto eu quero (7 - 4) - 5.

Como posso hackear isso? Eu sinto que eu deveria ser capaz de escrever uma calculadora com a correta precedência do operador, independentemente. Devo tokenizar tudo primeiro e depois inverter meus tokens? Está tudo bem para mim apenas virar minha árvore, pegando todos os filhos de filhos certos e tornando-os o filho certo do pai da criança certa e fazendo dos pais o filho da esquerda da criança ex-direita? Parece bom em uma primeira aproximação, mas eu realmente não pensei muito sobre isso. Eu sinto que deve haver apenas algum caso que estou perdendo.

Minha impressão é que só posso fazer um analisador de LL com os analisadores de scala. Se você conhece outra maneira, por favor me diga!

questionAnswers(2)

yourAnswerToTheQuestion