转载

我的第一个玩具语言 JCScheme 问世了

记得在上大学那会，就想着能够实现门编程语言的，尤其是在看了 SICP 后，由于之前技能不足，一直没能实现，正好最近 SICP 看的正热火朝天，又赶上国庆七天假期，终于把这个愿望给实现了。

实现 JCScheme 这个语言前后大概用了一天左右，真是“纸上得来终觉浅，绝知此事要躬行”，之前觉得像 Scheme 语法这么简单的语言应该很好实现，做了后才知道有多少坑。

本文没有复杂难懂的编译原理知识，如果你和之前的我一样，想实现一门语言但又苦于无从下手，那么你应该花半个小时看看本文，相信你看完本文后一定能够实现一门自己的语言。

当然，JCScheme 语言只是刚开始，还比较简陋，高手请不要见笑，后面随着学习的深入我会逐步完善。

预备知识

由于 JCScheme 极其简单，所以你不需要什么背景知识即可看懂本文，不过你最好了解点 Scheme 语言，如果不了解也没关系，你只需要知道 JCScheme 中的语句使用前缀表达式（也称为波兰表示法）表达，如果你之前没了解过，需要适应下。

# 这是我们常用的中缀表达式

(5 − 6) * 7

# 这就是前缀表达式

* (− 5 6) 7

前缀表达式最明显的一个好处是其操作符可以有不定个，像 (+ 1 2 3 4) 。

JCScheme 简介

在介绍如果实现 JCScheme 之前，先看看 JCScheme能干什么

从上图可以看到 JCScheme 有以下基本特性：

支持整数（Java int实现）与布尔（Java bool实现）、函数三种类型。
支持 def 定义变量、函数
支持 if 进行逻辑判断
支持整数的 + 、 - 、 * 、 / 四种基本算术操作，支持不定个参数。

其次，还有一点需要明确，现在 JCScheme 中只有一个全局环境（Java Map实现），后面定义的同名变量或函数会覆盖之前的。

基本概念与实现

要实现自己的一个语言，定义好基本的语法规则后，剩下的任务就是实现一个解释器（interpreter），由它来分析执行源程序。由于我这里用的是 Java 来实现 JCScheme 的解释器，也就是说，JCScheme 解释器的功能就是读入源程序，然后转化为 Java 代码，最终在 JVM 上执行。没有涉及到编译（Compile）、组装（Assembly）阶段，这一点需要明确。

说白了，解释器其实也是一个程序，输入为源程序，输出为该源程序最终的执行结果。

我在实现这个解释器时，遵循一般的的步骤：

词法分析 —> 语法分析 —-> 语义分析 —-> 求值

词法分析

词法分析（lexical analysis）就是将源程序中的字符分割为一个个单词（token，构成源代码最小的单位）。由于 JCScheme 中使用前缀表示，所以词法解析很简单，两行代码：

src = src.replaceAll( "//(" , "( " ).replaceAll( "//)" , " )" );

String [] tokens = src.split( "//s+" );

语法分析

语法分析（Syntactic analysis，也叫Parsing）也就是把词法分析得到的token序列转化为语法树（AST），语法树是程序的中间表示形式，与具体语言无关。JCScheme才用 Lisp 中经典的 S表达式（S-expression）来表示语法树

AST 其实也是一种树，大家可以先想想数据结构课上一般都是说怎么设计树的存储结构的，其实只要设计的数据结构能够保证能够获取到当前节点的父阶段与子节点就可以了。下面看看我的实现：

