[size=1]《手把手教你武装自己的语言》之第零章——简单的解释器与开发环境编写（上）

-----------------------------------------------------------------------------------------------------------------------


话说本来想在第零章里面写一个Hello World程序，比如这样：
    键入 shout "Hello World"输出Hello Wirld，键入shout var输出var的值。
不过转念一想，试图自己写设计编译器、解释器的人一般来说都有一定的编程基础了，要是在第零章里面写这么个弱智的东西，那真是叫人想不跳过都难。

于是呢，结合最近一些比较痴迷的东西，我决定在第零章里面写一个真正的，已存在语言的解释器。
    这个语言就是大名鼎鼎的BF语言。

下面是BF语言介绍，知情者可以果断跳过：

    BF语言我个人感觉真的是世界上最好学的语言之一，因为你只要三分钟就能学会这个语言的全部，至于如何用BF语言编程，那就看你的脑袋了。

    BF语言的全称叫BrainF**k，是一种极小化的计算机语言，它是由Urban Müller在1993年创建的。Müller的目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。这种语言由八种状态构成，为Amiga机器编写的编译器（第二版）只有240个字节大小。
    就象它的名字所暗示的，BF程序很难读懂。尽管如此，BF图灵机一样可以完成任何计算任务。虽然BF的计算方式如此与众不同，但它确实能够正确运行。
    这种语言基于一个简单的机器模型，除了指令，这个机器还包括：一个以字节为单位、被初始化为零的数组、一个指向该数组的指针（初始时指向数组的第一个字节）、以及用于输入输出的两个字节流。*

        *来自WikiPedia中文版
    
    好了，介绍完毕，下面是基本语法：
        '>' 符号表示指针自增一，'<' 符号反之
        '+' 符号表示指针所指内容自增一，'-' 符号反之
        '.'  表示输出当前指针所指内容，',' 表示输入内容到指针所指处
        '[' 表示如果当前指针所指内容为零，跳转至下一个']'后面
        ']' 表示如果当前指针所指内容非零，跳转至下一个'['后面

    
好了，BF语言介绍完了，真实言如其名，非常的Brain F**king，非常的Coder Unfriendly，但是无疑，这个语言对于解释器很友好。

