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

你应该去了解Recursive Descent parsers .

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

Code Golf: Mathematical expression evaluator (that respects PEMDAS)

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

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

您可能还对如何使用 BNF 表达解析器以及如何使用该 BNF 执行某些操作感兴趣。这是
example of how to parse and manipulate algebra symbolically以显式 BNF 和隐式 AST 为基础。这不是编译器传统上做的事情，但这样做的机器深深地建立在编译器技术中。