cucu: a compiler you can understand (part 1)

译者序：

最近在学习一些编译器的基本知识，就找到了这篇英文的博客，在csdn搜了一下貌似没有人翻译，所以我干脆翻译了算了，反正都是学习。

原文地址：http://zserge.com/blog/cucu-part1.html

cucu: 一个易于理解的编译器 (part 1)

让我们来讨论一下编译器吧。你有想过自己去写一个编译器吗？

我将会让你看到这是一件多么简单的事情！但这个博客的第一部分有点偏理论，所以希望你们能够保持耐心。

我们的目标

CUCU 是一个“玩具”编译器用来编译一个“玩具”语言。我希望这个玩具语言能尽可能的像标准C语言，因此一个正确的CUCU程序同样能够使用C编译器进行编译。当然，整个Ｃ语言标准时非常复杂的，我们这里的CUCU所使用的语法只是C语言的一小部分。

比如说，这里有一个有效的CUCU程序片段:

int cucu_strlen(char *s) {    int i = 0;    while (s[i]) {        i = i + 1;    }    return i;}

语法

We're about to define a grammar for our language. It's an important step, because everything in our compiler design depends on it.

接下来我们要定义我们这个编程语言的语法。这是一个重要的步骤，因为在设计我们编译器的时候将会依赖于这个语法。

让我们从上到下来设计语法。我们的源文件包含一个程序。什么是程序？根据经验我们可以知道，程序就是一个列表，包括变量声明、函数声明、函数定义等，比如：

int func(char *s, int len); /* function declaration */int i;                      /* variable declaration */int func(char *s, int len) { /* function definition */    ...}

让我们尝试着将它写成EBNF的形式（如果你不知道什么是EBNF也没关系，它看上去很直观）：

（译者：关于EBNF的详细信息请参考http://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F）

<program> ::= { <var-decl> | <func-decl> | <func-def> } ;

这个表示法说明：一个函数是一个重复的序列，这个序列中的每一项是变量声明、函数声明或者函数定义。那么，这些所谓的声明和定义又是啥呢？让我们继续往下走。

<var-decl> ::= <type> <ident> ";"<func-decl> ::= <type> <ident> "(" <func-args> ")" ";"<func-def> ::= <type> <ident> "(" <func-args> ")" <func-body><func-args> ::= { <type> <ident> "," }<type> ::= "int" | "char *"

因此，变量声明很简单：一个类型名加上一个标识符，然后在后面加上一个分号，就像我们经常在C语言中使用的那样。

int i;char *s;

函数声明稍微要复杂一点，首先是“类型+标识符”，然后在括号里可以有选择性的加上 <func-args>

函数的参数表，是一个用逗号分割开的“类型+标识符”的序列，比如：

char *s, int from, int to

Actually, trailing comma in CUCU is still allowed, but not required. It will just simplify our parser code.

The supported data types are only int and char *. Identifier is a sequence of letters, digits and an underscore symbol.

The only thing left is <func-body>. But let's talk about statements and expressionsfirst.

Statement is a smallest standalone element of the language. Here are valid statements in out language:

事实上，参数表最后的逗号在CUCU语言里是允许的，但不是必要的。之所以这么做是为了使我们分析代码变的简单。

语言所支持的类型只有int和char*，标识符是一串字母、数字或者下划线。

唯一没有说明的只有<func-body>. 但首先我们需要讨论一下语句（statements）和表达式（experssions）。

语句是指我们的语言中最小的独立元素。下面是一下有效的语句：

/* 这是一些简单的语句 */i = 2 + 3; /* 赋值语句 */my_func(i); /* 函数调用语句 */return i; /*返回语句 *//* 这是一些复合语句 */if (x > 0) { .. } else { .. }while (x > 0) { .. }

Expression is a smaller part of the statement. As opposed to statements, expressions always return a value. Usually, it's just the arithmetic. For example in the statementfunc(x[2], i + j) the expressions are x[2] and i+j.

So, looking back at <func-body>. It's just a valid statement (which is usually a block statement).

表达式是语句的一部分，它比语句更小。和语句不同的是，表达式总是会返回一个值。通常，表达式会是算数预算。比如在语句func(x[2], i + j)里，表达式是 x[2] 和 i+j。

因此根据上述分析，我们有:

<func-body> ::= <statement><statement> ::= "{" { <statement> } "}"                /* 语句块 */                | [<type>] <ident> [ "=" <expr> ] ";"  /* 赋值 */                | "return" <expr> ";"                | "if" "(" <expr> ")" <statement> [ "else" <statement> ]                | "while" "(" <expr> ")" <statement>                | <expr> ";"

下面是一些CUCU语言中可行的表达式:

<expr> ::= <bitwise-expr>            | <bitwise-expr> = <expr><bitwise-expr> ::= <eq-expr>                   | <bitwise-expr> & <eq-expr>                   | <bitwise-expr> | <eq-expr><eq-expr> ::= <rel-expr>              | <eq-expr> == <rel-expr>              | <eq-expr> != <rel-expr><rel-expr> ::= <shift-expr>               | <rel-expr> < <shift-expr><shift-expr> ::= <add-expr>                 | <shift-expr> << <add-expr>                 | <shift-expr> >> <add-expr><add-expr> ::= <postfix-expr>               | <add-expr> + <postfix-expr>               | <add-expr> - <postfix-expr><postfix-expr> ::= <prim-expr>                   | <postfix-expr> [ <expr> ]                   | <postfix-expr> ( <expr> { "," <expr> } )<prim-expr> := <number> | <ident> | <string> | "(" <expr> ")"

