Monday, October 18, 2010

内存杂碎

编译时分配内存 ---------------
楼上说的对的,编译时是不分配内存的。此时只是根据声明时的类型进行占位,到以后程序执行时分配内存才会正确。所以声明是给编译器看的,聪明的编译器能根据声明帮你识别错误。
运行时分配内存 ---------------
这是对的,运行时程序是必须调到“内存”的。因为CPU(其中有多个寄存器)只与内存打交道的。程序在进入实际内存之前要首先分配物理内存。
编译过程 --------------
只能简单说一下,因为如果要详细的话,就是一本书了《编译原理》。编译器能够识别语法,数据类型等等。然后逐行逐句检查编译成二进制数据的obj文件,然后再由链接程序将其链接成一个EXE文件。此时的程序是以EXE文件的形式存放在磁盘上。
运行过程 --------------
当执行这个EXE文件以后,此程序就被加载到内存中,成为进程。此时一开始程序会初始化一些全局对象,然后找到入口函数(main()或者WinMain()),就开始按程序的执行语句开始执行。此时需要的内存只能在程序的堆上进行动态增加/释放了。
--http://zhidao.baidu.com/question/41868474.html?fr=qrl&cid=866&index=1&fr2=query

编译其实只是一个扫描过程,进行词法语法检查,代码优化而已,编译程序越好,程序运行的时候越高效。 我想你说的“编译时分配内存”是指“编译时赋初值”,它只是形成一个文本,检查无错误,并没有分配内存空间。 当你运行时,系统才把程序导入内存。一个进程(即运行中的程序)在主要包括以下五个分区: 栈、堆、bss、data、code 代码(编译后的二进制代码)放在code区,代码中生成的各种变量、常量按不同类型分别存放在其它四个区。系统依照代码顺序执行,然后依照代码方案改变或调用数据,这就是一个程序的运行过程。
--http://zhidao.baidu.com/question/41868474.html?fr=qrl&cid=866&index=1&fr2=query

我对于C++动态绑定的理解,一句话,就是编译器用静态分析的方法加上虚拟函数的设计实现在程序运行时动态 智能执行正确虚拟函数的技术。因此要彻底理解动态绑定技术,只需要掌握两点,一是编译器的静态编译过程,二是 虚拟函数的基本知识。只要有了这两点理解,任何动态绑定的分析都是很容易的。 下面就以例子代码说明:
#include
using namespace std;

class A
...{
public:
void fA() ...{ cout << "A::fA()" << endl; }
virtual void vfA() ...{ cout << "A::vfA()" << endl; }
void emptyB() ...{ cout << "A::emptyB()" << endl; }
void vfAonly() ...{ cout << "A::vfAonly()" << endl; }
};

class B : public A
...{
public:
void fB() ...{ cout << "B::fB()" << endl; }
virtual void vfA() ...{ cout << "B::vfA()" << endl; }
virtual void vfB() ...{ cout << "B::vfB()" << endl; }
void emptyA() ...{ cout << "B::emptyA()" << endl; }
virtual void vfAonly() ...{ cout << "B::vfAonly()" << endl; }
};

int main()
...{
A* p = new B;
B& r = *(B*)p;

p->fA(); // 1
//p->fB(); // 2
p->vfA(); // 3
//p->vfB(); // 4
//p->emptyA(); // 5
p->emptyB(); // 6
p->vfAonly(); // 7

cout << endl;

r.fA(); // 8
r.fB(); // 9
r.vfA(); // 10
r.vfB(); // 11
r.emptyA(); // 12
r.emptyB(); // 13
r.vfAonly(); // 14

delete p;
return 0;
}

输出结果:

A::fA()
B::vfA()
A::emptyB()
A::vfAonly()

A::fA()
B::fB()
B::vfA()
B::vfB()
B::emptyA()
A::emptyB()
B::vfAonly()


