language-agnostic - 我将如何手动编写复杂的公式解析器？

Question

嗯，这是与语言无关的，我更喜欢用 C# 或 F# 来做，但这次我对“无论如何它会如何工作”这个问题更感兴趣。

我想要完成的是：

a）我想学习它——这次是关于我的自我，这是一个有趣的项目，我想向自己展示我非常擅长这些东西

b) 我对 EBNF 有一点了解（虽然我还不知道，运算符优先级在 EBNF 中是如何工作的 - Irony.NET 做得对，我检查了示例，但这对我来说有点不祥）

c) 我的解析器应该能够接受这个：例如 5 * (3 + (2 - 9 * (5 / 7)) + 9) 并给我正确的结果

d) 坦率地说，这似乎是我编写编译器甚至解释器时遇到的最大问题。我什至可以生成 64 位汇编代码（我可以手动编写汇编程序），但是公式解析器...

e) 另一个想法：即使是简单的计算机（比如我的旧 Sharp 1246S，只有大约 2kB 的 RAM）也可以做到这一点……它不会那么难，对吧？甚至非常非常古老的编程语言也有公式评估...... BASIC 是从 1964 年开始的，他们已经可以计算出我作为示例提出的那种公式

f）一些想法，一些灵感就足够了 - 我只是不知道如何做运算符优先级和括号 - 但是我知道它涉及 AST 并且很多人使用堆栈

所以你怎么看？

Answer 1

你应该去了解递归下降解析器。

查看 Code Golf 练习，以 10 种不同的方式执行此操作：

Code Golf：数学表达式评估器（尊重 PEMDAS）

这些“高尔夫”解决方案中有几个是递归下降解析器，只是以不同的方式编码。

您会发现仅进行表达式解析是迄今为止编译器中最简单的事情。解析语言的其余部分更难，但理解代码元素如何交互以及如何生成好的代码要困难得多。

您可能还对如何使用 BNF 表达解析器以及如何使用该 BNF 做一些事情感兴趣。下面是一个示例，说明如何以显式 BNF 和隐式 AST 作为基础，以符号方式解析和操作代数。这不是编译器传统上所做的，但所做的机器深深地建立在编译器技术中。

Answer 2

计算机上的传统公式处理器使用 POSTFIX 表示法。他们使用堆栈，弹出 2 个项目作为操作数，弹出第三个项目作为运算符，然后推送结果。

你想要的是一个非常简单的 INFIX 到 POSTFIX 符号转换器。一旦你在后缀处理是你做过的最简单的事情。

Answer 3

对于在 PHP 中实现的基于堆栈的解析器，它使用 Djikstra 的分流码算法将中缀转换为后缀表示法，并且支持具有不同数量参数的函数，您可以查看PHPExcel计算引擎的源代码

Answer 4

如果您想使用现有的解决方案，我可以推荐一个有效的、PSR-0 兼容的调车场算法实现：https ://github.com/andig/php-shunting-yard/tree/dev 。