一个100行Python的手写数学解析器

这个资源库包含一个手写解析器，用于用100行Python代码编写形式为2*(3+4)的简单数学表达式，它的存在完全是出于教育目的。

你应该会得到14分作为结果。这可能并不令人惊讶，但你也可以。

现在，为任何东西创建手写解析器都是完全无用的，因为有像ANTLR这样的工具可以帮你完成所有繁重的工作。而且，这个特殊的问题肯定已经被世界各地的计算机科学本科生解决了数百万次。但是，直到今天，我才解决了这个问题，就像我在维也纳理工大学的本科生学习时一样，我们跳过了低级的工作，建立了一个基于yacc/bison的解析器。我真的很喜欢做这个小的边项目，因为它把你带回了计算机科学的根源(根据维基百科，这个东西可以追溯到1969年，我很喜欢你最终得到一个漂亮而简单的解决方案。

请注意，我绝对不是编译器构建方面的专家，可能有人会对这里发生的一些事情感到不寒而栗，但对我来说，这是一次很好的教育练习。

关于这个主题的文献非常正式，这使得一个外行很难进入这个话题。在这个描述中，我试图更多地关注直观的解释。但是，对我来说，很清楚的是，如果你不坚持这个理论，那么你很快就会遇到一些很难理解的事情，如果你不能将它与文献中发生的事情联系起来的话。

问题是如何将表示为字符串的代数表达式转换为便于重用的形式，以便对其进行有趣的操作，例如计算表达式的结果或很好地将其可视化。允许的代数运算有+、-、*/以及使用(嵌套的)括号(...)。运算符优先的标准规则适用。

这个问题有不同的解决方法，但一般来说，LL(1)解析器以实现非常简单而著称。

LL(1)解析器是一个自上而下的解析器，它不断用当前匹配的语法规则的右侧替换解析器堆栈上的元素。此决定基于两条信息：

解析器堆栈上的顶端符号，可以是终端，也可以是非终端。终端是出现在输入中的标记，如+，而非终端是语法规则的左侧，如Exp。

例如，如果堆栈上的当前符号是S，并且当前输入端子是A，并且在语法中存在允许。

那么应该用P替换S。这里，S和P是非终止符，并且对于本文档的其余部分，大写的语法元素被认为是非终止符，而诸如a之类的小写语法元素被认为是终止符。为了继续该示例，现在将堆栈顶部的a与输入流终端a相匹配并从堆栈中移除。该过程一直持续到堆栈为空(这意味着解析成功)或出现错误(这意味着输入流不符合语法)。

因为通常有多个语法规则可供选择，所以在哪种情况下应用哪种规则的信息需要以某种方式编码，并且通常存储在解析表中。然而，在我们的例子中，语法是如此简单，以至于这几乎是一种过度杀伤力，因此解析表由代码中的一些if语句来表示。

(1)Exp->；Exp+Exp(2)Exp->；Exp-Exp(3)Exp->；Exp*Exp(4)Exp->；Exp/Exp(5)Exp->；(Exp)(6)Exp->；Num。

语法是不言而喻的，但是它是模棱两可的，因为它包含NtN形式的规则。这意味着还没有定义2+3*4是否应该被解释为2+3=5，然后是5*4=20，还是应该被解释为3*4=12，然后是2+12=14。通过巧妙地重写语法，可以在语法中对运算符优先进行编码。

(1)Exp->；Exp+Exp2(2)Exp->；Exp-Exp2(3)Exp->；Exp2(4)Exp2->；Exp2*Exp3(5)Exp2->；Exp2/Exp3(6)Exp2->；Exp3(7)Exp3->；(Exp)(8)Exp3->。

Exp(1)Exp+Exp2(3)Exp2+Exp2(6)Exp3+Exp2(8)Num+Exp2(4)Num+Exp2*Exp3(6)Num+Exp3*Exp3(8)Num+Num*Exp3(8)Num+Num*Num*Num

Exp(1)Exp+Exp2(3)Exp2+Exp2(4)Exp2*Exp3+Exp2(6)Exp3*Exp3+Exp2(8)Num*Exp3+Exp2(8)Num*Num+Exp2(6)Num*Num+Exp3(8)Num*Num+Num。

我们看到，在这两个示例中，运算符+和*的规则应用顺序是相同的。先出现+可能有点令人困惑，但如果您查看生成的解析树，您可以说服自己*的结果作为输入流向+，因此需要首先计算它。

这里，我使用了输入流的最左边的派生，这意味着您总是尝试替换下一个最左边的符号(它对应于堆栈顶部的符号)，而不是位于解析树中间的符号。这是LL(1)中的一个L实际表示的，所以这也是我们的解析器将如何操作的。

然而，还有一个问题。我们提出的语法现在是无歧义的，但它仍然不能被LL(1)解析器解析，因为多个规则以相同的非终结符开始，解析器需要向前看一个以上的标记才能确定要应用哪条规则。实际上，对于上面的例子，您必须向前看一个以上的规则才能自己找出派生。正如LL(1)中的1所指示的那样，LL(1)-解析器只向前看一个符号。通过将语法规则中的所有左递归重写为右递归，可以使语法LL(1)对解析器友好。

(0)Exp>；Exp$(1)Exp->；Exp2 Exp'；(2)Exp'；->；+Exp2 Exp&39；(3)Exp'；->；-Exp2 Exp&39；(4)Exp2-&>；ϵ(5)Exp2->；Exp3 Exp2'；(6)Exp2&39；->；*Exp3 Exp2&39；(7)Exp2'；-&>；/Exp3 Exp2'；(8)Exp2'；->；ϵ(9)Exp3->；Num(10)Exp3->；(Exp)。

在这里，ϵ意味着堆栈的当前符号应该只是弹出，而不是被任何其他符号替换。

此外，我们还添加了另一个规则(0)，以确保解析器在输入完成时能够理解。这里，$代表输入结束。

虽然我们不打算使用显式的解析表，但我们仍然需要知道它的内容，以便解析器可以确定下一步应用哪个规则。为了简化解析表的内容，我将使用我在实现整个过程中发现的一个小技巧，即：

如果特定的非终端只有一个语法规则，那么只需扩展它，而不关心输入流上有什么。

这与您在文献中发现的稍有不同，在文献中，您只能在当前终端允许的情况下展开非终端。在我们的示例中，这意味着无论如何都会扩展非终端S、Exp和Exp2。

+-&>规则(2)--&>规则(3)*--&>规则(6)/--&>规则(7)编号->规则(9)(-&>规则(10)。

请注意，只有当堆栈上的当前符号适合语法规则的左手边时，才能应用规则。例如，规则(2)仅当当前表达式在堆栈上时才能应用。

因为我们也有一些可以扩展到ϵ的规则，所以我们需要计算出实际应该在什么时候发生。为此，有必要查看可为空的非终结符之后出现的是什么终结符。在我们的例子中，可为空的非终结符是Exp'；和Exp2'；。(在我们的例子中，可以为空的非终结符是Exp'；和Exp2'；)。Exp'；后跟)和$，Exp2后跟+，-，)和$。因此，每当我们在输入流中遇到)或$时，当Exp#39；在堆栈顶部时，我们只需将Exp#39；弹出并继续前进。

抽象语法树可以在解析过程中动态构建，这里的诀窍是只包含那些感兴趣的元素(在本例中为num、+、-、*/)，并跳过所有仅出于语法原因而存在的元素。

有一件事你可能会觉得值得一试，那就是从包含所有语法元素的具体语法树开始，剔除你发现无用的东西。保持可视化的东西肯定会对这一点有帮助。

LL(1)解析的一个好处是，您可以只使用调用堆栈来跟踪当前非终结点，因此在Python实现中，您会发现非终结点Exp的函数parse_e()除了首先调用parse_e2()，然后调用parse_ea(对应于Exp'；)之外没有什么别的。

Def parse_E3(令牌)：if tokens[0].Token_type==TokenType.T_NUM：返回Tokens.op(0)Match(Tokens，TokenType.T_LPAR)e_node=parse_e(Tokens)Match(Tokens，TokenType.T_RPAR)返回e_node。

这里，检查来自输入流的当前令牌是否为数字。如果是，我们直接使用输入令牌，而不将其放在某个中间堆栈上。这与规则(9)相对应。如果不是数字，则必须是(，因此我们尝试使用此令牌(如果预期令牌和传入令牌不同，则函数Match()会引发异常)。