所以我一直在尝试用Scala的解析器编写一个计算器,它很有趣,除了我发现操作符关联性是倒退的,当我试图让我的语法左递归时,即使它完全是明确的,我得到了堆栈溢出.
为了澄清,如果我有一个规则,如:def减法:Parser [Int] = num~" - "~add {x => x._1._1 - x._2}然后评估7 - 4 - 3出来是6而不是0.
我实际实现这个的方式是我正在组成一个二叉树,其中运算符是非叶节点,叶节点是数字.我评估树的方式是留给孩子(操作员)的右孩子.在为7 - 4 - 5构建树时,我希望它看起来像是:
-
- 5
7 4 NULL NULL
Run Code Online (Sandbox Code Playgroud)
其中 - 是根,其子节点是 - 和5,第二个孩子是7和4.
但是,我能够轻松构建的唯一树是
-
7 -
NULL NULL 4 5
Run Code Online (Sandbox Code Playgroud)
这是不同的,而不是我想要的.
基本上,简单的括号是7 - (4 - 5),而我想要(7 - 4) - 5.
我怎么能破解这个?无论如何,我觉得我应该能够编写一个具有正确运算符优先级的计算器.我应该首先对所有内容进行标记,然后反转我的令牌吗?我是否可以通过抓住正确孩子的所有左子女并让他们成为正确孩子的父母的正确孩子并让父母成为前右孩子的左孩子来翻转我的树?它在第一次近似似乎很好,但我并没有真正考虑过它.我觉得必须有一些我不知道的情况.
我的印象是我只能使用scala解析器创建一个LL解析器.如果您了解其他方式,请告诉我!