Straight-Line編程語言的分析和解釋

　　這裡介紹一個極其簡單的編程語言的部分實現即StraightLine編程語言沒有循環和ifelse的結構

　　StraightLine語言的語法(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

    StraightLine語言的語義如下s;s先執行s再執行si := e 計算e的值保存在變量i中print(e e e_n)打印出e e e_n的值用空格隔離結尾換行(Stm Exp)類似C中的逗號表達式先執行Stm為了Stm的Side Effect然後計算Exp返回Exp的值舉個例子
      a := + ; b := (print (a a) *a); print(b)
輸出
       
      

    怎樣在編譯器中表達StraightLine語言的程序呢？StraightLine程序是一個樹狀結構可以用樹狀的數據結構來表示 節點表示程序的不同單元從StraightLine語言的語法我們可以推出怎樣在Java中用類的結構表達StraightLine的程序每個符號對應一個抽象類比如Stm抽象類對應Stm符號每條語法規則用一個具體類的構造函數實現比如CompoundStm的右邊有兩個Stm組成那麼繼承自Stm的CompoundStm的一個構造函數的參數是兩個Stm這兩個Stm保存在CompoundStm的屬性裡

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

class CompoundStm extends Stm {
    Stm stm stm;
    CompoundStm(Stm s Stm s) { stm = s; stm = s; }
}

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 =  Minus =  Times =  Div = ;
    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; }
}

　　上面這幾個Java類描述了StraightLine語言的語法結構使用Parsing的技術可以將a := + ; b := (print (a a) *a); print(b) 這段程序轉化為如下的樹狀結構

Stm testprog = new CompoundStm(new AssignStm(a new OpExp(
            new NumExp() OpExpPlus new NumExp())) new CompoundStm(
            new AssignStm(b new EseqExp(new PrintStm(new PairExpList(
                    new IdExp(a) new LastExpList(new OpExp(new IdExp(a)
                            OpExpMinus new NumExp())))) new OpExp(
                    new NumExp() OpExpTimes new IdExp(a))))
            new PrintStm(new LastExpList(new IdExp(b)))));
    在這裡我要略過Parsing從上面這段樹狀結構開始對StraightLine程序做分析和解釋分析是指分析一個StraightLine程序的屬性比如int maxargs(Stm stm)分析stm中的Print表達式的最大參數個數解釋就是執行一個StraightLine程序下面我們來實現maxargs和StraightLine程序的一個解釋器我們采用一種沒有Side Effect的實現方式也就是變量和對象屬性除了在構造時不能改變對局部變量用定義時即賦值的方式

首先是maxargs我們先寫測試代碼

package tigerslpl;

import junitframeworkTestCase;

public class TestCountMaxPrintStmArgs extends TestCase {

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

    public void testMaxargs() {
        CountMaxPrintStmArgs counter = new CountMaxPrintStmArgs();
        assertEquals( countermaxargs(TestProgtestprog));
    }
}

TestProgtestprog即是上面給出的程序print表達式參數個數的最大值是 現在實現maxargs


package tigerslpl;

import static javalangMathmax;

/**
 * This Interpreter is too in functional style<br>
 *         no assignment<br>
 *         definition with initialization<br> 
 *             <code>int i = ;</code> 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 eg Stm
     */
    private int _maxargs(Stm stm) {
        if (stm instanceof CompoundStm) {
            CompoundStm cstm = (CompoundStm) stm;
            return max(_maxargs(cstmstm) _maxargs(cstmstm));
        } else if (stm instanceof AssignStm) {
            AssignStm astm = (AssignStm) stm;
            return _maxargs(astmexp);
        } else { // Then it can be only PrintStm
            PrintStm pstm = (PrintStm) stm;
            return max(countargs(pstmexps) _maxargs(pstmexps));
        }
    }

    private int _maxargs(ExpList exps) {
        if (exps instanceof PairExpList) {
            PairExpList pexps = (PairExpList) exps;
            return max(_maxargs(pexpshead) _maxargs(pexpstail));
        } else { // Then it can be LastExpList
            LastExpList lexps = (LastExpList) exps;
            return _maxargs(lexpsexp);
        }
    }

    private int _maxargs(Exp exp) {
        if (exp instanceof IdExp)
            return ;
        else if (exp instanceof NumExp)
            return ;
        else if (exp instanceof OpExp) {
            OpExp oexp = (OpExp) exp;
            return max(_maxargs(oexpleft) _maxargs(oexpright));
        } else { // Then it can be EseqExp
            EseqExp eexp = (EseqExp) exp;
            return max(_maxargs(eexpstm) _maxargs(eexpexp));
        }
    }

    private int countargs(ExpList exps) {
        if (exps instanceof LastExpList)
            return ;
        else { // Then it is a PairExpList
            PairExpList pexps = (PairExpList) exps;
            return  + countargs(pexpstail);
        }
    }
}
    這裡解釋一下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放在各自的類下比如CompoundStmmaxargs計算一個CompoundStm的maxargs這種方式的一個缺點是將分析算法放在模型結構類中如果有很多種分析要做模型類就比較混亂可以使用Visitor設計模式對不同的算法定義不同的Visitor類兼顧前面兩種方式的優點當然這是一篇有關編譯技術的隨筆代碼采用最容易理解的實現方式

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26757.html