前言##
一艘轮船3小时航行90千米。照这样的速度，航行300千米需要多少小时？
300 / (90/30) = 10' //没有写单位，扣1分 :>
现在如果要让计算机做这题呢,讲讲编译原理吧.
没办法,大学没这么高深的课~后来一直到见到Babel才知道有AST,编译原理这些东西.
挺神奇的,有了他你就能自己写个postCss插件,也可以写TeaScript
简介##
图中可以看到存在于人脑和电脑中的表达式是不太一样的
所以转换是关键,那么转换到中间的物件我们叫做AST
AST他只表达不实现这就是他abstract的意义所在,正因为如此他才能够在源和目标两端之间运转自如.
QQ截图20170614102158.png
ast.png
识别四则运算语法##
先不管要转换成的是什么样子,首先我们得知道他是个什么东西.
那么来观察一下四则运算是什么,这里列几条式子.
1+2*3*4 = 3*3*4 = 9*4 = 36
1+2*(3*4) = 3*(3*4) = 9*4 = 36
没错,这两条写的都是错的.
重点在于,我们需要将操作符** , () 的优先级*表达出来.
再看几条式子
2*1+3*4
2/1+3*4
2+(3*4)
(3*4)*2
可以想象到解析的时候要么从最高优先级开始,要么从最低开始.(因为那样只要递归进去,回溯出来就ok了)
我们这里从最低开始,也就是+,-号
--加减号--
加减号旁边的每一项怎么得到 : split with ( +, - ) 得到的分别是 " 2*1, 2/1, 2, (3*4)*2"
来一招高中物理教过的遮住法的受力分析,将以上得到的结果遮住,比如第一条:
Term+3*4 // 原式 2*1+3*4
这里用Term这个单词遮住了'2*1',那么我们此时只知道Term发出的作用力是2
同理可得:
Term+TermB = 2 + 12 // 原式 2*1+3*4
那么就已经抽象出来了
TermA(+,-)TermB....(+,-)TermN
--再到乘除号--
再进一步对每一项Term抽象,一样的遮住法,就不展开讲了
可以很容易得到
Term = FactorA (*,/) FactorB.....
代码遇到Term因为是要沉下去的,浮出结果的,所以优先级自然会存在于此
这里多提一点, (Expr)和Number都能归纳成Factor
--归纳--
整个四则运算规则已经分析完毕了,一共抽象出了2.3条式子,列一下
Factor = num | (Expr)
Term = Term (*,/) Factor
Expr = Expr (+,-) Term
第2,3条要连乘连加,所以要存在自递归
Factor =Term || Factor * Term || Factor / Term
这里的语法中的递归,写代码的时候你会发现写不出来的!
这个说是叫左递归来着,要把左递归给干掉.把自递归的一项置后
很容易想到,只要将左边的一项固定;右边一项的能力么~既能衍生出无限多也能止于空串就可以了,
Expr = Term ExprTail ExprTail = + Term ExprTail | - Term ExprTail | null
Term = Factor TermTail TermTail = * Factor TermTail | / Factor TermTail | null
Factor = (Expr) | num
实现部分##
全部已经走通后,接下来写代码就好了
token-->prase-->anything
--token
简单说就是将每个char分解成各个单词,
比如一篇文章的话.只要split空格,判断前一个单词是空格后面就是单词.
在本例中也差不多,比如前一个单词不是数字,后面的减号就是负号而不是减号.
--parse
单词有了,拿单词去套句子,也就是上面的最后消除左递归后的规则.
怎么套呢,也很简单,就是匹配不匹配,不匹配抛出错误就好了
多提一点,空串匹配也是匹配
--anything
根据parse得到的AST,去解释就好了,在示例代码中实现了计算和转换.
结尾##
参考中的文章说实话以我的水平看不太懂,所以本文是为了让更多人能理解其中的一些转换的关键,并且能给出图形后能帮助更好的理解.
另外Vue大法好 (￣︶￣)
--Todo
1.本例功能上未实现,小数的识别,以及更多的友好报错(正如编译器检查)
2.UI上的不足,树长的太随意辣 ↗
3.生成AST代码不够自然,想要达到就像打日志一样的流畅
4.不理解,既然能转换左递归,我认为即使存在左递归也能写的出代码,
可能因为学的不够深入吧,还有很多如文法方面的,下推的,可配置词法分析器等等
网友评论