public class SExpression {

private String value ;

private SExpression parent;

private List<SExpression> children;

public SExpression (String value , SExpression parent) {

this . value = value ;

this .parent = parent;

this .children = new ArrayList<>();

}

public boolean addChild (SExpression child) {

return this .children.add(child);

}

// 3个 getter 函数省略

// 进行求值的 eval 函数省略

@Override

public String toString () {

if ( 0 == children.size()) {

return value ;

} else {

StringBuffer displayBuffer = new StringBuffer( value + " " );

for (SExpression child : children) {

displayBuffer.append(child.toString() + " " );

}

return displayBuffer.toString();

}

解析token序列生产AST的函数是

public static final String START_TOKEN = "(" ;

public static final String END_TOKEN = ")" ;

public static SExpression parse(String[] tokens) {

SExpression root = new SExpression( "" , null );

SExpression parent = root;

for (String token : tokens) {

SExpression newNode = new SExpression(token, parent );

parent .addChild(newNode);

switch (token) {

case Constants.START_TOKEN:

parent = newNode;

break ;

case Constants.END_TOKEN:

parent = parent .getParent();

break ;

}

return root;

}

可以看到，每个 AST 根节点是token为空，父节点为 null 的一节点。这里解析的方法是：

每一个token为AST上的一节点，父节点为 parent（初始为root）。
遇到 ( token时，开始创建该节点的子树（通过让这个节点成为 parent 实现）
遇到 ) token时，进行回溯，让 parent 为 parent.getParent()。

下面看下 (+ 1 2 (* 3 4)) 生成怎样的 SExpression ：

（图画的比较搓，大家将就着看）

上图最主要的一点就是与左括号相匹配的右括号位于左括号的最后一个孩子节点上（从左到右）。

语义分析

语义分析（Semantic analysis，也叫context sensitive analysis）根据上一步生产的AST，收集源代码的信息，比如类型校验、变量在使用前是否声明等一系列操作。

因为 JCScheme 0.0.1-SNAPSHOT 中类型比较简单，而且去做语义分析，需要做很多异常处理，我这里为了简单都忽略了。所有如果你输入的语法有误（比如括号不匹配），那么我的这个解释器就会报错，在后面的迭代中会逐步改善这块。

求值（eval与apply）

做完了词法分析、语法分析，我们已经得到了与具体语言无关的 AST，那么如果求值呢，SICP 书中给出了 eval-apply cycle ，如下图

无奈现在我 SICP 现在才看到第三章，这应该是第四章的内容，在 StackOverflow 上找到一比较好理解的解释：

the one that eval is doing, is dealing with the syntactic translation of code to its meaning — but it’s doing almost nothing except dispatching over the expression type
apply is to call function with values.
A major enlightenment moment here is to realize that there is a major difference between this eval and apply — the former inherently deals with syntax, but the latter deals with values.
如果你也在读 SICP，可以参考下面的 eval 、与 apply 的具体实现，对 Scheme 不了解的可以直接略过。

( define ( eval exp env)

( cond ( ( self-evaluating? exp) exp)

( ( variable? exp) ( lookup-variable-value exp env) )

( ( quoted? exp) ( text-of-quotation exp) )

( ( assignment? exp) ( eval-assignment exp env) )

( ( definition? exp) ( eval-definition exp env) )

( ( if? exp) ( eval-if exp env) )

( ( lambda? exp)

( make-procedure ( lambda-parameters exp)

( lambda-body exp)

env))

( ( begin? exp)

( eval-sequence ( begin-actions exp) env) )

( ( cond? exp) ( eval ( cond->if exp) env) )

( ( application? exp)

( apply ( eval ( operator exp) env)

( list-of-values ( operands exp) env) ))

( else

( error "Unknown expression type -- EVAL" exp) )))

( define ( apply procedure arguments)

( cond ( ( primitive-procedure? procedure)

( apply-primitive-procedure procedure arguments) )

( ( compound-procedure? procedure)

( eval-sequence

( procedure-body procedure)

( extend-environment

( procedure-parameters procedure)

arguments

( procedure-environment procedure) )))

( else

( error

"Unknown procedure type -- APPLY" procedure))))

简单来说， eval 的主要作用就是理解 AST 的含义，根据其含义进行相应处理，比如赋值语句有其独特的处理方式，if 语句有其独特的处理方式等等。

为了能够让 apply 进行函数调用求值，我们现在需要做的是把 AST 树解释为 JCScheme 中内置的类型，这就是 JCScheme 中 eval 的主要作用。

类型定义

定义一个基类

public abstract class SObject {

}

然后是整数类型与布尔类

public class SNumber extends SObject {

private int value;

public int getValue () {

return value;

}

public SNumber ( int value) {

this .value = value;

}

@Override

public String toString () {

return String.valueOf(value);

}

public class SBool extends SObject {

private boolean value;

public boolean getValue () {

return value;

}

public SBool ( boolean value) {

this .value = value;

}

@Override

public String toString () {

return String.valueOf(value);

}

这两个类比较简单，并且注意到没有为其成员变量提供 setter 函数，这说明这些类型是不可变的。

最后一个比较重要的是函数类型

public class SFunction extends SObject {

List<String> param;

SExpression body;

public SFunction (List<String> param, SExpression body) {

this .param = param;

this .body = body;

}

public SObject apply (SObject... args) {

for ( int i = 0 ; i< args.length; i ++) {

SScope.env.put(param.get(i), args[i]);

}

SObject ret = body.eval();

for ( int i = 0 ; i< args.length; i ++) {

SScope.env.remove(param.get(i));

}

return ret;

}

@Override

public String toString () {

StringBuffer buffer = new StringBuffer( "Function : args [" );

for (String p : param) {

buffer.append(p + ", " );

}

buffer.append( "]/n" );

buffer.append( "Body :/n" );

buffer.append(body.toString());

return buffer.toString();

}

可以看到， SFunction 内部有两个成员变量，用来表示其 参数列表 与 函数体 。其中的 apply 表示函数调用，可以看到无非就是把形式参数与实际参数进行捆绑（我这里都放到了全局环境中），之后调用 SExpression 的 eval 方法，得到用内置类型表示的结果。

可以看到，这里的重点又回到 eval 方法上去了。 JCScheme 的主要复杂点也就算在这个 SExpression 的 eval 方法上了，因为它涉及到把 SExpression 转为内置类型，所以按理说也应该是复杂的。

eval 的具体代码后面我会经常改动，感兴趣的可参考 Github 。