Straight-Line编程语言的分析和解释

    这里介绍一个极其简单的编程语言的部分实现，即Straight-Line编程语言，没有循环和if-else的结构。

Straight-Line语言的语法(Grammar)

Stm ::= Stm; Stm	CompoundStm
Stm ::= id := Exp	AssignStm
Stm ::= print(ExpList)	PrintStm
ExpList ::= Exp, ExpList	PairExpList
ExpList ::= Exp	LastExpList
Exp ::= id	IdExp
Exp ::= num	NumExp
Exp ::= Exp Binop Exp	OpExp
Exp ::= (Stm, Exp)	EseqExp
Binop::= + | - | * | /	Arithmetic Operators

    Straight-Line语言的语义如下，s₁;s₂先执行s₁，再执行s₂。i := e, 计算e的值，保存在变量i中。print(e₁, e₂, ..., e_n)打印出e₁, e₂, ..., e_n的值，用空格隔离，结尾换行。(Stm, Exp)类似C中的逗号表达式，先执行Stm，为了Stm的Side Effect，然后计算Exp，返回Exp的值。举个例子，
      a := 5 + 3; b := (print (a, a-1), 10*a); print(b)
输出
      8  7
      80

    怎样在编译器中表达Straight-Line语言的程序呢？Straight-Line程序是一个树状结构，可以用树状的数据结构来表示, 节点表示程序的不同单元。从Straight-Line语言的语法我们可以推出怎样在中用类的结构表达Straight-Line的程序。每个符号对应一个抽象类，比如Stm抽象类对应Stm符号。每条语法规则用一个具体类的构造函数实现。比如CompoundStm的右边有两个Stm组成，那么继承自Stm的CompoundStm的一个构造函数的参数是两个Stm。这两个Stm保存在CompoundStm的属性里。

abstract class Stm {}
abstract class Exp {}
abstract class ExpList {}

class CompoundStm extends Stm {
    Stm stm1, stm2;
    CompoundStm(Stm s1, Stm s2) { stm1 = s1; stm2 = s2; }
}

class AssignStm extends Stm {
    String id; Exp exp;
    AssignStm(String i, Exp e) { id = i; exp = e; }
}

class PrintStm extends Stm {
    ExpList exps;
    PrintStm(ExpList e) { exps = e; }
}

class PairExpList extends ExpList {
    Exp head; ExpList tail;
    PairExpList(Exp h, ExpList t) { head = h; tail = t; }
}

class LastExpList extends ExpList {
    Exp exp;
    LastExpList(Exp e) { exp = e; }
}

class IdExp extends Exp {
    String id;
    IdExp(String i) { id = i; }
}

class NumExp extends Exp {
    int num;
    NumExp(int n) { num = n; }
}

class OpExp extends Exp {
    final static int Plus = 1, Minus = 2, Times = 3, Div = 4;
    Exp left, right; 
    int oper;

    OpExp(Exp l, int o, Exp r) { left = l; oper = o; right = r; }
}

class EseqExp extends Exp {
    Stm stm; Exp exp;
    EseqExp(Stm s, Exp e) { stm = s; exp = e; }
}

    上面这几个类描述了Straight-Line语言的语法结构。使用Parsing的技术可以将a := 5 + 3; b := (print (a, a-1), 10*a); print(b) 这段程序转化为如下的树状结构

Stm testprog = new CompoundStm(new AssignStm("a", new OpExp(
            new NumExp(5), OpExp.Plus, new NumExp(3))), new CompoundStm(
            new AssignStm("b", new EseqExp(new PrintStm(new PairExpList(
                    new IdExp("a"), new LastExpList(new OpExp(new IdExp("a"),
                            OpExp.Minus, new NumExp(1))))), new OpExp(
                    new NumExp(10), OpExp.Times, new IdExp("a")))),
            new PrintStm(new LastExpList(new IdExp("b")))));

    在这里，我要略过Parsing，从上面这段树状结构开始，对Straight-Line程序做分析和解释。分析是指分析一个Straight-Line程序的属性，比如int maxargs(Stm stm)分析stm中的Print表达式的最大参数个数。解释就是执行一个Straight-Line程序。下面我们来实现maxargs和Straight-Line程序的一个解释器。我们采用一种没有Side Effect的实现方式，也就是变量和对象属性除了在构造时不能改变，对局部变量用定义时即赋值的方式。

首先是maxargs。我们先写测试代码。

package tiger.slpl;

import junit.framework.TestCase;

public class TestCountMaxPrintStmArgs extends TestCase {

    public TestCountMaxPrintStmArgs(String m) {
        super(m);
    }

    public void testMaxargs() {
        CountMaxPrintStmArgs counter = new CountMaxPrintStmArgs();
        assertEquals(2, counter.maxargs(TestProg.testprog));
    }
}

TestProg.testprog即是上面给出的程序，print表达式参数个数的最大值是2. 现在实现maxargs。

package tiger.slpl;

import static java.lang.Math.max;

/**
 * This Interpreter is too in functional style.

 *         no assignment

 *         definition with initialization
 
 *             int i = 1; introduces a new variable 
 * 
 * @author pan
 */
class CountMaxPrintStmArgs {

    /**
     * Entry Point
     */
    int maxargs(Stm stm) {
        return _maxargs(stm);
    }