分析: 我们通过模拟编译器的编译过程来进行解释。只看编译器是怎么编译带有标号的那些函数调用的行的。 行1. 在编译器眼中,p就是一个纯粹的A类指针,跟他指向的B类对象没有任何联系。因此,当看到 p->fA()时,编译器便去A的定义中寻找fA,找到了,于是生成调用代码。 行2. 这行如果不被注释,编译器去A的定义中寻找定义fB,但是找不到这个名字,便会输出错误信息。 行3. 编译器继续去A定义中寻找vfA,这次找到了,而且发现关键字virtual,于是,采用虚拟函数调用 代码生成技术,根据vfA的偏移值,生成代码调用虚拟函数表中该偏移值指向的函数。特别指出的 是,在静态编译期间,编译器只知道偏移值,并不知道运行时该偏移到底指向什么函数。实际效果 是,因为运行时,p指向的是B对象,因此调用的是B的虚拟函数vfA(). 行4. 这行如果不被注释,编译器去A的定义中寻找名字vfB,找不到,出错。记住第一条原则,编译器 是静态编译,不知道p和类B有联系。 行5. 同4,找不到名字emptyA。 行6. 简单,找到名字emptyB. 行7. 简单,找到名字vfAonly。 行8. 从这里开始,函数由B类引用r调用。在编译器眼中,r就是一个纯粹的B类引用,他不假设r和A有任何 关系。因此这一行,编译器去B类定义寻找名字fA。由于B继承自A,包括所有A的public函数定义, 编译器成功找到A::fA。 行9. 类似行8,找到B自身的函数定义fB。 行10. 类似行3,编译器生成代码调用虚拟函数表某偏移指向的函数。运行时该偏移指向B::vfA. 行11. 编译器生成代码调用虚拟函数表某偏移指向的函数。运行时该偏移指向B::vfB. 行12. 简单,找到名字emptyA. 行13. 简单,找到名字A::emptyB. 因为B继承自A。 行14. 编译器生成代码调用虚拟函数表某偏移指向的函数。运行时该偏移指向B::vfAonly. 为什么编译器知道 指向的是B的虚拟函数vfAonly而不是A的非虚拟函数呢?这跟另一个静态编译规则,名字隐藏,有关。 继承类的作用域中如果有基类的同名函数,继承类中的名字将隐藏基类同名函数,因此这时,编译器看 不见A::vfAonly--http://zhidao.baidu.com/question/36832319.html?si=1

所谓绑定是指,对于参与多态行为的类型,他们具有多态行为的接口是在公共基类的设计中就预先确定的。而非绑定则对于参与多态行为的类型,他们的接口没有预先定义。 在C++中通过继承实现的多态是动态绑定,通过模板实现的多态是静态绑定。动态绑定的接口是在运行期间(动态)完成的,静态绑定的接口是在编译期间(静态)完成的 --http://zhidao.baidu.com/question/16751113.html?si=5

在计算机领域,堆栈是一个不容忽视的概念,但是很多人甚至是计算机专业的人也没有明确堆栈其实是两种数据结构。
要点:
堆:顺序随意
栈:先进后出
堆和栈的区别
一、预备知识—程序的内存分配
一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放(就会造成内存泄漏的问题),程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。
3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域(data), 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域(BSS,Block Started by Symbol)。 - 程序结束后有系统释放(在整个程序的执行过程中都是有效的)
4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放 (文字常量区内的数据可以修改吗?)
5、程序代码区(code)—存放函数体的二进制代码。
二、例子程序
这是一个前辈写的,非常详细
//main.cpp
int a = 0; 全局初始化区
char *p1; 全局未初始化区
main()
{
int b; 栈
char s[] = "abc"; 栈 //abc是在栈里面,而下面的123456\0却在在常量区内,要注意这两种情况的区别
char *p2; 栈
char *p3 = "123456"; 123456\0在常量区,p3在栈上。
static int c =0; 全局(静态)初始化区
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
分配得来得10和20字节的区域就在堆区。
strcpy(p1, "123456"); 123456\0放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。 (所谓的优化是什么意思,是指P1和P2指向的是同一块内存吗?)
}

