WsztRush
Blog Categories About

编程语言实现模式

很久之前已经把这本书看过一遍了，但是一直没有实践过!于是，拿出来再复习一遍，顺便记录笔记。关于这本书有几点：

  1. ANTLR贯穿全书：作者是Terence Parr，这点也就不奇怪了
  2. ANTLR生成的代码是LL(K)的
  3. 偏重实践，原理很少，想看原理要去看龙书

另外，你应该先知道编译的过程大概分成哪几步骤以及为什么这样划分！废话少说，来看这本书的内容。

解析输入

词法分析和语法分析很多地方都是相同的，解析器结构如下：

public class G extends Parser {
    // 类型定义
    // 合适的构造函数
    // 规则对应的方法
}

在一个规则中包含很多子规则时，根据向前看符号来决定使用哪个，这个逻辑的代码描述可以用if-else来做：

if(向前看到alt1){
    // 匹配alt1
} else if(向前看到alt2){
    // 匹配alt1
}....

当然这里也可以用switch做，在规则上定义的一些常见操作有：

  1. (T)?：T可有可无
  2. (T)+：多个T
  3. (T)*：零个或多个T

这些操作的代码描述：

// (T)?
if(向前看到T){ match(T);}
// (T)+
do{
    match(T);
} while(向前看到T)
// (T)*
while(向前看到T){
    match(T);
}

能利用好这三个操作大部分的规则都可以搞定了！词法分析相对语法分析了来说简单很多，Lexer会提供nextToken()来供Parser使用来不断地获取TOKEN：

public Token nextToken(){
    while(lookahead-char != EOF) {
        switch(lookahead-char){
            case 空白字符: { consume(); continue; }
            case 字符后面可能是T1: return T1();
            case 字符后面可能是T2: return T2();
			// ...
            default:
                出错;
        }
    }
    return EOF;
}

直观上来看用switch进行预测，相当于构造了一个状态机吧，其中consume()方法自增下标并将下一个字符当做向前看字符（消费字符）。在仅使用一个向前看符来进行语法分析时，也就是LL(1)，对于下面语法：

list : '[' elements ']';
elements : element (',' element)*;
element : NAME | list;

生成的Paser如下：

public class ListParser extends Parser {
    public void list(){
        match(ListLexer.LBRACK); // 匹配并消耗词法单元
        elements();
        match(ListLexer.RBRACK);
    }
    public void elements(){
        element();
        while(lookahead.type == ListLexer.COMMA) {
            match(ListLexer.COMMA);
            element();
        }
    }
    public void element(){
        if(lookahead.type == ListLexer.NAME) match(ListLexer.NAME);
        else if(lookahead.type == ListLexer.LBRACK) list();
        else throw new Error("语法错误");
    }
}

很简单的语法用LL(1)是没有问题的，对于稍微复杂一点的其预测能力差就暴露出来了，怎么办？当然是多拿几个进行预测！可以构造环形缓冲区来存放用来预测的TOKEN，另外增加两个方法：

  1. LA：返回第k个向前看词法单元的类型
  2. LT：返回第k个词法单元

那么文法：

element : NAME '=' NAME : NAME : list ;

对应的程序描述就变为：

public void element(){
    if(LA(1) == LookaheadLexer.NAME && LA(2) == LookaheadLexer.EQUALS) {
        match(LookaheadLexer.NAME);
        match(LookaheadLexer.EQUALS);
        match(LookaheadLexer.NAME);
    } else if(LA(1) == LookaheadLexer.NAME) {
        match(LookaheadLexer.NAME);
    } else if(LA(1) == LookaheadLexer.LBACK) {
        list();
    } else {
        throw new Error("语法错误!");
    }
}

但是LL(K)也不是万能的，如果向前看k个解决不了问题，那么向前无限个总应该可以搞定了吧？回溯解析中使用递归尝试不同的规则，在发现无法匹配时把消费掉的TOKEN吐出来：

