有哪些关于c4 - C in four function 编译器的文章?

如题 rswier/c4 · GitHub
关注者
457
被浏览
7341
原问题:
有没有关于c4 - C in four function 编译器的文章? 看不懂

不知道有没有,不过没有的话写一篇就有了呗 ^_^
下面 @李凌 的回答提到的系列博文写得还不错,有条理的剖析了C4的各个部分。
下面 @Comzyh 的回答提到的注解版代码也不错,赞一下。
可以先读他们的回答,再回来补充点他们没提到的背景知识。
说来还有Reddit讨论:C4 - C in 4 functions

(下面的文字显然比C4的代码长多了…没耐心读的话还是请直接去啃代码吧 >_<)

===============================================

前言

许多人推荐C4给想实现一个简单的类C语言的初学者读,但不知道这些推荐它的人们有多少是真的完全读懂了C4之后才推荐的。

GitHub - rswier/c4: C in four functions
Robert Swierczek所写的原始版C4是一个适合有经验的人阅读、把玩、鉴赏的实验作品。它是个精巧的编译器虚拟机(解释器)。它遵循“极简主义”,只用尽量少的变量和函数,只最小限度的使用C语言的功能,并且只实现自己使用了的功能,为了能“自举”——用自己编译并运行自己。

这导致一些本来用更丰富的C语言功能可以更清晰描述的逻辑,在C4里实现得略微绕弯——知道的人一眼就能看出来它在干什么,但完全没头绪的初学者读它可能像在读密码一样。
所以,其实要完整理解C4到底是如何实现的,与其一开始就一口气钻进代码里然后碰得满头灰,还不如先读读一些入门的编译原理书,了解一下编译的过程中会经历哪些步骤,使用怎样的数据结构,然后再回到C4里去寻找那些步骤和结构。

后续有别人写的一些改进版在不同方面增强了原版C4的功能,例如Dmytro Sirenko版C4把解释器改为针对x86的JIT编译器: GitHub - EarlGray/c4: x86 JIT compiler in 86 lines
Robert Swierczek自己也有在C4的基础上做改进版,例如最近的C5添加了AST:AST + Code Generator · rswier/c4@d8e61a8 · GitHub
下面都还是以原始版C4为准来讲解。本文具体使用的C4版本是:c4/c4.c at e78a343e1d71fd9e96c2e1860735fdc19ef58e8f · rswier/c4 · GitHub <- 如果发现下面有链接的行号对不上我的描述的话,请切换到这个版本来看。

在“极简主义”的路上,下面这几个C编译器是从“弱”到“强”——“弱”这里指更普通的、易于理解的设计;而“强”则指把许多步骤/结构糅合在一起,虽然代码简单,但语义高度浓缩、不易于理解的设计:
LCC < TCC < C4 < OTCC
所以如果不想先读啥虎书龙书,而还是想先从一个实际编译器的资料和代码着手学习的话,先从LCC或者TCC开始会更合适一些。

国内有王博俊编写的《自己动手写编译器、链接器》一书,介绍的也是简易的C编译器SCC(Simple C Compiler)及配套链接器的实现。这个编译器比早期版本的TCC要简单一些,如果对TCC感兴趣但是想读中文资料的话,可以试试从这本书开始。
当然这SCC存在抄袭TCC的争议。我不知道SCC作者的背景如何,是否存在主观上抄袭TCC的情况,但是这几点事实是同时存在的:
  • TCC在先,SCC在后;
  • SCC源码中存在一些与TCC完全一致的代码,从名字到顺序到结构都一样,另外有些不是完全一致的则是SCC的比TCC的略为简化一些但仍然有对应关系;
  • TCC以LGPL许可证开源,SCC作者声称拥有完全版权,仅公开源码供读者以学习研究用途使用。
这是不是抄袭大家可以自己有判断。这里就不多跑题了。关于SCC请到相关问题去讨论:

===============================================

C4所实现的C语言子集