二、堆和栈的理论知识

2.1申请方式
stack:
由系统自动分配。 例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间
heap:
需要程序员自己申请,并指明大小,在c中malloc函数

如p1 = (char *)malloc(10);
在C++中用new运算符
如p2 = (char *)malloc(10);
但是注意p1、p2本身是在栈中的。

2.2 申请后系统的响应
栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。
堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,
会 遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内 存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大 小,系统会自动的将多余的那部分重新放入空闲链表中。

2.3申请大小的限制
栈:在Windows下,栈是向低地址扩展的数 据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因 此,能从栈获得的空间较小。
堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。

2.4申请效率的比较:
栈由系统自动分配,速度较快。但程序员是无法控制的。
堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.
另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度快,也最灵活

2.5堆和栈中的存储内容
栈: 在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由 右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。 当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。

堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

2.6存取效率的比较
char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在运行时刻赋值的;
而bbbbbbbbbbb是在编译时就确定的;
但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。
比如:
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
}

对应的汇编代码
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];

0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中,而第二种则要先把指针值读到edx中,在根据edx读取字符,显然慢了。

2.7小结:

堆和栈的区别可以用如下的比喻来看出:
使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗
菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。
堆和栈的区别主要分:

操作系统方面的堆和栈,如上面说的那些,不多说了。

还有就是数据结构方面的堆和栈,这些都是不同的概念。这里的堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的优先权;栈实际上就是满足先进后出的性质的数学或数据结构。

虽然堆栈,堆栈的说法是连起来叫,但是他们还是有很大区别的,连着叫只是由于历史的原因。
----http://blog.csdn.net/yulaotou/archive/2009/09/21/4577879.aspx

Tuesday, October 12, 2010

编译原理学习导论

转自 四川大学唐良
CSDN


大学课程为什么要开设编译原理呢?这门课程关注的是编译器方面的产生原理和技术问题,似乎和计算机的基础领域不沾边,可是编译原理却一直作为大学本科的必修课程,同时也成为了研究生入学考试的必考内容。编译原理及技术从本质上来讲就是一个算法问题而已,当然由于这个问题十分复杂,其解决算法也相对复杂。我们学的数据结构与算法分析也是讲算法的,不过讲的基础算法,换句话说讲的是算法导论,而编译原理这门课程讲的就是比较专注解决一种的算法了。在20世纪50年代,编译器的编写一直被认为是十分困难的事情,第一Fortran的编译器据说花了18年的时间才完成。在人们尝试编写编译器的同时,诞生了许多跟编译相关的理论和技术,而这些理论和技术比一个实际的编译器本身价值更大。就犹如数学家们在解决著名的哥德巴赫猜想一样,虽然没有最终解决问题,但是其间诞生不少名著的相关数论。



推荐参考书

虽然编译理论发展到今天,已经有了比较成熟的部分,但是作为一个大学生来说,要自己写出一个像Turboc C,Java那样的编译器来说还是太难了。不仅写编译器困难,学习编译原理这门课程也比较困难。

正是因为编译原理学习相对困难,那么就要求有好的教师和好的教材。教师方面不是我们能自己更改的,而在教材方面我们却可以按自己的意愿来阅读。我下面推荐几本好的编译原理的教材。我推荐的书籍都是国外的经典教材,因为在国内的教材中,确实还没发现什么让人满意的。



第一本书的原名叫《Compilers Principles,Techniques,and Tools》,另外一个响亮的名字就是龙书。原因是这本书的封面上有条红色的龙,也因为这本书在编译原理基础领域确实太有名气了,所以很多国外的学者都直接取名为龙书。最近机械工业出版社已经出版了此书的中文版,名字就叫《编译原理》。该书出的比较早,大概是在85或86年编写完成的,作者之一还是著名的贝尔实验室的科学家。里面讲解的核心编译原理至今都没有变过,所以一直到今天,它的价值都非凡。这本书最大的特点就是一开始就通过一个实际的小例子,把编译原理的大致内容罗列出来,让很多编译原理的初学者很快心里有了个底,也知道为什么会有这些理论,怎么运用这些理论。而这一点是我感觉国内的教材缺乏的东西,所以国内的教材都不是写给愿意自学的读者,总之让人看了半天,却不知道里面的东西有什么用。

