如何更好的掌握编译器的设计与实现

一般的编译器可能包含下面这些模块:

1, 词法分析器:

输入: 源代码

输出: token

2, 语法分析器:

输入: token

输出: AST

在这个过程中, 可以识别出不符合语法规则的语句, 就可以报syntax错误, 如果有syntax错误, 编译结束

3, 语义分析器:

输入: AST

输出: 无

在这个过程中, 根据语言的语义规则来识别语义错误, 要识别语义错误 就必须编译AST, 因为是树的遍历, 假如你先遍历到了int a 这个节点, 接着又遍历到了一个表达式a = 4这个节点, 你需要检查变量a有没有声明啊, 变量a和4的类型批不匹配呢? 这时你如果没有保存变量a的信息, 那么你怎么检查? 所以就需要符号表来保存这些信息了.

4, 代码优化:

最简单的就是常量折叠优化了, 比如: a = 1 + 2 这个语句可以直接换成: a = 3了, 也就是说在编译阶段就把一些必要的运算先计算完成, 在程序运行的时候就不需要计算这些了, 就提高了程序的运行效率. 这部分是最复杂的了, 还有各种各样各样的优化

5, 代码生成:

输入: AST

输出: 可以是虚拟机代码, 可以是本地汇编代码

简单性——词法分析技术不如语法分析技术技术复杂，分开之后词法分析过程更简单。(这里还有一些意思差不多的话)

效率——词法分析占用的时间是整个编译时间的一大部分，所以将它们分开有利于优化词法分析，而提高编译效率

可移植性——词法分析通常平台相关，语法分析器可以是平台无关的。分开了对移植有利。

（引自《程序设计语言概念》(第9版)  Sebesta著）

全加器有3个输入端：a,b,ci；有2个输出端：s,co.

与3-8译码器比较，3-8译码器有3个数据输入端：a,b,c；3个使能端；8个输出端，out(0-7)。

这里可以把3-8译码器的3个数据输入端当做全加器的3个输入端，即3-8译码器的输入a、b、c分别对应全加器的输入a,b,ci；将3-8译码器的3个使能端都置为有效电平，保持正常工作；这里关键的就是处理3-8译码的8个输出端与全加器的2个输出的关系。

现在写出全加器和3-8译码器的综合真值表：

（a/a,b/b,c/ci为全加器和译码器的输入，out为译码器的输出（0-7），s为加法器的和，co为加法器的进位输出）ps:假定译码器的输出为高电平有效。

a/a

b/b

c/ci

out

s

co

0

0

0

0

0

0

0

0

1

1

1

0

0

1

0

2

1

0

0

1

1

3

0

1

1

0

0

4

1

0

1

0

1

5

0

1

1

1

0

6

0

1

1

1

1

7

1

1

根据上面的真值表，可以设计出电路图：

将3-8译码器的输出out(1、2、4、7)作为一个4输入的或门的输入，或门的输出作为加法器的和；将3-8译码器的输出out(3、5、6、7)作为一个4输入的或门的输入，或门的输出作为加法器的进位输出。即完成了加法器的设计。

回过头来分析：

当加法器的输入分别为：a=1,b=0,ci=1时，对应3-8译码器的输入为a=1,b=0,c=1，这是译码器对应的输出为out(5)=1,其余的为0，根据上面设计的连接关系，s=0,co=1,满足全加器的功能，举其他的例子也一样，所以，设计全加器的设计正确。

第1章　编译器概述

　1.1　为什么要学习编译技术

　1.2　编译器和解释器

　1.3　编译器的功能分解和组织结构

　1.4　编译器的伙伴

　1.5　编译器的复杂性

　1.6　编译器的设计与实现

　1.7　编译器的测试与维护

第2章　一个微型编译器

　2.1　基础知识

　2.2　ToyL语言

　2.3　ToyL语言词法分析器

　2.4　ToyL语言语法分析器

　2.5　ToyL语言解释器

　2.6　ToyL语言编译器

第3章　有穷自动机与词法分析

　3.1　词法分析基础

3.1.1　词法分析器的功能

3.1.2　单词识别

3.1.3　词法分析的复杂性

3.1.4　字符串

