利用编译技术实现一门简单的计算器语言

我们需要实现一门简单的计算器语言，可以支持简单的加减法，比如类似js的语法

var id = 123
id = id + 456
var myid = id

执行完这段代码之后，myid的值会变成579，那么如何来实现这个简单的语言呢？我们需要实现一个简单的编译器来完成这个事情。

一个编译器的编译过程一般包括以下几个步骤：

词法分析

词法分析的阶段就是需要识别一个一个的词，比如var id = 123里面就有3个var、id、=、123这些标识符，这些词我们一般称为token，词法分析阶段就是解析token的过程。我们需要一个一个的读取字符，比如读到v的时候，我们需要继续读下一个字符，如果下一个字符是空格或者=，那么v就是变量名。如果下一个字符不是空格或者=，那么需要继续读下一个字符。整体思路就是读取的当前字符可以判断之前的字符串是一个token的话，那么就解析出token，否则就需要继续往下读。我们可以一个一个字符解析然后判断每一种情况来实现词法解析的过程。一般常用的做法是用状态机来实现，每个字符是一种状态。比如一个能识别出var、id、=、+、123的状态机就像下面一样：

• 1是开始，7是结束
• 每个状态之间有一个输入，空转换表示状态直接可以直接转换
• 第1条状态路径可以判断关键字var
• 第2条状态路径可以判断变量名
• 第3条状态路径可以判断操作符+
• 第4条状态路径可以判断赋值=
• 第5条状态路径可以判断数字字面量

用代码实现状态机就可以判断每个token了，词法分析的阶段就完成了

语法分析

语法分析的阶段就是根据词法分析产生的token，形成一个抽象语法树。比如关键字var不能单独使用，后面得跟着一个变量名id，“var id”在一起是有意义的，就是声明一个变量，后面还可以跟=形成赋值，也是可以的。“var var”就是一个错误的语法。所以根据定义好的语法规则，就可以形成语法树。语法树是一棵树状结构，整个代码片段都可以形成一个棵树，还是以最上面的语句为例，可以形成这样一棵树：

• main是程序的入口
• 第一条语句对应的就是第一棵语法树
• 第二条语句对应的就是第二棵语法树
• 第三条语句对应的就是第三棵语法树

程序执行的过程就是执行一条一条的语句，每一条语句对应的是一棵语法树，那么如何处理这棵语法树呢？

• 其实只需要后序遍历这棵树就可以了，先遍历左子树，再遍历右子树，然后遍历根节点，根据根节点的运算符，执行不同的运算符操作。比如赋值运算符=，就是把右子树的结果赋值给左子树的变量，比如加法运算符+，就是把左子树的结果和右子树的结果相加
• 另外，运算符有优先级和结合性的概念，比如(1+2)+(3+4)和1+2+3+4这个表达式，虽然结果都是一样的，但是运算的过程是不一样的，这个就直接影响最后语法树的形状，比如(1+2)+(3+4)的语法树形状是这样，而1+2+3+4的语法树是这样
• 在生成语法树的过程中，需要校验语法格式是否正确，比如表达式123 + + 456就是一个错误的语法。针对每一种符合语法的语句，我们也可以定义状态机，比如表达式语句的状态机是这样：

（图中ε表示空转换） 

• 生成语法树的过程中，还可以发现123+(456+789这种缺少右括号，或者123+456+789)这种多余右括号的情况

但是如果表达式中引用了一个上下文未声明的或者未初始化的变量，类似这种错误需要等到所有语法树生成之后才能判断，这些判断就是语义分析阶段的工作

语义分析

语义分析就是分析程序语法含义的过程。程序语法看上去没问题，但是真实含义有问题，比如有：

• 变量重复定义
• 变量未初始化就直使用
• 变量未定义就直接使用

类似这种错误需要在所有语法树生成之后，遍历所有语法树的节点才能判断。除了发现语义错误之外，还可以计算一些附加属性，比如表达式的语法树的最大层数，变量的类型，变量的作用域等。除此之外，还可以做一些优化，比如(1+2)+(3+4)表达式对应的语法树，可以把左子树(1+2)计算出来是3，右子树(3+4)计算出来是7，再继续计算出来是10，经过常量计算，语法树就直接求出值了，这样就不需要程序运行期间再求值了

生成中间代码和生成目标代码

生成中间代码和生成目标代码一般指后端语言的编译过程。像Javascript语言，是解释执行的，不需要编译成中间代码或者机器码。比如Java语言，编译之后会生成字节码文件，字节码就是一种中间代码，然后由Java虚拟机解释执行字节码或者编译成机器码执行。假如要实现一门后端编译型语言，生成中间代码的过程可以生成LLVM IR的中间表示形式，然后由LLVM生成机器码。生成中间代码的过程是为了生成跨平台的统一的语言表达形式，就比如Java字节码，每个平台的字节码是一样的，由各个平台的Java虚拟机适配操作系统和底层硬件架构。LLVM IR也是一种跨平台的统一的语言表达形式，再由LLVM框架适配操作系统和底层硬件架构。

为了方便，这里我们生成Java字节码。Java字节码是属于JVM规范的一种（https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.html#jvms-4.5），字节码的文件格式如下：

ClassFile {
    u4             magic;
    u2             minor_version;
    u2             major_version;
    u2             constant_pool_count;
    cp_info        constant_pool[constant_pool_count-1];
    u2             access_flags;
    u2             this_class;
    u2             super_class;
    u2             interfaces_count;
    u2             interfaces[interfaces_count];
    u2             fields_count;
    field_info     fields[fields_count];
    u2             methods_count;
    method_info    methods[methods_count];
    u2             attributes_count;
    attribute_info attributes[attributes_count];
}

• 字节码里面每个字节都是无符号字节，u4表示4个字节长度，u2表示2个字节长度，u1表示1个字节长度
• 魔数是一个固定值
• 指定小版本和大版本用来限制最低的Jdk版本
• 常量池是类中出现的字段、方法、类、变量名、常量等，每个常量有编号，默认从1开始
• 访问修饰符就是类的访问级别
• 当前类和超类指向的是常量池中的具体哪个常量，保存的是编号
• 接口定义是当前类实现了哪些接口
• 字段定义是当前类由哪些字段，包括static字段和非static字段
• 方法定义是当前类由哪些方法，包括static方法和非static方法，里面会有实例构造方法和类构造方法
• 属性定义是当前类的一些属性，包括源文件名等

由类js语法翻译成字节码的思路是：

• 一个文件生成一个类，文件名前面加下划线作为类名
• 变量作为类的static字段，变量的声明放在字段定义中，变量的赋值过程放在类构造方法中，变量的赋值表达式翻译成一条一条的JVM指令
• 源文件名放在属性定义中

示例代码如 https://gitee.com/liuanyou/myjs