Próbowałem więc napisać kalkulator za pomocą parsera Scali i było fajnie, poza tym, że stwierdziłem, że asocjatywność operatora jest wsteczna, a kiedy próbuję uczynić moją gramatykę rekurencyjną lewą, nawet jeśli jest to całkowicie jednoznaczne, otrzymuję przepełnienie stosu.

Aby wyjaśnić, jeśli mam regułę taką jak: def subtract: Parser [Int] = num ~ "-" ~ add {x => x._1._1 - x._2} następnie ocena 7 - 4 - 3 wychodzi 6 zamiast 0.

Sposób, w jaki to zaimplementowałem, jest taki, że tworzę drzewo binarne, w którym operatory są węzłami innymi niż liścia, a węzły liścia są liczbami. Sposób, w jaki oceniam drzewo, to lewe dziecko (operator) prawe dziecko. Podczas konstruowania drzewa na 7 - 4 - 5 chciałbym, aby wyglądało to tak:

-
-   5
7   4   NULL   NULL

gdzie - jest korzeniem, jego dzieci - i 5, a dzieci drugiego - 7 i 4.

Jednak jedynym drzewem, które mogę łatwo zbudować, jest

-
7   -
NULL   NULL   4   5

co jest inne, a nie to, czego chcę.

Zasadniczo, proste nawiasowanie wynosi 7 - (4 - 5), podczas gdy chcę (7 - 4) - 5.

Jak mogę to zhakować? Czuję, że powinienem być w stanie napisać kalkulator z poprawnym priorytetem operatora niezależnie od tego. Czy powinienem najpierw tokenizować wszystko, a następnie odwrócić moje tokeny? Czy to w porządku, że mogę po prostu przewrócić moje drzewo, biorąc wszystkie lewe dzieci właściwych dzieci i czyniąc je właściwym dzieckiem rodzica właściwego dziecka i czyniąc z rodziców lewe dziecko byłego dziecka? Wydaje się to dobre w pierwszym przybliżeniu, ale tak naprawdę nie myślałem o tym zbyt głęboko. Czuję, że musi być jakiś przypadek, którego brakuje.

Mam wrażenie, że mogę utworzyć parser LL tylko z parserami scala. Jeśli znasz inny sposób, powiedz mi!