3.1.5　保留字处理

3.1.6　空格符、回车符、换行符

3.1.7　括号类配对预检

3.1.8　词法错误修正

3.1.9　词法分析独立化的意义

　3.2　有穷自动机

3.2.1　确定有穷自动机的定义

3.2.2　确定有穷自动机的实现

3.2.3　非确定有穷自动机

3.2.4　NFA到DFA的转换

3.2.5　确定有穷自动机的极小化

3.2.6　自动机状态转换表的实现

　3.3　正则表达式

3.3.1　正则符号串集

3.3.2　正则表达式的定义

3.3.3　正则表达式的局限性

3.3.4　正则定义

3.3.5　正则表达式到有穷自动机的转换

　3.4　词法分析器的构造

3.4.1　用DFA人工构造词法分析器

3.4.2　词法分析器的生成器Lex

　练习

第4章　文法与语法分析

　4.1　语法分析

4.1.1　语法分析器的输入

4.1.2　语法分析的任务

4.1.3　语法分析方法分类

　4.2　文法和文法分析

4.2.1　上下文无关文法和语言

4.2.2　最左推导和最右推导

4.2.3　语法分析树与二义性

4.2.4　文法分析算法

4.2.5　自顶向下方法概述

4.2.6　自底向上方法概述

　4.3　递归下降法——自顶向下分析

4.3.1　递归下降法原理

4.3.2　消除公共前缀

4.3.3　代入

4.3.4　消除左递归

　4.4　LL分析方法——自顶向下分析

4.4.1　LL(1)文法

4.4.2　LL(1)分析表

4.4.3　LL(1)分析的驱动器

4.4.4　LL(1)中的If-Then-Else问题

4.4.5　LL(1)分析器的自动生成器LLGen

4.4.6　LL(1)分析法与递归下降法的比较

4.4.7　正则文法

　4.5　LR方法——自底向上分析

4.5.1　句柄

4.5.2　活前缀

4.5.3　归约活前缀识别器——LR(0)自动机

4.5.4　LR(0)文法及其分析算法

4.5.5　SLR(1)文法及其分析算法

4.5.6　LR(1)文法

4.5.7　LALR(1)文法

4.5.8　二义性文法的处理

4.5.9　另一种Shift-Reduce分析技术：简单优先法

4.5.10　LL(1)和LALR(1)方法比较

　4.6　LR分析器的生成器

4.6.1　LALR分析器的生成器YACC

4.6.2　LALR分析器的生成器LALRGen

　4.7　语法错误处理

4.7.1　错误恢复和修复

4.7.2　递归下降分析的错误恢复

4.7.3　LL分析的错误恢复

4.7.4　LR分析的错误恢复

　练习

第5章　语义分析

　5.1　语义分析基础

5.1.1　语义分析内容

5.1.2　标识符信息的内部表示

5.1.3　类型信息的内部表示

5.1.4　运行时值的表示

　5.2　符号表

5.2.1　符号表查找技术

5.2.2　符号表的局部化

5.2.3　二叉式局部符号表

5.2.4　散列式全局符号表

5.2.5　嵌套式全局符号表

5.2.6　符号表界面函数

　5.3　类型分析

5.3.1　类型的等价性和相容性

5.3.2　类型分析的总控算法

5.3.3　类型名分析

5.3.4　枚举类型分析

5.3.5　数组类型分析

5.3.6　记录类型分析

5.3.7　联合类型分析

5.3.8　指针类型分析

5.3.9　递归类型分析

　5.4　声明的语义分析

5.4.1　声明的语法结构

5.4.2　标号声明部分的语义分析

5.4.3　常量声明部分的语义分析

5.4.4　类型声明部分的语义分析

5.4.5　变量声明部分的语义分析

5.4.6　过程、函数声明的语义分析

　5.5　执行体的语义分析

5.5.1　执行体的语义分析

5.5.2　带标号语句和转向语句的语义分析

5.5.3　赋值语句的语义分析

5.5.4　条件语句的语义分析

5.5.5　while循环语句的语义分析

5.5.6　for循环语句的语义分析

5.5.7　过程调用语句的语义分析

5.5.8　表达式的语义分析

