My favorites | Sign in
Project Home Downloads Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
IterpreterPatternDesign  

Featured, Phase-Design
Updated Mar 21, 2013 by pin...@gmail.com

#InterpreterPatternDesign 解释器模式的实现

Introduction

使用OOC-GCC完成简单解释器的设计

假定要设计一个非常简单的解释器[这个例子出自良葛格的学习笔记,至少我最早是在他那里看到的,因为简单所以就用了],这个解释器不干别的,仅仅是按照一定的格式输出一定的字符.
比如,

  PROGRAM 
    REPEAT 2 
        LINEBREAK 
        PRINT dog 
        BREAK 
    END 
  END
这个里面出现了PROGRAM,REPEAT,NUMBER,LINEBREAK,PRINT,STRING,BREAK,END等字符. 并规定PROGRAM用来定义一个程序,REPEAT用来定一个反复执行n次的代码块,LINEBREAK和BREAK用来输出不同形式的换行,PRINT用来输出指定的字符.如果BREAK输出的是换行,而LINEBREAK输出的是一段"----"和一个换行,那么其输出结果类似,
------------------------------ 
 dog 
------------------------------ 
 dog
为了方便再假定一个SPACE用来输出一个空格. 恩,假定就这么多吧,因为这样足够简单,每个指令只需要通过空白来区分.当然简单是有代价的,这样的程序似乎毫无实际意义.
实现一个解释器的第一步(如果分布的话)就是把字符串(代码)按照一定的格式分离出来,形成一个一个可识别的标识.而在这之后就是把这些标识按照一定的规则解析成一定的数据结构(特定的树或是广义表之类的),最后再通过一定顺序访问这一结构中存储的数据完成程序的"执行".

提取标识的部分个人感觉并不算是解释器模式的内容,而上面的定义的语法又比较简单只需要按空白(' ','\t','\n'等等)区分并提取就可以了. 解释器模式主要就是解决后两部分的.每一个使用该模式的类具备一个parse和一个execute方法,parse用来构造类树的结构,execute则负责具体的执行.

总结下其文法有

<program> ::= PROGRAM <command list> 
<command list> ::= <command>* END 
<command> ::= <repeat> | <primitive> 
<repeat> ::= REPEAT <number> <command list> 
<primitive> ::= PRINT <string> | BREAK | SPACE | LINEBREAK

从文法来说也就是要声明和program,command list,command,repeat,primitive相关的5个类,并且都具备parse和execute方法. 具体来说, 比如对于相对高层的program类,其要具备一个command list元素, 在parse的时候只需去执行其包含command list的parse方法, 在execute的时候只需去执行其包含command list的execute方法. 而相对底层的primitive类要 包含两个字符串元素,一个用来存放parse到的具体指令名,另一个用来存放输出的string 在parse的时候讲上面的说的两个字符串存储起来, 在execute的时候根据第一个字符串按一定格式输出第二个字符串.

注意在command list类中有一个*符号,这意味着其存储多个command 这需要一个专门的但并不复杂的数据结构的辅助,比如链或堆栈什么的都是可以的.

Details

CLASS(Stack){
        unsigned int len;
        void **data;
        unsigned int size;
        STATIC(Stack);
            tFn push;
            vPtFn at;
};
#include "stack.h"
#undef T
#undef T_DATA
#define T Stack
#define T_DATA void *

static size_t Stack_needExpand(T* self,unsigned int want){
        if(want==0) want=1;
        if(self->len*sizeof(T_DATA)+want*sizeof(T_DATA)>self->size){
                return 1;
        }
        return 0;
}
static size_t Stack_expand(T* self,unsigned int want){
        void * alloc=NULL;
        if(want==0) want=self->size-self->len*sizeof(T_DATA)/2;

        if(self->size==0) {
                alloc=ALLOC((want)*2);
                if(alloc==NULL) return (-1);
                self->data=alloc;
                self->size=(want)*2;
                return 0;
        }
        alloc=REALLOC(self->data,self->size+(want));
        if(alloc==NULL) return (-1);
        self->data=alloc;
        self->size+=want*sizeof(T_DATA);
        return 1;
}

static size_t Stack_autoExpand(T* self,unsigned int want){
        if(Stack_needExpand(self,want)==1){
                if(Stack_expand(self,want)==(-1)){
                        return (-1);
                }
        }
        return 0;
}

static int Stack_push(Stack *self,void *value){
        if(Stack_autoExpand(self,8)<0) return (-1);
        *(T_DATA *)(((unsigned char *)self->data)+sizeof(T_DATA)*self->len)=value;
    self->len++;
        return 0;
}
static void* Stack_at(Stack *self,unsigned int offset){
        return *(T_DATA *)(((unsigned char *)self->data)+sizeof(T_DATA)*offset);
}
static size_t StStack_reload(StStack *self,void *p){
        self->push=(void *)Stack_push;
        self->at=(void *)Stack_at;
        return 0;
}