That's it. Did you notice the recursion in the expression notation? Basically, the notation above shows us the precedence of the operators from bottom to top: parens and square brackets are evaluated first, and assignment goes the last.

For example, according to this grammar an expression 8>>1+1 will be evaluated to 2 (like in 8>>(1+1)), not to 5 (like in (8>>1)+1), because >> has lower precedence than +.

注意到递归定义的表达式了吗？除此之外这些表达式还说明了运算符的优先级，从下到上优先级以此降低：括号和方括号的优先级较高，而赋值的优先级较低。

例如，根据语法定义，表达式 8>>1+1 的运算顺序将会是 8>>(1+1)), 而不会是 (like in (8>>1)+1), 因为 >> 的优先级要低于 +.

词法分析器

当我们解决了语法问题，我们差不多可以开始了。第一件事是做一个词法分析器。我们的编译器使用一个字节流作为输入，而词法分析器的作用就是将这个字节流分割成更小的符号（token），以便于后续的处理。词法分析器为我们提供了某种程度的抽象使得之后的解析器得以简化。

例如，一个字节序列 "int i = 2+31;"将会分成以下的符号：

inti=2+31;

在一个普通的词法分析器中，一个词素是一个由类型和值组成的二元组。因此，相对于以上的列表，我们更期望能得到一个如下的二元组<TYPE:int>,<ID:i>, <ASSIGN:=>,<NUM:2>,<PLUS:+>,<NUM:31>,<SEMI:;>。为了简便我们现在是通过值来反推类型，当然这是非常不严谨的。

词法分析器的主要问题是一旦一个字节从流中读取了之后，它就再也不能被重新放回流中。因此，如果我们读到了一个字节，而这个字节不能被加入到当前的符号中，这时候应该怎么办呢？我们应当把这个字节存到哪里，等待当前符号处理完成之后再去处理这个字节呢？

事实上，几乎任何词法解析器都有预读的机制。我们的语法很简单，因此我们只需要一个字节 - nextc当缓冲区就足够了。它存储一个从流中读取出来的但还没有被加入到当前符号中的字节。

另外，我必须在这里提个醒- 我在CUCU的代码的词法分析器中使用了很多全局变量。我知道这是个不好的习惯，但如果我把所有的变量都作为函数参数的话，这个编译器的代码看起来就不是那么的简洁了。

The whole lexer is just a single function readtok(). The algorithm is simple:

skip leading spacestry to read an identifier (a sequence of letters, digits and _)if it's not an identifier - try to read a sequence of special operators, like &, |, <, >, =, !.if it's not an operator - try to read a string literal "...." or '....'if failed - maybe it's a comment, like /* ... */?if failed again - just read a single byte. It might be another single-byte token, like "(" or "[".

Here's the whole CUCU sources we've got so far:

词法解析器的全部就是一个函数 readtok() 。而它的算法也很简单：

跳过开头的所有空格尝试读取一个标识符(一个字母、数字以及下划线的序列)如果发现不是一个标识符，尝试读取一些运算符，比如 &, |, <, >, =, !.如果不是运算符，尝试读取字符串文本，比如"...." 或者 '....'如果仍然失败，或许是一个注释，比如 /* ... */如果继续失败，尝试读取一个字节，或许是括号之类的字符，比如 "("或者 "["。

#include <stdio.h> /* for vpritnf */#include <stdarg.h> /* for va_list */#include <stdlib.h> /* for exit() */#include <ctype.h> /* for isspace, isalpha... */#define MAXTOKSZ 256static FILE *f; /* input file */static char tok[MAXTOKSZ];static int tokpos;static int nextc;void readchr() {    if (tokpos == MAXTOKSZ - 1) {        tok[tokpos] = '\0';        fprintf(stderr, "token too long: %s\n", tok);        exit(EXIT_FAILURE);    }    tok[tokpos++] = nextc;    nextc = fgetc(f);}void readtok() {    for (;;) {        while (isspace(nextc)) {            nextc = fgetc(f);        }        tokpos = 0;        while(isalnum(nextc) || nextc == '_') {            readchr();        }        if (tokpos == 0) {            while (nextc == '<' || nextc == '=' || nextc == '>'                    || nextc == '!' || nextc == '&' || nextc == '|') {                readchr();            }        }        if (tokpos == 0) {            if (nextc == '\'' || nextc == '"') {                char c = nextc;                readchr();                while (nextc != c) {                    readchr();                }                readchr();            } else if (nextc == '/') {                readchr();                if (nextc == '*') {                    nextc = fgetc(f);                    while (nextc != '/') {                        while (nextc != '*') {                            nextc = fgetc(f);                        }                        nextc = fgetc(f);                    }                    nextc = fgetc(f);                }            } else if (nextc != EOF) {                readchr();            }        }        break;    }    tok[tokpos] = '\0';}int main() {    f = stdin;    nextc = fgetc(f);    for (;;) {        readtok();        printf("TOKEN: %s\n", tok);        if (tok[0] == '\0') break;    }    return 0;}

如果我们把一个C语言的源文件作为这个词法分析器的输入，它将会输出一个符号的列表，每个符号一行。

搞定，让我们稍微休息一下，接着进入第二部分。