5.5.9　变量的语义分析

　练习

第6章　运行时的存储环境

　6.1　运行时的存储空间结构与分配

6.1.1　运行时的存储空间基本结构

6.1.2　静态区的存储分配

6.1.3　栈区的存储分配

6.1.4　堆区的存储分配

6.1.5　堆区空间管理

　6.2　过程活动记录与栈区组织结构

6.2.1　过程活动记录

6.2.2　活动记录的填写

6.2.3　栈区组织结构——AR链

　6.3　运行时的变量访问环境

6.3.1　可访问活动记录

6.3.2　局部Display表方法

6.3.3　静态链方法

6.3.4　全局Display表方法和寄存器方法

6.3.5　无嵌套时的AR及访问环境

　6.4　分程序和动态数组空间

6.4.1　无动态数组时的分程序空间

6.4.2　动态数组空间

　练习

第7章　面向语法的语义描述

　7.1　动作文法

7.1.1　动作文法定义

7.1.2　动作文法的递归实现

7.1.3　动作文法的LL实现

7.1.4　动作文法的LR实现

　7.2　动作文法应用

7.2.1　用动作文法描述表达式计算

7.2.2　用动作文法描述表达式抽象树的构造

7.2.3　用动作文法描述语句抽象树的构造

　7.3　抽象动作文法及其应用

7.3.1　抽象变量

7.3.2　抽象动作文法

7.3.3　栈式LL动作文法驱动器

7.3.4　抽象动作文法到栈式LL动作文法的转换

7.3.5　栈式LR动作文法驱动器

7.3.6　抽象动作文法到栈式LR动作文法的转换

　7.4　属性文法

7.4.1　属性文法定义

7.4.2　属性语法树和属性依赖图

7.4.3　计算顺序

7.4.4　属性值的计算方法

7.4.5　拷贝型属性文法

　7.5　属性文法在编译器设计中的应用

7.5.1　类型树的属性文法描述

7.5.2　表达式中间代码的属性文法描述

7.5.3　变量中间代码的属性文法描述

7.5.4　语句中间代码的属性文法描述

7.5.5　正则表达式到自动机转换的属性文法描述

　7.6　S-属性文法及其属性计算

7.6.1　S-属性文法

7.6.2　S-属性文法的递归实现

7.6.3　S-属性文法的LR实现

　7.7　L-属性文法及其属性计算

7.7.1　L-属性文法

7.7.2　L-属性文法的递归实现

7.7.3　L-属性文法的LR(1)实现

　7.8　语义分析器的自动生成系统

7.8.1　YACC

7.8.2　LALRGen

7.8.3　Accent系统

　练习

第8章　中间代码生成

　8.1　中间代码

8.1.1　中间代码的种类

8.1.2　后缀式中间代码

8.1.3　三地址中间代码

8.1.4　抽象语法树和无环有向图

8.1.5　多元式中间代码

8.1.6　中间代码分量ARG结构

　8.2　表达式的中间代码生成

8.2.1　表达式的语义信息

8.2.2　表达式的中间代码

8.2.3　变量的中间代码

8.2.4　表达式的中间代码生成

8.2.5　变量的中间代码生成

8.2.6　布尔表达式的短路中间代码

　8.3　原子语句的中间代码生成

8.3.1　输入/输出语句的中间代码生成

8.3.2　goto语句和标号定位语句的中间代码生成

8.3.3　return语句的中间代码生成

8.3.4　赋值语句的中间代码生成

8.3.5　函数（过程）调用的中间代码生成

　8.4　结构语句的中间代码生成

8.4.1　条件语句的中间代码生成

8.4.2　while语句的中间代码生成

8.4.3　repeat语句的中间代码生成

8.4.4　for语句的中间代码生成

8.4.5　case语句的中间代码生成

8.4.6　函数声明的中间代码生成

　练习

第9章　中间代码优化

　9.1　引言

9.1.1　优化的目标和要求

9.1.2　优化的必要性

9.1.3　优化的内容

9.1.4　局部优化和全局优化

9.1.5　基本块和程序流图

　9.2　常表达式优化

9.2.1　常表达式的局部优化

9.2.2　基于常量定值分析的常表达式全局优化

