仅用50行代码实现一个Python编写的计算器的教程

 简介

在这篇文章中，我将向大家演示怎样向一个通用计算器一样解析并计算一个四则运算表达式。当我们结束的时候，我们将得到一个可以处理诸如 1+2*-(-3+2)/5.6+3样式的表达式的计算器了。当然，你也可以将它拓展的更为强大。

我本意是想提供一个简单有趣的课程来讲解 语法分析 和 正规语法（编译原理内容）。同时，介绍一下PlyPlus,这是一个我断断续续改进了好几年的语法解析 接口。作为这个课程的附加产物，我们最后会得到完全可替代eval（）的一个安全的四则运算器。

如果你想在自家的电脑上试试本文中给的例子的话，你应该先安装 PlyPlus ,使用命令pip install plyplus  。（译者注：pip是一个包管理系统，用来安装用python写的软件包，具体使用方法大家可以百度之或是google之，就不赘述了。）

本篇文章需要对python的继承使用有所了解。

语法

对于那些不懂的如何解析和正式语法工作的人而言，这里有一个快速的概览：正式语法是用来解析文本的一些不同层面的规则。每一个规则都描述了相对应的那部分输入的文本是如何组成的。

这里是一个用来展示如何解析1+2+3+4的例子：
 

Rule #1 - add IS MADE OF add + number
            OR number + number

</div>

或者用 EBNF:
 

add: add'+'number
  | number'+'number
  ;

</div>

解析器每次都会寻找add+number或者number+number，找到一个之后就会将其转换成add。基本上而言，每一个解析器的目标都在于尽可能的找到最高层次的表达式抽象。

以下是解析器的每个步骤：

  number + number + number + number

</div>

    第一次转换将所有的Number变成“number”规则

  [number + number] + number + number

</div>

    解析器找到了它的第一个匹配模式！

  [add + number] + number

</div>

    在转换成一个模式之后，它开始寻找下一个

  [add + number]
  add

</div>

这些有次序的符号变成了一个层次上的两个简单规则: number+number和add+number。这样，只需要告诉计算机如果解决这两个问题，它就能解析整个表达式。事实上，无论多长的加法序列，它都能解决! 这就是形式文法的力量。
运算符优先级

算数表达式并不仅仅是符号的线性增长，运算符创造了一个隐式的层次结构，这非常适合用形式文法来表示:

1 + 2 * 3 / 4 - 5 + 6

</div>

这相当于:

1 + (2 * 3 / 4) - 5 + 6

</div>

我们可以通过嵌套规则表示此语法中的结构:
 

add: add+mul
  | mul'+'mul
  ;
mul: mul '*; number
  | number'*'number
  ;

</div>

通过将add设为操作mul而不是number，我们就得到了乘法优先的规则。

让我们在脑海中模拟一下使用这个神奇的解析器来分析1+2*3*4的过程：

  number + number * number * number
  number + [number * number] * number

</div>

    解析器不知道number+number的结果，所以这是它（解析器）的另一个选择

  number + [mul * number]
  number + mul
  ???

</div>

现在我们遇到了一点困难! 解析器不知道如何处理number+mul。我们可以区分这种情况，但是如果我们继续探索下去，就会发现有很多不同的没有考虑到得可能，比如mul+number, add+number, add+add, 等等。

那么我们应该怎么做呢？

幸运的是，我们可以做一点小“把戏”：我们可以认为一个number本身是一个乘积，并且一个乘积本身是一个和！

这种思路一开始看起来有点古怪，不过它的确是有意义的：
 

add: add'+'mul
  | mul'+'mul
  | mul
  ;
mul: mul'*'number
  | number'*'number
  | number
  ;

</div>

但是如果 mul能够变成 add, 且 number能够变成 mul ， 有些行的内容就变得多余了。丢弃它们，我们就得到了：
 

add: add'+'mul
  | mul
  ;
mul: mul'*'number
  | number
  ;

</div>

让我们来使用这种新的语法来模拟运行一下1+2*3*4：

  number + number * number * number

</div>

    现在没有一个规则是对应number*number的了，但是解析器可以“变得有创造性”

  number + [number] * number * number
  number + [mul * number] * number
  number + [mul * number]
  [number] + mul
  [mul] + mul
  [add + mul]
  add

</div>

成功了！！！

如果你觉得这个很奇妙，那么尝试着去用另一种算数表达式来模拟运行一下，然后看看表达式是如何用正确的方式来一步步解决问题的。或者等着阅读下一节中的内容，看看计算机是如何一步步运行出来的！

运行解析器

现在我们对于如何让我们的语法运作起来已经有了非常不错的想法了，那就写一个实际的语法来应用一下吧:
start: add;            // 这是最高层
add: add add_symbol mul | mul;
mul: mul mul_symbol number | number;
number:'[d.]+';      // 十进制数的正则表达式
mul_symbol:'*'|'/';// Match * or /
add_symbol:'+'|'-';// Match + or -</div>
你可能想要复习一下正则表达式，但不管怎样，这个语法都非常直截了当。让我们用一个表达式来测试一下吧:
 

>>>fromplyplusimportGrammar
>>> g=Grammar("""...""")
>>>printg.parse('1+2*3-5').pretty()
start
 add
  add
   add
    mul
     number
      1
   add_symbol
    +
   mul
    mul
     number
      2
    mul_symbol
     *
    number
     3
  add_symbol
   -
  mul
   number
    5

</div>

干得漂亮!

仔细研究一下这棵树，看看解析器选择了什么层次。

如果你希望亲自运行这个解析器，并使用你自己的表达式，你只需有Python即可。安装Pip和PlyPlus之后，将上面的命令粘贴到Python内(记得将'...'替换为实际的语法哦~)。

使树成形

Plyplus会自动创建一棵树，但它并不一定是最优的。将number放入到mul和将mul放入到add非常有利于创建一个阶层，现在我们已经有了一个阶层那它们反而会成为一个负担。我们告诉Plyplus对它们加前缀去“展开”（i.e.删除）规则。

碰到一个@常常会展开一个规则，一个#则会压平它，一个?会在它有一个子结点时展开。在这种情况下，?就是我们所需要的。
 

start: add;
?add: add add_symbol mul | mul;   // Expand add if it's just a mul
?mul: mul mul_symbol number | number;// Expand mul if it's just a number
number:'[d.]+';
mul_symbol:'*'|'/';
add_symbol:'+'|'-';

</div>

在新语法下树是这样的：
 

>>> g=Grammar("""...""")
>>>printg.parse('1+2*3-5').pretty()
start
 add
  add
   number
    1
   add_symbol
    +
   mul
    number
     2
    mul_symbol
     *
    number
     3
  add_symbol
   -
  number
   5

</div>

哦，这样变得简洁多了，我敢说，它是非常好的。

括号的处理及其它特性

目前为止，我们还明显缺少一些必须的特性：括号，单元运算符(-(1+2))，及表达式中间允许存在空字符。其实这些特性都很容易就能实现，下面我们来尝试一下。

需要先引入一个重要的概念：原子。在一个原子里面（括号中