static size_t Stack_unload(Stack *self,void *p){
        unsigned int i=0;
        void * at=NULL;
        if(self->data==NULL) return 0;
        if(p!=NULL){
                for(i=0;i<self->len;i++){
                        at=Stack_at(self,i);
                        FREE(at);
                }
        }else{
                for(i=0;i<self->len;i++){
                        at=Stack_at(self,i);
                        if(DELETE0(at)<0) return (-1);
                }
        }
        FREE(self->data);
        return 0;
}

ASM(Stack,NULL,Stack_unload,StStack_reload,NULL)
而前文所述的几个和文法相关的类定义如下,
CLASS(Node) {
        STATIC(Node);
        vFn parse,execute;
};
CLASS(Program){
        Node * commandList;
        STATIC_EX(Program,Node);
};
CLASS(CommandList){
        Stack *commands;
        STATIC_EX(CommandList,Node);
};
CLASS(Command){
        Node * node;
        STATIC_EX(Command,Node);
};
CLASS(Primitive){
        char *name,*text;
        STATIC_EX(Primitive,Node);
};
CLASS(Repeat){
        int number;
        Node * commandList;
        STATIC_EX(Repeat,Node);
};
CLASS(Context){
        Stack * tokens;
        char *tokenPt;
        int tokenId;
        STATIC(Context);
        vFn skipToken;
        iFn currentNumber;
        cPtFn nextToken,currentToken;
};
static StStack * stack=NULL;
#define ND(var) ((StNode*)ST(var))
#define CT(var) ((StContext*)ST(var))

//////////////////////////////////////////////
static void Program_parse(Program *self,Context *context){
        CT(context)->skipToken(context,"PROGRAM");
        ND(self->commandList)->parse(self->commandList,context);
}
static void Program_execute(Program *self){
        ((StNode*)ST(self->commandList))->execute(self->commandList);
}
static size_t Program_reload(Program *self,void *p){
        ND(self)->parse=(void *)Program_parse;
        ND(self)->execute=(void *)Program_execute;
        self->commandList=NEW0(CommandList);
        return 0;
}
static size_t Program_unload(Program *self,void *p){
        return DELETE0(self->commandList);
}
ASM(Program,Program_reload,Program_unload,NULL,NULL)
//////////////////////////////////////////////
static void CommandList_parse(CommandList *self,Context *context){//printf("%s!!!\n",__FUNCTION__);
        while (1) {
                if(((StContext*)ST(context))->currentToken(context) == NULL) {
                        printf("Missing 'END'\n");
                        break;
                }else if(!strcmp(CT(context)->currentToken(context),"END")) {
                        CT(context)->skipToken(context,"END");
                        break;
                }else {
                        Command * command=NEW0(Command) ;
                        ND(command)->parse(command,context);
                        stack->push(self->commands,command);
                }
        }
}
static void CommandList_execute(CommandList *self){//printf("%s!!!\n",__FUNCTION__);
        Command *command=NULL;
        unsigned int i=0;
        for(i=0;i<self->commands->len;i++){
                command=stack->at(self->commands,i);
                ND(command->node)->execute(command->node);
        }
}
static size_t CommandList_reload(CommandList *self,void *p){//printf("%s!!!\n",__FUNCTION__);
        self->commands=NEW0(Stack);
        ND(self)->parse=(void *)CommandList_parse;
        ND(self)->execute=(void *)CommandList_execute;
        return 0;
}
static size_t CommandList_unload(CommandList *self,void *p){//printf("%s!!!\n",__FUNCTION__);
        return DELETE0(self->commands);
}

ASM(CommandList,CommandList_reload,CommandList_unload,NULL,NULL)

//////////////////////////////////////////////
static void Command_parse(Command *self,Context *context){
        if(!strcmp(CT(context)->currentToken(context),"REPEAT")){
                self->node=NEW0(Repeat);
        }else{
                self->node=NEW0(Primitive);
        }
        ((StNode*)ST(self->node))->parse(self->node,context);
}
static void Command_execute(Command *self){
        ND(self->node)->execute(self);
}
static size_t Command_reload(Command *self,void *p){
        ND(self)->parse=(void *)Command_parse;
        ND(self)->execute=(void *)Command_execute;
        return 0;
}
static size_t Command_unload(Command *self,void *p){
        if(self->node!=NULL) return DELETE0(self->node);
        return 0;
}
ASM(Command,Command_reload,Command_unload,NULL,NULL)
//////////////////////////////////////////////
static void Primitive_parse(Primitive *self,Context *context){//printf("%s!!!\n",__FUNCTION__);
        self->name=CT(context)->currentToken(context);
        CT(context)->skipToken(context,self->name);
        if(!(	!strcmp(self->name,"PRINT")||
                        !strcmp(self->name,"BREAK")||
                        !strcmp(self->name,"LINEBREAK")||
                        !strcmp(self->name,"SPACE")	)){
                printf("%s ERROR!\n",__FUNCTION__);
        }
        if(!strcmp(self->name,"PRINT")){
                self->text=CT(context)->currentToken(context);
                CT(context)->nextToken(context);
        }
}

