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

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

  number + number + number + number

  [number + number] + number + number

  [add + number] + number

  [add + number]
  add

1 + 2 * 3 / 4 - 5 + 6

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

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

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

  number + [mul * number]
  number + mul
  "htmlcode">

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



干得漂亮!
仔细研究一下这棵树，看看解析器选择了什么层次。
如果你希望亲自运行这个解析器，并使用你自己的表达式，你只需有Python即可。安装Pip和PlyPlus之后，将上面的命令粘贴到Python内(记得将'...'替换为实际的语法哦~)。
使树成形
Plyplus会自动创建一棵树，但它并不一定是最优的。将number放入到mul和将mul放入到add非常有利于创建一个阶层，现在我们已经有了一个阶层那它们反而会成为一个负担。我们告诉Plyplus对它们加前缀去“展开”（i.e.删除）规则。
碰到一个@常常会展开一个规则，一个#则会压平它，一个"htmlcode">

start: add;
"htmlcode">

> 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;
"htmlcode">

>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



                                
                                

                                    Python 
                                
DDR爱好者之家 Design By 杰米