C4到底实现了C语言的哪些功能?或者说,哪些C89/C99的功能是它不支持的?

这里先列举几个C4实现上的例子。这些例子都影响到(简化了)C4的实现:
  • 忽略预处理指令:遇到 '#' 就忽略当前整行代码 c4/c4.c at master · rswier/c4 · GitHub。像是说C4要编译自己的时候,其实会把开头的#include全忽略掉,然后在main()里hack一下,把依赖的外部函数先硬插进符号表里。
  • 只支持int、char及对int或char的一级或多级指针类型,不支持typedef或结构体(struct) / 联合体(union)。所以语法分析时不需要查符号表来判断一个用户自定义的标识符是不是类型——肯定不是。
  • 只支持匿名枚举类型,实际上也就是用于批量声明常量用。对有名字的枚举类型,忽略它的名字。
  • 把返回void的函数当作返回char处理。
  • 变量必须先声明再使用;变量声明不能带初始化表达式
  • 作用域只有全局和局部两种。局部变量必须全部在函数体的最开头声明,不能在中间声明,也不支持块作用域。所以符号表只要一个简单的线性符号表足矣,不需要为了支持嵌套作用域而实现嵌套符号表。
  • 不支持数组的声明,不过还是支持通过指针做下标访问。
  • 没有实现do-while、for、switch这些可以用更简单的if和while实现的控制流语句。
  • 不支持goto,不支持label,不支持break或continue。
  • 不支持前向声明(forward declaration)。于是也就没办法做相互递归(mutal recursion)的函数调用了。这么一来就算想完全使用递归下降来实现语法分析也做不到,因为递归下降在分析表达式时必然会出现相互递归的情况,例如分析被括号包围的表达式。
  • 虽然语法上支持强制类型转换,但实际上既不做充分的类型检查,也不充分执行实际的类型转换。
对最后一点举个简单的例子:
$ ./c4 -s -d xx.c
1: int main() {
2:   int i;
3:   char c;
4:   i = 97;
    ENT  2
    LEA  -1
    PSH 
    IMM  97
    SI  
5:   c = (int***) i;
    LEA  -2
    PSH 
    LEA  -1
    LI  
    SC  
6:   i = (char) i;
    LEA  -1
    PSH 
    LEA  -1
    LI  
    SI  
7:   printf("%d\n", c);
    IMM  1150976
    PSH 
    LEA  -2
    LC  
    PSH 
    PRTF
    ADJ  2
8: 
9:   return 0;
    IMM  0
    LEV 
10: }
    LEV 
11: 
这种类型对不上的代码C4也会毫无踌躇的编译并执行…

===============================================

C4的一段例子

问题评论里,显然有同学对下面这段代码陷入了深深的困惑:
70行,识别标识符那里,tk = tk * 147 + *p++; 和后面的看不懂

c4/c4.c at master · rswier/c4 · GitHub
    else if ((tk >= 'a' && tk <= 'z') || (tk >= 'A' && tk <= 'Z') || tk == '_') {
      pp = p - 1;
      while ((*p >= 'a' && *p <= 'z') || (*p >= 'A' && *p <= 'Z') || (*p >= '0' && *p <= '9') || *p == '_')
        tk = tk * 147 + *p++;
      tk = (tk << 6) + (p - pp);
      id = sym;
      while (id[Tk]) {
        if (tk == id[Hash] && !memcmp((char *)id[Name], pp, p - pp)) { tk = id[Tk]; return; }
        id = id + Idsz;
      }
      id[Name] = (int)pp;
      id[Hash] = tk;
      tk = id[Tk] = Id;
      return;
    }

这里正好用到了C4里的若干“隐秘”的设计,懂的人一眼就知道这是啥,但是…这到底是在干嘛呢?

先让我把这段代码改写为功能等价的伪代码:
// global declarations

