简介
在这篇文章中,我将向大家演示怎样向一个通用计算器一样解析并计算一个四则运算表达式。当我们结束的时候,我们将得到一个可以处理诸如 1+2*-(-3+2)/5.6+3样式的表达式的计算器了。当然,你也可以将它拓展的更为强大。
我本意是想提供一个简单有趣的课程来讲解 语法分析 和 正规语法(编译原理内容)。同时,介绍一下PlyPlus,这是一个我断断续续改进了好几年的语法解析 接口。作为这个课程的附加产物,我们最后会得到完全可替代eval()的一个安全的四则运算器。
如果你想在自家的电脑上试试本文中给的例子的话,你应该先安装 PlyPlus ,使用命令pip install plyplus 。(译者注:pip是一个包管理系统,用来安装用python写的软件包,具体使用方法大家可以百度之或是google之,就不赘述了。)
本篇文章需要对python的继承使用有所了解。
语法
对于那些不懂的如何解析和正式语法工作的人而言,这里有一个快速的概览:正式语法是用来解析文本的一些不同层面的规则。每一个规则都描述了相对应的那部分输入的文本是如何组成的。
这里是一个用来展示如何解析1+2+3+4的例子:
1 2 |
Rule #1 - add IS MADE OF add + number OR number + number |
或者用 EBNF:
1 2 3 |
add: add'+'number | number'+'number ; |
解析器每次都会寻找add+number或者number+number,找到一个之后就会将其转换成add。基本上而言,每一个解析器的目标都在于尽可能的找到最高层次的表达式抽象。
以下是解析器的每个步骤:
- number + number + number + number
第一次转换将所有的Number变成“number”规则 - [number + number] + number + number
解析器找到了它的第一个匹配模式! - [add + number] + number
在转换成一个模式之后,它开始寻找下一个 - [add + number]
- add
这些有次序的符号变成了一个层次上的两个简单规则: number+number和add+number。这样,只需要告诉计算机如果解决这两个问题,它就能解析整个表达式。事实上,无论多长的加法序列,它都能解决! 这就是形式文法的力量。
运算符优先级
算数表达式并不仅仅是符号的线性增长,运算符创造了一个隐式的层次结构,这非常适合用形式文法来表示:
1 + 2 * 3 / 4 – 5 + 6
这相当于:
1 + (2 * 3 / 4) – 5 + 6
我们可以通过嵌套规则表示此语法中的结构:
1 2 3 4 5 6 |
add: add+mul | mul'+'mul ; mul: mul '*; number | number'*'number ; |
通过将add设为操作mul而不是number,我们就得到了乘法优先的规则。
让我们在脑海中模拟一下使用这个神奇的解析器来分析1+2*3*4的过程:
- number + number * number * number
- number + [number * number] * number
解析器不知道number+number的结果,所以这是它(解析器)的另一个选择 - number + [mul * number]
- number + mul
- ???
现在我们遇到了一点困难! 解析器不知道如何处理number+mul。我们可以区分这种情况,但是如果我们继续探索下去,就会发现有很多不同的没有考虑到得可能,比如mul+number, add+number, add+add, 等等。
那么我们应该怎么做呢?
幸运的是,我们可以做一点小“把戏”:我们可以认为一个number本身是一个乘积,并且一个乘积本身是一个和!
这种思路一开始看起来有点古怪,不过它的确是有意义的:
1 2 3 4 5 6 7 8 |
add: add'+'mul | mul'+'mul | mul ; mul: mul'*'number | number'*'number | number ; |
但是如果 mul能够变成 add, 且 number能够变成 mul , 有些行的内容就变得多余了。丢弃它们,我们就得到了:
1 2 3 4 5 6 |
add: add'+'mul | mul ; mul: mul'*'number | number ; |
让我们来使用这种新的语法来模拟运行一下1+2*3*4:
- number + number * number * number
现在没有一个规则是对应number*number的了,但是解析器可以“变得有创造性” - number + [number] * number * number
- number + [mul * number] * number
- number + [mul * number]
- [number] + mul
- [mul] + mul
- [add + mul]
- add
成功了!!!
如果你觉得这个很奇妙,那么尝试着去用另一种算数表达式来模拟运行一下,然后看看表达式是如何用正确的方式来一步步解决问题的。或者等着阅读下一节中的内容,看看计算机是如何一步步运行出来的!
运行解析器
现在我们对于如何让我们的语法运作起来已经有了非常不错的想法了,那就写一个实际的语法来应用一下吧:
1 2 3 4 5 6 |
start: add; // 这是最高层 add: add add_symbol mul | mul; mul: mul mul_symbol number | number; number:'[d.]+'; // 十进制数的正则表达式 mul_symbol:'*'|'/';// Match * or / add_symbol:'+'|'-';// Match + or - |
你可能想要复习一下正则表达式,但不管怎样,这个语法都非常直截了当。让我们用一个表达式来测试一下吧:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
>>>fromplyplusimportGrammar >>> g=Grammar(&ܨ这篇文章中,我将向大家演示怎样向一个通用计算器一样解析并计算一个四则运算表达式。当我们结束的时候,我们将得到一个可以处理诸如 1+2*-(-3+2)/5.6+3样式的表达式的计算器了。当然,你也可以将它拓展的更为强大。
我本意是想提供一个简单有趣的课程来讲解 语法分析 和 正规语法(编译原理内容)。同时,介绍一下PlyPlus,这是一个我断断续续改进了好几年的语法解析 接口。作为这个课程的附加产物,我们最后会得到完全可替代eval()的一个安全的四则运算器。 如果你想在自家的电脑上试试本文中给的例子的话,你应该先安装 PlyPlus ,使用命令pip install plyplus 。(译者注:pip是一个包管理系统,用来安装用python写的软件包,具体使用方法大家可以百度之或是google之,就不赘述了。) 本篇文章需要对python的继承使用有所了解。 语法 对于那些不懂的如何解析和正式语法工作的人而言,这里有一个快速的概览:正式语法是用来解析文本的一些不同层面的规则。每一个规则都描述了相对应的那部分输入的文本是如何组成的。 这里是一个用来展示如何解析1+2+3+4的例子:
或者用 EBNF:
解析器每次都会寻找add+number或者number+number,找到一个之后就会将其转换成add。基本上而言,每一个解析器的目标都在于尽可能的找到最高层次的表达式抽象。 以下是解析器的每个步骤:
这些有次序的符号变成了一个层次上的两个简单规则: number+number和add+number。这样,只需要告诉计算机如果解决这两个问题,它就能解析整个表达式。事实上,无论多长的加法序列,它都能解决! 这就是形式文法的力量。 运算符优先级 算数表达式并不仅仅是符号的线性增长,运算符创造了一个隐式的层次结构,这非常适合用形式文法来表示: 1 + 2 * 3 / 4 – 5 + 6 这相当于: 1 + (2 * 3 / 4) – 5 + 6 我们可以通过嵌套规则表示此语法中的结构:
通过将add设为操作mul而不是number,我们就得到了乘法优先的规则。 让我们在脑海中模拟一下使用这个神奇的解析器来分析1+2*3*4的过程:
现在我们遇到了一点困难! 解析器不知道如何处理number+mul。我们可以区分这种情况,但是如果我们继续探索下去,就会发现有很多不同的没有考虑到得可能,比如mul+number, add+number, add+add, 等等。 那么我们应该怎么做呢? 幸运的是,我们可以做一点小“把戏”:我们可以认为一个number本身是一个乘积,并且一个乘积本身是一个和! 这种思路一开始看起来有点古怪,不过它的确是有意义的:
但是如果 mul能够变成 add, 且 number能够变成 mul , 有些行的内容就变得多余了。丢弃它们,我们就得到了:
让我们来使用这种新的语法来模拟运行一下1+2*3*4:
成功了!!! 运行解析器 现在我们对于如何让我们的语法运作起来已经有了非常不错的想法了,那就写一个实际的语法来应用一下吧:
你可能想要复习一下正则表达式,但不管怎样,这个语法都非常直截了当。让我们用一个表达式来测试一下吧:
|