[分享]Basic程序解释器及编译原理的简单化

[分享]Basic程序解释器及编译原理的简单化

在网上,看到还是有部分程序爱好者希望能编出自己的编译器.当然,这的确是件难事,许多人都说要去看什么编译原理和精通汇编语言,结果让这些爱好者都望而却步.但是,当我们亲手去做做后,发现要做一个简单的程序解释器(就像Java和Basic)那样,还是挺容易的.你根本不用去看那些东西,只要你懂C语言,在看了本文后,就可以完成那样的解释器.

在网上,有许多大型C语言,Perl语言的编译器源代码.但当你下载后看看,竟发现点都看不懂.其实那些东西还是不看为妙.看了本文后,我相信你宁愿自己动手编,也不愿意去领会那些庞大的源代码了.

少说费话了,我们开始讲解.

这一篇Basic解释器的代码.十分经典.而且十分简单化.

get_token()是词汇提取,譬如 PRINT A+B

通过调用一次get_token(),就在 字符串token里装上PRINT
再调用一次get_token(),token里就装上A
再调用一次get_token(),token里就装上+
再调用一次get_token(),token里就装上B

很简单吧!

putback()是将prog指针向回移动一格.其中包含了词发分析和十分关键的代数式求值get_exp(int *result)

关于它的代数式求值get_exp(int *result),用到递归函数

void get_exp(),level2(),level3(),level4(),level5();
void level6(),primitive(),arith(),unary();

,确实难看懂,不过你尽管拿来用就是了.

话不多说,你看源代码就是了.最后,我将给你看看C++中完整的源代码

复制内容到剪贴板

代码:

/*
   recursive descent parser for integer expression
   which may include variables
*/

#include <STDIO.H>
#include <SETJMP.H>
#include <MATH.H>
#include <CTYPE.H>
#include <STDLIB.H>

#define DELIMITER 1
#define VARIABLE 2
#define NUMBER 3
#define COMMAND 4
#define STRING 5
#define QUOTE 6

#define EOL 9
#define FINISHED 10

extern char *prog;  /* holds expression to be analyzed */

extern jmp_buf e_buf;  /* hold enviroment */
extern int variables[26];  /* variables */
extern struct commands {
    char command[20];
    char tok;
} table[];

extern char token[80];  /* holds string representation of token */
extern char token_type;  /* contains type of token */
extern char tok;  /* holds the internal representation of token */

void get_exp(),level2(),level3(),level4(),level5();
void level6(),primitive(),arith(),unary();
void serror(),putback();


/* entry point into parser */
void get_exp(int *result)
{
    get_token();
    if (!*token) {
        serror(2);
        return;
    }
    level2(result);
    putback();  /*return last token read to input stream */
}


/* add or subtract two terms */
void level2(int *result)
{
    register char op;
    int hold;

    level3(result);
    while ((op = *token) =='+' || op == '-')  {
        get_token();
        level3(&hold);
        arith(op,result,&hold);
    }
}


/* multiply or divide two factors */
void level3(int *result)
{
    register char op;
    int hold;

    level4(result);
    while ((op = *token) == '*' || op == '/' || op == '%')  {
        get_token();
        level3(&hold);
        arith(op,result,&hold);
    }
}


/* process integer exponent */
void level4(int *result)
{
    register char op;
    int hold;

    level5(result);
    if (*token == '^') {
        get_token();
        level4(&hold);
        arith(op,result,&hold);
    }
}


/* is a unary + or - */
void level5(int *result)
{
    register char op;

    op = 0;
    if ((token_type==DELIMITER) && *token == '+' || *token == '-' )  {
        op = *token;
        get_token();
    }
    level6(result);
    if (op)  unary(op,result);
}


/* process parenthesized expression */
void level6(int *result)
{
    if ((*token == '(') && (token_type == DELIMITER))  {
        get_token();
        level2(result);
        if (*token!=')')
            serror(1);
        get_token();
    }
    else
        primitive(result);
}


/* find value of number or variable */
void primitive(int *result)
{
    switch (token_type)  {
        case VARIABLE:
            *result = find_var(token);
            get_token();
            return;
        case NUMBER:
            *result = atoi(token);
            get_token();
            return;
        default:
            serror(0);
    }
}


/* perform the specified arithmetic */
void arith(char o,int *r,int *h)
{
    register int t,ex;

    switch (o)  {
        case '-':
            *r = *r-*h;
            break;
        case '+':
            *r = *r+*h;
            break;
        case '*':
            *r = *r**h;
            break;
        case '/':
            *r = (*r)/(*h);
            break;
        case '%':
            *r = (*r)%(*h);
            break;
        case '^':
            ex = *r;
            if (*h==0)  {
                *r = 1;
                break;
            }
            for (t=*h-1;t>0;--t)  *r=(*r)*ex;
            break;
    }
}