typedef struct {
  int token;  // token kind of this symbol
  int hash;   // hash code of this symbol
  char* name; // the actual string contents of this token
  int class;  // storage class - global / local / numeric literal / function / system function
  int type;   // type of the variable - int, char, ptr
  int val;    // For global variable: index into data section
              // For local variable: index from base pointer into data section
              // For numeric literal: integer value of the literal
              // For function: offset into code section of the bytecode
              // For system function: opcode for the system function
  int hclass; // "backup slot" of `class' for global variable hidden by a local
  int htype;  // "backup slot" of `type' for global variable hidden by a local
  int hval;   // "backup slot" of `val' for global variable hidden by a local
} symbol_t;

symbol_t* id;  // currently parsed identifier
symbol_t* sym; // global symbol table: a closed hash table implemented by linear search

// in main()
// poolsz = 256*1024; // arbitrary pool size
// sym = malloc(poolsz / sizeof(symbol_t));

////////////////////////////////

// helper functions

int is_valid_identifier_start_char(int c) {
  // [a-zA-Z_]
  return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '_';
}

int is_valid_identifier_char(int c) {
  // [a-zA-Z0-9_]
  return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_';
}

int is_symbol_allocated(symbol_t* s) {
  return s.token != 0;
}

int is_symbol_equals(symbol_t* s, char* str, int length, int hash) {
  return hash == s.hash && strncmp(s.name, str, length) == 0; 
}

void initialize_symbol(symbol_t* s, char* str, int hash) {
  s.name = str;
  s.hash = hash;
  s.token = Id;
}

symbol_t* find_or_insert_symbol(char* str, int length, int hash) {
  symbol_t* current_symbol = sym; // start searching from the start of the linear symbol table
  while (is_symbol_allocated(current_symbol)) {
    if (is_symbol_equals(current_symbol, str, length, hash)) {
      return current_symbol;
    }
    current_symbol++; // try the next entry in the symbol table
  }

  // Otherwise, we've found a entry that hasn't been used yet.
  // Initialize a new entry here.
  initialize_symbol(current_symbol, str, hash);
  return current_symbol;
}

////////////////////////////////

  // identifier case:
  else if (is_valid_identifier_start_char(token)) { // [a-zA-Z_]
    char* start_of_identifier = current_position - 1; // the current_position has already advanced by 1
    int hash_code = token;

    // get the rest of the identifier, and compute a hash code
    while (is_valid_identifier_char(*current_position)) { // [a-zA-Z0-9_]
      hash_code = hash_code * 147 + *current_position;
      current_position++;
    }

    // do a final hash
    int length = current_position - start_of_identifier;
    hash_code = (hash_code << 6) + length;

    // track the current symbol in global variable 'id'
    id = find_or_insert_symbol(start_of_identifier, length, hash_code);
    // track the current token kind in global variable 'tk'
    tk = id.token;
    return;
  }
看看是不是就清楚一些了?这个改写的版本如果看不懂的话就真的得回去补基础了嗯。

我为了让代码能直接反映语义,把变量名都加长了,例如把 'p' 改为 'current_position';另外也把一些“多用途”的变量分离为不同的变量,例如 'tk' 在C4里有时候是当前读到的字符,有时候是hash_code,有时候又是真正的token kind…也难怪会有人觉得难解。

C4的代码里,最“难解”的地方之一恐怕就是这神奇的“id”全局变量的使用了。
C4没有实现struct / union功能,所以自身的代码也避免使用它。但是它所使用的“符号表”(symbol table)却需要一种表示“符号”内容的结构体。怎么办?
它用了一种很“直观”的变通办法:用数组代替结构体。