那么下面我们就来着手BF解释器的编写：
    我们的解释器可不仅仅是解释器，我们力求打造一个Coder Friendly的集成解释器的IDE，他要有如下功能：
        对BF语言文件进行解释运行（废了个话！）
        要能够对BF语句实时处理（像P可爱的ython那样）
        要能够在解释运行时实时显示各种信息，包括内存状态啦，指针位置啦，等等~
        要能够容忍不为指令的字符，大家要注释啊喂。
        调试环境要能够在程序出错时指出错误所在，否则IDE干神马吃的
        等等等等……按需扩充（这四个字很重要啊关系到你的代码可扩展性啊~！）
        
    激动吗，终于要作解释器了，第零步当然是给自己打气了~！
        跟我一起念：“BrainFk好！”“BrinFK好！”
    好了，接下来要让这既好又好的BrainFk转起来，Coding Time~！
    
    本文的上篇中，我们要写一个内核和一个简单的实时解释，首先，我们建立一个 .c 文件，随便你怎么命名了~
        /*  至于为什么用C语言，原因很简单，因为她快~！
            盗梦空间告诉我们，如果你用一个解释器来运行另一个解释器，那么一切都会变得死慢~！
            所以如果你试图用神马Python之类的脚本写解释器，你就……
        */
    在这个新建的C语言文件中写下如下的东西：
        
        #include <stdio.h>
        #include <malloc.h>

        #define INIT_SIZE 255
        #define INC_SIZE 15

        typedef char bfdata;
    前两句就不用解释了吧你懂的~
    常量INIT_SIZE代表初始时BF所用数组的最大长度，INC_SIZE代表当数组不够用时该增加多少。
        别问我为神马用常量而不直接把数字写进后面的代码里去，这叫做代码的可维护性，关于这方面的书可以看看《代码大全》之类。
    
    数据类型bfdata代表BF语言中每个数组元素的内部数据。
        使用typedef而不是直接用char也是为了代码可维护性
            比如哪天如果你要让BF语言中存储单元变大，你只要改这句就行了。
    
    接下来写上：
        bfdata* bfInit (int *locationOfPointer, int *memoryInUse) {
            int i;
            bfdata *bfhead;
            
            bfhead = (bfdata*) malloc(INIT_SIZE * sizeof(bfdata));
            
            for (i = 0; i < INIT_SIZE; i++) bfhead[i] = 0;
            
            *locationOfPointer = 0;
            *memoryInUse = INIT_SIZE;
            
            return bfhead;
        }
        
    这个函数的名字我本来想写bfEgineInit的，但是我发现过长的函数名有些编译器居然不能识别，真是悲剧。
    该函数的作用是初始化，创建一个长度为INIT_SIZE的数组用来模拟BF语言的运行环境，并返回该数组的指针。
        对于函数返回指针这个问题，我想说一下，别轻易用函数返回指针，因为函数在调用完毕时会清空其局部变量所使用的内存。
        不过，malloc()（以及Calloc()、realloc()等）函数所动态分配的内存不会在函数调用结束后清空，所以在这里是可以的。
    在创建了初始数组之后，我们要对数组进行一个可靠的初始化——所有元素置零，也就是
        for (i = 0; i < INIT_SIZE; i++) bfhead[i] = 0;  
  这句的含义。

    初始化函数写完了，我们要开始写解释部分了，一步一步来，写上：
        bfdata* bfExecCmd (char* bfCmd,  int *locationOfPointer, int *memoryInUse, bfdata* bfpointer) {

            int locationOfLoader = 0;
            int jumpSearcher = 0;
            while ( bfCmd[locationOfLoader] != '\0' ) {
                switch (bfCmd[locationOfLoader]){
    
    bfExecCmd函数用来解释执行BF命令，形参表中bfCmd用来传递BF命令
    locationOfPointer、memoryInUse、bfpointer分别用来传递当前指针的位置、当前所用内存和当前指针所指内容。
        注意这里使用传址方式，因为locationOfPointer、memoryInUse、bfpointer这三个变量将会在其它函数中用到。
        
    locationOfLoader用来定位当前所解释的字符（即当前字符在BF语句字符串中的位置），jumpSearcher用来控制跳转（具体使用将在下文中加以解释）。
    
    下面开始写：
        case '+':
            //printf("+\n");
            (bfpointer[*locationOfPointer])++;
        break;
            
        case '-':
            //printf("-\n");
            (bfpointer[*locationOfPointer])--;
        break;
        
    以上就不过多解释了，地球人都知道~
    那两个很奇怪的注释掉的printf是我当初用来调试的，相信我，在程序出问题的时候每一步操作写一个相应的输出是很有用的。
    
        case '<':
            //printf("<\n");
            if ( (*locationOfPointer) > 0 ) {
                (*locationOfPointer)--;
                --bfpointer;
            }
        break;
        
        case '>':
            //printf(">\n");
            if ( ( *locationOfPointer + 1 ) < *memoryInUse ) {
                (*locationOfPointer)++;
                ++bfpointer;
            } else {
                *memoryInUse += INC_SIZE;
                *locationOfPointer++;
                bfpointer = (bfdata*) realloc(bfpointer, *memoryInUse);
                bfpointer += *locationOfPointer;
                bfpointer;
            }
        break;
    
    这里要注意的就是指针不能越界，locationOfPointer必须大于零，且memoryInUse必须大于locationOfPointer。
    当然，我们可以在'<'被调用且当前指针位置为零时扔出一个错误信息，这事之后会加上的。
    重点在于'>'的判定以及新内存的分配，这里使用realloc()函数增长数组，注意常量INC_SIZE的出现。
    
        
        
    不解释，地球人都知道。
    
    现在的程序已经具有了顺序执行的能力了，我们可以先把switch神马的都 } 掉，写一个测试用的 main()函数，如下：
        int main () {

            bfdata* bfInit (int *locationOfPointer, int *memoryInUse);
            bfdata* bfExecCmd (char* bfCmd,  int *locationOfPointer, int *memoryInUse, bfdata* bfpointer);
        
            int locationOfPointer, memoryInUse;
            bfdata* bfpointer = bfInit (&locationOfPointer, &memoryInUse);

            char bfCmd[125] = {'\0'};
            
            while(1) {
                printf("\n: ");
                clearString(bfCmdBuffer);
                scanf("%s",bfCmd); fflush(stdin);
                bfpointer = bfExecCmd (bfCmd, &locationOfPointer, &memoryInUse, bfpointer);
            }
        }
    
    这里我们写了一个只有+-<>,.的BF实时解释器，使用while(1)循环来实现多次运行。
    运行结果如下：
        
    看！多有爱！
    
    接下来我们开始跳转的实现，首先重温一下BF语言中的跳转：
        '[' 当前指针内容为零时，跳转至所对的']'之后；
        ']' 当前指针内容非零时，跳转至所对的'['之后；
        
    那么我们当即可以在Switch中写下：
        case '[':
            //printf("[\n");
            if (bfpointer[*locationOfPointer] == 0) {
                //jump
            }
        break;
                    
        case ']':
            //printf("]\n");
            if (bfpointer[*locationOfPointer] != 0) {
                if( jumpSearcher == 0 ) jumpSearcher = 1;
                    //jump
            }
            break;
        }
    
    然后就是跳转的实现了，为了实现跳转，我们引入一个辅助变量jumpSearcher，定义为当[]符号配对成功时jumpSearcher为零，跳转。
    原理如下：
        当遇到一个'['（']'）跳转命令时我们置jumpSeacher为1，接下来向后（前）遍历，寻找配对的']'（'['），然后jumpSeacher置零。
        如果我们遇到一个']'（'['），有如下两种可能：
            配对成功，跳转。
            非对应字符，不跳转。
        由于'['和']'的数量相等，遇到后一种情况说明遍历时必定遇到了其他的'['（']'），于是我们可以用如下方法解决：
            每遇到一个'['（']'），jumpSeacher加一；
            每遇到一个']'（'['），jumpSeacher减一；
        
        这样当jumpSeacher为零时，必然代表找到匹配的符号，那么完整的跳转代码如下：
            case '[':
                //printf("[\n");
                if (bfpointer[*locationOfPointer] == 0) {
                    if( jumpSearcher == 0 ) jumpSearcher = 1;
                    locationOfLoader++;
                    while ( jumpSearcher != 0 ) {
                        if ( bfCmd[locationOfLoader] == '[' ) {
                            jumpSearcher++;
                        }
                        if ( bfCmd[locationOfLoader] == ']' ) {
                            jumpSearcher--;
                        }
                        printf("%d %d",locationOfLoader,jumpSearcher);
                    }
                }
            break;
                    
            case ']':
                //printf("]\n");
                if (bfpointer[*locationOfPointer] != 0) {
                    if( jumpSearcher == 0 ) jumpSearcher = 1;
                    while ( jumpSearcher != 0 ) {
                        locationOfLoader--;
                        if ( bfCmd[locationOfLoader] == ']' ) {
                            jumpSearcher++;
                        }
                        if ( bfCmd[locationOfLoader] == '[' ) {
                            jumpSearcher--;
                        }
                    }
                    //printf("%d %d",locationOfLoader,jumpSearcher);
                }
            break;
        }
        
    注释掉的printf用来输出对应的调试信息，非常有用。
    
    完整的bfExec()如下：
        bfdata* bfExecCmd (char* bfCmd,  int *locationOfPointer, int *memoryInUse, bfdata* bfpointer) {

            int locationOfLoader = 0;
            int jumpSearcher = 0;
            while ( bfCmd[locationOfLoader] != '\0' ) {
                switch (bfCmd[locationOfLoader]){            

                    case '+':
                        //printf("+\n");
                        (bfpointer[*locationOfPointer])++;
                    break;
                        
                    case '-':
                        //printf("-\n");
                        (bfpointer[*locationOfPointer])--;
                    break;
            
                    case '<':
                        //printf("<\n");
                        if ( (*locationOfPointer) > 0 ) {
                            (*locationOfPointer)--;
                            --bfpointer;
                        }
                    break;
                
                    case '>':
                        //printf(">\n");
                        if ( ( *locationOfPointer + 1 ) < *memoryInUse ) {
                            (*locationOfPointer)++;
                            ++bfpointer;
                        } else {
                            *memoryInUse += INC_SIZE;
                            *locationOfPointer++;
                            bfpointer = (bfdata*) realloc(bfpointer, *memoryInUse);
                            bfpointer += *locationOfPointer;
                            bfpointer;
                        }
                    break;
            
                    case '.':
                        putchar(bfpointer[*locationOfPointer]);
                        fflush(stdout);
                    break;
                
                    case ',':
                        bfpointer[*locationOfPointer] = getchar();
                        fflush(stdin);
                    break;
            
                    case '[':
                        //printf("[\n");
                        if (bfpointer[*locationOfPointer] == 0) {
                            if( jumpSearcher == 0 ) jumpSearcher = 1;
                            locationOfLoader++;
                            while ( jumpSearcher != 0 ) {
                                if ( bfCmd[locationOfLoader] == '[' ) {
                                    jumpSearcher++;
                                }
                                if ( bfCmd[locationOfLoader] == ']' ) {
                                    jumpSearcher--;
                                }
                                printf("%d %d",locationOfLoader,jumpSearcher);
                            }
                        }
                    break;
                    
                    case ']':
                        //printf("]\n");
                        if (bfpointer[*locationOfPointer] != 0) {
                            if( jumpSearcher == 0 ) jumpSearcher = 1;
                            while ( jumpSearcher != 0 ) {
                                locationOfLoader--;
                                if ( bfCmd[locationOfLoader] == ']' ) {
                                    jumpSearcher++;
                                }
                                if ( bfCmd[locationOfLoader] == '[' ) {
                                    jumpSearcher--;
                                }
                            }
                            //printf("%d %d",locationOfLoader,jumpSearcher);
                        }
                    break;
                }
        
                locationOfLoader++;
            }
            //printf("%d",locationOfLoader);
            return bfpointer;
        }
    
    main()如下：
        int main () {

            bfdata* bfInit (int *locationOfPointer, int *memoryInUse);
            bfdata* bfExecCmd (char* bfCmd,  int *locationOfPointer, int *memoryInUse, bfdata* bfpointer);
        
            int locationOfPointer, memoryInUse;
            bfdata* bfpointer = bfInit (&locationOfPointer, &memoryInUse);

            char bfCmd[125] = {'\0'};
            
            while(1) {
                printf("\n: ");
                clearString(bfCmdBuffer);
                scanf("%s",bfCmd); fflush(stdin);
                bfpointer = bfExecCmd (bfCmd, &locationOfPointer, &memoryInUse, bfpointer);
            }
        }
        
    运行结果如下：
        
    哇哈哈哈，Hello The Brain Phucking World~！！！！！！
    
    好了，我们有时候喜欢换行输入代码来增强可读性，比如
        ++++++++++[
            >+++++++
            >++++++++++
            >+++
            >+
            <<<<-
        ]
    如果我们把上面代码的第一行输入程序，那么就会出错了，程序找不到对应的']'
    
    解决方案如下：
        现在的程序是输入的字符串立即当做BF命令来执行，但是有时候我们需要延迟执行BF命令
        那么我们可以先将获得的BF命令存入一个缓冲区，待执行时从缓冲区调出命令再执行。
        什么时候需要延迟执行命令呢？
            当然是在命令中'['和']'的数量不相等的时候！
        那么我们就可以获得如下的算法：
            0 清空缓冲区
            1 从用户端读入字符串并存入缓冲区
            2 如果已有待执行的命令，将缓冲区中的内容加入待执行的命令之后
            3 分析'['和']'的数量，如果相等，执行命令并清空内存中已处理的命令
            4 返回0
        根据算法，我们设定新字符串变量bfCmdBuffer，并加入bfLoadCmd()函数用来将缓冲区的字符串读入命令区，通过函数返回值判定'['与']'是否相等。
        
        main()函数如下：
            int main () {

                bfdata* bfInit (int *locationOfPointer, int *memoryInUse);
                bfdata* bfExecCmd (char* bfCmd,  int *locationOfPointer, int *memoryInUse, bfdata* bfpointer);
                int bfLoadCmd (char* bfCmdBuffer, char* bfCmd, int* jumpCount);
    
                int locationOfPointer, memoryInUse;
                bfdata* bfpointer = bfInit (&locationOfPointer, &memoryInUse);

                char bfCmd[125] = {'\0'};
                char bfCmdBuffer[255] = {'\0'};
                int jumpCount = 0;
                
                int j = 0;
                while(1) {
                    printf(": ",jumpCount);
        
                    //clear bfCmdBuffer);
                    scanf("%s",bfCmdBuffer);
                    fflush(stdin);
                    if (bfLoadCmd(bfCmdBuffer, bfCmd, &jumpCount) == 0) {
                        bfpointer = bfExecCmd (bfCmd, &locationOfPointer, &memoryInUse, bfpointer);
                        printf("\n");
                        //clear bfCmd;
                    }
                    //printf("%s",bfCmd);
                }
            }
            
        bfLoadCmd由三个循环组成：
            int bfLoadCmd (char* bfCmdBuffer, char* bfCmd, int* jumpCount) {

                int i = 0;
                int j = 0;
    
                while ( bfCmdBuffer[i] != '\0' ) {
                    if ( bfCmdBuffer[i] == '[') (*jumpCount)++;
                    if ( bfCmdBuffer[i] == ']') (*jumpCount)--;
        
                    //printf(" jin %d", *jumpCount);
                    i++;
                }
                //printf("\njin %d", *jumpCount);
    
                i = 0;
    
                while (bfCmd[j] != '\0') {
                    j++;
                    //printf("%d %d |",i,j);
                }
    
                while (bfCmdBuffer[i] != '\0') {
                    bfCmd[j] = bfCmdBuffer[i];
                    i++;
                    j++;
                    //printf("%d %d |",i,j);
                }
    
                bfCmd[j] = '\0';
    
                //printf("%s",bfCmd);
    
                return *jumpCount;
            }
            
        第一个循环遍历缓冲区中的字符，判断[]数量是否相等，之后计数器复位，等待下一次循环。
        第二个循环将j计数器累加到命令区字符段长度
        第三个循环将缓冲区字符串追加至命令区后面，循环结束后将命令区最后一个字符置'\0'
        
        注意这里所有的参数都是传址的，因为这些数据在函数外会被调用。
        
        注释掉的printf调试时是很有用的。
                
        编写clearString函数：
            int clearString(char* strToClear) {

                strToClear[0] = '\0' ;
                return 0;
            }
            
        同时我们在main()函数中加入缩进功能，即：
            当我们发现指令区'['数量大于']'数量时，我们自动在输入前缩进以增强可读性。
            
        最终的程序如下：