/* reverse the sign */
void unary(char o,int *r)
{
    if (o=='-')  *r = -(*r);
}


/* find the value of a variable */
int find_var(char *s)
{
    if (!isalpha(*s))  {
        serror(4);  /* not a variable */
        return 0;
    }
    return variables[toupper(*token)-'A'];
}


/* display an error message */
void serror(int error)
{
    char *e[] = {
        "syntax error",
        "unbalanced parentheses",
        "no expression present",
        "equal sign expected",
        "not a variable",
        "label table full",
        "duplicate label",
        "undefined label",
        "THEN expected",
        "TO expected",
        "too many nested FOR loops",
        "NEXT without FOR",
        "too many nested GOSUB",
        "RETURN without GOSUB"
    };

    printf ("%s\n",e[error]);
    longjmp(e_buf,1);  /* return to save point */
}


/* get a token */
get_token()
{
    register char *temp;

    token_type = 0;tok = 0;
    temp = token;

    if (*prog == '\0')  {   /* end of file */
        *token = 0;
        tok = FINISHED;
        return (token_type = DELIMITER);
    }

    while (iswhite(*prog))  ++prog;  /* skip over white space */

    if (*prog == '\r')  {   /* CR LF */
        ++prog;++prog;
        tok = EOL;*token = '\r';
        token[1] = '\n';token[2] = 0;
        return (token_type = DELIMITER);
    }

    if (strchr("+-*^/%=;(),><",*prog))  {  /* delimiter */
        *temp = *prog;
        prog++;  /* advance to next position */
        temp++;
        *temp=0;
        return (token_type = DELIMITER);
    }

    if (*prog == '"')  {   /* quote string */
        prog++;
        while (*prog!='"'&&*prog!='\r')  *temp++=*prog++;
        if (*prog=='\r')  serror(1);
        prog++;*temp=0;
        return (token_type = QUOTE);
    }

    if (isdigit(*prog))  {   /* number */
        while (!isdelim(*prog))  *temp++=*prog++;
        *temp = '\0';
        return (token_type = NUMBER);
    }

    if (isalpha(*prog))  {   /* var or command */
        while (!isdelim(*prog))  *temp++=*prog++;
        token_type = STRING;
    }

    *temp = '\0';

    /* see if a string is a command or a variable */
    if (token_type == STRING)  {
        tok = look_up(token);  /* convert to internal rep */
        if (!tok)  token_type = VARIABLE;
        else token_type = COMMAND;  /* is a command */
    }
    return token_type;
}


/* return a token to input stream */
void putback()
{
    char *t;
    t = token;
    for (;*t;t++)  prog--;
}


look_up(char *s)
{
    register int i,j;
    char *p;

    /* convert to lowercase */
    p = s;
    while (*p)  { *p = tolower(*p); p++;  }

    /* see if token is in table */
    for (i=0;*table[i].command;i++)
        if (!strcmp(table[i].command,s))  return table[i].tok;
    return 0;   /* unknown command */
}


/* return true if c is a delimiter */
isdelim(char c)
{
    if (strchr(";,+-<>/*%^=() ",c)||c==9||c=='\r'||c==0)
        return 1;
    return 0;
}


iswhite (char c)
{
    if (c==' '||c=='\t')  return 1;
    else return 0;
}

这是CMake的源代码.主要负责词汇的提取
你可以调用它的CMake::get_token(),返回个CToken的类.

复制内容到剪贴板

代码:

/////////////////////////////////////////////////////
// Make.h
///////////////////////////////////////////////////

enum token_types{DELIMITER,VARIABLE,NUMBER,COMMAND,
             STRING,QUOTE,FINISHED,NONE,ENTER};         // 标记类型集合


#define TOKEN_MAX 80
#define STRDELIMITER "+-*^/=;(),><" // 符号集合
#define DIM     11 // Dim
#define AS      12 // As
#define INTEGER 13 // Integer
#define PRINT   14 // Print

class CToken
{
public:
char token[TOKEN_MAX];
int token_type;
int tok;
};

class CMake  
{
public:
CMake(char *Prog,int Proglength);
virtual ~CMake();
public:
    char *prog;
int proglength;
int isdelim(char c);     // 如果是运算符号返回1,不是则返回0
int iswhite(char c);     // 是空格返回1,不是则返回0
int look_up(char *c);    // 返回COMMAND类型,c是COMMAND字符串的指针
CToken get_token(void);   // 得到标记
int findchar(char *str,char ch); // 从str里找到ch,返回其在str里的引索;如果str里没有ch,则返回-1
};

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





