|
这里介绍一个极其简单的编程语言的部分实现即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 en)打印出e e en的值用空格隔离结尾换行(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的属性里 abstractclassStm{} abstractclassExp{} abstractclassExpList{} classCompoundStmextendsStm{ Stmstmstm; CompoundStm(StmsStms){stm=s;stm=s;} } classAssignStmextendsStm{ Stringid;Expexp; AssignStm(StringiExpe){id=i;exp=e;} } classPrintStmextendsStm{ ExpListexps; PrintStm(ExpListe){exps=e;} } classPairExpListextendsExpList{ Exphead;ExpListtail; PairExpList(ExphExpListt){head=h;tail=t;} } classLastExpListextendsExpList{ Expexp; LastExpList(Expe){exp=e;} } classIdExpextendsExp{ Stringid; IdExp(Stringi){id=i;} } classNumExpextendsExp{ intnum; NumExp(intn){num=n;} } classOpExpextendsExp{ finalstaticintPlus=Minus=Times=Div=; Expleftright; intoper; OpExp(ExplintoExpr){left=l;oper=o;right=r;} } classEseqExpextendsExp{ Stmstm;Expexp; EseqExp(StmsExpe){stm=s;exp=e;} } 上面这几个Java类描述了StraightLine语言的语法结构使用Parsing的技术可以将a := + ; b := (print (a a) *a); print(b) 这段程序转化为如下的树状结构 Stmtestprog=newCompoundStm(newAssignStm(anewOpExp( newNumExp()OpExpPlusnewNumExp()))newCompoundStm( newAssignStm(bnewEseqExp(newPrintStm(newPairExpList( newIdExp(a)newLastExpList(newOpExp(newIdExp(a) OpExpMinusnewNumExp()))))newOpExp( newNumExp()OpExpTimesnewIdExp(a)))) newPrintStm(newLastExpList(newIdExp(b))))); 在这里我要略过Parsing从上面这段树状结构开始对StraightLine程序做分析和解释分析是指分析一个StraightLine程序的属性比如int maxargs(Stm stm)分析stm中的Print表达式的最大参数个数解释就是执行一个StraightLine程序下面我们来实现maxargs和StraightLine程序的一个解释器我们采用一种没有Side Effect的实现方式也就是变量和对象属性除了在构造时不能改变对局部变量用定义时即赋值的方式 首先是maxargs我们先写测试代码 packagetigerslpl; importjunitframeworkTestCase; publicclassTestCountMaxPrintStmArgsextendsTestCase{ publicTestCountMaxPrintStmArgs(Stringm){ super(m); } publicvoidtestMaxargs(){ CountMaxPrintStmArgscounter=newCountMaxPrintStmArgs(); assertEquals(countermaxargs(TestProgtestprog)); } } TestProgtestprog即是上面给出的程序print表达式参数个数的最大值是 现在实现maxargs packagetigerslpl; importstaticjavalangMathmax; /** *ThisInterpreteristooinfunctionalstyle<br> *noassignment<br> *definitionwithinitialization<br> *<code>inti=;</code>introducesanewvariable * *@authorpan */ classCountMaxPrintStmArgs{ /** *EntryPoint */ intmaxargs(Stmstm){ return_maxargs(stm); } /* *BecauseExpListcanoccursonlyforPrintStm *ThatisthesametocountlengthofExpList *buthereIuseanotherapproachtocountonlyfor *PrintStm * *ifyouwanttoavoidinstanceofthenyoucan *packmaxargsmethodsinclassesegStm */ privateint_maxargs(Stmstm){ if(stminstanceofCompoundStm){ CompoundStmcstm=(CompoundStm)stm; returnmax(_maxargs(cstmstm)_maxargs(cstmstm)); }elseif(stminstanceofAssignStm){ AssignStmastm=(AssignStm)stm; return_maxargs(astmexp); }else{//ThenitcanbeonlyPrintStm PrintStmpstm=(PrintStm)stm; returnmax(countargs(pstmexps)_maxargs(pstmexps)); } } privateint_maxargs(ExpListexps){ if(expsinstanceofPairExpList){ PairExpListpexps=(PairExpList)exps; returnmax(_maxargs(pexpshead)_maxargs(pexpstail)); }else{//ThenitcanbeLastExpList LastExpListlexps=(LastExpList)exps; return_maxargs(lexpsexp); } } privateint_maxargs(Expexp){ if(expinstanceofIdExp) return; elseif(expinstanceofNumExp) return; elseif(expinstanceofOpExp){ OpExpoexp=(OpExp)exp; returnmax(_maxargs(oexpleft)_maxargs(oexpright)); }else{//ThenitcanbeEseqExp EseqExpeexp=(EseqExp)exp; returnmax(_maxargs(eexpstm)_maxargs(eexpexp)); } } privateintcountargs(ExpListexps){ if(expsinstanceofLastExpList) return; else{//ThenitisaPairExpList PairExpListpexps=(PairExpList)exps; return+countargs(pexpstail); } } } 这里解释一下int _maxargs(Stmstm)一个Stm可以是CompoundStm AssignStm或者PrintStm如果是CompoundStm那么_maxargs(Stmstm)等于stm下两个子Stm的maxargs的较大值如果是AssignStm等于AssignStm的表达式的maxargs如果是PrintStm那么是PrintStm的参数个数(countargs数PrintStm的参数个数)或者ExpList的maxargs看哪个更大其他的函数的解释也是类似的对照Straight Line语言的语法不难理解 上面的maxargs的实现中用了很多instanceof另外的一种实现方式可以把各个maxargs放在各自的类下比如CompoundStmmaxargs计算一个CompoundStm的maxargs这种方式的一个缺点是将分析算法放在模型结构类中如果有很多种分析要做模型类就比较混乱可以使用Visitor设计模式对不同的算法定义不同的Visitor类兼顾前面两种方式的优点当然这是一篇有关编译技术的随笔代码采用最容易理解的实现方式 |