第二本书的原名叫《Modern Compiler Design》,中文名字叫做《现代编译程序设计》。该书由人民邮电出版社所出。此书比较关注的是编译原理的实践,书中给出了不少的实际程序代码,还有很多实际的编译技术问题等等。此书另外一个特点就是其“现代”而字。在传统的编译原理教材中,你是不可能看到如同Java中的“垃圾回收”等算法的。因为Java这样的解释执行语言是在近几年才流行起来的东西。如果你想深入学习编译原理的理论知识,那么你肯定得看前面那本龙书,如果你想自己动手做一个先进的编译器,那么你得看这本《现代编译程序设计》。

第三本书就是很多国内的编译原理学者都推荐的那本《编译原理及实践》。或许是这本书引入国内比较早吧,我记得我是在高中就买了这本书,不过也是在前段时间才把整本书看完。此书作为入门教程也的确是个不错的选择。书中给出的编译原理讲解也相当细致,虽然不如前面的龙书那么深入,但是很多地方都是点到为止,作为大学本科教学已经是十分深入了。该书的特点就是注重实践,不过感觉还不如前面那本《现代编译程序设计》的实践味道更重。此书的重点还是在原理上的实践,而非前面那本那样的技术实践。《编译原理及实践》在讲解编译原理的各个部分的同时,也在逐步实践一个现代的编译器Tiny C.等你把整本书看完,差不多自己也可以写一个Tiny C了。作者还对Lex和Yacc这两个常用的编译相关的工具进行了很详细的说明,这一点也是很难在国内的教材中看到的。



推荐了这三本教材,都有英文版和中文版的。很多英文好的同学只喜欢看原版的书,不我的感觉是这三本书的翻译都很不错,没有必要特别去买英文版的。理解理论的实质比理解表面的文字更为重要。



编译原理的实质

前面已经说过,学习编译原理其实也就是学习算法而已,没什么特别的。只不过这些算法的产生已经形成了一套理论。下面我来看看编译原理里面到底有什么高深的理论吧。



几乎每本编译原理的教材都是分成词法分析,语法分析(LL算法,递归下降算法,LR算法),语义分析,运行时环境,中间代码,代码生成,代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的,所以那本龙书的内容格式几乎成了现在编译原理教材的定式,包括国内的教材也是如此。一般来说,大学里面的本科教学是不可能把上面的所有部分都认真讲完的,而是比较偏重于前面几个部分。像代码优化那部分东西,就像个无底洞一样,如果要认真讲,就是单独开一个学期的课也不可能讲得清楚。所以,一般对于本科生,对词法分析和语法分析掌握要求就相对要高一点了。



词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧,很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候,重点把正则表达式和自动机原理加了进来,然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显,就是要让词法分析从程序上升到理论的地步。



语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法,LL自顶向下算法和LR自底向上算法。LL算法还好说,到了LR算法的时候,困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了,又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器,一般都是用工具Yacc来生成,实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法,因为其实践十分简单,那么就应该要求每个学生都能自己写。当然,现在也有不少好的LL算法的语法分析器,不过要是换在非C平台,比如Java,Delphi,你不能运用YACC工具了,那么你就只有自己来写语法分析器。



