自定义编程语言的实现

2018-03-01 本文已影响0人懵逼的码畜

小刘是一名出色的软件工程师，能流畅的使用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的生成规则形如：

<char>  ::= A|B|C|D|E|F|G|H|... 偷个懒

更详细的规则，可参考巴科斯范式

针对上面四则运算，简单的 bnf 文件内容如下：

<exp>  ::= <fac>|<fac>+<exp>|<fac>-<exp>
<fac>  ::= <int>|<int>*<int>|<int>/<int>
<int>  ::= <digit><int>|<digit>
<digit>  ::= 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 了（意义何在？）