Cheng Meng’s Small Talk

compiler-aho.pdf
今天终于把龙书第二版的电子书传上去了。不知道链接什么时候会失效。
失误，一开始写成第三版了

阅读(722 次)

说到龙书(Dragon Book)，喜欢玩编译器和程序语言的老大们肯定是人手一册，在编译器技术这一块的教科书中地位几乎有如圣经。说到这儿又要鄙视一下国产的什么编译原理教材，简直是不知所云，抄都抄得这么潦草。

计算机领域的经典著作，常常会有些“小名”或俗名，如无人不知的TAOCP，C语言圣经K&R，算法入门宝典CLR。TAOCP是书名的缩写，此书堪称最有名的算法书籍，我估计也是被完整阅读次数最少的计算机书籍，之一都省掉了。K&R和CLR都是作者名字的开头第一个字母。龙书算是比较有个性的，这个外号来自其封面。1977年，Alfred V. Aho和Jeffrey D. Ullman写了一本Principles of Compiler Design，封面是一位骑士枪挑一头绿色恐龙，因此得名龙书。到了1986年，此书升级换代，书名变成了Compilers: Principles, Techniques and Tools，沿用至今，作者增加了Ravi Sethi。封面依然是一位骑士和一头恐龙，只不过恐龙变成了红色，骑士则坐在了电脑前。仔细看的话，发现龙身上纹身“Complexity of Compiler Design”，骑士全副武装，盔甲上书“Data Flow Analysis”，夹着一把写着”LALR Parser Generator”的宝剑，盾牌上则写着”Syntax Directed Translation”。

一晃过了20年，龙书终于出了新版。封面当然是骑士斗恶龙。作者又加了一位，篇幅猛增了200多页，变化十分巨大。除了一些古典内容如词法分析，语法分析，语法制导翻译，中间代码生成没怎么动，后面的运行环境，代码优化部分可谓焕然一新。从Run-time Environment这一部分就可以看出程序语言这些年来的变化：Java，.NET，Python，Ruby…自动内存管理已经不是什么新鲜事，所以龙书里开了近半章的篇幅给垃圾收集。内存管理是个大题目，完全铺开来一本书都不够，从目录上看，龙书已经包括了现在主流的一些技术，估计作者安排这一块内容时也死了不少脑细胞。变化最大的当属代码优化，原来只有一章，现在一下子撑成了四章，洋洋洒洒近400页，可以单独成一本书了，较之第一版，作者似乎不满足于做一本入门教材，要一揽子把从入门到高级全包了。

其他内容上的变化，暂时只能从目录上看一下。Flow Analysis增加了一些较新的算法，比如Region-Based Analysis。优化部分花了不少力气讲Parallel Machine，现在看来也是大势所趋。

书肯定是不可能仔细看了；也不知道什么时候会有中文版；这么一本1000页的大砖头翻成中文后也不知道厚成什么样。我个人的一点观察，最近几年动态语言与函数式语言开始逐渐成为主流，用马克思的话，一个函数式编程的幽灵开始在C++/C#/Java中徘徊。现在的编译技术，似乎应该包括Dynamic Typing, JIT等等，特别是种种针对动态语言的优化（比如方法缓存）。作为一本教材，不可能面面俱到，更不能跟风，编者总有自己的原则和取舍，大概龙书的四位作者认为这些东西还不值得进入大学的编译技术课程。但我觉得现在正是一个计算环境变革的前夜；或者说变革已经在进行时了。这样的话，也许下一个版本，不用再让我们等20年。

说到这儿，又要损一下中国这帮写教科书的人。为了避免打击面过广，不失一般性，限定于计算机行业。老外写书，一版二版三版，真是与时俱进。当年Dirichlet写了一本数论讲义，每次重版他的学生Dedekind都会在后面添个附录反映一下最新的研究进展，到最后附录比正文还厚得多。在我国，就少见这种延续性。人家真是把教材当作一项事业来做的。中国最有名的计算机书估计是谭老师的C语言，去年貌似也出了个新版，除了换个封面，里面新瓶装旧酒，继续误人子弟。对谭老师C语言书的声讨网上已经进行多年，我也没有重复的必要。只是想到这些状况，不能不有点觉得外国月亮有点圆。

本来想把电子版放上来，但尺寸实在吓人（近50M)，我估计赛族上对这个感兴趣的人也不会太多，如果想要电子版的话，私人联系吧。当然直接google也可以。

下面是三版龙书封面展览：

阅读(1172 次)

A Short Definition

A static library is basically a collection of object files.During the linking phase of compilation,the static library,or the object files in it, will be simply copied into the target executable file.Static libraries usually ends with a “.a” suffix in UNIX variants(including MinGW) and “.lib” in Windows.

A shared library,also called dynamic library(on Windows,they are the familiar dlls,the origin of “DLL Hell”) is “dynamically” linked into program in runtime.Why I use “dynamically” here is that during compilation the object files contained in shared library are not inserted into the final executable file;instead, when the program is started, a program in the system (called a dynamic loader) checks out which shared libraries were linked with the program, loads them to memory, and attaches them to the copy of the program in memory.

Creating Static Library

Suppose you have some object files with the name util1.o,util2.o,….Then then following command will create a static library “libutil.a” and puts all the objs into it:

ar rcs libutil.a util1.o util2.o ...

Note that the static library must start with “lib” and have the suffix “.a”

ar can be used to creating,modifying and checking static libraries.
Read the rest of this entry »

阅读(662 次)

While I’m working on the module of my project which translating arithmetic operations into machine code,I think I should take a look at how gcc does it,especially (one of)the most wierd operation in i386 instruction set,div.After examining gcc’s output(using -S option when compiling),I find something interesting.When divisor is a constant integer,for example,an expression like x/3 (assuming x is a local variable with type int)in C source code,gcc will translate it into a seemingly strange sequence of instructions:

movl  $1431655766, %eax
imull x
movl  %edx, %ecx
movl  x, %eax
sarl  $31, %eax
subl  %eax, %ecx

(the result is stored in %ecx)

Read the rest of this entry »

阅读(847 次)

考完试了，有几天空闲时间。我想起还有个建设中的编译器被我遗忘在目录深处，决定利用这几天工夫好好来写点代码。

这个玩具编译器（我的计划是未来某一天它不再是一个toy language，我设想了许多美好的特性，但我现在还没有足够的技术和时间来实现他们）的前端已经完工。编译器前端——词法分析、语法分析——在教科书上占一半的篇幅，涉及到不少理论知识，但实际上是个无聊的工作。而code generation则是麻烦而繁琐的。网上可以找到全套的工具——从flex、bison这样的前端生成器，到MLRISC这样完备的后端，但我还是想自己动手写一遍。 我现在去看几个月以前写的code generation，惊奇于这样丑陋而复杂的代码居然（貌似）是对的。

我的目标是生成机器代码，这两天花了不少功夫研究IA32处理器的浮点运算，深刻地认识到FPU是一个多么难看的设计，让我的代码增加了无数的条件分支和switch。想了解一下MIPS在这个问题上是怎么处理的。string，class等已经初步提上日程。至于我幻想中的gc及lambda expression,high-order function,continuation等一干functional特性，现在还遥遥无期。

从书签里翻出一篇老文章，一直没细读，Modern x86 assembly （blogspot….被和谐掉了。同志们上代理。），里面着重谈了alignment(对齐）和caching(缓存）。对现代的计算机架构，这两样东西对性能有极其重要的影响。对齐主要是编译器考虑的问题；而cache的影响则更为微妙。准备好好学习一下。

阅读(603 次)