// Make.cpp: implementation of the CMake class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Make.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CMake::CMake(char *Prog,int Proglength)
{
  proglength=Proglength;
  prog=new char[Proglength+1];
  strcpy(prog,Prog);
}

CMake::~CMake()
{

}


CToken CMake::get_token(void)
{
register char *temp;
CToken m_token;
    m_token.token_type=0;
m_token.tok=0;
temp=m_token.token;
if(*prog=='\0')
{
  *m_token.token='\0';
  m_token.tok=0;
  m_token.token_type=FINISHED;
  return m_token;
}
while(iswhite(*prog)) ++prog;
   
if(*prog=='\r') // 如果是换行符
{
  m_token.token[0]=*prog;
  m_token.token[1]='\0';
  m_token.token_type=ENTER;
  prog++;
  return m_token;
}
if( isdelim(*prog)) // 如果找得到运算符号标记
{
    *m_token.token=*prog;
    *(m_token.token+1)='\0';
    m_token.tok=0;
    m_token.token_type=DELIMITER;
    prog++;
    return m_token;            // 譬如 token[0]='+' token[1]='\0';
}

if(*prog=='"')   // 如果是字符串
{
  prog++;
  int i=0;
  while(*prog!='"' && *prog!='\r')
  {
   m_token.token[i]=*prog;
   i++;
   prog++;
  }
  prog++;
  m_token.token[i]='\0';
  m_token.token_type=QUOTE;
  return m_token;
}

if( isdigit(*prog)) // 如果找到数字标记
{
  int i=0;
  while(isdigit(*prog) && i<TOKEN_MAX) // 小于token最长为80个字符
  {
   m_token.token[i]=*prog;
   i++;
   prog++;
  }
  m_token.token[i]='\0';
  m_token.token_type=NUMBER;
  return m_token;
}
if( isalpha(*prog)) // 如果是命令COMMAND或是一般标记STRING
{
  int i=0;
  while(!isdelim(*prog) && *prog!=' ') // 不能是运算符号和空格
  {
   m_token.token[i]=*prog;
   i++;
   prog++;
  }
  m_token.token[i]='\0';
  if(look_up(m_token.token)) // 如果能查到它是命令COMMAND
  {
   m_token.token_type=COMMAND;
   m_token.tok=look_up(m_token.token);
  }
  else
  {
   m_token.token_type=STRING;
  }
  return m_token;
}


m_token.token_type=NONE;
prog++;
return m_token;
}

int CMake::iswhite(char c)
{
if(c==' '||c=='\t') return 1;
else return 0;
}

int CMake::isdelim(char c)
{
if( findchar(STRDELIMITER,*prog) >= 0 || c==9 || c=='\r' || c==0)
  return 1;
return 0;
}

int CMake::findchar(char *str,char ch)
{
int length=strlen(str);
if(length>0)
{
  for(int i=0;i<length;i++)
   if(str[i]==ch)
      return i;
   return -1;
}
else return -1;
}

int CMake::look_up(char *c)
{
if(strcmp(c,"print")==0)
  return PRINT;
    if(strcmp(c,"Integer")==0)
  return INTEGER;
if(strcmp(c,"Dim")==0)
  return DIM;
if(strcmp(c,"As")==0)
  return AS;

    return 0;
}

这是执行代码的CExecutable封装

//////////////////////////////////////////////////
// CExecutable.h
////////////////////////////////////////////////

class CintMember
{
public:
char name[64];
int value;
};

class CExecutable  
{
public:
CExecutable(vector <CToken> tokens);
virtual ~CExecutable();
void Run();
private:
vector <CToken> m_tokens; <a>file://装</A>所有标记的数据库
vector <CintMember> m_intArray; <a>file://装</A>所有int类型的变量
void Run_Print(int *index); <a>file://*</A>index是重要的m_tokens里的指针
void Run_Dim(int *index); <a>file://~~</A>
void Run_Assignment(int *index);// 赋值语句
<a>file://Ai</A>是辅助的意思,Ai_*()是辅助函数
int Ai_GetNextValue(void* result,int type,int *index); <a>file://得</A>到代数式的值result
int Ai_GetVarNo(char *name,int *result,int type);//得到变量在Array中的引索result
void get_exp(int *result,int *index);
void level2(int *result,int *index);
void level3(int *result,int *index);
void level4(int *result,int *index);
void level5(int *result,int *index);
    void level6(int *result,int *index);
void primitive(int *result,int *index);
void arith(char o,int *r,int *h);
void serror(int error);
int look_up(char *c);
int find_var(char *var_name,void *value); // 查找变量,将变量值装在*value
int Isvar(char *name); // 看name是否是变量,返回变量类型 0:什么都不是,1:Integer,2:string
};


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

