呐，文如标题，这次要说的是一次十分失败的装逼经历，或者说，一场惨痛的人生教训。有那么严重么？至少，对于新年的第一天和第二天的我来说，是这样的。

讲道理，在我看来，其实装逼本身就可以说是失败的。真正的强者不需要装逼，他们的强势永远都是一种自然的流露。当然，在弱者，或者说特定圈子之外的人，可能也会把这样的行为当成是装逼。就像，知乎上的很多习惯和流露的价值观，对于知乎社区的活跃用户来说，是无比正常的事情。但是对于一些微博或者贴吧上的网友而言，这些思维方式和语言习惯必是装逼无疑。

那我为什么还要说自己是装逼呢？

废话，因为我失败了啊。

事情是这样的，我再叙述一遍。软件学院大一上的C期末作业要求我们写一个解释器，要解释的语言被称作Mao，包含int和double两类变量的声明、表达式求值和print变量。其实一开始接到这个项目我是很高兴的。因为比起去年的JSON Parser来说，这个项目可以扩展的地方太多了。语言确实没有办法描述我的心情。那是一个星期二，下午无课，我跑到图书馆看了一个下午的编译原理。

「我要做一门真正的编程语言。」

从那天开始，直到2015年结束，可以说，我的脑子里从来没有忘过这事，偶尔梦里也梦到过。以至于我11月去无锡给我朋友过生日的时候，在路上因为突然想通了Mao语言的上下文无关文法，而突然哈哈大笑起来。

然后就是紧锣密鼓的设计和写代码。其实我不是一个执行力很强的人，很多想法都停留在脑海里要拖延很久才会去实现。这带来了很多问题。递归下降的语法解析器我从十二月下旬才开始写，由于是第一次写，代码删删改改，自己觉得满意了，结果对了（我当时是怎么判断出结果对的呢？）就停下来了。好，停下来之后又开始写对象系统，整个活生生朝着PHP的方向做。直到2015年的最后一天，我把对象的运算做好了之后，输入1+1+1测试，然后……

是的，我就是这么后知后觉。

我写的递归下降语法分析器，在解析表达式的时候，因为要考虑优先级，所以把包含相同优先级的运算式，划到上下文无关文法中同一类的非终结符里。举个例子，就像很多编译原理教材都会讲的一样，两个表达式加减的结果叫做term，两个表达式乘除的结果叫做factor，一个term可以这样定义：

term = term op-1 factor
     | factor

op-1 = '+'
     | '-'

在理论上，这是一个十分完美的结构，从这样的语法结构构造出的表达式树，也可以按照正确的执行顺序进行计算。比方说1-1-1，先算左边的1-1得0，再做0-1，最后得结果是-1. 因此第二个减号是树根，第一个减号是左子树的树根。这是左结合性的运算符。那么对于右结合性的运算符，比如乘方符号^，或者说赋值号=，这些是先算右边的，那么我们修改一下语法即可：

assignment = identifier assign-op assignment
           | expr

power = expr exponent-op power
      | expr

assign-op = '='

exponent-op = '^'

当我们计算表达式2^3^4的时候，顺序并不是跟加减乘除一样的，而是先算右边的3^4，得81，然后整个表达式的值是2^81，结果就不说了，因为写不下。

但是这样做有一个很大的缺陷，那就是我们的LL(k)解析器无法解析左递归的情况，会陷入无限循环。什么是左递归呢？就是上文提到的描绘左结合性运算符的文法形式。一个term是一个term加或减一个factor，但是这个term到底到哪里为止呢？我们的递归下降解析器，至少是理论上，做不到的。所以从文法上，我们需要移除左递归。当然，如果解析器是从右向左读的，那么也处理不了右递归。

移除左递归的过程可以说是范式化的，引入一个新的非终结符，修改一下规则，像这样：

term = factor term-rest

term-rest = null
          | op-1 term

这个看上去也很好啊，能够解决我们的问题。然而两者合在一起，问题出现了——移除左递归之后，程序解析到的树，结合性出现了问题！而事实上，我写得更蠢：

term = factor op-1 factor
     | factor

