简介
在这篇文章中，我将向各人演示奈何向一个通用计较器一样理会并计较一个四则运算表达式。当我们竣事的时候，我们将获得一个可以处理惩罚诸如 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
可能用 EBNF:
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
我们可以通过嵌套法则暗示此语法中的布局:
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自己是一个乘积，而且一个乘积自己是一个和！
这种思路一开始看起来有点离奇，不外它简直是有意义的：
add: add'+'mul
| mul'+'mul
| mul
;
mul: mul'*'number
| number'*'number
| number
;
可是假如 mul可以或许酿成 add, 且 number可以或许酿成 mul ， 有些行的内容就变得多余了。扬弃它们，我们就获得了：
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
乐成了！！！
假如你以为这个很奇妙，那么实验着去用另一种算数表达式来模仿运行一下，然后看看表达式是如何用正确的方法来一步步办理问题的。可能等着阅读下一节中的内容，看看计较机是如何一步步运行出来的！
运行理会器
此刻我们对付如何让我们的语法运作起来已经有了很是不错的想法了，那就写一个实际的语法来应用一下吧:
start: add; // 这是最高层
add: add add_symbol mul | mul;
mul: mul mul_symbol number | number;
number:'[d.]+'; // 十进制数的正则表达式
mul_symbol:'*'|'/';// Match * or /
add_symbol:'+'|'-';// Match + or –
你大概想要温习一下正则表达式，但不管奈何，这个语法都很是直截了当。让我们用一个表达式来测试一下吧:
>>>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
干得大度!
仔细研究一下这棵树，看看理会器选择了什么条理。
#p#分页标题#e#
假如你但愿亲自运行这个理会器，并利用你本身的表达式，你只需有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:'+'|'-';
在新语法下树是这样的：
>>> 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
哦，这样变得简捷多了，我敢说，它长短常好的。
括号的处理惩罚及其它特性
今朝为止，我们还明明缺少一些必需的特性：括号，单位运算符(-(1+2))，及表达式中间答允存在空字符。其实这些特性都很容易就能实现，下面我们来实验一下。
需要先引入一个重要的观念：原子。在一个原子内里（括号中及单位运算）产生的所有操纵都优先于所有加法或乘法运算（包罗位操纵）。由于原子只是一个优先级的结构器，并无语法意义，帮我们加上"@"标记以确保在编译时它被能展开。
答允空格呈此刻表达式内最简朴的要领就是利用这种表明方法：add SPACE add_symbol SPACE mul | mul; 但个表明功效烦琐且可读性差。所有，我们需要令Plyplus老是忽略空格。
下面是完整的语法，海涵了以上所述特性：
start: add;
?add: (add add_symbol)? mul;
?mul: (mul mul_symbol)? atom;
@atom: neg | number |'('add')';
neg:'-'atom;
number:'[d.]+';
mul_symbol:'*'|'/';
add_symbol:'+'|'-';
WHITESPACE:'[ t]+'(%ignore);
请确保领略这个语法再进入下一步：计较！
运算
此刻，我们已经可以将一个表达式转化成一棵分层树了，只需要逐分支地扫描这棵树，便可获得最终功效。
我们此刻要开始编写代码了，在此之前，我需要对这棵树做两点表明：
1.每个分支都是包括如下两个属性的实例：
头(head)：法则的名字(譬喻add可能number);
尾(tail)：包括所有与其匹配的子法则的列表。
2.Plyplus默认会删除不须要的标志。在本例中，'( ' ，')' 和 '-' 会被删除。但add和mul会有本身的法则，Plyplus会知道它们是必需的，从而不会被删除它们。假如你需要保存这些标志，可以手动关掉这项成果，但从我的履向来看，最好不要这样做，而是手动修改相关语法结果更佳。
#p#分页标题#e#
言归正传，此刻我们开始编写代码。我们将用一个很是简朴的转换器来扫描这棵树。它会从最外面的分支开始扫描，直到达到根节点为止，而我们的事情是汇报它如何扫描。假如一切顺利的话，它将总会从最外层开始扫描!让我们看看详细的实现吧。
>>>importoperator as op
>>>fromplyplusimportSTransformer
classCalc(STransformer):
def_bin_operator(self, exp):
arg1, operator_symbol, arg2=exp.tail
operator_func={'+': op.add,
'-': op.sub,
'*': op.mul,
'/': op.div }[operator_symbol]
returnoperator_func(arg1, arg2)
number =lambdaself, exp:float(exp.tail[0])
neg =lambdaself, exp:-exp.tail[0]
__default__=lambdaself, exp: exp.tail[0]
add=_bin_operator
mul=_bin_operator
每个要领都对应一个法则。假如要领不存在的话，将挪用__default__要领。我们在个中省略了start,add_symbol和mul_symbol，因为它们只会返回本身的分支。
我利用了float()来理会数字，这是个懒要领，但我也可以用理会器来实现。
为了使语句整洁，我利用了运算符模块。譬喻add根基上是 'lambda x,y: x+y'之类的。
OK，此刻我们运行这段代码来查抄一下功效。
>>> Calc().transform( g.parse('1 + 2 * -(-3+2) / 5.6 + 30'))
31.357142857142858
那么eval()呢？7
>>>eval('1 + 2 * -(-3+2) / 5.6 + 30')
31.357142857142858
乐成了:)
最后一步：REPL
为了雅观，我们把它封装到一个不错的计较器 REPL：
defmain():
calc=Calc()
whileTrue:
try:
s=raw_input('> ')
exceptEOFError:
break
ifs=='':
break
tree=calc_grammar.parse(s)
printcalc.transform(tree)
完整的代码可从这里获取：
https://github.com/erezsh/plyplus/blob/master/examples/calc.py