// Executable.cpp: implementation of the CExecutable class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Executable.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CExecutable::CExecutable(vector <CToken> tokens)
{
m_tokens=tokens;
}

CExecutable::~CExecutable()
{
m_intArray.clear();
m_tokens.clear();
}

void CExecutable::Run(void)
{
   for(int i=0;i<=m_tokens.size()-1;i++)//注意:i是个十分重要的读取指针
   {
  if(m_tokens.at(i).token_type==COMMAND)
  {
   switch(m_tokens.at(i).tok) <a>file://tok</A>表示是什么命令
   {
   case PRINT: Run_Print(&i);
         break;
   case DIM:   Run_Dim(&i);
            break;
   default:   break;
   }
  }
  <a>file://赋</A>值语句一定要在最后来判断,因为这样如果是if后的条件判断就可以在
  <a>file://前</A>面的if命令中跳过
  if(*m_tokens.at(i).token=='=') <a>file://如</A>果是赋值语句
   Run_Assignment(&i);
   }
}

void CExecutable::Run_Print(int *index) <a>file://*</A>index是m_tokens里的指针
{
if(*index<m_tokens.size()-1) // 如果下面还有token
{   
  if(m_tokens.at((*index)+1).token_type==ENTER) <a>file://如</A>果接下来是命令
  {
   printf("\n");
   return;
  }
  (*index)++;   
  int token_type=m_tokens.at(*index).token_type;
  if(Isvar(m_tokens.at(*index).token)) <a>file://如</A>果接下来是变量
   token_type=VARIABLE;
        
  switch(token_type)
  {
  case QUOTE: <a>file://如</A>果是要打印字符串
   {
    printf(m_tokens.at(*index).token);
    return;
   }
  case VARIABLE:  <a>file://打</A>印代数式 type只要不是COMMAND就是可以当代数式处理
  case NUMBER:
  case DELIMITER:     
   {
    int result;
          Ai_GetNextValue(&result,INTEGER,index);
    printf("%d",result);
    return;
   }
  default: printf("\n");
     return;
  }
}
printf("\n");

}

void CExecutable::Run_Dim(int *index) <a>file://~~</A>
{
int i=*index;
if(i<m_tokens.size()-1)//~~
  if(m_tokens.at(i+1).token_type==STRING)
  {
   if(i<m_tokens.size()-3) <a>file://如</A>果下面还应该有 变量名,As,类型 三个tokens
   {
    CintMember member;
    if(m_tokens.at(i+2).token_type==COMMAND &&
     m_tokens.at(i+2).tok==AS) <a>file://如</A>果接下来的token是As
    {
    if(m_tokens.at(i+3).token_type==COMMAND)//接下来是变量类型
     switch(m_tokens.at(i+3).tok) <a>file://看</A>看是什么变量类型
     {
          case INTEGER: // 如果是Integer类型
        strcpy(member.name,m_tokens.at(i+1).token);
        member.value=0;
        m_intArray.push_back(member);
        *index+=3; // 将m_tokens里的指针跳3个
        break;
          default:     
        break;
     }
    }
   }
  }
}

void CExecutable::Run_Assignment(int *index) <a>file://index</A>必须指到'='的token
{
int var_type=Isvar(m_tokens.at(*index - 1).token);
if(!var_type) // 如果等号前面不是个变量
{
  serror(0);
  return;
}
switch(var_type)
{
case INTEGER:
  {
   int Var_No,value;
   if(!Ai_GetVarNo(m_tokens.at(*index-1).token,&Var_No,INTEGER))
               break;
   (*index)++;
            if(!Ai_GetNextValue(&value,INTEGER,index))
      break;
   m_intArray.at(Var_No).value=value;
   break;
  }
default: break;
}
}



int CExecutable::Ai_GetNextValue(void *result,int type,int *index) <a>file://index</A>指到代数式的第一个token
{
switch(type)
{
case INTEGER: get_exp((int*)result,index);
            return 1;
default:    return 0;
}

}