    /*
     * Because ExpList can occurs only for PrintStm.
     * That is the same to count length of ExpList
     * but here I use another approach to count only for
     * PrintStm
     * 
     * if you want to avoid instanceof, then you can
     * pack maxargs methods in classes e.g. Stm
     */
    private int _maxargs(Stm stm) {
        if (stm instanceof CompoundStm) {
            CompoundStm cstm = (CompoundStm) stm;
            return max(_maxargs(cstm.stm1), _maxargs(cstm.stm2));
        } else if (stm instanceof AssignStm) {
            AssignStm astm = (AssignStm) stm;
            return _maxargs(astm.exp);
        } else { // Then it can be only PrintStm
            PrintStm pstm = (PrintStm) stm;
            return max(countargs(pstm.exps), _maxargs(pstm.exps));
        }
    }

    private int _maxargs(ExpList exps) {
        if (exps instanceof PairExpList) {
            PairExpList pexps = (PairExpList) exps;
            return max(_maxargs(pexps.head), _maxargs(pexps.tail));
        } else { // Then it can be LastExpList
            LastExpList lexps = (LastExpList) exps;
            return _maxargs(lexps.exp);
        }
    }

    private int _maxargs(Exp exp) {
        if (exp instanceof IdExp)
            return 0;
        else if (exp instanceof NumExp)
            return 0;
        else if (exp instanceof OpExp) {
            OpExp oexp = (OpExp) exp;
            return max(_maxargs(oexp.left), _maxargs(oexp.right));
        } else { // Then it can be EseqExp
            EseqExp eexp = (EseqExp) exp;
            return max(_maxargs(eexp.stm), _maxargs(eexp.exp));
        }
    }

    private int countargs(ExpList exps) {
        if (exps instanceof LastExpList)
            return 1;
        else { // Then it is a PairExpList
            PairExpList pexps = (PairExpList) exps;
            return 1 + countargs(pexps.tail);
        }
    }
}

    这里解释一下int _maxargs(Stm stm)。一个Stm可以是CompoundStm, AssignStm或者PrintStm。如果是CompoundStm，那么_maxargs(Stm stm)等于stm下两个子Stm的maxargs的较大值。如果是AssignStm，等于AssignStm的表达式的maxargs。如果是PrintStm，那么是PrintStm的参数个数(countargs数PrintStm的参数个数)，或者ExpList的maxargs，看哪个更大。其他的函数的解释也是类似的，对照Straight Line语言的语法不难理解。

    上面的maxargs的实现中用了很多instanceof，另外的一种实现方式可以把各个maxargs放在各自的类下，比如CompoundStm.maxargs计算一个CompoundStm的maxargs。这种方式的一个缺点是，将分析算法放在模型结构类中。如果有很多种分析要做，模型类就比较混乱。可以使用Visitor设计模式，对不同的算法定义不同的Visitor类，兼顾前面两种方式的优点。当然这是一篇有关编译技术的随笔，代码采用最容易理解的实现方式。

【责编:Youping】

--------------------next---------------------
package tiger.slpl;

import static java.lang.Math.max;

/**
 * This Interpreter is too in functional style.

 *         no assignment

 *         definition with initialization
 
 *             int i = 1; introduces a new variable 
 * 
 * @author pan
 */
class CountMaxPrintStmArgs {

    /**
     * Entry Point
     */
    int maxargs(Stm stm) {
        return _maxargs(stm);
    }

    /*
     * Because ExpList can occurs only for PrintStm.
     * That is the same to count length of ExpList
     * but here I use another approach to count only for
     * PrintStm
     * 
     * if you want to avoid instanceof, then you can
     * pack maxargs methods in classes e.g. Stm
     */
    private int _maxargs(Stm stm) {
        if (stm instanceof CompoundStm) {
            CompoundStm cstm = (CompoundStm) stm;
            return max(_maxargs(cstm.stm1), _maxargs(cstm.stm2));
        } else if (stm instanceof AssignStm) {
            AssignStm astm = (AssignStm) stm;
            return _maxargs(astm.exp);
        } else { // Then it can be only PrintStm
            PrintStm pstm = (PrintStm) stm;
            return max(countargs(pstm.exps), _maxargs(pstm.exps));
        }
    }

    private int _maxargs(ExpList exps) {
        if (exps instanceof PairExpList) {
            PairExpList pexps = (PairExpList) exps;
            return max(_maxargs(pexps.head), _maxargs(pexps.tail));
        } else { // Then it can be LastExpList
            LastExpList lexps = (LastExpList) exps;
            return _maxargs(lexps.exp);
        }
    }

    private int _maxargs(Exp exp) {
        if (exp instanceof IdExp)
            return 0;
        else if (exp instanceof NumExp)
            return 0;
        else if (exp instanceof OpExp) {
            OpExp oexp = (OpExp) exp;
            return max(_maxargs(oexp.left), _maxargs(oexp.right));
        } else { // Then it can be EseqExp
            EseqExp eexp = (EseqExp) exp;
            return max(_maxargs(eexp.stm), _maxargs(eexp.exp));
        }
    }

    private int countargs(ExpList exps) {
        if (exps instanceof LastExpList)
            return 1;
        else { // Then it is a PairExpList
            PairExpList pexps = (PairExpList) exps;
            return 1 + countargs(pexps.tail);
        }
    }
}
--------------------next---------------------