C4一开头就有这么一个声明:
// identifier offsets (since we can't create an ident struct)
enum { Tk, Hash, Name, Class, Type, Val, HClass, HType, HVal, Idsz };
而在后面的实现中,可以经常看到这样的代码:
id[Tk] = Id;
id[Hash] = tk;
id[Name] = (int)pp;
id[Class] = Loc;
id[Type] = INT;
而这 'id' 是个全局变量:
int* id,      // currently parsed identifier
这用得岂不是很怪?别着急,继续看下去。
其实 id 总是指向 sym 全局变量为开头的一个 int 数组。该数组就是C4所使用的“符号表”。而这个数组的结构并不只是一个扁平的int数组,而是:
sym ->  [0] [ [0+Tk    ] ] //<- sym + 0*Idsz
        [1] [ [0+Hash  ] ]
        [2] [ [0+Name  ] ]
        [3] [ [0+Class ] ]
        [4] [ [0+Type  ] ]
        [5] [ [0+Val   ] ]
        [6] [ [0+HClass] ]
        [7] [ [0+HType ] ]
        [8] [ [0+HVal  ] ]
        [9] [ [1+Tk    ] ] //<- sym + 1*Idsz
       [10] [ [1+Hash  ] ]
       [11] [ [1+Name  ] ]
       [12] [ [1+Class ] ]
       [13] [ [1+Type  ] ]
       [14] [ [1+Val   ] ]
       [15] [ [1+HClass] ]
       [16] [ [1+HType ] ]
       [17] [ [1+HVal  ] ]
       [18] [ [2+Tk    ] ] //<- sym + 2*Idsz
       [19] [ [2+Hash  ] ]
       [20] [ [2+Name  ] ]
       [21] [ [2+Class ] ]
       [22] [ [2+Type  ] ]
       [23] [ [2+Val   ] ]
       [24] [ [2+HClass] ]
       [25] [ [2+HType ] ]
       [26] [ [2+HVal  ] ]
       [..] [ ...        ]
在原版C4代码的第74行开始的代码就体现了这种结构的用法:
      id = sym;
      while (id[Tk]) {
        if (tk == id[Hash] && !memcmp((char *)id[Name], pp, p - pp)) { tk = id[Tk]; return; }
        id = id + Idsz;
      }
其实就是让id先指向sym所指向的int数组,然后每轮循环去通过 id[固定下标] 去访问这数组里的结构,如果循环还没结束的话就让id步进Idsz这么多个元素——走到下一个结构去。
其实这就是模拟了一个“包含9个字段的结构体”的数组而已。如果能用C的struct语法,那么大致就会用我上面改写的版本的方式来写,直接声明出合适的struct结构。

如果有同学觉得这种模拟结构体的做法很奇葩的话,您可能会觉得更意外这种做法在生产代码里也不罕见。
例如说,HotSpot VM里就有个用short[]数组来模拟结构体的地方:
jdk7/jdk7/hotspot: 9b0ca45cd756 src/share/vm/oops/instanceKlass.hpp
  // Instance and static variable information, 5-tuples of shorts [access, name
  // index, sig index, initval index, offset].
  typeArrayOop    _fields;