#include <stdio.h>
#include <malloc.h>

#define INIT_SIZE 255
#define INC_SIZE 15

typedef char bfdata;

bfdata* bfInit (int *locationOfPointer, int *memoryInUse) {
    int i;
    bfdata *bfhead;
    bfhead = (bfdata*) malloc(INIT_SIZE * sizeof(bfdata));
    for (i = 0; i < INIT_SIZE; i++) bfhead[i] = 0;
    *locationOfPointer = 0;
    *memoryInUse = INIT_SIZE;
    return bfhead;
}

int bfLoadCmd (char* bfCmdBuffer, char* bfCmd, int* jumpCount) {

    int i = 0;
    int j = 0;
    
    while ( bfCmdBuffer[i] != '\0' ) {
        if ( bfCmdBuffer[i] == '[') (*jumpCount)++;
        if ( bfCmdBuffer[i] == ']') (*jumpCount)--;
        
        //printf(" jin %d", *jumpCount);
        i++;
    }
    //printf("\njin %d", *jumpCount);
    
    i = 0;
    
    while (bfCmd[j] != '\0') {
        j++;
        //printf("%d %d |",i,j);
    }
    
    while (bfCmdBuffer[i] != '\0') {
        bfCmd[j] = bfCmdBuffer[i];
        i++;
        j++;
        //printf("%d %d |",i,j);
    }
    
    bfCmd[j] = '\0';
    
    //printf("%s",bfCmd);
    
    return *jumpCount;
}

