计算机系大四学生如何在六个月的时间内完成一个编译器？要学些什么？-Python教程

已经有了完成操作系统的问题
一个大四的计算机学生如何在六个月（大概只有晚上有空）的时间内完成一个简单的操作系统。应该要学些什么？
在答案里看到很多人推荐写编译器，希望了解一下例如要写Javascript或Python的编译器，需要做什么，怎样安排？

回复内容：

如果你不执着于主流语言的话，可以看看SICP第1、2以及第4章，看完后写scheme解释器。

我不推荐龙书、虎书什么的，是因为门槛。那种偏理论的书，对于相对缺乏实践的在校生来说，不容易理解；加上节奏比较慢，成就感来得晚，很可能烂尾。所以在这里我姑且只提供短平快的建议。

SICP第1、2章，作为函数式及编程技法的教程，都已经很能让人受益。
对有一定经验的同学来说，看完第2章对闭包实现的简单描述（2句话）后，很可能已经迫不及待的撸了一个简单的scheme解释器了；但是现阶段你的解释器实现，冗余、缓慢、不支持尾调用，所以你还需要看第4章。如果你愿意多想多写的话，第4章可谓本书的精华，lazy evaluation、pattern matching、continuation、partial evaluation都能从书中得到启发。

实现一个scheme解释器能让你收获什么？
你对解释器的基本原理及优化，都有一定感觉了。
如果一上来就阅读lua源码里闭包实现，你可能会陷入各种细节，等好容易理清来龙去脉过后，却又觉得它过于精巧。毕竟，一个准工业级项目中的关键设施，往往是几经调整、高度优化的产物。
而如果有在scheme中，通过聊聊数行代码，实现一个简洁、正确的闭包的经验，这时，再反过来看lua源码，反汇编.Net字节码看C#的闭包实现，实在非常容易了。毕竟，先作对，再做好，这个路子往往更顺利。

如果有一定执行力，那么，1~2个月，你总应该看完书中相关内容，做出1个或多个解释器，不至于白走这一遭了。

下面是一个可供参考的步骤：

1. 看完SICP相关章节，用scheme写一个scheme解释器。由于scheme中的基本结构list，很容易用来构造抽象语法树，加上scheme语言动态类型的特点、以及强大的模式匹配，用scheme实现一个最基本的自举解释器，只需数十行代码（完美的支持闭包哦）。你会发现，这个解释器的几个关键分支，正好对应lambda演算的3要素，也是SICP全书反复强调的“基本单元”、“抽象”、“应用”三元素。
2. 观摩一下Peter Norvig用数十行python代码实现一个scheme解释器：(How to Write a (Lisp) Interpreter (in Python))。于是，你开始知道怎样用主流语言实现解释器了，欢迎回到地球...Norvig也介绍了一个技法，让你的解释器能够支持尾递归。
3. 用C/C++语言实现解释器。第一次用非GC语言实现GC语言，你必须开始认真思考内存管理的问题。建议暂时不实现赋值，这样，你的函数式语言解释器中，将总是只有新对象引用老对象，不会出现环形引用，于是可以直接使用引用计数。
4. 更快，更好。
   

• 之前实现的解释器，都是基于抽象语法树的匹配，相当于OO设计模式中的visitor pattern；比起遍历语法树的同时进行解释的做法，尝试在遍历的过程中，先生成字节码并保存下来，之后只解释执行字节码？你能获得显著的性能提高。这样的预处理，是一种partial evaluation。
• 发现性能瓶颈在变量求值？你需要引入词法寻址（lexical addressing）了。这里你一步步优化的话，会发现你的环境链，被折叠成lua/C#那种主流形式。
• 放弃引用计数，转向真正的GC？mark and sweep、copying gc、mark-compact gc、generational gc？怎样让注册到你环境中的c函数，其函数体中分配的临时GC对象，总是可达？移动gc对象时，怎样保证所有指向它的指针被修改？（尤其是栈上的指针变量）
• 显然，一个程序并不总能写成尾递归形式，怎样才能让非尾递归程序的解释，也不栈溢出呢？Norvig介绍的技巧不够用了，你需要考虑实现CPS解释器或者进行全文CPS变换；于是栈空间被移动到堆中，栈将总是只有一帧。
• 尝试在scheme中进行一趟预处理，将library forms如let、let*、cond展开成基本形式？于是你开始意识到宏的威力，这是常见的data abstraction、functional abstraction之外的强力武器，syntactic abstraction。
• 在CPS解释器中实现call/cc？通过一趟全文CPS变换，输出不包含call/cc的普通scheme源码给你的DS解释器?
• 如果你想做得更好，还有很多很多问题需要你思考，而解决这些问题的过程，是很能让你得到锻炼的