等学到词法分析和语法分析时候,你可能会出现这样的疑问:“词法分析和语法分析到底有什么?”就从编译器的角度来讲,编译器需要把程序员写的源程序转换成一种方便处理的数据结构(抽象语法树或语法树),那么这个转换的过程就是通过词法分析和语法分析的。其实词法分析并非一开始就被列入编译器的必备部分,只是我们为了简化语法分析的过程,就把词法分析这种繁琐的工作单独提取出来,就成了现在的词法分析部分。除了编译器部分,在其它地方,词法分析和语法分析也是有用的。比如我们在DOS,Unix,Linux下输入命令的时候,程序如何分析你输入的命令形式,这也是简单的应用。总之,这两部分的工作就是把不“规则”的文本信息转换成一种比较好分析好处理的数据结构。那么为什么编译原理的教程都最终把要分析的源分析转换成“树”这种数据结构呢?数据结构中有Stack, Line,List…这么多数据结构,各自都有各自的特点。但是Tree这种结构有很强的递归性,也就是说我们可以把Tree的任何结点Node提取出来后,它依旧是一颗完整的Tree。这一点符合我们现在编译原理分析的形式语言,比如我们在函数里面使用函树,循环中使用循环,条件中使用条件等等,那么就可以很直观地表示在Tree这种数据结构上。同样,我们在执行形式语言的程序的时候也是如此的递归性。在编译原理后面的代码生成的部分,就会介绍一种堆栈式的中间代码,我们可以根据分析出来的抽象语法树,很容易,很机械地运用递归遍历抽象语法树就可以生成这种指令代码。而这种代码其实也被广泛运用在其它的解释型语言中。像现在流行的Java,.NET,其底层的字节码bytecode,可以说就是这中基于堆栈的指令代码的。



关于语义分析,语法制导翻译,类型检查等等部分,其实都是一种完善前面得到的抽象语法树的过程。比如说,我们写C语言程序的时候,都知道,如果把一个浮点数直接赋值给一个整数,就会出现类型不匹配,那么C语言的编译器是怎么知道的呢?就是通过这一步的类型检查。像C++语言这中支持多态函数的语言,这部分要处理的问题就更多更复杂了。大部编译原理的教材在这部分都是讲解一些比较好的处理策略而已。因为新的问题总是在发生,旧的办法不见得足够解决。



本来说,作为一个编译器,起作用的部分就是用户输入的源程序到最终的代码生成。但是在讲解最终代码生成的时候,又不得不讲解机器运行环境等内容。因为如果你不知道机器是怎么执行最终代码的,那么你当然无法知道如何生成合适的最终代码。这部分内容我自我感觉其意义甚至超过了编译原理本身。因为它会把一个计算机的程序的运行过程都通通排在你面前,你将来可能不会从事编译器的开发工作,但是只要是和计算机软件开发相关的领域,都会涉及到程序的执行过程。运行时环境的讲解会让你更清楚一个计算机程序是怎么存储,怎么装载,怎么执行的。关于部分的内容,我强烈建议大家看看龙书上的讲解,作者从最基本的存储组织,存储分配策略,非局部名字的访问,参数传递,符号表到动态存储分配(malloc,new)都作了十分详细的说明。这些东西都是我们编写平常程序的时候经常要做的事情,但是我们却少去探求其内部是如何完成。



关于中间代码生成,代码生成,代码优化部分的内容就实在不好说了。国内很多教材到了这部分都会很简单地走马观花讲过去,学生听了也只是作为了解,不知道如何运用。不过这部分内容的东西如果要认真讲,单独开一学期的课程都讲不完。在《编译原理及实践》的书上,对于这部分的讲解就恰到好处。作者主要讲解的还是一种以堆栈为基础的指令代码,十分通俗易懂,让人看了后,很容易模仿,自己下来后就可以写自己的代码生成。当然,对于其它代码生成技术,代码优化技术的讲解就十分简单了。如果要仔细研究代码生成技术,其实另外还有本叫做《Advance Compiler Desgin and Implement》,那本书现在由机械工业出版社引进的,十分厚重,而且是英文原版。不过这本书我没有把它列为推荐书给大家,毕竟能把龙书的内容搞清楚,在中国已经就算很不错的高手了,到那个时候再看这本《Advance Compiler Desgin and Implement》也不迟。代码优化部分在大学本科教学中还是一个不太重要的部分,就是算是实践过程中,相信大家也不太运用得到。毕竟,自己做的编译器能正确生成执行代码已经很不错了,还谈什么优化呢?