这样的递归下降解析器根本无法解析1+1+1这样的式子！它到第二个1处就停下来了！而当我发现这个问题的时候，时间已然是2015年的最后一个晚上了。

没有办法了，第二天早上起来试图改进，发现越改问题越过。中午决定放弃，推倒表达式解析重来。其他像for、while等写好的语法也暂时搁置下来。撸了一个下午到晚上，在1月2日前完成了作业。

然而好景不长，第二天晚上当我写好文档准备交的时候，又发现bug了！我的程序不能正确处理表达式开头的负号。简单说就是，我的程序会自动“分划”输入的表达式。为了解决负号的问题，程序会判断当前表达式开头是不是有负号，如果有的话，就整个表达式取负。出发点是对的，但是后面一遇到加减或者各种叠加的括号，问题就来了，比如会把-1+2的结果当成-3.

剩下二十分钟，真没办法了，先交吧。

然后我改到了两点。

讲道理，我感觉自己真的没有资格参加答辩。

就是这样。

好了，前面我们说到了词法分析的过程。如果你按照我的思路进行的话，现在你已经可以把源代码转换成一个一个的词法单元，也就是所谓的token了。接下来要做的就是按照我们人为设定好的语法规则把这些词法单元组织起来。我们前面说过，Mao语言的语法结构极其简单，只有声明变量、表达式和print输出三个部分。而表达式所包含的内容也只包括加减乘除和括号。更关键的是它是保证输入的代码不会出错的。（当然你要满足程序对于健壮性的要求那就是另一回事了）

首先从变量的声明开始讨论起。Mao语言里只有int和double两种类型。所以我们可以一句一句地读取，直至分号结束。

struct token tkindex;
while (!istokenend(tkindex = gettoken())) {
    /* 你要记住这是伪代码，不要问我这个函数怎么来的 */
    if (tkindex.type == TOKEN_INT) {
        while (!istokenend(tkindex = gettoken())) {
            if (tkindex.type == TOKEN_VARIABLE) {
                /* 把这个名字和类型加到变量列表里 */
            } else if (tkindex.type == TOKEN_COMMA) {
                /* 如果是逗号，继续前进 */
                continue;
            } else if (tkindex.type == TOKEN_SEMICOLON) {
                /* 遇见分号，声明语句结束，循环停止 */
                break;
            }
        }
    } else if (tkindex.type == TOKEN_DOUBLE) {
        /* 跟上面一样玩 */
    } else if (/* 其他类型 */) {
        /* 其他的处理代码 */
    }
}

为什么可以写得这么简单？因为变量声明的时候保证没有带等号的初始化语句哦。

变量定义还是很简单的事情，重头戏在于表达式的求值。就算是后面的print语句，你不能保证它不会给你来个print(a+b)或者直接print(1*3/2)，所以要先把表达式求值做好才能实现输出语句。（注：有同学指出需求文件里只说了print不会输出表达式，只会输出变量，这样就更容易咯）

如何给表达式求值呢？参考文档里给的暗示方法，是把中缀表达式转换为后缀表达式（逆波兰表示法），其中要用到所谓的调度场算法。然后利用栈来求解。这个方法不难，不过我们这里为了程序的可扩展性和方便理解，决定采用树的方式来实现。并且这里的树还是最简单的一种情况，即二叉树。如图：

所以，你以为我会这样老老实实写个结构：

struct expr_node {
    int type;
    char * var_name;
    union {
        int ival;
        double dval;
    };
    struct expr_node * left_child;
    struct expr_node * right_child;
};

哼哼，想错了。在这个话题上，为了说明问题，我们用不着那么麻烦。

我在软件工程学生如何学好C语言？这个问题的回答里面说过，理解数据结构不要过分机械地非要做一堆结构体和指针来模拟。计算机科学的核心是抽象。把握好抽象然后再来特化到适合特定场合的结构。所以呢，还是用数组吧。

什么？数组不是顺序存储的结构吗？naive，我们可以这样定义：

• 数组的第一个元素，可以看作整个树的头
• 对于任意第n个元素，它的左子节点是第2n个元素，右子节点是第2n+1个元素
• 类似地，对于任意第n（不论奇偶）个元素，它的父节点编号是n/2

