如何写一个简单的编译器？

https://www.zhihu.com/question/36756224 初学编译原理，想写一个简单的编译器。 是时候亮出我的 LL 语言了，全称：Lambda Lite Js。 LL 是一个类似 haskell 的函数式语言，使用 Javascript 实现。在线demo：Lambda-lite-js。项目地址：GitHub - moevis/lambda-lite-js: a tiny FUNCITONAL LANGUAGE implemented by javascript. 一个函数式语言，使用 js 实现。。 大概写了两周多，有了很多很有趣的功能了，比如可以玩 lambda 演算，可以柯里化，可以玩闭包，可以玩模式匹配，可以使用 Point-Free 风格，具有局部 lazy-evaluation 特性等等。 先给几个阶乘的示例代码。 普通阶乘 let fact = \n ->     if n == 1 then 1 else n * (fact n - 1); print $ fact 5; 利用模式匹配写阶乘： let fact n@1 = 1; let fact n@Number = n * (fact n - 1); print $ fact 5; 不动点组合子阶乘： let z = \f -> (\x -> f (\y -> x x y)) (\x -> f (\y -> x x y)); let makeFact = \g -> \n -> if n < 2     then 1     else n * (g n - 1); let fact = z makeFact; print $ fact 5; 网页版运行截图： 是的，就是和 haskell 这么像。 =====说正事===== 之前我写过一个 js 代码高亮插件，用于高亮 html、js、css 代码，GitHub - moevis/code-lighter: a lightweight code highlighting tool, 代码高亮工具。原理是将代码切分成一系列 tokens， 然后给这些 tokens 添加着色就好了。 至于如何切分 tokens 呢？Parser 就是负责这个事情的。我们先将输入的代码先分成以下几个基本元素： 数字 Number 字面量 Literial 标点 Punctuar 空白符 White 文件结束符 EOF 我们的任务就是要区分它们，这个目标还是蛮容易的，我们使用递归下降法来解析，这就是一个状态机的模型： 首先，我们的初始状态机 State 处于默认状态。 读入待解析代码，读第一个字符 c ，这时候有五种可能： c 属于 '9' ~ '0'，State 转为数字模式。 c 属于 'a' ~ 'z' 或者 'A' ~ 'Z'，State 转为字面量模式。 c 属于 '*,;"+'... 的标点，State 转为标点模式。 c 属于 '\t' 或者 '\n' 或者空格，State 转为空白符模式。 c 为空，则到了代码的最后，State 为文件结束模式。 进入另一个模式后，我们会用不同的策略来接收下一个字符。比如，在数字模式假如下一个字符是 '0' ~ '9'，那么读入数字，并拼接到之前的数字后；直到接收到一个非数字的字符（这里我们就不考虑小数了）。当退出数字模式，我们就能得到一个数字的 token 啦。同理我们可以得到标点，字面量等等。 关于字面量，我们还需要做一些分类，字面量包括变量名，关键字，所以我们实现要有一个关键字表，当字面量不再关键字表里面，我们视为一个变量或者是函数名，否则就是有语法意义的字符比如 if else 。 初步的 tokens 切分结束后，去除空白 tokens，我们就得到一个 token 数组。 这时候我们要建立抽象语法树 （Abstract syntax tree）了。先设计几个基本语法，比如声明一个函数或者变量时，使用`let`关键字，`if...else...then...`做分支判断，声明匿名函数使用类似'\n -> n + 1'的语法（有且只有一个参数 n ，n + 1 为返回值），表达式采用中缀 `1 + 2 + a`。 这时候我们可以定义几个树节点类型了： 声明节点, defineNode (let x = 5) 匿名函数节点, lambdaNode (\n -> n + 1) 分支节点，conditionNode (if ... then ... else ...) 引用节点，代表某一个已声明的变量值或者函数名 objectNode 数字节点，代表一个数字，numberNode 表达式节点, 代表某一中缀表达式，其本身储存运算符，比如 a + b，节点储存 `+`，expressNode 函数调用节点，表示对函数的调用，比如 print x，callNode 我们的任务就是将 tokens 转为这些节点的相互关系。 首先还是读入第一个 token，判断 token 类型，如果是`let`，那么就按照声明节点来解析; 如果是`\`则是一个匿名函数声明节点，如果是`if`，则解析一个分支节点…… 解析表达式节点会难一点，因为有运算符的优先级，我参照了 llvm 教程中的 kaleidoscope 语言来写（传送门，Kaleidoscope: 实现解析器和抽象语法树）。 总之这是需要你认真理解的一步，这一步完后，就可以根据语法树来得到代码运行结果了。每一种节点的结果计算方式都不同，但是有统一的接口 getValue()。比如声明节点无返回值，匿名函数返回一个函数，分支节点先对 condition 求值，当 condition 为 true，返回第一个分支的 value，否则是第二个…… 当这一切结束后，你的第一个语言就完成了。当然，现在我的语言已经比较复杂了，比如加入了模式匹配节点，声明多参数函数的语法糖，改变结合方向等等。 你可以看我的 commit log 来看到我是如何一步一步添加这些功能的。 编译原理这个方向，龙书虎书是经典，若要深入学习，一定要看。不过我也没有时间啃下来，不过有一本书也是简单有趣，叫做《计算的本质》，O‘REILY 出的，值得信赖。 说了那么多，我这个只能算是解释器，并没有真正编译，当然对于初级已经够了。你不满足的话我再给你指条路，llvm 教程中有一个小语言叫做 kaleidoscope，你按照这个教程来，https://github.com/moevis/Kaleidoscope-LLVM-tutorial-zh-cn，这是我当年留下的中文翻译坑，当时翻了一些后就去做实验室任务了。这个从 parser 到 ast 到 ir 到各种优化都很全。 如果是用 Haskell 的话，三篇文章足矣。 prerequisite: 懂 state monad就行了 第一篇，《How to build a monadic interpreter in one day》http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.368.2522 跟着做，可以完成一个简单的backend， 也就是架构基本的AST 并执行的步骤。 然后到frontend， 也就是parser的部分你就会发现你看不懂了， 这个时候看第二篇。（因为该文的 parser  部分其实是 第二篇 的一个浓缩版，所以不看第二篇基本很难看懂这个部分） 第二篇，《Monadic Parser Combinator》 ，http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf 看了也就能对照第一篇，把 parser 写出来了， 然后就能和之前的backend 组合，完成一个基本的，完全由自己手写的，monadic的解释器（parser 和 backend 分别由一个自定义的 state monad 实现）。顺便加深对 monad 的理解。 看第二篇的时候，回过头对照第一篇看效果会更高，虽然逻辑一样，但第二篇是用 monad comprehension 的形式来写， 第一篇是用 do notation 来写。有的复杂的地方你两种方式对照看一下，会有茅塞顿开的效果。 然后再看第三篇 第三篇，llvm的haskell 教程， Implementing a JIT Compiler with Haskell and LLVM ( Stephen Diehl )  ， 把你的backend 换成llvm. （注：事先对 llvm 不熟的话，可以和 hackage 上面 llvm-general, llvm-general-pure 这两个库的 wiki, 以及 LLVM Language Reference Manual对照着看） 至于frontend， 可以换成Parsec之类，但也可以就不断扩充之前自己写的版本。 齐活儿~ ------ 今天闲着没事儿，撸了一个 swift 的版本，GitHub - aaaron7/swift_monadic_parser: A simple haskell-style monadic combinator-based parser written in Swift.   仅包含最基本的 parser 和 interpreter 的功能，写法完全按照前面两篇文章的思路实现，有兴趣可以看看。 这个题目有点久了，现在才想起来答，主要还是因为暑假才找到空闲的时间，把我的C11编译器写完了。 这个编译器，(GitHub - wgtdkp/wgtcc: a tiny C compiler in C++) 一方面是为了学习 C11, 一方面为了练习C++。 在约11k代码中实现了： 几乎完整的C11语法解析(除去变长数组); 语义与类型检查(仿gcc的错误提示) 预处理器 x86-64汇编代码生成， 多谢  @RednaxelaFX  的回答寄存器分配问题？ - 编译器，把我从无休止的手动优化中拯救回来 精简的x86-64 ABI 心形很流行嘛，wgtcc编译的M大(  @Milo Yip  ) 在 如何用C语言画一个“心形”？ - C（编程语言）回答里的代码： #include <stdio.h> int main() {     for (float y = 1.5f; y > -1.5f; y -= 0.1f) {         for (float x = -1.5f; x < 1.5f; x += 0.05f) {             float a = x * x + y * y - 1;             putchar(a * a * a - x * x * y * y * y <= 0.0f ? '*' : ' ');         } putchar('\n');     } }  C11 中有一些非常实用或者好玩的新特性，如 compound literal. 一个典型的用途是当我们想获得一个数据的另一种表示的时候， 我们可能会这么做： float f = 1.5; int i = *(int*)&f;  然而gcc 在开 -O2 时会报 break strict-aliasing rules 的warning。 有了 compound literal， 我们可以这么做： #define CAST(s_t, d_t, sv) \     (union {s_t sv; d_t dv;}){sv}.dv float f = 1.5; int i = CAST(float, int, f); 而且这是一个模板呢～ C11 也支持在identifier 中使用unicode字符了，中文编程很exciting： #define 整型    int #define 输出    printf #define 面函数  main #define 返回    return #define 定义    typedef #define 不可变  const #define 字符    char #define 指针    * #define 为 定义 不可变 字符 指针 为 字面值; 整型 面函数() {   字面值 蛤蛤 = "\u82df\u5229\u56fd\u5bb6\u751f\u6b7b\u4ee5\uff0c"                "\u5c82\u56e0\u7978\u798f\u907f\u8d8b\u4e4b";   输出("%s\n", 蛤蛤);   返回 0; } 这些例子在example/目录下可以找到。 说说写这个小编译器总结的方法吧： 以最快的速度做到能够解析下面这段代码： int main(int argc, char** argv) {      int i;      return 0; } 以最快的速度看到hello，world。 开始对照语言标准一个一个实现特性，并同步做单元测试。因为已经看到hello world,这一步虽然工作量有点大，但是因为有了前面的经验，可以很快。 解析声明是最复杂的，所以先写解析声明。 龙书是必需的，一个好的参考也非常重要（如GitHub - rui314/8cc: A Small C Compiler）。 尝试自举(因为我用的C++，所以没法自举)。 写一个编译器的坏处是，以后写一段代码都试图在脑子里面翻译成汇编。。。 // Update_1 // Date: 09/20/2016 匆忙写的回答，感觉仅仅是抛出结果和小结，实在是太不负责任了=-=。没有实现过的同学可能还是不知如何入手，下面就写写我是如何一步一步做的吧(某些内容只限于C编译器) 1. 初始状态，你必须有一本第二版的龙书。其它的答案可能会推荐《编译器实现》或者《编程语言实现模式》。《编译器实现》因为中文翻译的比较生硬，读了几章，发现还是龙书比较好，后来基本没有看《编译器实现》了。如果你是直接读原版，那么还是推荐龙书，毕竟都有决心读原版了，干脆彻底一点读龙书原版好了^_^。其实龙书并没有那么难，公式记不住，不理解，跳过就好了。《编程语言实现模式》其实很好的，各种实现方法都有所涉及。唯一不足的是，作者没有向《代码大全》的作者那样，对我耳提面命 ----- 直接告诉我怎么做就好了(相信这是新手最需要的...)。 2. 你必须有C11 standard。open-std 上面的draft就够了(http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf)。(如果是其他语言的编译器，对应之。如果是自己设计，那么应该学着standard那样，将grammar，constraints等写下来) 3. 一个简单的不带优化的编译器，基本只需要3个步骤：词法分析，语法分析，代码生成；对应到代码里面，就是3个class：Scanner, Parser, Generator;  4. 对于C语言编译器，支持预处理器，相当于又支持了一门新的简单语言了。所以一开始不必去支持预处理器。在测试时，只使用不包含预处理器的代码就好了。或者，用gcc进行预处理，将其输出作为你的编译器的输入。 5. 在真的动手开始写Scanner之前，有必要读n1548的5.1节，对C源程序的编译步骤有基本的了解。其实ad-hoc的词法解析一点也不比写一个split()函数更复杂，尤其是开始的时候不必去记录 Source Location(当然后面如果写错误提示，可以再加进来)。实现的时候，也不要吝惜内存了，直接将所有的token一次解析掉存起来就好。因为这对于后面Parser要回溯的时候会方便一点。 6. 已经得到Token List 之后，就可以开始做Parser部分了。暂时不做错误恢复，即遇到错误即exit。这里有一个很实用的设计建议：准备好下面这四个函数： a. Peek() 返回下一个Token(只测试该Token，不向前移动Token List的offset指针) b. Next() 消费下一个Token c. Expect(expectedToken) , 这代替了下面的这段错误处理： if (Peek() != expectedToken) {     Error("expect %s, but got %s\n", expectedToken, Peek()); }  d. Try(expectedToken), 这代替了下面这段代码： if (Peek() == expectedToken) {     Next(); // 消费之 }       这很有用，因为Parser里面可能会有上百个这段代码，在我的Parser里面，有84个Expect()调用，81个Peek()(Peek和Test), 39个Next()，62个Try()。相信我，这4个函数会让你的代码干净一倍。 7. C的语言组成，大致可以分为 Expression, Declaration, Statement and Block 三个部分。这里面Statement and Block是最简单的，Declaration难一点。按照我前面的心得体验，应该从简单的入手，但是我们非先做Declaration不可。因为Statements都是在函数内的啊，不搞定Declaration就没法继续了呢～ 其实，Declaration也好做，对着n1548的7.A.2.2节一个一个将grammar翻译为Parser里面的逻辑就好了(是的，除去语义和类型检查，Parser就是这么简单)。做完Declaration，你还没有往AST上添加任何node，是的，仅仅是Declaration，是没有一行代码需要生成的。所有的成就都在符号表里面。这里又有tip：暂时不要做Initializer，它有一点烦人的(C标准把它搞得好繁琐)。 8. struct/union 类型；如果只是支持一个小小的子集，那么大可以跳过这一部分不做。struct会引入一些工作量，一方面，需要为tag(tag 和普通的identifier不在同一个命名空间)另开一个符号表(我使用一个小trick避免了这个麻烦)；另一方面，它也是使Initializer变复杂的原因之一，尤其是匿名struct/union。tip：对struct/union的支持步骤是：普通嵌套的结构，匿名无tag的 struct成员，位域，union；这里把union放到最后是因为，它和struct除去存储布局之外，别无二致(所以你甚至不必区分这两个类型)；你也可以在任何一步就开始支持union。 9. 数组和函数；除去作为sizeof关键字的操作数，数组总是会被cast成一个指针；你一定写过这样的代码： typedef void (*func_t)(void); func_t f = func; f(); // 难道不应该是 (*f)(); ?  其实函数也是被cast成指针了，所以上面的调用方式都对，更微妙的是，任何一个函数调用都会被先cast成指针，再解引用(至少我的实现是这样的)； 10. storage 和 linkage；起初只实现所有的对象分配在栈空间；这会大大简化代码生成部分，因此对于“以最快速度看到hello world”是非常重要的；linkage对于前向声明是重要的，如果你没有打算支持，那么也可以跳过，等你看到hello world再回来支持，或者等你的函数和标准库的冲突了。 11. expression；这个最简单，该怎么样就怎么样=-=。tip：联合赋值运算符： a *= 5; a = a * 5;  是不是总是被告知效果和下面那行效果相等？那么不要害羞，就这么翻译！(嗯，这么做是会产生bug（如果左值表达式有副作用），但是可以通过额外的检查规避掉；对于带优化的编译器，这根本不是问题，因为它们怎么会对公共子表达式求两遍值呢？) 12. statement；这是我最喜欢的部分，不仅仅是因为它简单，而且让我明白那些控制语句是怎么生成到汇编代码的(对应请看龙书6.6和6.7节)；如最简单的while循环的展开： /*  * while (expression) statement    * 展开后：   * cond:    *       if (expression) then   *           empty   *       else   *           goto end   * statement   * goto cond   * end:   */  这里，我将 if 语句保留为基本的翻译单元，因为将其他的控制结构翻译为 if 语句会带来很大的便利。tip:支持顺序：if-else, while/do-while, for, switch-case;  这些基本是一个C语言Parser的动手步骤了，现在你可以parse这段代码了： int main() {     puts("hello world\n");     return 0; } 你可以手动将 puts插入到符号表以应付过去(某些builtin的函数还真就是这么干的)，也可以在这个hello.c文件中声明puts: extern int puts(const char* str);  或者你就要实现对struct/union的支持， 不然是没有办法 #include <stdio.h> 的了。这里没有使用 printf，因为暂时没有必要实现变参函数。 这样，你与hello world只有一步之遥了：汇编代码生成。 // TODO(wgtdkp): 汇编代码生成 // End of update_1 // Update_2 // Date: 09/21/2016 因为按照"以最快的速度看到hello world"来做的话，语义检查和类型检查可以暂且放一放，或者只是实现parse过程中必不可少的一部分。下面是以x86-64 汇编代码生成为例，说说代码生成。这里又可以跳过中间代码生成，直接由AST生成汇编代码～ 1. intel x86-64 手册；显然这是必需的，虽然我拿到这3000多页的手册时，也是虎躯一震的。不过，实实在在地讲，我只看了大概30页的内容；更多的时候，我是对照着gcc生成的汇编代码照虎画猫; tip：对于某些指令，如乘除法，移位，对照gcc进行翻译是非常有效的；但你不应该企图生成像gcc那么高效的代码！(具体方法见下面) 2. System V x64 ABI；你必须至少看chapter 3(chapter 3就够用了， 不过只有30多页，放心吧)；至少掌握stack frame的结构和对齐。注意x86-64的调用规约会稍微复杂一点，不过你可以做一些大胆的简化：  a. scalar type (除去struct/union,剩下的都是)按照 ABI里面的就好；  b. struct/union 是比较复杂的，这里可以直接按照stack传参(而不是寄存器传参去做)，毕竟又有多少代码会直接传递struct/union 呢？等到你决意要做一个full featured的编译器时，再来考虑它吧。 可以参考这里Introduction to X86-64 Assembly for Compiler Writers 3. visitor 模式；相信这个不必赘述，取决于怎么使用它，可以有很多作用；比如Parser中会需要做常量表达式求值，我们会用到它；获得一个表达式的左值地址时，我们又需要用到它；(考虑你该如何翻译赋值表达式) 4. 数据类型；在代码生成这一步，我们的数据类型只有3种：整型，浮点型，struct/union(集合)；我将能够用通用寄存器存储的数据称为整型，包括指针；struct/union的处理比较特殊，对于一个类型为struct/union的表达式，visit该表达式，总是得到此struct/union对象的地址值(存储于%rax寄存器中)；只要我们在所有代码中遵守这一规则，那么它确实很管用，即使会有一些冗余的拷贝； 5. 翻译函数定义；一个函数的翻译可以分为下面几个步骤： 保存栈指针； 确定函数参数的位置(在哪个寄存器或者stack上的位置)，将它们复制到当前stack frame的上，更新每个参数(object)的offset成员(object的地址)。更新当前stack frame的偏移量； 确定当前作用域内的object的地址， 这只需要扫描当前scope内的所有object，并线性地分配到stack frame上面就好；注意不包括内层scope内定义的object。这是一种优化，能够充分利用栈空间，而且实现更简单。更新当前的stack frame偏移量。 翻译函数体； 在return 语句和函数结尾处，恢复栈指针并退出函数； 6. 翻译函数调用；也可以分为下面几个步骤： 确定函数地址；这可能是函数的名字，也可能是一个寄存器；这里就需要一个能够计算表达式左值地址的 evaluator 了（后面会讲到)； 对函数参数求值，暂存之(push到stack上)； 确定函数参数的位置，即，应该在哪个寄存器或stack的位置；拷贝参数值到对应位置； 调整栈指针以正确地对齐(这个很重要，不然会有segment fault的，都是泪)； 调用之～ 7. 翻译赋值表达式；对左值表达式的赋值，需要获得左值表达式的地址，而不是值；因此我们需要一个 LValGenerator 来取得左值表达式的地址，然后将右操作数的值load到该地址中； 8. 翻译表达式；建议采用1-TOSCA方法，不懂的可以看看R大的回答寄存器分配问题？ - 编译器；这里的tip：不要被gcc生成的各种高效代码蛊惑了而去做大量的手动优化，那是一个很大的坑，尤其是我们没有生成中间代码，是做不到全局寄存器分配的效果的。 ========

