這里介紹一個(gè)極其簡單的編程語言的部分實(shí)現(xiàn)，即Straight-Line編程語言，沒有循環(huán)和if-else的結(jié)構(gòu)。
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
1;s
2先執(zhí)行s
1，再執(zhí)行s
2。i := e, 計(jì)算e的值，保存在變量i中。print(e
1, e
2, ..., e
n)打印出e
1, e
2, ..., e
n的值，用空格隔離，結(jié)尾換行。(Stm, Exp)類似C中的逗號(hào)表達(dá)式，先執(zhí)行Stm，為了Stm的Side Effect，然后計(jì)算Exp，返回Exp的值。舉個(gè)例子，
a := 5 + 3; b := (print (a, a-1), 10*a); print(b)
輸出
8 7
80
怎樣在編譯器中表達(dá)Straight-Line語言的程序呢？Straight-Line程序是一個(gè)樹狀結(jié)構(gòu)，可以用樹狀的數(shù)據(jù)結(jié)構(gòu)來表示, 節(jié)點(diǎn)表示程序的不同單元。從Straight-Line語言的語法我們可以推出怎樣在Java中用類的結(jié)構(gòu)表達(dá)Straight-Line的程序。每個(gè)符號(hào)對(duì)應(yīng)一個(gè)抽象類，比如Stm抽象類對(duì)應(yīng)Stm符號(hào)。每條語法規(guī)則用一個(gè)具體類的構(gòu)造函數(shù)實(shí)現(xiàn)。比如CompoundStm的右邊有兩個(gè)Stm組成，那么繼承自Stm的CompoundStm的一個(gè)構(gòu)造函數(shù)的參數(shù)是兩個(gè)Stm。這兩個(gè)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; }
}
上面這幾個(gè)Java類描述了Straight-Line語言
的語法結(jié)構(gòu)。使用Parsing的技術(shù)可以將a := 5 + 3; b := (print (a, a-1), 10*a); print(b)
這段程序轉(zhuǎn)化為如下的樹狀結(jié)構(gòu)
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，從上面這段樹狀結(jié)構(gòu)開始，對(duì)Straight-Line程序做分析和解釋。分析是指分析一個(gè)Straight-Line程序的屬性，比如int maxargs(Stm stm)分析stm中的Print表達(dá)式的最大參數(shù)個(gè)數(shù)。解釋就是執(zhí)行一個(gè)Straight-Line程序。下面我們來實(shí)現(xiàn)maxargs和Straight-Line程序的一個(gè)解釋器。我們采用一種沒有Side Effect的實(shí)現(xiàn)方式，也就是變量和對(duì)象屬性除了在構(gòu)造時(shí)不能改變，對(duì)局部變量用定義時(shí)即賦值的方式。
首先是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表達(dá)式參數(shù)個(gè)數(shù)的最大值是2. 現(xiàn)在實(shí)現(xiàn)maxargs。
package tiger.slpl;
import static java.lang.Math.max;
/**
* This Interpreter is too in functional style.<br>
* no assignment<br>
* definition with initialization<br>
* <code>int i = 1;</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 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)。一個(gè)Stm可以是CompoundStm, AssignStm或者PrintStm。如果是CompoundStm，那么_maxargs(Stm stm)等于stm下兩個(gè)子Stm的maxargs的較大值。如果是AssignStm，等于AssignStm的表達(dá)式的maxargs。如果是PrintStm，那么是PrintStm的參數(shù)個(gè)數(shù)(countargs數(shù)PrintStm的參數(shù)個(gè)數(shù))，或者ExpList的maxargs，看哪個(gè)更大。其他的函數(shù)的解釋也是類似的，對(duì)照Straight Line語言的語法不難理解。
上面的maxargs的實(shí)現(xiàn)中用了很多instanceof，另外的一種實(shí)現(xiàn)方式可以把各個(gè)maxargs放在各自的類下，比如CompoundStm.maxargs計(jì)算一個(gè)CompoundStm的maxargs。這種方式的一個(gè)缺點(diǎn)是，將分析算法放在模型結(jié)構(gòu)類中。如果有很多種分析要做，模型類就比較混亂。可以使用Visitor設(shè)計(jì)模式，對(duì)不同的算法定義不同的Visitor類，兼顧前面兩種方式的優(yōu)點(diǎn)。當(dāng)然這是一篇有關(guān)編譯技術(shù)的隨筆，代碼采用最容易理解的實(shí)現(xiàn)方式。
下一篇來介紹如何解釋Straight Line語言的程序。
轉(zhuǎn)載請(qǐng)保留
http://www.aygfsteel.com/xilaile/archive/2007/05/13/117159.html