bfdata* bfExecCmd (char* bfCmd,  int *locationOfPointer, int *memoryInUse, bfdata* bfpointer) {

    int locationOfLoader = 0;
    int jumpSearcher = 0;
    while ( bfCmd[locationOfLoader] != '\0' ) {
        switch (bfCmd[locationOfLoader]){            

            case '+':
                //printf("+\n");
                (bfpointer[*locationOfPointer])++;
            break;
                
            case '-':
                //printf("-\n");
                (bfpointer[*locationOfPointer])--;
            break;
            
            case '<':
                //printf("<\n");
                if ( (*locationOfPointer) > 0 ) {
                    (*locationOfPointer)--;
                    --bfpointer;
                }
            break;
                
            case '>':
                //printf(">\n");
                if ( ( *locationOfPointer + 1 ) < *memoryInUse ) {
                    (*locationOfPointer)++;
                    ++bfpointer;
                } else {
                    *memoryInUse += INC_SIZE;
                    *locationOfPointer++;
                    bfpointer = (bfdata*) realloc(bfpointer, *memoryInUse);
                    bfpointer += *locationOfPointer;
                    bfpointer;
                }
            break;
            
            case '.':
                putchar(bfpointer[*locationOfPointer]);
                fflush(stdout);
            break;
                
            case ',':
                bfpointer[*locationOfPointer] = getchar();
                fflush(stdin);
            break;
            
            case '[':
                //printf("[\n");
                if (bfpointer[*locationOfPointer] == 0) {
                    if( jumpSearcher == 0 ) jumpSearcher = 1;
                    locationOfLoader++;
                    while ( jumpSearcher != 0 ) {
                        if ( bfCmd[locationOfLoader] == '[' ) {
                            jumpSearcher++;
                        }
                        if ( bfCmd[locationOfLoader] == ']' ) {
                            jumpSearcher--;
                        }
                        printf("%d %d",locationOfLoader,jumpSearcher);
                    }
                }
            break;
                    
            case ']':
                //printf("]\n");
                if (bfpointer[*locationOfPointer] != 0) {
                    if( jumpSearcher == 0 ) jumpSearcher = 1;
                    while ( jumpSearcher != 0 ) {
                        locationOfLoader--;
                        if ( bfCmd[locationOfLoader] == ']' ) {
                            jumpSearcher++;
                        }
                        if ( bfCmd[locationOfLoader] == '[' ) {
                            jumpSearcher--;
                        }
                    }
                    //printf("%d %d",locationOfLoader,jumpSearcher);
                }
            break;
        }
        
        locationOfLoader++;
    }
    //printf("%d",locationOfLoader);
    return bfpointer;
}

