小刘是一名出色的软件工程师，能流畅的使用5种编程语言打印 hello world。一天他的准岳父(养老院院长)找到他，拜托他一件事：教养老院的老人们编程，不用太难，体验一把思想就行了
院长，别说了，拔刀吧
小刘内心是拒绝的，一些不可抗拒的原因，让他强忍住内心的翻滚，“嗯，没啥问题”。小刘神志有些恍惚，准备离开院长办公室。院长补充道：“对了小刘，老人们都不会英语，但ABCD还是认识的，这个你知道的吧,知道的吧 吧 吧 ...”
三天狂风暴雨般的发泄后，憔悴的小刘坐在台阶上吸着烟，开始想怎么去做这个事。有两种方案：
1:选一门现成的编程语言，但大部分都是老外写的，语言关键字和规则繁多，老人们吃不消
2:自己设计一门中文的编程语言，实现简单的输入输出，告诉老人什么是编程就行了
小刘选择自己设计一门编程语言，提笔一挥，寥寥的在小字本上涂涂画画。
定义 A,B,C;
B 等于 3;
输入 A ;
C 等于 A乘B;
输出 C;
当然，上面的例子，这只是小刘写在小字本上的草稿，具体语言规则怎么定义？怎么解析这个语言？怎么执行这个语言？懵逼的小刘开始查阅一些资料。了解市面上的语言是如何实现的。
小刘的故事先说到这儿。我们开始严肃一点...
『设计模式』中有一个模式可以解释特定的语法规则，它就是解释器模式(Interpreter Pattern)，不同于的工厂模式或者策略模式，解释器模式在java或者.net中并不常见，业务中很少用去解释特定的语法，所以并不被广泛的使用。一个解释器可大可小，大可为复杂的编译器，小可以是一个简单的字符串解析。但本质都是对特定语法做出合理解释。
假设输入一个公式字符串: 1+2*3 注意这是一个字符串，要解析这个公式字符串，得到最终的值我们有两种方案：
循环遍历字符串，将括号，运算符，数字提取出来，然后根据运算符左右结合以及优先级来计算
将表达式转换为树结构的对象，树结构的每个节点，可以是数字，可以是运算符，每个节点类型不
同，然后递归遍历这个树结构，遇到运算符号节点，递归求运算符节点下的左右节点值，然后将两个节点值做相应的运算。
很显然，第一种方案简单直白易理解，但实现起来相当繁重，代码可读性也不佳。第二种则是目前最好的解决方式,将表达式字符串解析为一个对象树。
所以我们的第一个难点是如何将表达式转换为一颗树
对于算术表达式而言，比如1+3-2，6-1，语法是两个数字之间必须出现+，-，*，/，如果出现1+-2,6--1那这就是错误的语法
那我们怎么来制定语法呢，在编译原理领域，有一个通用的方法来描述语法，叫是BNF范式
语言的描述——BNF范式
为什么不用自然语言来定义我们的语言的规范？很难啊！，现在自然语言处理，仍然是世界性的难题，目前还没有哪种程序能够将自然语言处理的很好。
描述一个文法，我们常常使用巴斯克范式(BNF范式)来描述一个文法的结构
科普一下，世间万语，皆可用归纳为4种文法，计算机编程主要使用 2型，3型 文法。(0，1型交给我们语文老师处理了)
0型即自然语言文法
1型称为上下文相关文法
2型称为上下文无关文法
3型称为正则文法
简单介绍一下bnf范式文件格式
< > 尖括号内为必选项
| 竖线表示在其左右两边任选一项，相当于"OR"的意思
::= 是“被定义为”的意思
一条BNF的生成规则形如：
::= A|B|C|D|E|F|G|H|... 偷个懒
更详细的规则，可参考巴科斯范式
针对上面四则运算，简单的 bnf 文件内容如下：
::= |+|-
::= |*|/
::= |
::= 0|1|2|3|4|5|6|7|8|9
digt: 数字，int 整形，fac:优先级高的运算，exp:表达式
有了bnf范式规则，我们需要表达式字符串1+3-2构造成一个符合bnf规则的数据结构，如下图：
四则运算_ast.png
我们需要自己写解析函数，然后构造成上图所示的数据结构，在编译原理领域这种结构叫 抽象语法树(AST)
简单介绍一下抽象语法树
抽象语法树(AST)
语言解释分为前后端，前端语言 java,c,php,js。后端主要是指编译器 例如 GJC,GCC 等。
例如实现一个c 版的 for 循环，需要用GCC 将c 源代码编译成一个GCC语言版抽象语法树，然后GCC 在解释执行这个抽象语法树。
抽象语法树特点
不依赖源语言文法
如果按bnf 文法解析源代码，解析为一个自定义的结构，那在解释这个自定义结构的时候，肯定是为bnf 文法量身定制的。一旦这个语言有了升级，bnf 文法发生变动，相应的，后端解释器也会做相应的改动，十分麻烦。
抽象语法树，相当于一个后端解释器给前端定制的一个规范，无论语言规范怎么变动，只需要改变将源代码解析为抽象语法树的解析器就行了，解析抽象语法树的解释器并不用改动。
不依赖细节
不同语言实现一个for 循环
在c中为：
if(condition){
dosomthing();
}
在fortran中为：
If condition then
dosomthing()
end if
语法树只需要两个分支节点来表示
AST_IF.png
在源程序中出现的关键字 if 括号等，都将忽略，两种语言最终生成一样的抽象语法树
抽象语法树作用
前端领域使用抽象语法树极为广泛，将js代码转换为抽象语法树后，可以很轻松的对语法树进行分析与优化，语法树带给我们的便利充斥在开发过程中的方方面面，例如IDE对代码进行格式化缩进。
简单列举抽象语法树，的作用：
格式化存储(存储网页，存储sql 语句，描述json 的json)
语法检查、格式化、高亮、错误提示、代自动补全
ide 功能糖
代码混淆
uglifyjs
CssMinify
代码优化
webpack 梳理依赖关系
amd,cmd 规范相互转换
bable 编译 es6
CoffeeScript、TypeScript、JSX等转化为原生Javascript
抽象语法树结构
将 javascript 源代码 1+1 转换为抽象语法树(AST)
源代码
1+1
将js 源代码转换为AST 抽象语法树，
{
"type": "Program",
"body": [
{
"type": "ExpressionStatement",
"expression": {
"type": "BinaryExpression",
"operator": "+",
"left": {
"type": "Literal",
"value": 1,
"raw": "1"
},
"right": {
"type": "Literal",
"value": 1,
"raw": "1"
}
}
}
],
"sourceType": "script"
}
转换为AST语法树的工具比较多，v8,Esprima,UglifyJS2,Acorn 等。能转换抽象语法树的也不只是 java,js ,php 等，html,css,sql,json,这些都可转换为抽象语法树
这种树结构为js 通用的AST树结构，基本上主流开源的解析器都解析为这种结构，当然也可以转换为其他格式的AST树结构，相应的，解析器就需要自己去实现。
回到正题，我们有了语法树，接下来要做啥？
我们需要去遍历这个树，然后对树的每个节点，做相应的处理，例如,遇到 int 节点，直接返回他的值，遇到 exp节点，则先计算 exp 左右节点的值，然后根据自身的运算符号(+,-等)做相应的加减操作。
遍历节点，并处理节点这个过程，我们叫文法识别(解释器)，也是解释器模式中的解释过程。在编程语言领域，做这方面工作的我们叫编译器
这儿就一笔带过说一下解释器，我了解的并不深入。
文法识别 (解释器)
解释器，输入为ast抽象语法树，然后遍历ast的每个节点，针对每个节点做响应处理，直到节点遍历完成。
任何语言的抽象语法树和解释器都是基于他底层语言的，例如v8引擎 js解析的底层就是c ，他的AST抽象语法树，也是c语言版本的语法树，解释器也是c 语言版本的解释器。而c语言的抽象语法树则是GCC编译器了。
像ide,uglifyjs,bable 等虽然也可以解析js 为抽象语法树，但这个语法树都是js 版本的语法树，并不需要解释器，语法树只是辅助他们做一些js 语法的优化等。如果用js 写一个java 抽象语法树的解释器，那就可以在node 里面执行 java 了(意义何在？)
自定义编程语言
上面的描述，我已经写懵逼了，估计看的人也是懵逼的,接下来我们要用解释器模式，实现一套自己的编程语言 ,bnf+ast+ 解释器。取个好听的名字 懵逼 语言
首先定义我们语言的bnf 范式，如下：
::=
::= 定义 ;
::= , |
::= |
::= |||||
::= 输入 ;
::= 输出 ;
::= 如果 { } ;
::= | ! | [ && ] | [ or ]
::= ( )
::= != | == | < | > | <= | >=
::= | | ( )|
::= | |
::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
::= |
::= 0|1|2|3|4|5|6|7|8|9
然后编写符合上述范式规则的程序源代码
源代码
定义 Y;
输入 Y;
如果 ( Y > 0 ) {
输出 Y ;
};
然后是写解析器，将源代码按bnf 规则，解析为抽象语法树。
解析器代码这儿就不粘贴，可以在git 项目中查看 (解析器源代码)
语法树可视化后如下
火星语言_AST.png
此时 ast 构造已经完成，剩下的就是实现解释器。解释器，输入为AST树对象，然后对树进行递归遍历，针对不同节点，做不同处理。最终将整个AST 树执行完。后续再粘代码...
demo 地址
git 地址