9.2.3　常量定值分析

　9.3　公共表达式优化

9.3.1　基于相似性的公共表达式局部优化

9.3.2　基于值编码的公共表达式局部优化

9.3.3　基于活跃代码分析的公共表达式全局优化

9.3.4　活跃运算代码分析

　9.4　程序流图循环

9.4.1　循环的基本概念

9.4.2　支撑结点

9.4.3　自然循环

9.4.4　可归约程序流图

9.4.5　基于文本的循环及其处理

　9.5　循环不变代码外提

9.5.1　代码外提的基本概念

9.5.2　循环不变代码的判定

9.5.3　循环不变代码外提的条件

9.5.4　基于文本循环和定值表的不变代码外提

9.5.5　一种简单的外提优化方案

9.5.6　别名分析

9.5.7　过程与函数的副作用分析

　9.6　循环内归纳表达式的优化

9.6.1　归纳变量

9.6.2　归纳变量计算的优化算法原理

　练习

第10章　目标代码生成

　10.1　目标代码

10.1.1　虚拟机代码

10.1.2　目标机代码

10.1.3　窥孔优化

　10.2　临时变量

10.2.1　临时变量的特点

10.2.2　临时变量的存储空间

10.2.3　临时变量的存储分配

10.2.4　变量状态描述

　10.3　寄存器

10.3.1　寄存器分类及其使用准则

10.3.2　寄存器分配单位

10.3.3　寄存器状态描述

10.3.4　寄存器分配算法

　10.4　基于三地址中间代码的目标代码生成

10.4.1　目标地址生成

10.4.2　间接目标地址的转换

10.4.3　表达式中间代码的目标代码生成

10.4.4　赋值中间代码的目标代码生成

10.4.5　其他寄存器分配法

10.4.6　标号和goto语句中间代码的目标代码生成

10.4.7　return中间代码的目标代码生成

10.4.8　变量中间代码的目标代码生成

10.4.9　函数调用中间代码的目标代码生成

　10.5　基于AST的代码生成

10.5.1　三地址中间代码到AST的转换

10.5.2　标记需用寄存器个数

10.5.3　从带寄存器个数标记的AST生成代码

　10.6　基于DAG的代码生成

10.6.1　从AST到DAG的转换

10.6.2　DAG排序和虚寄存器

10.6.3　从带序号和虚寄存器标记的DAG生成代码

　10.7　代码生成器的自动生成

10.7.1　代码生成器的自动化

10.7.2　基于指令模板匹配的代码生成技术

10.7.3　基于语法分析的代码生成技术

　练习

第11章　对象式语言的实现

　11.1　引言

　11.2　SOOL语法

11.2.1　程序

11.2.2　分程序

11.2.3　类声明

11.2.4　类型

11.2.5　变量声明

11.2.6　函数声明和方法声明

11.2.7　语句

11.2.8　变量

11.2.9　表达式

11.2.10　程序示例

　11.3　SOOL语义

11.3.1　声明的作用域

11.3.2　Class声明的语义

11.3.3　语句的语义

　11.4　SOOL语义分析

11.4.1　标识符的符号表项

11.4.2　符号表结构

11.4.3　符号表的局部化

　11.5　SOOL目标代码

11.5.1　对象空间

11.5.2　当前对象——self

11.5.3　活动记录

11.5.4　成员变量的目标地址

11.5.5　表达式的目标代码

11.5.6　Offset原理

11.5.7　类的多态性

11.5.8　目标代码区

11.5.9　方法的动态绑定

11.5.10　快速动态绑定目标代码

主要参考文献

编译器，是一种翻译软件。它将用一种语言编写的程序，翻译成另一种语言的程序，而保持功能不变。一般编译器多数是将高级语言翻译成低级语言。

计算机图形学－－主要是一些图形显像的原理和算法，和编程靠点边，但是有点复杂，这个和楼主的专业有一点点联系吧，不过图形学里面的编程似乎其他地方都用不到

密码学－－基本上是纯数学了，讲密码的加密和解密，感觉不深学的话很简单，学了不搞研究的话基本没有用

如果楼主想好好学学编程的话，不如直接去把C看个透彻，了解一下C＋＋，其他都是一通百通的