对于这棵树，我们可以稍微分析一下。这棵二叉树每一“层”包含的元素数量是2^n个。所以我们给这个等比数列求一个和，结果就是2^n – 1次方。也就是说对于一个10层的二叉树，我们需要1023个空间的数组。其实也不是很大，而且我们也不太可能出现一个需要10层的表达式数……好吧，如果你实在不放心，C99标准支持以变量初始化数组，自己先感受一下再开数组吧。

好了，数据结构准备好了，我们可以开始构建这个树了。讲道理说语法树有点言过其实，我们这里构建树的过程连什么LL(1)都用不到。我们来思考一下，假如我是一台计算机，我要怎么计算公式k * (a+c) + (j=3)呢？

你也许会说，我们从k开始，k右边的第一个符号就作为树根。但是加减乘除是有优先级的，最后算的应该是加号。注意，我们给这个表达式树求值是自上而下递归求值的，我们把下层计算好之后再把结果返回给上层来计算。所以我们应该以哪个符号开始呢？嗯，第一个优先级最低的符号。在这里，我们的最低优先级的符号是等号，其次是加减，最后是乘除。

等等，貌似有点不对。对于上面的那个等式，如果我们要搜到第一个优先级最低的符号也就是等号，那逻辑不对啊。嗯，因为上面我们没有考虑到括号。所以修正一下上面的规则——第一个括号之外的优先级最低的符号。你需要定义一个变量来记录当前是否外面还有括号。唔，是“第一个”吗？我想应该是最后一个吧，因为在你搜索到最后一个优先级最低的符号之前，是不知道当前位置上的符号是不是最后一个的。像a=1+1这种当然好判断，有等号就行了，可是比如a*21/b+11我怎么知道后面还有没有更低的呢？所以，应该改成——最后一个(括号之外的(优先级最低的(符号)))。（打括号是为了好断句）

好了好了，我们已经把“寻找树根”的任务搞定了。任务已经完成了一半了。什么，你不相信？我们构造这个树是递归的喂！我们只要找到树根，然后正确分划，这个树就搞定了。这就是递归的力量。So，我们再来讨论分划的问题。其实分划挺简单的，我们已经找到了那个“树根”的token，然后parse它左边的部分和右边的部分。

空话说得太多没用，我们来讨论下具体的实现。根据上文的思考，我们可以总结出从token流产生语法树的若干规则：

• 如果整个串中只有一个token，是数或者变量，那么这个表达式树的值就是这个数或者变量的值
• 否则，当前表达式树的值是左子树的值同右子树的值经过计算的结果，计算的方式由树根类型决定
• 树根定义为当前token流中不在任何括号内的最后一个优先级最低的符号，左子树是从token流开始一直到树根的所有内容，右子树同理
• 如果有括号，把括号内内容当作一个整体

由于叙述需要严谨性，所以听起来很复杂。其实整个的实现过程非常的清晰明了，我们来举个例子说明：

对于表达式foo = sample * (3 + 5)而言，我们的搜索过程是这样：

1. 从左至右找到最后一个不在括号内的最低优先级符号“=”，将其作为树根。
2. 树根左边的子token流里只有一个变量foo，所以左子树的值就是foo，停止。
3. 树根右边最后一个不在任何括号内优先级最低的运算符是“*”，将其作为子树的树根。
4. 子树树根的左边的token流也只有一个内容，就是sample变量，所以同样停止搜索。
5. “*”右边的括号是一个整体，我们在括号内部搜索不在任何“括号”（打引号是因为这里的“不在”是指不在这个括号内部的另外的括号里）内的最低优先级运算符，找到了，是“+”。
6. “+”左右都各是一个数，所以这两个子树停止搜索。

如果把这棵二叉树表达为一个数组，我们的数组结构是这样（编号表示下标，C语言的话要全部减1）：

1. 符号 =
2. 变量 foo
3. 符号 *
4. （空）
5. （空）
6. 变量 sample
7. 符号 +
8. （空）
9. （空）
10. （空）
11. （空）
12. （空）
13. （空）
14. 数值 3
15. 数值 5