public void rule() {
    if(speculate_alt1()){
        // 匹配alt1
    } else if(speculate_alt2()){
        // 匹配alt2
    } else { throw new Error("语法错误！"); }
}
public boolean speculate_alt1() {
    boolean success = true;
    mark();// 标记当前位置，供release使用
    try{
        // 匹配alt1
    } catch(Exception e){ success = false; }
    release();// 将消费掉的TOKEN重新放回去
    return success;
}

回溯解析最大的缺陷就是性能低，而其中一个原因则是做了不少重复工作，对于语法：

s : expr ':' | expr ';';

在尝试第一个子规则失败时会去尝试第二个，那么expr就会被匹配两次！如果能把之前匹配过的结果记住就好了（参考记忆化搜索），此时仅需要做一些很小的修改：

// 每个规则有一个Map来保存结果
Map<Integer, Integer> list_memo = new HashMap<Integer, Integer>;
public void list(){
    boolean failed = false;
    int startTokenIndex = index();
    if(isSpeculating() && aleadyParsedRule(list_memo)) return;
	try{_list();}
    catch(Exception e) {failed = true; throw e; }
    finally{
         if(isSpeculating())
             memoize(list_memo, startTokenIndex, failed);
    }
}
public void _list(){
    match(XXX);
    elements();
    match(XXX);
}

简单说明下上面用到的几个方法：

  1. aleadyParsedRule：使用缓存的结果：成功返回TRUE、失败抛异常、未处理过返回FALSE
  2. memoize：回溯时将结果记录到缓存

另外需要清楚一个细节：

推演时没有通过的try-catch逻辑在非推演时更不可能走到！

最后，在遇到上下文相关的语法时使用谓词是个不错的选择，用代码描述就是增加条件：

public void rule(){
    if(向前看符号测试alt1 && 谓词1) {
        // 匹配alt1
    } else if(向前看符号测试alt2 && 谓词2) {
        // 匹配alt2
    } ...
}
while(对循环的alt进行向前看符号判断 && 谓词判断) {
    子规则的代码用来匹配alt
}

到这里解析输入的逻辑基本上就看完了，简单来说：

  1. Lexer产出Token流
  2. Parser产出方法执行流

接下来我们就需要在Parser产出的方法执行流上面来进行分析。

分析输入

将源码结构化时一般用到两种方式：语法分析树和抽象语法树，从三个方面来看：

  1. 紧凑：不含无用节点
  2. 易用：很容易遍历
  3. 显意：突出操作符、操作对象，以及它们互相间的关系，不再拘泥于文法

抽象语法树都要更优秀一些！程序实现时，我们在Parser匹配的过程中向方法中插入一些代码即可得到想要的树形结构：

public void rule(){
    RuleNode r = new RuleNode("规则名");
    if(root == null) root = r;
    else currentNode.addChild(r);
    ParseTree _save = currentNode;
    // 原始的规则代码
    currentNode = _save;
}

要比想象的简单很多，因为在LL的解析中：

解析过程就可以看做是在语法分析树上做DFS，任意当前树节点的父亲必然是前面遍历过的某个节点！

不同实现节点的方式后续树的遍历等都是有影响的，有如下方式：

类型 含义
同型AST 只有一种节点类型AST，要依据TOKEN来区分不同类型
规范异型AST 从基类AST派生不同的节点类型，子节点列表统一
不规范异型AST 可以添加不同的子节点属性，能够让代码的可读性更高

好不容易拿到树形结构了，遍历它也不是一个轻松的活。回想大学用Java写二叉树遍历的时候通常是这样：

public class Node {
    Node left, right;
    void visit(){
        left.visit();
        right.visit();
    }
}

把遍历操作嵌入节点内部最明显的缺点是：逻辑散落在各节点中操作起来很麻烦，可以将遍历操作统一放到一个地方：

public abstract class VecMathNode extends HeteroAST {
    public abstract void visit(VecMathVisitor visitor);
}
public interface VecMathVisitor {
    void visit(AssignNode n);
    void visit(PrintNode n);
    void visit(StatListNode n);
    void visit(VarNode n);
    // ...
}

在实现的时候在Visitor中将this传递就可以达到遍历的目的了：

public class PrintVisitor implements VecMathVisitor {
    public void visit(AssignNode n){
        n.id.visit(this);// 看这里
        System.out.print("=");
        n.value.visit(this);
    }
}