要是非要在这三个课程里面选一个的话，我建议楼主选计算机图形学。<

学习编程，从何入手？

如果您想学习编程，却又不知从何入手，那么您不妨看看下面的几种学习方案，可能会给您一些启示吧！

方案一 Basic语言 &Visual Basic

优点

（1）Basic 简单易学，很容易上手。

（2）Visual Basic 提供了强大的可视化编程能力，可以让你轻松地做出漂亮的程序。

（3）众多的控件让编程变得象垒积木一样简单。

（4）Visual Basic 的全部汉化让我们这些见了English就头大的人喜不自禁。

缺点

（1）Visual Basic 不是真正的面向对象的开发文具。

（2）Visual Basic 的数据类型太少，而且不支持指针，这使得它的表达能力很有限。

（3）Visual Basic 不是真正的编译型语言，它产生的最终代码不是可执行的，是一种伪代码。它需要一个动态链接库去解释执行，这使得Visual Basic 的编译速度大大变慢。

综述：方案一适合初涉编程的朋友，它对学习者的要求不高，几乎每个人都可以在一个比较短的时间里学会vB编程，并用VB 做出自己的作品。对于那些把编程当做游戏的朋友来说，VB 是您最佳的选择。

方案二 Pascal语言 &Delphi

优点

（1）Pascal语言结构严谨，可以很好地培养一个人的编程思想。

（2）Delphi是一门真正的面向对象的开发工具，并且是完全的可视化。

（3）Delphi使用了真编译，可以让你的代码编译成为可执行的文件，而且编译速度非常快。

（4）Delphi具有强大的数据库开发能力，可以让你轻松地开发数据库。

缺点

Delphi几乎可以说是完美的，只是Pascal语言的过于严谨让人感觉有点烦。

综述: 方案二比较适合那些具有一定编程基础并且学过Pascal语言的朋友。

方案三 C语言 &Visual C++

优点

（1）C语言灵活性好，效率高，可以接触到软件开发比较底层的东西。

（2）微软的MFC库博大精深，学会它可以让随心所欲地进行编程。

（3）VC是微软制作的产品，与操作系统的结合更加紧密。

缺点

对使用者的要求比较高，既要具备丰富的C语言编程经验，又要具有一定的WINDOWS编程基础，它的过于专业使得一般的编程爱好者学习起来会有不小的困难。

综述: VC是程序员用的东西。如果你是一个永不满足的人，而且可以在编程上投入很大的精力和时间，那么学习VC你一定不会后悔的。

方案四 C++语言 &C++ Builder

优点

（1）C++语言的优点全部得以继承。

（2）完全的可是化。

（3）极强的兼容性，支持OWL、VCL和MFC三大类库。

（4）编译速度非常快。

缺点

由于推出的时间太短，关于它的各种资料还不太多。

综述：我认为C++ Builder 是最好的编程工具。它既保持了C++语言编程的优点，又做到了完全的可视化。

方案五 SQL语言 &Power Builder

对于一些传统的数据开发人员来说，Foxpro系列也许让他们感到更加熟悉。但是对于初学者来说，PowerBuilder也许是最好的数据库开发工具。各种各样的控件，功能强大的PowerBuilder语言都会帮助你开发出自己的数据库应用程序<

难道编写这些功能强大的软件调用的是编译器中内置的已经写好的具有某种强大功能的函数吗？

要想实现具有某些复杂功能的界面软件，一般都有库函数让你调用，windows下有MFC,linux下有QT等，JAVA上面则有swing，但是切记，一般的图形界面库只给你提供界面的显示，其具体功能还是要你自己来实现的，这就好比这些库函数给你一个外壳，你向里面装什么东西由你决定。

至于你所说的在屏幕上打印结果，则是编程的基础，因为大多数软件的作用都是和数据打交道，无非是对数据的增、删、改、查，显示等操作。而你在屏幕上打印的计算结果，即是对数据的改，和显示的过程，只不过显示的时候放在终端而已，而当你使用界面库函数的时候，就可以把这个结果显示到你需要显示的界面上去了。

最后，编程语言不仅仅只是对阿拉伯数字的