之所以会有那么多空位是因为数或变量是没有子节点的，而数组的话必须要把它们的空间留足。好了，我们解决了理论上生成树的问题，如何用代码来实现呢？首先要面对的一个问题是，不管我们如何递归处理这个表达式，它始终都是一个整体，比如上面，当我们在创建符号“*”的左右子树的时候，为什么不会搜索到“=”那里去呢？所以我们需要两个变量，来标记我们可以搜索的token范围。如果你觉得我说的话很晦涩的话，那是因为我没说清楚。想想子字符串吧，一样的道理。

struct expr_node tmp_tree[128];
struct token stream[1000];
/* stream数组假设已经经过了词法分析阶段的输入 */
/* 为了说明问题，我才使用的全局变量 */
void create_tree(size_t tkstart, size_t tkend, size_t tree_root)
{
    if (tkstart == tkend) {
    /* 如果整个流只有一个内容 */
        if (stream[tkstart].type == TOKEN_INTNUM) {
            tmp_tree[tree_root].type = TOKEN_INTNUM;
            tmp_tree[tree_root].var_name = NULL;
            tmp_tree[tree_root].ival = atoi(stream[tkstart]);
            /* 结构体中的匿名联合体是C11标准支持的新语法，可以直接访问它的内部成员 */
            /* 这里我们假设在词法分析阶段对于数保存的是它们的字符串形式 */
        } else if (stream[tkstart].type == TOKEN_DOUBLENUM) {
            /* 同样处理double的情况 */
        } else if (stream[tkstart].type == TOKEN_VARIABLE) {
            /* 变量的情况也是类似，只不过需要保存它们的名字 */
        }
    }

    int parentheses = 0;
    size_t lowest_token = tkstart;
    /* 在没有出问题的情况下，第一个token不可能是运算符，所以可以专门规定非运算符的运算符优先级最高 */

    for (size_t i = tkstart; i <= tkend; ++i) {
        if (is_operator(stream[i])) {
            if (priority(stream[i]) < priority(stream[lowest_token] &&
                !parentheses) {
                /* is_operator和priority都是自己定义的宏 */
                lowest_token = i;
            }
        } else if (stream[i].type == TOKEN_LPAREN) {
            /* 左括弧，标记变量加一 */
            ++parentheses;
        } else if (stream[i].type == TOKEN_RPAREN) {
            --parentheses;
        }
    }

    create_tree(tkstart, lowest_token - 1, tree_root * 2);
    create_tree(lowest_token + 1, tkend, tree_root * 2 + 1);
}

这段构造树的代码原理清晰，但是其实它是有问题的：

• 如果一个表达式整个被括号包住，那么它是无法处理的，因为自始至终变量parentheses不为0
• Mao语言的文档里有写y=(c+6)*-(1+1)这样的表达式，而我们的程序无法处理两个符号连在一起的情况

解决第一个问题，可以用一个简单粗暴但是很脏的办法。所有带括号的表达式，最后都会递归到一个括号从前往后包住的形式。所以如果我们发现第一个token是左括号，我们识别一下是不是从头到尾都被包住了，如果是，就再去掉括号往下识别。

第二个问题，要解决需要我们在识别lowest_token的时候修改一下算法。所谓’+’和’-‘，如果前面有其他非括号的符号，那必然是正负号，否则是加减号。所以，如果发现加减的上一个有运算符，那就把正负号连上作为子树。然后，如果开头是加减号，那就自动补0.

计算的话，很简单的。用一个switch…case语句分开判断当前是什么符号，default表示是数或变量。类型转换的事情交给编译器就好，你要负责的只是判断这个变量应该是什么类型。什么，一个函数不能返回多种类型的值？那可以返回struct嘛，哈哈哈……

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

好了，言归正传，说说这次的期末作业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还是非常容易的。不过又一个还没有提到的东西，就是词法分析整数或者浮点数的时候，前面的正负号会被识别成加减号。当然这个问题无关紧要，讲道理的话在后面的语法分析阶段也能解决。不过就当作一个练习吧。

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