這里介紹一個(gè)極其簡(jiǎn)單的編程語(yǔ)言的部分實(shí)現(xiàn)，即Straight-Line編程語(yǔ)言，沒(méi)有循環(huán)和if-else的結(jié)構(gòu)。
Straight-Line語(yǔ)言的語(yǔ)法(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語(yǔ)言的語(yǔ)義如下，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)類(lèi)似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語(yǔ)言的程序呢？Straight-Line程序是一個(gè)樹(shù)狀結(jié)構(gòu)，可以用樹(shù)狀的數(shù)據(jù)結(jié)構(gòu)來(lái)表示, 節(jié)點(diǎn)表示程序的不同單元。從Straight-Line語(yǔ)言的語(yǔ)法我們可以推出怎樣在Java中用類(lèi)的結(jié)構(gòu)表達(dá)Straight-Line的程序。每個(gè)符號(hào)對(duì)應(yīng)一個(gè)抽象類(lèi)，比如Stm抽象類(lèi)對(duì)應(yīng)Stm符號(hào)。每條語(yǔ)法規(guī)則用一個(gè)具體類(lèi)的構(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類(lèi)描述了Straight-Line語(yǔ)言
的語(yǔ)法結(jié)構(gòu)。使用Parsing的技術(shù)可以將a := 5 + 3; b := (print (a, a-1), 10*a); print(b)
這段程序轉(zhuǎn)化為如下的樹(shù)狀結(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")))));
在這里，我要略過(guò)Parsing，從上面這段樹(shù)狀結(jié)構(gòu)開(kāi)始，對(duì)Straight-Line程序做分析和解釋。分析是指分析一個(gè)Straight-Line程序的屬性，比如int maxargs(Stm stm)分析stm中的Print表達(dá)式的最大參數(shù)個(gè)數(shù)。解釋就是執(zhí)行一個(gè)Straight-Line程序。下面我們來(lái)實(shí)現(xiàn)maxargs和Straight-Line程序的一個(gè)解釋器。我們采用一種沒(méi)有Side Effect的實(shí)現(xiàn)方式，也就是變量和對(duì)象屬性除了在構(gòu)造時(shí)不能改變，對(duì)局部變量用定義時(shí)即賦值的方式。
首先是maxargs。我們先寫(xiě)測(cè)試代碼。
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ù)的解釋也是類(lèi)似的，對(duì)照Straight Line語(yǔ)言的語(yǔ)法不難理解。
上面的maxargs的實(shí)現(xiàn)中用了很多instanceof，另外的一種實(shí)現(xiàn)方式可以把各個(gè)maxargs放在各自的類(lèi)下，比如CompoundStm.maxargs計(jì)算一個(gè)CompoundStm的maxargs。這種方式的一個(gè)缺點(diǎn)是，將分析算法放在模型結(jié)構(gòu)類(lèi)中。如果有很多種分析要做，模型類(lèi)就比較混亂。可以使用Visitor設(shè)計(jì)模式，對(duì)不同的算法定義不同的Visitor類(lèi)，兼顧前面兩種方式的優(yōu)點(diǎn)。當(dāng)然這是一篇有關(guān)編譯技術(shù)的隨筆，代碼采用最容易理解的實(shí)現(xiàn)方式。
下一篇來(lái)介紹如何解釋Straight Line語(yǔ)言的程序。
轉(zhuǎn)載請(qǐng)保留
http://www.aygfsteel.com/xilaile/archive/2007/05/13/117159.html