Chaofan

For the next train

标签： C语言

  • 构建Mao语言运行器－词法分析

    这个世界的本质是无序的。所以编程最广泛也是最常被讨论的用途就是处理在计算机看来什么意义也没有的字符串。而处理编程语言的源代码在其中是很特殊的一种，因为编程语言包含的信息按照一定的规则聚合，解析起来比自然语言容易得多。而处理编程语言的源代码的时候该干什么，取决于软件的目的以及这门语言本身的特性。

    好了，言归正传，说说这次的期末作业Mao语言吧。一开始很多同学估计还没反应过来是怎么一回事。以为做一个解释器只要用宏替换就可以了。另外一些人估计连解释器和编译器的区别都没有分清楚。讲道理的话，大一的期末项目不太可能要求学生做编译器的，那么多数据结构都没学，汇编也不懂，没法弄。

    那么什么是解释器呢？

    解释器是能够执行用其他计算机语言编写的程序的系统软件，它是一种翻译程序。 它的执行方式是一边翻译一边执行，因此其执行效率一般偏低，但是解释器的实现较为简单，而且编写源程序的高级语言可以使用更加灵活和富于表现力的语法。

    懂了没？一边翻译一边执行。读入输入然后处理的作业在之前也做过不少，所以有人想到一个一个“单词”地做。关键是，我们处理这些源代码的基本单位是什么？先来看看范例里的一段代码。

    int a;
double x, y;
int b, c, d;
a=5.5;
x=y=(1+a)*6.44;
a+4;
a=a/2;
print(a);
y=(c+6)*-(1+1);
print(y);
d=a/(2/5);
print(d);

    这段代码基本上涵盖了Mao语言所有能用到的符号。仔细观察可以发现，关键字只有int和double，如果把print写死进去那就是三个。程序中可以出现任意的空格，因此我们需要把这些空格要么去掉要么屏蔽掉。变量名可以是一个字母也可以是很多个字母和数字的组合，当作一个char来弄显然也不行。我们需要一个专门的过程来将源代码里的“多个字符”映射到一个单位里。我们理想的结果应该是生成一个更有结构的数据流，其中一个符号（int、变量名或者是运算符）是一个单位，没有空格的存在。这样的话，很多东西就方便很多了。

    这个扫描源代码生成结构化数据流的过程就叫做词法分析。大多数编译器或者解释器接收到源代码做的第一件事就是词法分析。词法分析生成的东西叫做token，记号还是符文还是什么，随便翻译。显然，我们要做词法分析，就要把整个源代码字符串遍历一遍，并且扫描完之后就可以把它丢掉了，之后的处理是针对这个数据流而不是纯文本进行的。在整个编译或者解释执行的过程中，对源代码或者它对应的信息我们需要过不止一趟 (pass)。多趟的处理也许对效率有影响，但是实现更加简单。所谓one-pass的编译器，很多时候只是作者的炫技之举。当然，对语法极其简单的Mao语言，这不是不能做，只是写得太杂乱就会失去很多乐趣。

    好了，如何定义我们的数据结构呢？比如：

    struct token {
    int type;
    char * content;
};

    这是最简单的形式。content表示什么自不必说，可以指变量名或者整数浮点数。而更多的固定形式的符号，我们直接用type表示，然后把content设为NULL即可。

    #define TOKEN_INT       1
#define TOKEN_DOUBLE    2
#define TOKEN_PRINT     3
#define TOKEN_VARIABLE  4
#define TOKEN_INTNUM    5
#define TOKEN_DOUBLENUM 6
#define TOKEN_COMMA     7
#define TOKEN_SEMICOLON 8
#define TOKEN_ADD       9
#define TOKEN_SUB       10
#define TOKEN_MUL       11
#define TOKEN_DIV       12
#define TOKEN_ASSIGN    13
#define TOKEN_LPAREN    14
#define TOKEN_RPAREN    15

    整个Mao语言的符号不超过这区区十五种。规定好了token的结构和type的取值，我们就可以开始扫描的过程了。

    开始这个扫描的过程应该不算是什么难事。我们从输入的第一个字符开始判断，就像《C程序设计语言》里常用的那样：

    char ch;