关于实践

编译原理的课程毕竟还只是讲解原理的课程,不是专门的编译技术课程。这两门课程是有很大的区别的。编译技术更关注实际的编写编译器过程中运用到的技术,而原理的课关注讲解其基本理论。但是计算机科学本身就是一门实践性很强的课程,如果能够学以致用,那才叫真正的学会。李阳在讲解疯狂英语的时候就说到,只要当你会实际中运用一个单词一个词组的时候你才能叫学会了这个单词或者词组,而不是只是知道了它的拼写和意思。其实任何学习都是一样的,如果缺少了实践的结合,你不能算学会。



编译原理的课程主要就是讲解编译器产生的理论和原理,那么很简单,自己写个编译器就是最好的实践过程了。不过你得小心,编译系统可能是所有软件系统中最复杂的系统之一,不然为什么大学里面还会把编译器的编写开成一门叫做编译原理的课程来讲?我很佩服那些学了操作系统原理就开始自己写操作系统,学了编译原理就开始自己写编译器的人们,确实,在中国,敢这么做的学生太少了。且不管你这样做能不能做成功,至少有了这个尝试,会让你的程序设计,系统规划安排的功底增进不少。我下面给出一些关于实践过程中可能会遇到的困难,希望能够在你陷入困境的前帮你一把。



1. Lex和Yacc. 这两工具是作为词法分析很语法分析的工具。如果你自己写一个编译器,我十分不建议你连词法分析这种事情都亲手来写。Lex和Yacc应该是作为每本编译原理的教材的必备内容,可是在国内的教材中缺很少看到。这两个工具是Unix系统下的小东西,如果你要在Windows中运用,那么你最好去下在cygwin这个软件。它是个在Windows下模拟Unix的东东,里面就包含了flex.exe和bison.exe(yacc)这两个工具.这两个工具使用起来还挺麻烦的(其实unix 下的很多十分有用的工具都是这样), 不过在《编译原理与实践》这本书上对于这两个工具的讲解十分详细,还列举了不少实际的例子。

2. 做解释型语言比做生成机器代码的编译器简单。虽然说,做解释型的编译器,像Java那样的,你还得自己去写解释器,不过这样你就不必去查找机器代码的资料了。如果你做生成的最终机器代码编译器可能会遇到问题还有就是寄存器为基础的代码生成方法。前面说过,如果你生成的是以堆栈为基础的代码,那么其代码生成过程十分简单,需要考虑的东西也不多,如果你考虑最终的机器代码生成的话,你必须考虑机器的寄存器如何分配等麻烦的问题。

3. 考虑用别人已经生成的语法文件,尽量不要自己动手写词法文件和语法文件.以前一个朋友曾经说过,写出一个好的程序语言的语法定义,就几乎完成了一个编译器的一半.确实是这样,语法文件的编写是个很难的事情.现在网上到处都可以找到比如C语言,C++,Java, Tiny C,Minus C等语言的词法文件和语法文件,你完全可以自己下下来来用.



在《编译原理及实践》的书中,作者给出了一个Tiny C的全部代码.我自我感觉作者的这个编译器做得很不错,相对于其它php,perl等语言的源代码来说,简单得多,容易看懂,而且很清晰地展现了一个完成的编译系统的实现过程.其源代码可以在作者的网站上下载.



后话

编译原理的学习可能算是一个困难的历程,特别是对于那些不对编译系统感兴趣的同学来说.既然它已经作为了大学本科的必修课程,那么就说明的它引申出来的一套理论在整个计算机科学领域还是占有相对重要的地位.

如果我们考究一下历史,就会发现很多被称为程序设计大师的人都是编译领域的高手.写出第一个微型机上运行的Basic语言的比尔盖茨,设计出Delphi的Borland的”世界上最厉害的程序员”, Sun的JAVA之父, 贝尔实验室的C++之父…


