自己动手编Basic解释器.doc

那些客套话咱就不扯那么多了，啥写编译器是多少程序员梦想阿，多牛逼阿之类云云这之类的话咱就不聊了，主要是这里是C(不是java)，C程序没java那么多套路，直接单刀赴会了。好了既然我们是写basic解释器，那我们至少先要明白两件事情:第一，什么是解释器；第二，basic语法这个至少要了解大概吧。第一，什么是解释器？编译器大家应该都知道，GCC，VC(当然这个不纯粹是编译器了)，简单的说呢，编译器将程序的源代码转化为可执行代码的形式。通常情况下，这种可执行代码由计算机的CPU指令组成，因此可以直接在计算机上执行。而解释器就不同了，它顺序读入程序的源代码，然后依次执行每一条语句。因此，解释器并不真正将源代码转化为目标代码，而是直接执行程序。 第二，basic语法(以及我们为什么选择basic解释器作为编写目标) 先说第一个为什么写basic？ 因为basic语法简单，你听名字也大概知道了，比如我不会选择advance作为编写目标，名字就比较吓人。basic我们不来详细讲了，因为我们做得这个解释器本来就很小，没涉及到多少东东，有需要的可以google一下。这里先贴一小段代码，混个脸熟: PRINT A Simple Small BASIC Program 打印字符串 FOR X = 1 TO 10 for循环 GOSUB 100 跳到标号100 语句执行 注意这里100是标号 NEXT 下一个x 表示x要加一 END 程序结束 100 PRINT X 这里相当于C中函数 RETURN 返回代码一目了然，我们解释器基本上也就处理这几个关键字。现在摆在我们面前的就是如何处理这些关键字，换句话来说，我们如何在程序读取到相应关键字时，做出相应反应了。比如 我们执行print，我们就要用printf把print后面的东东打印出来。这还比较好办，但是如果是一个for循环呢，我们又该如何处理？ 关键字处理是个大麻烦，因为我们面对不同关键字，要做出不同反应来。这个还是后话，眼前我们还是把主要框架先看看。第一步 装载源代码 用过gcc么？郁闷 gcc都没用过！看来在windows下生活滋润惯了，学计算机还是要来open source阵营阿，话扯远了。我们用gcc编译c文件时，都是gcc o target source 。 所以我们也仿照这格式，直接用命令行 (图形界面我们就不用实现了，再说俺也不懂)。main (int argc,char *argv) char *p_buf; char *t; if (argc!=2) printf (usage: %s n,argv0); exit (1); /* allocate memory for the program */ if (!(p_buf=(char *)malloc(PROG_SIZE) printf (allocation failure); exit (1); /* load the program to execute */ if (!load_program(p_buf,argv1) exit(1); 这里我们开辟一个PROG_SIZE大小空间，供装载程序源码用。然后我们把程序代码用load_program函数装入内存。代码如下: /* Load a program */ load_program (char *p,char *fname) FILE *fp; int i=0; if (!(fp=fopen(fname,rb) return 0; i=0; do *p = getc(fp); p+;i+; while (!feof(fp)&i查找prog */ *temp = *prog; /把这个分界符拷贝到token中 prog+; /* advance to next position */ temp+; *temp=0; /最后补上零 这样让token形成字符串 return (token_type = DELIMITER); /* 这里表明后面的是字符串 basic中常常出现的情况是 print hello world * 下面的例子就以此举例了 */ if (*prog = ) prog+; /prog指向了字符h，注意这里已经进入了字符串 while (*prog!=&*prog!=r) *temp+=*prog+; /只要字符串没结束(prog遇到双引号)，或者是没换行(r) 我们就要把原代码拷贝到token中 if (*prog=r) serror(1); /字符串不能换行 prog+;*temp=0; /prog已经走出字符串啦，照样的token要补上结束符 return (token_type = QUOTE); /token_type为字符串 /* 数字处理 * 唯一要注意的是我们现在的数字是字符串形式的. */ if (isdigit(*prog) while (!isdelim(*prog) *temp+=*prog+; /如果没有分界符，拷贝之 *temp = 0; return (token_type = NUMBER); /* 处理字符 仍举例 print hello world * 这里我们得到print * 注意该代码块没有马上返回 */ if (isalpha(*prog) while (!isdelim(*prog) *temp+=*prog+; /没有分界符拷贝之 token_type = STRING; /string类型 这只是一个中间类型 具体要划分为变量、关键字 你会想为什么不会是我们打印的常量字符串呢 因为上面我们已经处理了 *temp = 0; /不过这一句放在外面 其实没多大意义 前面的情况都return了， 剩下一个孤零零 因为接下来我们还要处理这玩意儿 /* 查看究竟是个命令呢,还是一个变量,拭目以待. */ if (token_type = STRING) tok = look_up(token); /* 在变量hash表中查之 */ if (!tok) token_type = VARIABLE; /变量 else token_type = COMMAND; /关键字 return token_type;get_token里面还有一些小函数，这里我们同样也罗列出来。里面嵌套的函数我都注释了的，都比较好懂，注意点我都有解释/* 回滚 */void putback() char *t; t = token; for (;*t;t+) prog-; / /* 这丫是帮我们在关键字table表里面搜索是否包含当前字符串 */look_up(char *s) register int i,j; char *p; /* 命令因为我们全都用小写字符 这里不得不转换了 */ p = s; while (*p) *p = tolower(*p); p+; /* 顺序查找 呃 这个是个tiny 所以效率不太考虑了 * 想想如果我们关键字很多的话 应该做一个hash表 * 这里如果查找成功返回一个标号 失败返回0 请参阅table结构 */ for (i=0;*mand;i+) if (!strcmp(mand,s) return tablei.tok; return 0; /* 查字符c是否是分界符 * 恩 有一点要注意 比如我们的数字是909 那么这里传进来的c的ASCII码可不是909 应该是9+0,0,9+0*/isdelim(char c) if (strchr(;,+-/*%=() ,c)|c=9|c=r|c=0) /所以这里c=9 表示t 0自然是0 return 1; return 0;/* 查是不是空白,就是空格和tab键*/iswhite (char c) if (c= |c=t) return 1; else return 0;至此 标识符处理我们全部完成，工作完成了一大块，剩下就是关键字处理了，里面涉及到语句逻辑。经过get_token，我们可以获取一个标识符，按理说来下步可以进行程序逻辑处理了，但是标识符获取后我们离后面的真正程序逻辑运行还有一个大障碍，这就是表达式求解的问题。 比如说我们遇到一条语句 PRINT 3*(a+b) ，这里print 倒是能识别是个关键字，我们按照程序逻辑应该打印后面的东东，是字符串就直接打印，是变量就取值打印，但是这里偏偏是一个表达式，我们需要事先计算出表达式的值。接下来的问题就演变成了如何计算一个表达式，或者说写一个四则运算器。关于如何写四则运算器，网上相关资料很多，源代码里的函数我没有解读，主要是看着不爽，逻辑性不够。再者这个东西其实我大一自学数据结构的时候写过，主要思想是建立二叉树，然后类似一个中序遍历即可。这里稍作解释，具体代码分析就不写了。大家可以参照我原来的博客四则运算重言式判别。我们策略是设置运算符权值，具体规则是设置初始权值为0，扫描整个表达式，遇到 - 号权值加1，赋给当前运算符号，遇到乘除号，权值加2，赋值；遇到乘方号，权值加3，赋值；遇到左括号，权值加4，遇到右括号，权值减4。 比如33*(4-2) 初始权值赋值为0 第一个加号，加上1，赋给加号。第二个乘号权值加上2，权值为2(注意前面权值加一只是为了赋值，本身不变)，赋给乘号。后面遇到左括号，权值本身再加4，这时权值为4，但是这里不赋值，因为括号不参与运算，当然这只是我这里图方便，你说要赋值也不是不可，就是后面麻烦点儿。马上又是减号，权值加1赋值，减号的权值变5，接着是右括号，权值减4。所以整个下来有33*(4-2) 表达式 1 2 5 权值权值分析完毕，然后就是找出最小权值的一个符号，作为二叉树的根，权值越大的越往下生长，叶子节点全是数字。然后递归遍历解决。我原来那个程序只能计算表达式，但其实稍作改动就能计算变量了。在此不再赘述。下面贴出计算核心代码:double calculator(binarytree *root) if(root) if(root-left=NULL&root-right=NULL) return atof(&root-data); else switch(root-data) case *: return calculator(root-left)*calculator(root-right); break; case /: return calculator(root-left)/calculator(root-right); break; case +: return calculator(root-left)+calculator(root-right); break; case -: return calculator(root-left)-calculator(root-right); break; case : return pow(calculator(root-left),calculator(root-right); default: break; 经过表达式求解函数get_exp(value)处理后，我们就得到这个表达式的值了。这样，万事具备，就等着程序的逻辑处理.表达式已求，下面可以进入程序逻辑处理了，这里的代码量比较大，不过都很简单，后面主要是以程序注释为主。先来看看完整版的主函数:main (int argc,char *argv) char in80; int answer; char *p_buf; char *t; if (argc!=2) printf (usage: run n); exit (1); /* allocate memory for the program */ if (!(p_buf=(char *)malloc(PROG_SIZE) printf (allocation failure); exit (1); /* load the program to execute */ if (!load_program(p_buf,argv1) exit(1); if (setjmp(e_buf) exit(1); /* initialize the long jump */ prog = p_buf; scan_labels(); /* 搜索所有的标签 */ ftos = 0; /* 初始化栈指针 这个是为for循环作准备的 */ gtos = 0; /* 初始化栈指针 这个是为gosub作准备的 */ do token_type = get_token(); /* 如果当前是变量 */ if (token_type=VARIABLE) putback(); /* 回退prog指针到变量前 */ assignment(); /* 赋值 */ else /* 除了变量那就是关键字了 可能有同学会问 呃 那个比如一个数字怎么没考虑 请想想一个数字怎么会单独出现 */ switch (tok) case PRINT: print(); break; case GOTO: exec_goto(); break; case IF: exec_if(); break; case FOR: exec_for(); break; case NEXT: next(); break; case INPUT: input(); break; case GOSUB: gosub(); break; case RETURN: greturn(); break; case END: exit(0); while (tok != FINISHED);main函数其实没啥好说的，主要是这个函数是个花架子，真正实在的逻辑处理不在这里。不过特别需要强调的是prog这个字符指针，这是程序的命根子，它打到哪儿我们就得运行到哪儿，get_token就得取哪儿的标识符。当然这种重要的东西肯定是掌握在我们自己手里。另外是setjmp函数，这个可以理解为windows系统中的系统还原，一旦出错我们程序可以跳到这个还原点。在while循环里，我们一行一行处理源代码，注意是一行一行的进行，比如print a,b,c 我们会在print函数里面循环打印a,b,c 。而不会多次调用print，这种设计很巧妙。来先看看变量赋值函数assignment:/* 给变量赋值 比如 a3 * 注意这里为了简化起见，我们的变量就设置为26个字母 */assignment() int var,value; /* getthe variable name */ get_token(); if (!isalpha(*token) /因为变量我们用字母代替 所以必定是字母类型 serror(4); return; var = toupper(*token)-A; /转化为大写字母 然后减去A 这样让变量在hash表中有了座次 比如A减去A为0 这样A字符变量在变量hash表中第一个位置 /* get the equals sign * 这里我们取a=3 中间的等号*/ get_token(); if (*token!=) /既然赋值么 肯定有等号了 serror(3); return; /* a=3 等号取走了 我们来取数值 */ get_exp(&value); /* 把我们取到的变量 比如a 值为3 存放在hash表中 */ variablesvar = value;这里的变量我们用26个字母表示，比较简单，减少了我们代码逻辑判断，当然缺点就是变量不能见名知义，还有有时不够用，要知道我们这个basic没有所谓的全局变量和局部变量，都作为全局处理的。这里面又嵌套了一个函数serror，看名字就知道是错误处理的:/* 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 (%sn,eerror); longjmp(e_buf,1); /* return to save point */这个函数就是个打印，里面有个longjmp，就是上面所说的跳到系统恢复点，与setjmp隔江相望。具体可以查查。是所谓先来后到，我们还是按照主函数出现的顺序，依次分析逻辑函数。1、printprint函数主要的关注两点，第一点是打印格式，第二点是打印方式。比如我举两例:print a print hello world 要分清楚打印变量还是打印字符串 这是打印方式的问题 print a,b print a;b 要分清楚打印格式，注意一个是分号一个是逗号 两者有区别!print代码:/* execute a simple version of the BASIC PRINT statement * 执行打印 这里我们还是举例说明*/ void print() int answer; int len=0,spaces; char last_delim; do get_token(); /* get next list item */ if (tok=EOL|tok=FINISHED) break; /如果取到的符号是一行结束或者文件结束 自然的打印结束 /BASIC 中print一般有两种用法 第二种就是print hello world 打印字符串 if (token_type=QUOTE) printf (%s,token); len+=strlen(token); get_token(); /注意我们打印了后又取了一次符号 else /打印变量的 putback(); get_exp(&answer); get_token(); /注意我们打印了后又取了一次符号 len += printf (%d,answer); last_delim = *token; /* Basic 有两种打印间隔标识 * 比如 print a,b 表示按标准格式打印 * 而print a;b 表示按照紧凑格式打印 * 所谓标准格式简单来讲就是间隔大点儿 紧凑自然间隔小点儿 */ if (*token=,) /* compute number of move to next tab */ spaces = 8-(len%8); len += spaces; /* add in the tabbing position */ while (spaces) printf ( ); spaces-; else if (*token=;) printf ( ); else if (tok != EOL & tok != FINISHED) serror (0); /print a,b 打完一次后 要么是逗号、分号 要么就是行结束或者文件结束 如果四者不居其一 必然错了 while (*token=;|*token=,); /例如 print a,b,c 如果token是逗号、分号 那么表示后面还有打印 继续来 /* 当处于行结束或者文件结束 那么前一次分界符不能是;或者, * 示例 如果 print a, 这个明显是语法错误 a后面不应该要逗号 * 那么打印完a取出token是逗号 我们赋值给last_delim 继续循环 * 下一个是行结束 跳出打印但是检验出last_delim是逗号 出错 */ if (tok=EOL|tok=FINISHED) if (last_delim != ; & last_delim != ,) printf (n); else serror(0); /* error is not, or ; */ 2、goto关于goto的争论还是上个世纪计算机洪荒时代，争论的结果是大量程序员在程序中尽量回避goto这个关键字，其实合理的使用goto不但提升效率，还能增加代码可读性。/* execute a GOTO statement. * goto一般形式即是 goto label */ void exec_goto() char *loc; get_token(); /* 这里获取标号，即是标签内容 */ loc = find_label (token); /标签是为跳转所用，所以获取标签后我们马上要想办法得到标签所代表地址 if (loc=0) serror(7); /* 出错 */ else prog=loc; /* 重新 设置prog指针 指出了下一个我们运行的地址 我们得完全听他的*/ label表在我们最开始处理程序的时候已经完成，我理解为预处理，代码如下，总的思路是扫描一遍代码，搜索标号。 注意 在我们这个basic中，我们标号的规定是必须在一行开头，并且是数字. 这个例子可以参照文章第一部分我举的那个basic例子，其实我们可以看到现实中确实有这样basic规定，比如smallbasic。标签初始化：scan_labels():/* 搜索所有标签 * 这个函数可以说是basic里面的预处理 * 我们搜索源代码 找出里面的标签 将其存入标签表 * 所谓标签label 其实C语言也有 不过一般不常用 因为label多半和goto一起出现的 而在结构化程序设计中 goto出现被人认为是绝对不能的 * 不过内核中goto却是常常出现 */ void scan_labels() int addr; char *temp; label_init(); /* zero all labels */ temp = prog; /* save poiter to top of program */ /* 如果源代码中第一个token是个数字的话 存入标签表中 表明是个标签*/ get_token(); if (token_type=NUMBER) strcpy (label_,token); label_table0.p=prog; find_eol(); /提行 do get_token(); if (token_type=NUMBER) /如果是数字 注意我们标签定义为行开头、数字 addr = get_next_label(token); if (addr=-1|addr=-2) (addr=-1) ? serror(5):serror(6); strcpy (label_,token); label_tableaddr.p = prog; /* 标签干什么用的 就是方便跳转阿 所以我们要记录标签所在地址 */ /* if not on a blank line , find next line */ if (tok!=EOL) find_eol(); while (tok!=FINISHED); prog = temp; /* restore to original */ 3、ifif这个函数貌似有点儿问题。我直接加在注释里的，如果我理解错了，还请各位指出:/* execute an IF statement * 执行if语句 */ void exec_if() int x,y,cond; char op; /* 这里我们只是处理一个简单的if 就是if (x operator y) */ get_exp(&x); /* 获取操作符左边数值 */ get_token(); /* 获取操作符 比较符 */ if (!strcmp(,*token) /这里有点儿问题 一个字符串不可能跟一个字符比较吧 serror(0); /* not a leagal oprator */ return; op = *token; get_exp(&y); /* 操作符右边 */ /* determine the outcome */ cond = 0; switch(op) case : if (x: if (xy) cond=1; break; case =: /这里也是有点儿问题，op是字符类型 怎么会可能会是=，而且好笑的是basic没有这个符号 if (x=y) cond=1; break; if (cond) /* is true so process target of IF */ get_token(); if (tok != THEN) /if 后面会连上then 所以有if没then是错误的 serror(8); return; /* else program execution starts on next line */ else find_eol(); /* find start of next line */ 4、for接着看for，for循环这里借助了栈来实现，很不错的方法。/* execute a FOR loop * for 循环 其主要格式 文章第一篇已经给出 * for i=1 to 10 * next i * 下面就引用此例了 */void exec_for() struct for_stack i; /申请一个栈元素 到时候加入 int value; get_token(); /* 获取标号 这里获取到变量i */ if (!isalpha(*token) /变量必定是字符型 serror(4); return; i.var = toupper(*token) - A; /* 我们是把变量放在hash表中的 所以这里来计算变量在hash表中位置 */ get_token(); /* 这里得到了等号 */ if (*token!=) serror(3); return; get_exp(&value); /* 初始值 比如这里是1 */ variablesi.var=value; /这里把初始值放在变量数组中 get_token(); if (tok != TO) serror(9); /* 读取to单词 */ get_exp(&i.target); /* 取得最终要达到的数值 比如这里是10 */ /* if loop can execute at least once, push into on stack */ if (valueFOR_NEST) serror(10); fstackftos=i; ftos+;for循环依靠next关键字来进入下一轮循环，并且要把循环变量加一/* execute a NEXT statement */void next() struct for_stack i; i = fpop(); /* 这里我们读出当年压栈的记录 */ variablesi.var+; /* 变量加一 */ if (variablesi.vari.target) return; /* 这个自然是作完了 */ fpush(i); /* 没做完事情，记录当前变量 压栈 */ prog = i.loc; /* 记得么 loc记录了for循环的第一个要执行的语句 这样我们就顺利地转入下次循环开始执行 */出栈代码