static void Primitive_execute(Primitive *self){
        if(!strcmp(self->name,"PRINT")) printf("%s",self->text);
        else if(!strcmp(self->name,"SPACE")) printf(" ");
        else if(!strcmp(self->name,"BREAK")) printf("\n");
        else if(!strcmp(self->name,"LINEBREAK")) printf("\n-----------\n");
        else printf("%s ERROR!\n",__FUNCTION__);
}
static size_t Primitive_reload(Primitive *self,void *p){
        ND(self)->parse=(void *)Primitive_parse;
        ND(self)->execute=(void *)Primitive_execute;
        return 0;
}
ASM(Primitive,Primitive_reload,NULL,NULL,NULL)

//////////////////////////////////////////////

static void Repeat_parse(Repeat *self,Context *context){
        CT(context)->skipToken(context,"REPEAT");
        self->number=CT(context)->currentNumber(context);
        CT(context)->nextToken(context);
        ND(self->commandList)->parse(self->commandList,context);
}
static void Repeat_execute(Repeat *self){
        unsigned int i=0;
        for(i=0;i<self->number;i++){
                ND(self->commandList)->execute(self->commandList);
        }
}
static size_t Repeat_reload(Repeat *self,void *p){
        ND(self)->parse=(void *)Repeat_parse;
        ND(self)->execute=(void *)Repeat_execute;
        self->commandList=NEW0(CommandList);
        return 0;
}
static size_t Repeat_unload(Repeat *self,void *p){
        return DELETE0(self->commandList);
}
ASM(Repeat,Repeat_reload,Repeat_unload,NULL,NULL)
//////////////////////////////////////////////
static char * Context_nextToken(Context *self){//printf("%s!!!\n",__FUNCTION__);

        self->tokenPt=NULL;
        if((self->tokenId)<(int)(self->tokens->len)){
                self->tokenId++;
                self->tokenPt=stack->at(self->tokens,self->tokenId);
        }
        return self->tokenPt;
}

static char * Context_currentToken(Context *self){
        return self->tokenPt;
}

static char* Context_skipToken(Context *self,char * token){
        if(strcmp(token,self->tokenPt)){
                exit(1);
        }
        return Context_nextToken(self);
}

int str2int(char *str){
        int i=0,tmp=0;
        while(str[i]!='\0'){
                if(str[i]>='0'&&str[i]<='9') tmp=tmp*10+(str[i]-'0');
                i++;
        }
        return tmp;
}
static int Context_currentNumber(Context *self){
        return str2int(self->tokenPt);
}

static size_t Context_reload(Context *self,char *code){
        char *window[2]={0,};
        self->tokens=NEW0(Stack);
        CT(self)->currentNumber=(void *)Context_currentNumber;
        CT(self)->currentToken=(void *)Context_currentToken;
        CT(self)->nextToken=(void *)Context_nextToken;
        CT(self)->skipToken=(void *)Context_skipToken;
        window[0]=window[1]=code;
        while(*(window[1])!='\0'){
                if(	(*(window[0])!=' ' && *(window[0])!='\t' && *(window[0])!='\n')&&
                        (*(window[1])==' ' || *(window[1])=='\t' || *(window[1])=='\n') ){
                        char * token=NULL;
                        token=ALLOC(sizeof(char)*(window[1]-window[0]+1));
                        memcpy(token,window[0],window[1]-window[0]);
                        printf(">>%s\n",token);
                        stack->push(self->tokens,token);
                        window[1]++;
                        window[0]=window[1];
                }else if(	(*(window[0])==' ' || *(window[0])=='\t' || *(window[0])=='\n')&&
                                        (*(window[1])!=' ' && *(window[1])!='\t' && *(window[1])!='\n') ){
                        window[0]=window[1];
                }else{
                        window[1]++;
                }
        }
        char * token=NULL;
        token=ALLOC(sizeof(char)*(window[1]-window[0]+1));
        memcpy(token,window[0],window[1]-window[0]);
        printf(">>%s\n",token);
        stack->push(self->tokens,token);

        self->tokenId=0;
        self->tokenPt=stack->at(self->tokens,0);
        return 0;
}

static size_t Context_unload(Context *self,char *code){
        return DELETE(self->tokens,(void *)1);
}
ASM(Context,Context_reload,Context_unload,NULL,NULL)
int main(int argc, char **argv){
        char code[512]={0,};
        Stack * s=NULL; 
        Node * node=NULL;
        StNode *ns=NULL;
        Context * context=NULL;
        FILE *fp = fopen(argv[1],"r");
        if (!fp) {
                printf("%s\n",argv[1]);
                perror("open"); exit(1);
        } 
        code[fread(code,1,512,fp)] = '\0';
        fclose(fp);
        s=NEW0(Stack);
        stack=ST(s);
        node=NEW0(Program);
        ns=ST(node);
        context=NEW(Context,code); 
        ns->parse(node,context);
        ns->execute(node);
        DELETE0(context);
        DELETE0(node);
        DELETE0(s);
        return 0;
}
Powered by Google Project Hosting