附一篇:

编译原理一般认为是较难的一门课.从网上的评论来看,有人说学了一年半软件理论,就一门编译看不懂;有人甚至说它是大本软件课程里最难的一门;有人抱怨国内的编译教材没有一本容易懂的。   从笔者学习实践来看,第一次学了一个多月,理论部分一知半解,第二次学了一星期,基本看懂词法分析的理论部分,语法分析就一知半解了,第三次学了一星期,才基本看懂词法分析和语法分析.由此看来,这门课确实有难度.网上有的帖子,把编译器的编写搞得高深莫测一般,似乎难度极大,非常人能及.   编译原理究竟难在哪里?笔者的体会,主要在这几点:   1.错误认识: 很多人以为编译原理只能应用在写程序语言的编译器上,觉得用处不大,学习兴趣不高.而且可能觉得写编译器就必须完全手工来写.   2.自动机理论: 象NFA,DFA之类,比较抽象,要费些脑子,特别如果学离散数学时没有学自动机理论的话,更是需要多花点时间.   3.集合论的推演: 主要是一些闭包运算之类,数学基础不好的话,学起来也会感到吃力.   4.LR文法: 主要是又引入了自动机   不管哪本编译教材,即使是绝对经典”龙书”也不例外,都要涉及到这几个难点.由于这些内容本身不好懂,作者有再大的本事,也很难把书写得象小说那么流畅好懂.   明确了难点,接着想对策.大致有这么几种:   1.端正认识: 编译原理在静态文本处理上有广泛的应用,举个简单的例子,把HTML文件转化为纯文本,利用编译原理来实现”非常”简单.理解了编译原理的实用性,大概可以提高学习兴趣.   2.反复看书: 这个办法看起来最笨,却是基本的方法.忘了是哪位名人说过,书只要多看,总能看得懂的.   3.结合源码来看: 这是经典教材Compiler Design in C的作者Allen Hollub建议的方法.这本教材的特色就是包含了大段yacc,lex的代码.这也是个好方法,而且,只有看懂了代码,才能说在根本上理解了理论.当然,要完全看懂yacc的代码,工作量是很大的,而且同样要先理解理论.   4.删繁就简,避重就轻.网上流传较广的一篇《编译原理学习导论》(作者四川大学唐良)就基本是这种思路,对于词法分析,作者避免了自动机理论和集合论推演的介绍,直接搬出源码来,大大降低了理解难度,对于语法分析,作者介绍了递归下降和LL文法及相应的源码,而对LR文法,只说”理解理论就可以了”.虽然这种方法回避了对于难点的学习,但是用这种方法学习,可以在较短时间内编写出一个能够运行的词法分析器和语法分析器,可以大大提高学习积极性. --http://www.pconline.com.cn/pcedu/empolder/life/0504/597581.html