while ((ch = getchar()) != EOF) {
    /*
     * 对输入字符的类型进行判断
     * 如果是一个字符，我们进入处理字母集合（类型、print或变量名）的函数
     * 如果是加减乘除等符号，我们进入处理运算符的函数
     * 如果是数字或者点号，我们进入处理整数或浮点数的函数
     */
}

    那么对此，我们可以声明这样的一堆函数：

    void type_var(char ch);
void number(char ch);
void symbol(char ch);

    这些函数内部是如何运作的呢？举个例子：

    void type_var(char ch)
{
    char tmp[20];
    size_t index = 0;
    do {
        tmp[index++] = ch;
    } while ((ch = getchar()) != EOF && isalnum(ch));
    tmp[index++] = '\0';
    if (!strcmp(tmp, "int")) {
        /* 将当前流指向的token设置为TOKEN_INT */
    } else if (!strcmp(tmp, "double") {
        /* 将当前流指向的token设置为TOKEN_DOUBLE */
    } else if (/* 其他情况 */) {
        /* 对应的处理 */
    } else {
        /* 不是关键字，那么定义成变量名，TOKEN_VARIABLE */
    }
    ungetc(ch, stdin); /* 退回一个字符输入 */
    /* 流指针向前进 */
}

    显然，这个词法分析程序会自动获取能够最大接收的token，并且不需要手动写，自动就排除掉了空格，并且将每个变量名与逗号分隔了开来。

    由于Mao语言的符号数量很少，并且各个类型的token规则特意设置得很简单（浮点数甚至不包含科学计数法的形式）。写一个tokenizer还是非常容易的。不过又一个还没有提到的东西，就是词法分析整数或者浮点数的时候，前面的正负号会被识别成加减号。当然这个问题无关紧要，讲道理的话在后面的语法分析阶段也能解决。不过就当作一个练习吧。

    词法分析就到这，下次来说说语法树的事情。

  • 用C写内存管理真累啊

    今天C语言老师布置了期末的大作业，要求实现一个毛语言。由于我进教室的时候迟到了，所以并不知道老师在此之前说了什么。不过看了一下屏幕上展示的PDF，只是要求实现最基本的变量声明和计算、输入输出的功能。不过我想着，既然做就做好点，把扩展的功能都给加上去。

    思索一会后，我决定把项目中的一部分分离为infrastructure目录，包含一些常用的数据结构，比如链表、字符串、树，以后可能还有散列表。今晚上完毛概以后我就开始动手写，从链表开始（qlist）。虽然之前写过好几次，不过要用C一次写对不出bug还是一件不容易的事情。尤其是我还要在这个链表上模拟泛形。由于C语言没有像C++一样强大的模版，于是我只有用void*来表示数据，然后给链表的结构体里加上一个data_size的成员以表示数据的长度，再要求两个函数指针分别作为深拷贝和内存释放的方法。不过这样也是有问题的，那就是基本数据类型的开销太大了，操作起来也麻烦。比如我要给一个成员类型为int的链表插入，我还得专门定义一个变量，然后把它的地址传给拷贝函数。所以可以考虑一下用宏来解决这个事情。

    话说回来，clion确实是个挺好用的IDE.

  • 我所习惯的C/C++代码格式

    1.函数开始的大括号专起一行。

    int sample()
{
    return 0xA0246 * 0454;
}

    2.类定义和内部内联函数定义。

    class foo {
public:
    foo() : data(0)
    {}
    foo(int d) : data(d)
    {}
    void print()
     {  printf("%d\n", data);  }
private:
     int data;
};

    3.for、while、if等关键字后面1空格，且总是使用大括号。

    while (in != 0) {
    s += in;
}

    4.头文件使用的保护。

    #ifndef FILE_H
#deinfe FILE_H

// ...

#endif // FILE_H

    5.缩进4空格。

    6.类定义和实现、变量声明和函数定义勤注释。

    7.太多了，最基本的就这些。

  • Linux下程序创建进程

    进程是操作系统中运行的程序实例。而多进程程序和多线程程序相比，具有更健壮，更简单的特点。

    在GNU/Linux操作系统中，创建一个新进程，可以使用fork，clone函数以及使用exec函数族调用其他程序替换当前进程镜像。

    这里主要讲fork函数。

    fork函数的原型为：

    #include <unistd.h>

pid_t fork(void);

    pid_t是系统定义的类型，一般被定义为short int。

    这里看一个最简单的调用示例。

    #include <stdio.h>

#include <unistd.h>

int main(void)
{
    pid_t pid;
    pid = fork();
    printf("My process ID is %d.\n", getpid());
    return 0;
}

    这样就最简单的创建了一个子进程，并且打印出了进程的pid。

    fork函数是分裂执行的，这也就是fork（分叉）命名的原因吧。如何理解这个“分裂”呢，看这段程序。

    #include <stdio.h>
#include <unistd.h>

int main(void)
{
    pid_t pid;
    pid = fork();
    if (pid > 0) {
        printf("I'm parent process.\n");
        /* 父进程的pid大于0 */
    } else if (pid == 0) {
        printf("I'm child process.\n");
        /* 子进程的pid等于0 */
    } else {
        printf("Cannot create process.\n");
        /* 如果pid小于0，表示出错 */
    }
    return 0;
}

    内核在第一次调用fork()时，将当前进程的所有内存空间和文件描述符等资源复制一份给创建的子进程（实际上采用了“Copy-on-write”（写时复制），第一次试图对内存进行写操作的时候才复制，提高了效率）。所以fork调用后有2个进程在同时执行后面的代码。如何区分呢？

    在父进程中，pid变量被标记为一个正整数；而子进程的pid被标记为0；当然，当pid为负数时，系统只有1个进程运行，表示创建进程出错。

    如何证明这一点呢？看下面这个程序：

    #include <stdio.h>
#include <unistd.h>

int main(void)
{
    pid_t pid1, pid2, pid3;
    pid1 = fork();
    pid2 = fork();
    pid3 = fork();
    printf("I'm a process.\n");
    return 0;
}

    这个程序会打印出几个”I’m a process.”字符串？答案是8个（2的3次方）。如果再加一个fork答案就会是16个（2的4次方）。运行结果证明了这一点。第一次fork调用产生一个子进程，第二次两个进程各产生一个，第三次四个进程各又产生一个……所以结果是2*2*2=8个。（fork炸弹？哈哈）

    现在你会发现，调用fork()的程序需要ctrl+c才能退出。这是因为父进程在等待子进程退出。如果父进程在子进程结束之前退出了，那么子进程就会成为所谓的“僵尸进程”。

    要结束子进程可以使用wait函数。

    #include <unistd.h>

pid_t wait(int * status);

    返回退出子进程的pid。调用后可以从status了解到wait的调用状态。

    以下的宏可以用来校验status变量。

    WIFEXITED正常退出，值为true
    WEXITSTATUS返回子进程exit状态，为int
    WIFSIGNALED子进程是否因为信号结束，是则为true
    WTERMSIG返回子进程退出的信号号（上个宏为true时才有意义）
    评估wait状态所用的宏

    如果当前有多个子进程，系统怎么能知道我要结束哪一个呢？所以，有了waitpid函数。

    #include <unistd.h>

pid_t waitpid(pid_t pid, int * status, int options);

    pid参数表示需要等待结束的子进程。几种值的情况如下：

    >0等待pid的进程退出
    0等待任何一个与调用进程组ID相同的子进程退出
    -1等待任何一个子进程退出（相当于wait()）
    <-1等待任何一个组ID与pid参数绝对值相同的子进程退出
    waitpid的pid参数值

    options提供了一些额外的选项来控制waitpid，目前只支持WNOHANG和WUNTRACED两个选项，可以用|连接起来。

    WNOHANG，如果没有子进程退出，它也会立即返回，不会一直等下去。

    WUNTRACED，用于跟踪调试。

    如果不想用options，可以传一个参数0。

    waitpid的status多了两个校验的宏，不过仅在设置WUNTRACED后可用。

    WIFSTOPPED如果子进程已经停止，返回true
    WSTOPSIG返回使子进程停止的型号（上个宏为true时才有意义）
    waitpid增加的校验宏

    如果调用出错，返回-1，并且errno被设置成特定的值；如果WNOHANG被设置且没有子进程退出，返回0；否则返回子进程的pid号。

    不过，有时候不需要这么麻烦。

    #include <unistd.h>
#include <signal.h>

int kill(pid_t pid, int sig_num);

    kill用于向进程发送信号。pid的各种值情况如下表：

    >0信号发送到pid指定的进程
    0信号发送到调用进程同组的所有进程
    -1信号发送到除init外的所有进程
    <0信号发送到pid绝对值指定进程组中所有进程
    kill函数的参数pid的值

    还有函数raise，用于给自己发信号。

    #include <unistd.h>
#include <signal.h>

int raise(int sig_num);
/* 等价于 kill(getpid(), sig_num); */

    所以，终止子进程也可以这样：

    #include <unistd.h>
#include <signal.h>

int main(void)
{
    pid_t pid = fork();
    kill(pid, SIGKILL);
    return 0;
}

    这里讲了fork函数创建子进程的一些用法。关于exec函数族和信号，将会在以后的文章里说到。

    希望这篇文章能带给您以收获！

  • C语言中数值和字符串的相互转换

    整数->字符串可以使用stdio.h中的sprintf函数，有的人可能会说到itoa，但其实itoa不是C标准库的函数，是微软自己添加的。

    sprintf的原型是：

    int sprintf ( char * str, const char * format, ... );

    和printf用法相同。当然也可用于其它类型如double。

    例：

    char str[20];
int s = 1000000;
sprintf(str, "%d", s);

    字符->整数同样使用的也是stdio.h中的sscanf函数，stdlib.h中也有atoi和strtol可以进行转换。

    int sscanf ( const char * str, const char * format, ... );
int atoi ( const char * str );
long int strtol ( const char * nptr, char ** endptr, int base);

    sscanf和atoi的用法都很简单。值得一提的是strtol这个函数。第一个参数是源字符串，第二个参数用于接收非法字符串的首地址，第三个参数是转换后的进制。

    什么叫非法字符串的首地址呢？比如nptr的值是”1234f5eg”，base是10，endptr在调用后的值就是”f5eg”。如果base是16，那么endptr的值就是”g”（f和e是16进制的合法字符，而在10进制中却不是）。可以看出非法字符的类型和base有关。由于要修改指针的值，所以需要用到二重指针。另外，开头和结尾的空格会被忽略，中间的空格会被视为非法字符。

    例：

    char buf[] = "12435 fawr22g"
char *stop;
printf("%d\n", (int)strtol(buf,&stop,10));
printf("%s\n",stop);

    输出结果为

    12435

 fawr22g

    另外，给出一个atoi的实现（glibc里的atoi是直接用strtol实现的）：

    #include <string.h>
#include <ctype.h>

int atoi(const char *s)
{
    int sign = (s[0] == '-') ? -1 : 1;
    int i, j, res = 0;
    int b = 1;
    for (j = strlen(s) - 1; j > i; --j) {
        b *= 10;
    }
    for (i = isdigit(s[0]) ? 0 : 1; i < strlen(s); ++i) {
        res += (s[i] - '0') * b;
        b /= 10;
    }
    return res;
}