真糟糕(掩面


这里还有一点“作弊”的地方,就是当使用 id[Name] 时,这个表达式的类型是 int ,但实际上它存着的是一个 char* 。所以写入和读出时都要做强制类型转换。
这种写法也就注定了它只能用在 int 与 char* 都是一样宽的环境中——通常就是32位的环境。这种假设贯穿于C4的代码中。
——如果在64位环境上运行,那就得烧炷香希望malloc()返回低32位(< 4GB)地址空间的值了…不然就得呵呵。

我在64位的Mac OS X上跑C4的时候,得这样编译:
$ clang -g -m32 c4.c -o c4
(-g是可选的,这里只是为了调试方便)
这样运行hello.c就正常:
$ ./c4 hello.c 
hello, world
exit(0) cycle = 9

不加-m32就会默认用-m64,那样编译出来的C4运行个hello.c就会:
$ ./c4 hello.c 
Segmentation fault: 11
…呵呵

===============================================

整体编译流程

一个简单的类C编译器,忽略开头的预处理(preprocessing)和后续的汇编(assembling)与链接(linking)动作的话,其工作流程从概念上可以如下所述:
   [ 输入的源代码 ]
-> 词法分析(lexical analysis) -> [ 单词流(token stream) ]
-> 语法分析(syntactic analysis / parsing) -> [ 语法树(syntax tree) ]
-> 语义分析(semantic analysis) -> [ 标注过的语法树(annotated syntax tree) ] + [ 符号表(symbol table) ]
-> 代码生成(code generation) -> [ 目标代码(object code) ]

上面每一行都是一“趟”(pass)——遍历一遍整个输入的程序。每趟在遍历时都使用上一趟生成的数据作为输入,而不必每次都在原始输入的源代码文本上遍历。

其中,词法分析与语法分析通常在实际实现中是混在同一趟中做的。语法分析器驱动词法分析器,从后者“拉”(pull)出单词(token)来。

语法分析过后,生成的树形数据结构有这么些叫法:
  • 语法树(syntax tree):或者叫“具体语法树”(concrete syntax tree)。通常意味着保留了输入源代码的大部分内容的、根据语法组织起来的一种树形结构,可能包括注释、括号、空白等内容。IDE用于支持语法高亮、代码编辑等功能的语法分析器可能会生成这样的树,因为注释之类的内容对用户编辑来说还是有用的。
  • 语法分析树(parse tree):通常跟“语法树”是同一个意思。不过这种叫法的侧重点意味着比“语法树”(syntax tree)更强调语法分析器的执行顺序对树的结构的影响。通常在教科书讲解概念时会用到,但甚少用于实际的编译器。
  • 抽象语法树(abstract syntax tree,AST):实际编译器里最常见的形式。与语法树相比,它会抛弃掉具体语法中一些对已经形成了树的形状后对语义无关紧要的语法细节,例如注释、括号、空白,以及可能会压缩掉一些不影响语义的语法层次结构。

AST可谓是编译器用于表达程序结构的最重要的一种数据结构了。但是编译器是否一定要生成它才可以走完整个编译流程呢?答案是否定的。

对XML处理有一定了解的同学可能会听说过,XML有两大种处理方式,一种是“文档对象模型”(DOM),另一种是事件响应模型(SAX)。
前者其实就是把XML解析(parse)成一棵AST,并把AST叫做了DOM。整个XML文档的内容都会被转换为树形结构,便于后续代码多次遍历该文档树做各种读写操作。
而后者很有趣:与其把XML文档生成为一个实际的树形结构,每当它解析完一个标签的所有内容时就会发出一个事件,而用户代码可以注册事件监听器(event listener)去响应这些事件做具体的动作。这种做法让XML的树形结构隐含在了事件触发的顺序中,而不需要生成显式的树形数据结构,适合只对XML文档遍历一次时使用,无论在内存占用还是执行速度上都会比DOM方式在同样只遍历一次的场景快。

SAX模型,用编译原理的术语说,就是一种“语法指导翻译”(syntax directed translation,SDT)。知乎上有这个话题:语法制导翻译 - 全部问题

C4的编译器部分的核心思想就是通过SDT把上述编译流程一股脑塞到同一趟中,实现所谓的“单趟编译器”(single-pass compiler)。所以C4的编译流程实际是:
   [ 输入的源代码 ]
-> 词法分析 / 语法分析 / 语义分析(把声明记录到符号表 / 记录声明类型 / 记录表达式类型等) / 代码生成 -> [ 目标虚拟机代码 ]

单趟编译器由于把语义分析和代码生成的各种逻辑都混入到语法分析的过程中,代码通常都是高度浓缩而难懂的。C4自然也不例外。

如果想把这种编译器的代码写得便于理解一些,可以从语法分析器提取出类似SAX模型的API,把嵌入的语义动作以回调函数的方式剥离到外面去,这样就可以让语法分析器的代码尽量保持干净,并且让某些相关的语义动作代码可以组织在一起。Clang的Parser与Sema就是这样在同一趟执行,但代码被分离开的:How Clang handles the type / variable name ambiguity of C/C++

大家可能留意到了,上面我写的C4的编译流程,最后生成的是一种虚拟机的代码。那有没有可能让它不生成任何目标代码,而是直接边做语法分析边解释执行呢?

答案是肯定的。这其实就是把解释器也通过SDT整合到语法分析中。
早期的PHP就是这样实现的。也有比较奇葩的JavaScript引擎也这样实现,例如TinyJS / Espruino。最近大家在讨论的许式伟的qlang的自举版本也是这样实现的:qlang/qnlang.qn · GitHub
这种做法就比C4更加浓缩而难懂了,而且也意味着如果要重复执行某段代码(例如循环)就得每次执行都重复对那段代码做语法分析,而如果要条件执行某段代码(例如if-else)则无论是需要执行还是不需要执行的分支都得语法分析并解释过去。
所以比较正常的、考虑执行效率的编程语言实现是不会采用这么极端的方式的。
不过这种方式用来实现简单的计算器倒是不错。我这里也放过一个Bison的例子:bison的运算符优先级一例

初学者要想对编译流程有个整体的把握的话,我还是推荐《Programming Language Pragmatics, Third Edition》。我的书单里有对它的介绍:学习编程语言与编译优化的一个书单
另外这本书原版的第四版也已经出了,我正在欢快阅读中。

而说到SDT,龙书第二版的附录A有个用Java写的完整的简单编译器前端,它就是通过SDT从源码生成出中间代码的。C4与这个的做法有异曲同工之妙。读读龙书第二版的第二章,有对这个附录A代码的详细讲解。
附录A代码可以在官网获取:Source code

===============================================

语法分析

既然C4的整个编译流程都混在语法分析过程中进行,理解它的语法分析采用了怎样的设计会对理解代码有很大帮助——不然看到相关的语义分析或代码生成动作都不知道这是“哪里”。

C4的语法分析器是个典型的手写的自顶向下的实现。
它在(变量和函数)的声明部分以及语句部分采用“递归下降”方式(recursive-descent),在表达式部分采用递归下降与“运算符优先级”方式(operator precedence)混合的做法。
  • 对单目运算符、函数调用、单个变量名等的部分可以说是用了递归下降方式
  • 对双目运算符采用了运算符优先级方式

手写的语法分析器里,采用递归下降与运算符优先级结合的方式是非常常见的做法。其实两者单独使用都足以分析整个程序的语法,但是前者在分析具有多级优先级的表达式时比较慢,而后者在分析声明、语句等大家一般不看作是运算符的结构时代码比较不直观,所以把两者结合起来用就互补了。
例如说,Clang的语法分析器、Google V8、Microsoft Managed JScript等的语法分析器都是采用这种混合方式实现的。

扩展阅读:

这“运算符优先级”方式的语法分析,需要用到的核心数据结构就是——栈。
还记得我的本科数据结构与算法课教到栈的时候就是用中缀四则混合运算表达式的求值来举例的,其中就用到了两个栈,一个用于处理运算符优先级,另一个用于存放表达式的中间计算结果。

C4把这俩栈都用上了。只不过,用于处理运算符优先级的那个栈是通过递归的函数调用,隐含在函数调用栈里了;而用于存放表达式中间结果的栈则在C4的虚拟机部分,而不在编译器部分。
为啥编译器部分只用了“两个栈”中的一个?因为C4的编译器生成的目标代码是C4的虚拟机的字节码,而这个虚拟机的指令集就是个“基于(表达式)栈”的——所以说另一个栈在虚拟机部分。这个虚拟机的指令集,在表达式部分其实就是一种后缀表达式,也可以叫做逆波兰记法(Reverse Polish Notation,RPN)。

C4的语法分析,具体到代码里看,
C4由“4个函数”实现,剩下的next()函数就是词法分析了。c4/c4.c at master · rswier/c4 · GitHub

===============================================

词法分析

C4的词法分析整个就在next()函数里。实现得很直观,没啥特别需要解释的。

唯一或许值得一提的是用C/C++写的parser里一种很常见的做法。
看C4的token类别的枚举类型:
c4/c4.c at master · rswier/c4 · GitHub
// tokens and classes (operators last and in precedence order)
enum {
  Num = 128, Fun, Sys, Glo, Loc, Id,
  Char, Else, Enum, If, Int, Return, Sizeof, While,
  Assign, Cond, Lor, Lan, Or, Xor, And, Eq, Ne, Lt, Gt, Le, Ge, Shl, Shr, Add, Sub, Mul, Div, Mod, Inc, Dec, Brak
};
这个枚举类型是从128开始的。为什么?
再看C4的语法分析器里的一些例子:
tk == '('
tk == Sizeof
有时候tk跟一个字符相比较,有时候又与上面说的枚举类型的值比较,这是什么意思?

其实重点就是:C4所支持的输入源码的字符集限定在7-bit ASCII上,所以每个输入的字符只可能在[0, 127]的闭区间范围内。
于是如果有的“单词”(token)就是1个字符的,例如圆括号('(' ')')、花括号('{' '}')、乘号('*')等,它们的ASCII码就可以直接用作表示它们的token类别;
而对于多于一个字符的,例如数字字面量和关键字("int"、"char"、"sizeof"等),或者需要区分1个或多个字符的,例如加号('+')或自增("++"),则用大于ASCII码范围的数字来表示其token类别。
所以就有了上面说的从128开始的枚举类型——其实从0到127,加上这Num(128)到Brak(164)的范围都可以表示token类别,只是ASCII的部分默认映射到对于的字符上而已。

===============================================

符号表

C4使用了符号表来记录符号(名字)与实体(函数、变量)的映射关系。关于符号表是什么,有什么用,与AST的关系怎样,请参考另外两个问题的回答:

C4具体使用的符号表结构就是前面例子提到的那个伪装成int数组的symbol_t数组。
它里面存的symbol_t虽然有hash值,但这个数组要叫做“哈希表”还是有点勉强——这真的就是个很简单的、每次从数组开头开始线性遍历的一个表,没有一般哈希表那种计算下标然后解决冲突的动作。这里的hash值主要是为了避免线性查找符号表时每一项都要做完整的memcmp() / strncmp()而做的一层优化。

C4向符号表填充信息是分几步做的。
  • 首先,词法分析在遇到标识符的时候就会向符号表插入一个新的项,此时只填入了hash、名字以及token类型(Id)等信息。前文举的那段例子就是词法分析向符号表填入新项或者获取已有项的动作。
  • 然后在对声明做语法分析时,会把该标识符所代表的实体具体的属性信息填到符号表,例如类型是int还是char、存储类别(storage class)是全局还是局部、全局变量或局部变量的下标——这就是变量的存储空间分配,函数定义对应的字节码在代码区里面的偏移量,等等。c4/c4.c at master · rswier/c4 · GitHub
  • 每当进入一个函数声明时,其中的局部变量声明会暂时“遮蔽”(hide)掉同名的全局变量声明。此时为了保留原本的全局变量声明的信息,会暂时把这些被遮蔽的声明信息从“正常位置”转移到“备份位置”,例如从 id[Class] 转移到 id[HClass]、id[Val] 转移到 id[HVal]。c4/c4.c at master · rswier/c4 · GitHub
  • 同理,每当离开一个函数声明时,需要从符号表中清除该函数中的局部变量声明的信息,同时恢复出可能被遮蔽的全局变量声明的信息。这就是上一步的逆过程,遍历整个符号表中有内容的符号,把信息从“备份位置”恢复到“正常位置”。c4/c4.c at master · rswier/c4 · GitHub
(这种局部作用域的实现其实比较傻…完全可以多用一个变量记录进入函数时符号表的“高水位线”,离开的时候高于该位置的内容直接无视就好,而低于该位置的还是得遍历一边看有没有被覆盖的全局变量信息是需要恢复的。)

值得留意的是,在C4在main()的开头部分,分配了存储空间之后它就向符号表强行插入了若干符号。这些符号包括C4所支持的关键字,以及它所依赖的外部函数的名字。c4/c4.c at master · rswier/c4 · GitHub
强行向符号表插入依赖的外部函数的声明就绕开了要处理#include头文件的需求。注意插入外部函数的符号时 id[Val] = i++; 这句很巧妙的把外部函数名跟C4的虚拟机字节码对应了起来,例如处理到 i 为 OPEN 字节码时,id 正好对应 "open" 这个符号的内容。这个信息在后面代码生成时会用到。

===============================================

代码生成

有需要的话再写点吧。

唯一看起来未必直观的,是处理局部变量作为左值(lvalue)与右值(rvalue)的差别的地方。
C4在遇到一个表示局部变量的标识符时,总是生成这样的字节码序列,两条指令:
LEA #offset    // Load address of local variable
LC / LI        // Load value from address. LC for char, LI for int or pointer types
这两条指令,
  • 第一条LEA加载了局部变量的地址。这个其实就是一个“左值”——可以赋值的存储空间。
  • 然后第二条从该地址加载该局部变量的值。这个其实就是一个“右值”——可以实际参与计算的值。

可是如果一个标识符出现在赋值符号('=')的左边,我们需要的是该标识符表示的局部变量的左值而非其右值。所以C4在后续处理作了个弊:当它发现处理了一个标识符之后,紧接着的操作是赋值相关的('='、'++'、'--'等),就会把刚刚生成的LC / LI指令“抹掉”,然后覆盖上后续正确操作的字节码。

这样就可以保证在处理表达式中的标识符时可以简单一致的生成代码,而不需要向前看再特殊处理了。挺鸡贼的 >_<

===============================================

基于虚拟机的执行

Robert Swierczek写的原版C4不只是一个编译器,还是一个虚拟机。它的编译器部分并不直接生成任何实际机器的汇编或机器码,而是在内存里生成C4自己的虚拟机的指令,接下来由该虚拟机解释执行。整个虚拟机的实现都在main()的后半部分。c4/c4.c at master · rswier/c4 · GitHub

C4的虚拟机是一个“基于栈的虚拟机”,并且带有1个栈顶缓存(1-TOSCA),然后有可以通过下标访问的变量区。
main()里的 'a' 变量就是那个栈顶缓存。它也叫做“累加器”(accumulator),其变量名就取自此。
关于栈式虚拟机和栈顶缓存,请参考另外两个回答:

这个虚拟机通过解释器的方式实现。具体用的是超简单直观的
while (true) {
  switch (opcode) {
    // instruction cases ...
  }
}
形式,也叫做“switch-threading”。
只不过由于C4没有实现switch语句,它自己也就不用switch来实现这个解释器,而是用串联的if-else if-else,道理一样。

最后还是得一提C4对外部函数(“标准库”)的实现。前面提到了,C4的前端在符号表里强行插入了一组外部函数的名字,然后在代码生成时会把调用这些函数的地方生成为对应的专有字节码指令。后面在虚拟机里执行到这些字节码指令就调用相应的函数:
c4/c4.c at e78a343e1d71fd9e96c2e1860735fdc19ef58e8f · rswier/c4 · GitHub
    else if (i == OPEN) a = open((char *)sp[1], *sp);
    else if (i == READ) a = read(sp[2], (char *)sp[1], *sp);
    else if (i == CLOS) a = close(*sp);
    else if (i == PRTF) { t = sp + pc[1]; a = printf((char *)t[-1], t[-2], t[-3], t[-4], t[-5], t[-6]); }
    else if (i == MALC) a = (int)malloc(*sp);
    else if (i == MSET) a = (int)memset((char *)sp[2], sp[1], *sp);
    else if (i == MCMP) a = memcmp((char *)sp[2], (char *)sp[1], *sp);
    else if (i == EXIT) { printf("exit(%d) cycle = %d\n", *sp, cycle); return *sp; }

===============================================

先写这么多。应该够用了吧…不够的等其它回答来补充了 >_<