第一个 C 语言编译器是怎样编写的

http://www.csdn.net/article/2015-11-27/2826350 摘要：当今几乎所有的实用的编译器/解释器（以下统称编译器）都是用C语言编写的，有一些语言比如Clojure,Jython等是基于JVM或者说是用Java实现的，IronPython等是基于。   当今几乎所有的实用的编译器/解释器（以下统称编译器）都是用C语言编写的，有一些语言比如Clojure,Jython等是基于JVM或者说是用Java实现的，IronPython等是基于.NET实现的，但是Java和C#等本身也要依靠C/C++来实现，等于是间接调用了C。所以衡量某种高级语言的可移植性其实就是在讨论ANSI/ISO C的移植性。 C语言是很低级的语言，很多方面都近似于汇编语言，在《Intel 32位汇编语言程序设计》一书中，甚至介绍了手工把简单的C语言翻译成汇编的方法。对于编译器这种系统软件，用C语言来编写是很自然不过的，即使是像Python这样的高级语言依然在底层依赖于C语言（举Python的例子是因为Intel的黑客正在尝试让Python不需要操作系统就能运行——实际上是免去了BIOS上的一次性C代码）。现在的学生，学过编译原理后，只要有点编程能力的都可以实现一个功能简单的类C语言编译器。 可是问题来了，不知道你有没有想过，大家都用C语言或基于C语言的语言来写编译器，那么世界上第一个C语言编译器又是怎么编写的呢？这不是一个“鸡和蛋”的问题…… 还是让我们回顾一下C语言历史：1970年Tomphson和Ritchie在BCPL（一种解释型语言）的基础上开发了B语言，1973年又在B语言的基础上成功开发出了现在的C语言。在C语言被用作系统编程语言之前，Tomphson也用过B语言编写过操作系统。可见在C语言实现以前，B语言已经可以投入实用了。因此第一个C语言编译器的原型完全可能是用B语言或者混合B语言与PDP汇编语言编写的。我们现在都知道，B语言的执行效率比较低，但是如果全部用汇编语言来编写，不仅开发周期长、维护难度大，更可怕的是失去了高级程序设计语言必需的移植性。所以早期的C语言编译器就采取了一个取巧的办法：先用汇编语言编写一个C语言的一个子集的编译器，再通过这个子集去递推完成完整的C语言编译器。详细的过程如下： 先创造一个只有C语言最基本功能的子集，记作C0语言，C0语言已经足够简单了，可以直接用汇编语言编写出C0的编译器。依靠C0已有的功能，设计比C0复杂，但仍然不完整的C语言的又一个子集C1语言，其中C0属于C1，C1属于C，用C0开发出C1语言的编译器。在C1的基础上设计C语言的又一个子集C2语言，C2语言比C1复杂，但是仍然不是完整的C语言，开发出C2语言的编译器……如此直到CN，CN已经足够强大了，这时候就足够开发出完整的C语言编译器的实现了。至于这里的N是多少，这取决于你的目标语言（这里是C语言）的复杂程度和程序员的编程能力——简单地说，如果到了某个子集阶段，可以很方便地利用现有功能实现C语言时，那么你就找到N了。下面的图说明了这个抽象过程： 那么这种大胆的子集简化的方法，是怎么实现的，又有什么理论依据呢？先介绍一个概念，“自编译”Self-Compile，也就是对于某些具有明显自举性质的强类型（所谓强类型就是程序中的每个变量必须声明类型后才能使用，比如C语言，相反有些脚本语言则根本没有类型这一说法）编程语言，可以借助它们的一个有限小子集，通过有限次数的递推来实现对它们自身的表述，这样的语言有C、Pascal、Ada等等，至于为什么可以自编译，可以参见清华大学出版社的《编译原理》，书中实现了一个Pascal的子集的编译器。总之，已经有计算机科学家证明了，C语言理论上是可以通过上面说的CVM的方法实现完整的编译器的，那么实际上是怎样做到简化的呢？这张图是不是有点熟悉？对了就是在讲虚拟机的时候见到过，不过这里是CVM（C Language Virtual Machine），每种语言都是在每个虚拟层上可以独立实现编译的，并且除了C语言外，每一层的输出都将作为下一层的输入（最后一层的输出就是应用程序了），这和滚雪球是一个道理。用手（汇编语言）把一小把雪结合在一起，一点点地滚下去就形成了一个大雪球，这大概就是所谓的0生1，1生C，C生万物吧？ 下面是C99的关键字：    仔细看看，其实其中有很多关键字是为了帮助编译器进行优化的，还有一些是用来限定变量、函数的作用域、链接性或者生存周期（函数没有）的，这些在编译器实现的早期根本不必加上，于是可以去掉auto, restrict, extern, volatile, const, sizeof, static, inline, register, typedef，这样就形成了C的子集，C3语言，C3语言的关键字如下：    再想一想，发现C3中其实有很多类型和类型修饰符是没有必要一次性都加上去的，比如三种整型，只要实现int就行了，因此进一步去掉这些关键词，它们是：unsigned, float, short, char(char 是 int), signed, _Bool, _Complex, _Imaginary, long，这样就形成了我们的C2语言，C2语言关键字如下：   继续思考，即使是只有18个关键字的C2语言，依然有很多高级的地方，比如基于基本数据类型的复合数据结构，另外我们的关键字表中是没有写运算符的，在C语言中的复合赋值运算符->、运算符的++、– 等过于灵活的表达方式此时也可以完全删除掉，因此可以去掉的关键字有：enum, struct, union，这样我们可以得到C1语言的关键字：  接近完美了，不过最后一步手笔自然要大一点。这个时候数组和指针也要去掉了，另外C1语言其实仍然有很大的冗杂度，比如控制循环和分支的都有多种表述方法，其实都可简化成一种，具体的来说，循环语句有while循环，do…while循环和for循环，只需要保留while循环就够了；分支语句又有if…{}, if…{}…else, if…{}…else if…, switch，这四种形式，它们都可以通过两个以上的if…{}来实现，因此只需要保留if,…{}就够了。可是再一想，所谓的分支和循环不过是条件跳转语句罢了，函数调用语句也不过是一个压栈和跳转语句罢了，因此只需要goto（未限制的goto）。因此大胆去掉所有结构化关键字，连函数也没有，得到的C0语言关键字如下：   只有5个关键字，已经完全可以用汇编语言快速的实现了。通过逆向分析我们还原了第一个C语言编译器的编写过程，也感受到了前辈科学家们的智慧和勤劳！我们都不过是巨人肩膀上的灰尘罢了！0生1，1生C，C生万物，实在巧妙！ ========