int CExecutable::Ai_GetVarNo(char *name,int *result,int type)
{
switch(type)
{
case INTEGER:
  {
   if(m_intArray.size()==0)
    return 0;
   for(int i=0;i<=m_intArray.size()-1;i++)
    if(!strcmp(name,m_intArray.at(i).name))
     *result=i;
    return 1;
  }
default: return 0;
}

}
void CExecutable::get_exp(int *result,int *index)
{
    if (!*m_tokens.at(*index).token)
{
        serror(2);
        return;
    }
    level2(result,index);
   
}


/* add or subtract two terms */
void CExecutable::level2(int *result,int *index)
{
    register char op;
    int hold;
    level3(result,index);
    while ((op = *m_tokens.at(*index).token) =='+' || op == '-')  
{
        (*index)++;
        level3(&hold,index);
        arith(op,result,&hold);
    }
}


/* multiply or divide two factors */
void CExecutable::level3(int *result,int *index)
{
register char op;
    int hold;
    level4(result,index);
    while ((op = *m_tokens.at(*index).token) == '*' || op == '/' || op == '%')  
{
        (*index)++;
        level3(&hold,index);
        arith(op,result,&hold);
    }
}


/* process integer exponent */
void CExecutable::level4(int *result,int *index)
{
register char op;
    int hold;
    level5(result,index);
    if ((op = *m_tokens.at(*index).token) == '^')
{
        (*index)++;
        level5(&hold,index);
        arith(op,result,&hold);
    }
}
              

/* is a unary + or - */              
void CExecutable::level5(int *result,int *index)
{
    register char op;
    op = 0;
    if ((m_tokens.at(*index).token_type==DELIMITER) &&
  *m_tokens.at(*index).token == '+' ||
  *m_tokens.at(*index).token == '-' )  
{
        op = *m_tokens.at(*index).token;
        (*index)++;
    }
    level6(result,index);
    if (op)  
  if(op=='-')
   *result=-(*result);
}
               

/* process parenthesized expression */               
void CExecutable::level6(int *result,int *index)
{
if ((*m_tokens.at(*index).token == '(') && (m_tokens.at(*index).token_type == DELIMITER))  
{
        (*index)++;
        level2(result,index);
        if (*m_tokens.at(*index).token!=')')
            serror(1);
        (*index)++;
    }
    else
        primitive(result,index);
}

/* find value of number or variable */
void CExecutable::primitive(int *result,int *index)
{
int token_type=m_tokens.at(*index).token_type;
    if(Isvar(m_tokens.at(*index).token))  
  token_type=VARIABLE;
    switch (token_type)  {
        case VARIABLE:
            find_var(m_tokens.at(*index).token,result);
            (*index)++;
            return;
        case NUMBER:
            *result = atoi(m_tokens.at(*index).token);
            (*index)++;
            return;
        default:
            serror(0);
    }
}

int CExecutable::find_var(char *var_name,void *value)
{
for(int i=0;i<=m_intArray.size()-1;i++)
  if(!strcmp(var_name,m_intArray.at(i).name))
  {
   int *int_value=(int *)value;
   *int_value=m_intArray.at(i).value;
   return 1;
  }
    return 0;
}

int CExecutable::Isvar(char *name)
{
if(m_intArray.size()==0)
  return 0;
for(int i=0;i<=m_intArray.size()-1;i++)
  if(!strcmp(name,m_intArray.at(i).name))
        return INTEGER;
return 0;
}

/* perform the specified arithmetic */
void CExecutable::arith(char o,int *r,int *h)
{
    /*register*/ int t,ex;
   
    switch (o)  {
        case '-':
            *r = *r-*h;
            break;
        case '+':
            *r = *r+*h;
            break;
        case '*':
            *r = *r**h;
            break;
        case '/':
            *r = (*r)/(*h);
            break;
        case '%':
            *r = (*r)%(*h);
            break;
        case '^':
            ex = *r;
            if (*h==0)  {
                *r = 1;
                break;
            }
            for (t=*h-1;t>0;--t)  *r=(*r)*ex;
            break;
    }
}

int CExecutable::look_up(char *c)
{
if(strcmp(c,"print")==0)
  return PRINT;
    if(strcmp(c,"Integer")==0)
  return INTEGER;
if(strcmp(c,"Dim")==0)
  return DIM;
if(strcmp(c,"As")==0)
  return AS;
    return 0;
}

void CExecutable::serror(int error)
{
char *e[] = {
        "syntax error",
        "unbalanced parentheses",
        "no expression present",
        "equal sign expected",
        "not a variable",
        "label table full",
        "duplicate label",
        "undefined label",
        "THEN expected",
        "TO expected",
        "too many nested FOR loops",
        "NEXT without FOR",
        "too many nested GOSUB",
        "RETURN without GOSUB"
    };

    printf ("%s\n",e[error]);
}