int clearString(char* strToClear) {

    strToClear[0] = '\0' ;
    return 0;
}

int main () {

    bfdata* bfInit (int *locationOfPointer, int *memoryInUse);
    bfdata* bfExecCmd (char* bfCmd,  int *locationOfPointer, int *memoryInUse, bfdata* bfpointer);
    int bfLoadCmd (char* bfCmdBuffer, char* bfCmd, int* jumpCount);
    int clearString(char* strToClear);
    
    int locationOfPointer, memoryInUse;
    bfdata* bfpointer = bfInit (&locationOfPointer, &memoryInUse);

    char bfCmd[125] = {'\0'};
    char bfCmdBuffer[255] = {'\0'};
    int jumpCount = 0;
    int i = 0;
    int j = 0;
    while(1) {
        printf(": ",jumpCount);
        for ( i = 0; i < jumpCount; i++ ) printf("    ");
        
        clearString(bfCmdBuffer);
        scanf("%s",bfCmdBuffer);
        fflush(stdin);
        //printf("%d",jumpCount);
        if (bfLoadCmd(bfCmdBuffer, bfCmd, &jumpCount) == 0) {
            bfpointer = bfExecCmd (bfCmd, &locationOfPointer, &memoryInUse, bfpointer);
            printf("\n");
            clearString(bfCmd);
        }
        //printf("%s",bfCmd);
    }
}

运行结果如下：

    

好了，一个带有基本内核的BF实时解释器就写完了，本文的上半部分也结束了。
在本文的中篇和下篇中，我们将探讨.bfk文件解释器、程序实时跟踪、调试器、纠错装置、图形界面的IDE以及改进型BF语言的解释器与开发环境的编写，敬请期待。[/size]