学习较底层编程：动手写一个C语言编译器

http://blog.jobbole.com/77305/ 动手编写一个编译器，学习一下较为底层的编程方式，是一种学习计算机到底是如何工作的非常有效方法。 编译器通常被看作是十分复杂的工程。事实上，编写一个产品级的编译器也确实是一个庞大的任务。但是写一个小巧可用的编译器却不是这么困难。 秘诀就是首先去找到一个最小的可用工程，然后把你想要的特性添加进去。这个方法也是Abdulaziz Ghuloum在他那篇著名的论文“一种构造编译器的捷径”里所提到的办法。不过这个办法确实可行。你只需要按照这篇论文中的第一步来操作，就可以得到一个真正可用的编译器！当然，它只能编译程序语言中的非常小的子集，但是它确实是一个真实可用的编译器。你可以随意的扩展这个编译器，然后从中学到更多更深的知识。 受到这篇文章的鼓舞，我就写了一个C编译器。从某种意义上来说这比写一个scheme的编译器要困难一些（因为你必须去解析C那复杂的语法），但是在某些方面又很便利（你不需要去处理运行时类型）。要写这样一个编译器，你只需要从你那个可用的最小的编译器开始。 对于我写的编译器来说，我把它叫 babyc，我选了这段代码来作为我需要运行的第一个程序： C int main() {     return 2; } int main() {     return 2; } 没有变量，没有函数调用，没有额外的依赖，甚至连if语句，循环语句都没有，一切看起来是那么简单。 我们首先需要解析这段代码。我们将使用 Flex 和 Bison 来做到这点。这里有怎么用的例子可以参考，幸好我们的语法是如此简单，下面就是词法分析器： "{" { return '{'; } "}" { return '}'; } "(" { return '('; } ")" { return ')'; } ";" { return ';'; } [0-9]+ { return NUMBER; } "return" { return RETURN; } "int" { return TYPE; } "main" { return IDENTIFIER; } "{" { return '{'; } "}" { return '}'; } "(" { return '('; } ")" { return ')'; } ";" { return ';'; } [0-9]+ { return NUMBER; } "return" { return RETURN; } "int" { return TYPE; } "main" { return IDENTIFIER; } 这里是语法分析器： function: TYPE IDENTIFIER '(' ')' '{' expression '}' ; expression: RETURN NUMBER ';' ; function: TYPE IDENTIFIER '(' ')' '{' expression '}' ;   expression: RETURN NUMBER ';' ; 最终，我们需要生成一些汇编代码。我们将使用32位的X86汇编，因为它非常的通用而且可以很容易的运行在你的机器上。这里有X86汇编的相关网站。 下面就是我们需要生成的汇编代码： .text         .global _start # Tell the loader we want to start at _start. _start:         movl    $2,