提到外面代码量并没有减少，但是这种代码很有规律，ANTLR可以大幅度地减少你的工作量！当然还有其他的方式来实现相同的目的，这里就不啰嗦了。

遍历语法树的过程中要和两个东西打交道：

  1. 操作
  2. 符号

操作很简单，把子节点收集起来进行计算、处理就行了，但是符号就没那么随意，关键就是作用域：

// 1
int x;
void f(){ // 2
    int y;
    { int i; } // 3
    { int j; } // 4
}
void g(){ // 5
    int i;
}

嵌套的作用域更加容易理解，嵌套关系可以用树形结构来表示（这种作用域的特点是只有一个父节点），上面这段代码生成的作用域如下：

在遍历树的时候用一个栈来保存能访问到的作用域：

在这个过程中用到的操作有：

操作 作用
push 向栈中压入作用域
pop 作用域结束后，要将当前的作用域弹出栈
def 在当前作用域中定义符号
resolve 解析符号

面向过程的变成语言很简单，这些已经够了，但是在面向对象编程的时候就不行了：

// 1 全局
class A {// 2
public :
    int x;
    void foo()// 3
    { ; } // 4
}
class B : public A {// 5
    int y;
    void foo()// 6
    {// 7
        int z =  x + y;
    }
}

由于继承关系的存在，在查找符号的时候不仅是要在当前类中找，而且要去父类中找，也就是说此时的父节点就不止一个了：

对于像a.x = 3这种访问对象属性的行为就不能按照上面套路来了，需要增加一个操作：

操作 作用
resolveMemeber 解析成员，只会根据superClass递归查找

到这里还没完，Java中的Class的定义可以在使用之前，那么在上面的处理属性引用时发现还没定义！直观的解决方法：

预先遍历一次来定义类型。

这里要小心处理好符号和作用域的关系。有了作用域和符号表之后需要对其进行简单的分析：

操作 含义
计算表达式类型 操作的返回结果
自动类型提升 根据操作的对象来决定是否需要对其中低等级的进行提升
静态类型检查 操作的对象类型是否合法
多态类型检查 面向对象中的父子关系

简单来说都是在遍历AST的时候完成的，下面来看如何运行程序~~

解释执行

经过上面这些步骤我们已经知道了源码所要表达的意思，那么就可以用代码来实现其逻辑（也就是解释执行），根据实现方式区分有：

  1. 语法制导解释器：不会生成AST，在解析源码的过程中完成；
  2. 基于树的解释器：先构建AST，在遍历的过程中完成执行；

这两种方式很好理解，用1+2*3的例子玩一玩就可以了，感觉这部分讲的有点啰嗦。用上面的方式执行优点简单、粗暴，缺点是耦合太强了，为了化解便有了：

  1. 字节码汇编器：将便于阅读的汇编语言翻译为二进制形式的字节码指令；
  2. 栈式解释器：执行指令时使用操作数栈存放临时变量；
  3. 寄存器解释器：执行指令时使用虚拟寄存器存放参数、局部变量和临时变量；

用中间指令（也可以理解为原子API）作为过渡，这样以后再有其他的DSL来了，只需要将其翻译为这种中间指令就可以了。

生成输出

要让自己定义的DSL可执行最简单的办法就是将其翻译为现有的一种语言，和各种CC干的差不多：

比如ANTLR就是讲文法翻译为Java代码。

语法制导是最简单的方案，读入内容在解析的过程中完成输出，无法处理前向引用：

而基于规则则是专注于指定一条一条的规则，在匹配到某条规则的时候执行（输出）对应的操作：

工业界普遍流行的是模型驱动翻译，先创建AST，然后在遍历的过程中生成代码：

对于简单的DSL可以使用模板（比如Velocity）来简化输出，但是难点并不在这里。

总结

这本书对于想实现DSL的人来说还是挺有作用的：例子、代码实现，但是想要学习理论的恐怕要失望了，因为这里几乎是没有的。

看到网上有人评价这本书能超过龙书，不知道是从哪里看出来的，类型差别这么大如何比较的？