笔者的思路大体上类似第4种方法,但也稍有不同.由于一个偶然的原因, 笔者需要编写一个词法分析器和语法分析器,用于程序源代码的静态分析.开始无从下手,硬着头皮看了点编译原理,觉得困难很大.后来偶然找到一个类似的开源程序,是利用一个叫做PCCTS的编译器自动生成工具开发的,大受启发.开源就是好!笔者找来了一个叫做ANTLR的工具(它是PCCTS的新版,支持生成java,c++和c#代码),又下载了一个c语言的语法文件(因为笔者需要处理c代码文件),然后自己编了少量动作(action)语句,界面代码,分析处理代码等,就这样,在对编译原理所知甚少(以前学过的因为理解不深都忘了,只记得正则表达式)的情况下,仅用一个星期就写出了程序.   这次实践使笔者对编译原理兴趣大增,重新又学了一遍编译原理,并归纳出笔者认为比较实用有效的编译原理学习步骤:   1.先利用ANTLR之类的编译器生成工具,做一个小程序(如上面提到的HTML文件转化成纯文本文件的程序),所需知识只是正则表达式的基本知识和生成工具本身的使用方法(可以看联机帮助和网上教程(tutorial)来掌握). 这样做的好处是:   1)可以体会到编译原理的实用性,提高学习兴趣   2)入门容易,消除编译原理学习的畏难情绪.   3)获得词法分析器和语法分析器的感性认识,有利于加深对理论的理解.   4)获得编译器自动生成工具(compiler compiler)的使用经验,提高解决实际问题的能力.(实际工作很多都不是手编而是利用工具的)   2.象ANTLR之类的工具是开源(open source)的,可研究其源码,以便必要时自己手编分析程序.   3.回过头来看编译原理教材. 这时大概会发现,很多理论很容易懂,剩下的只有上面说的几个难点,多看几遍,重点突破.   4.结合教材所附源码,进一步加深对教材的理解   这里顺便提一下,有的编译原理的教材,对于输入子系统不单立一章来讲,有的甚至完全忽略,笔者认为, 输入子系统相对于词法分析器和语法分析器来说当然简单地多,但也是两者的基础,故有必要看源码来理解.在这方面,ANTLR的实现机制和Lex是不同的(当然和java与c的差异有关),可对照着看.      笔者学习VC++时,深切体会到好教材的重要.笔者开始吃了劣质光盘版”教材”和”21天学VC++”的祸害,看了一个月还如入云雾之中,后来看了《VC++技术内幕》,方才豁然开朗.但是编译原理的教材却似乎质量相差不是特别大,关键还在于合适的方法.以上方法笔者也是误打误撞总结出来的,希望有所参考价值. --http://pcedu.pconline.com.cn/empolder/life/0504/597581_1.html

Saturday, October 2, 2010

Why is the Federal Reserve Buying US Treasury Bills?

http://econ.economicshelp.org/2008/12/why-is-federal-reserve-buying-us.html

今天和友人讨论到为何Federal要购买债券, 我顺手查了点资料, 转发一篇写得比较简单的.

The Federal Reserve are buying 30 year Treasury Bills in an attempt to increase the money supply and stimulate economic activity.


At the moment banks are reluctant to lend to the private sector. This is because the recession has made lending to private companies quite risky. Also, banks are reluctant to lend to each other because of the credit crunch. Banks are buying 30 year treasury bonds because they are seen as a safe investment. They may only yield 2%, but with interest rates at 0-0.25%, it does represent some profit for a bank; in addition it is seen as safe.

Because the Fed is worried about deflation and lack of credit, they are trying to get the banks to resume more normal lending practices (lending to each other and lending to private sector.

The Federal Reserve are buying treasury bonds because:

* By buying bonds, the value increases and the interest rate on them declines. The Fed are trying to reduce interest rates on long term bonds to encourage banks to spend less money on buying Treasury bonds and lend more to private sector. (If treasury yields fell to 0%, it is less attractive to buy bonds)
* The Federal Reserve are also trying to improve the balance sheet of banks by buying 'toxic assets' - mortgage backed securities which currently have little market value.


If successful, this will create inflationary expectations (rather than deflation), encourage lending and therefore encourage economic growth.
Problems With This Scheme

1. The Federal Reserve are increasing the monetary base, there is a danger this could lead to high levels of inflation, when the velocity of circulation picks up.
2. Increasing quantity of US dollars and reducing interest rates on bonds is likely to reduce value of dollar, so dollar is likely to fall.
3. US National Debt is over 73% of GDP and is increasing all the time. This relies on people being willing to buy bonds and finance the debt.
4. The worry is that lower interest rates and a falling dollar, will discourage foreign investors from holding US treasury bills and bonds. Then the US would struggle to finance its national debt. This would then cause either inflation (potentially very high) or an increase in interest rates to attract savers.

A key issues is whether:

* Investors retain trust in the dollar
* The US government's credit worthiness - If people feared US government could default this would create real problems for the US dollar and US deficit.