Javascript 的规范有 200 多页（Harmony 的页数还要翻倍），你看完 Spec 都得一个月……
做一个 lisp 方言的，在两个方面沿着下面这两张图点亮图里的技能

不是有这本书吗？

图灵社区 : 图书 : 两周自制脚本语言

还有这本：

图灵社区 : 图书 : 自制编程语言

毕业论文是编译器吧？是不是很紧张？o(≧v≦)o
先说清楚，你是否确定写一个编译器？如果没有想好那么就先看看我下面推荐的文章
前期：
編譯器
看完上面的如果确定好了，那么就进行下面的工作，既然你的时间很短暂。只有晚上有空，先学会安排时间19点（妈蛋，不要告诉我还太早了！！）开始到23点（很多学校是这个时间熄灯断网）.



基础知识

1. 想裸写编译器，除了编译原理外还有那些资料可以参考？应该从什么开始写起？（用c/c++）？
   
2. 开发一个 C++ 编译器的难度有多大，难点又在哪里？
   
3. 怎样去写一个编译器（用C语言写C语言编译器），需要哪些知识做铺垫，可以给一下相关网站和书籍的推荐吗？
   
4. 编译器在硬件层面上的工作原理是什么？
   
5. 从零开始写个编译器吧系列 - 平凡与非凡 - 知乎专栏
   

前4个是你第一个晚上需要弄明白的。4个小时，如果不懂那么就立即去查阅资料和谷歌(Google,这个不用翻)。第二晚上先不要继续第5点的内容。从头再看一次1-4点，看看还是否有遗漏的地方记录。
看看4点就好好确定下来你写一个什么语言的编译器，想好了就可以进行第5点了顺便你需要买一个本书，不要听他人说买龙书、虎书等，这些大作难度太大了。你就买一个本 @赵劼推荐的图灵社区 : 图书 : 两周自制脚本语言 。

写一个编译器是一个比较枯燥的事情，看到界面很不容易。归根结底就是"折腾"；且思且珍惜 从scheme这样的lisp语言的编译器开始写。。而且不必完全实现，可以选取子集，gc闭包什么的都可以不要。。

你可以先写解释器，再试试编译到其他语言，再试试编译成二进制

这个资料太多，你自己搜吧。

书嘛，我提过的一个问题，下面很多回答都很好，你自己找找看 我写过一个C的编译器，实际上只是把C翻译成汇编。编译器要做好，最重要的是汇编代码优化，不过新手把翻译做出来才是首要的。

词法简单，可以手写。文法可以找标准的C文法，用Bison之类的工具生成一个分析表（不过我和轮子哥类似，自己写了个LR1的分析表生成器），剩下的也简单了，可以生成一个AST。然后，翻译成汇编就是遍历AST了，我没有处理C的所有语法，比如结构体就没管。翻译基本的C语言结构，虽然复杂，但并不难，如果是汇编高手，就更轻松了。（其实最好生成中间表示IR，再翻译成汇编）

写的过程中，AST节点的设计比较关键，要保存很多信息，另外符号表的设计也很重要。翻译过程中才真真感觉到，类型是需要时时刻刻考虑的因素，同样是加减，整形和浮点型在汇编层面差很多。另外我一直认为，课本上教的语法制导翻译太狗血，对于文法很多的语言，得一条条改文法，所以还是老老实实地建立AST，翻译起来才比较快乐。 从C的编译器开始写，不要写Python和Javascript的编译器，特别是Javascript的编译器。]

昨天是在手机上打的，今天来解释一下。

Javascript和Python都不是上下文无关的语言，做起来相对难度要大一些。而C89有完整的LALR(1)相容的EBNF文法，网上也很容易搜到。

关于文法和分析方法的学习，请参见我的一个回答：

如何自创一门计算机语言？ 写编译器最简单的方法就是直接去看别人写的呗，题主大四当然是学过编译原理了的，我去年年底上编译原理课的时候就自己实现了一个，其实也就是根据别人的代码自己思考以后写出来，前后也就几周的时间而已
C++实现pascal子集 也就1200行左右
duduscript/pl0 · GitHub 欢迎fork 我自己是没有写编译器的能力的，但我听说，龙书，虎书，和鲸书，很不错，你看完了，不一定能写出来，但肯定有帮助！ “很多人推荐写编译器”，估计所谓的“很多人”有80%是装B