程序设计语言
第1部分：基础
第1章：引言
语言设计的艺术
概念的清晰性和实现的效率都是最基本的诉求；因此程序设计更像是一种艺术，因为它经常需要在二者之间做出折中；
程度设计语言的谱系
计算机的本质是在做计算，不同的语言，将计算视为不同的概念；
- 函数式：将计算视为输入和输出的函数；
- 面向对象：将计算视为不同独立对象之间的相互作用；
- 逻辑式：将计算视为找出满足某些特定关系的值的尝试过程；
- 冯诺依曼式：将修改变量的值做为计算的一种基本方式；
- 脚本式：粘合多个独立开发的程序部件，实现某些特定的目的；强调表达的方便，以便用于快速的建立原型，但一般会牺牲一些执行的速度；
程序语言本身的表达逻辑，会不自觉的影响程序员的思考方式；
编译和解释
编译和解释的区别
- 编译器本身也是由某种高级语言写的源程序编译而成的目标程序；编译器不控制输入的执行过程；在翻译成目标程序后，编译器就不再管了；
- 解释器通过迟约束（late binding），将有关程序实现的决策推迟到运行时再进行，从而带来了更大的灵活性，它完全控制了执行的过程，因此能对源程序做出更好的诊断和调试；缺点是牺牲了性能，尤其是当程序被多次运行的时候更加明显；
编译和解释的根本区别在于是否介入执行的过程；有很多语言的实现采用了编译和解释二者混合的形式；
编译与预处理的区别
- 是否进行彻底的分析和非简单的变换，即为编译器区别于预处理器的标志性特征；
编译在广义上可以指代很多事情，只要这些事情涉及将输入的语言进行彻底的分析，并进行非简单的变换，使之成为另外一种语言；
程序设计环境
设计一个程序的过程中，不仅需要编译器和解释器，还需要其他一系列工具相互配合，包括编辑器、预处理器、汇编器、链接器、调试器、性能分析器等；
集成开发环境 IDE 通过整合上述工具进行协同工作，提高了程序设计的效率；
编译概览
前端
| 阶段 | 输入 | 输出 |
|---|---|---|
| 词法分析 | 字符流 | 单词流 |
| 语法分析 | 单词流 | 语法分析树 |
| 语义分析 | 语法分析树 | 抽象语法树 |
后端
| 阶段 | 输入 | 输出 |
|---|---|---|
| 代码改进 | 抽象语法树 | 中间代码 |
| 目标代码生成 | 中间代码 | 目标代码 |
| 目标代码改进 | 目标代码 | 修改后的目标代码 |
词法和语法分析
- 词法分析（即扫描器）：作用在于将源代码文件中的字符组成单词，作为下一阶段语法分析的输入，提高其处理效率；同时还会移除注释，并为单词增加行号和列号信息，方便出错的定位诊断；
- 语法分析：作用在于将单词组成一棵语法树；在这棵语法树中，每一种结构，例如表达式、语句、子程序等，分别可以对应树中的一个节点；每个节点下面还有各自的子节点，每个子节点需要符合当前节点的语法规则的顺序要求；任何不符合语法规则的单词和顺序，都会被抛出错误；
语义分析和中间代码生成
语义分析的作用在于确定程序的意义，并构建出一棵抽象语法树；为了达到这个目的，它就构造一个符号表，将每个符号映射到关于该符号的所有已知信息，包括类型、内部结构、作用域等；有了符号表后，语义分析器就可以实施分析规则，确保整个程序是符合相关既定规则的；同时还可以知道哪些符号是重复引用相同的实体，因此它可以使用符号来构建出一棵更加简洁的语法树；
并非所有的语义规则都可以在编译时检查，有些需要延迟到运行时才能检查；前者称为静态语义，后者称为动态语义；
有些编译器的中间形式即是抽象语法树，而有些则是某种中间格式的语言；
目标代码生成
有了抽象语法树后，生成正确的目标代码并不困难，只需使用目标语言来翻译这棵树即可；真正的挑战在于，如何生成“良好的”目标代码；
在生成目标代码后，理论上已经不再需要符号表了，但一般仍会保存起来，因为它有利于后续的调试使用；
代码改进
改进即可以在生成目标代码之前进行，也可以在其后进行；不管哪一种，改进都是一项可选的工作，其作用在于提高程序的运算速度，或者减少资源的占用；
有些改进是机器无关，但也有些是与机器相关的；编译器可以根据程序要运行机器的特点，生成更高效的目标代码，例如利用超标量机器的并行运算能力；
第二章：程序设计语言的语法
在编写一个程序时，涉及两种角色的人员，分别是普通业务程序员和编译器程序员；
- 前者关心使用正确的语法规则来表达业务的逻辑；而这些语法规则是由一组正则表达式+上下文无关的方法进行限定的；
- 后者关心如何解析前者编写的代码，了解其代码的结构和含义，以便将其转换成目标语言；后者通过使用扫描器+语法分析器来实现这个目标；
2.1 描述语法：正则表达式和上下文无关文法
语法的表述需要某种形式化的规则；在实践中，通过三种形式化规则（拼接、选择、重复）来实现单词组合的集合；之后再使用“递归”来构建结构；二者一起共同完成了语法的表述；
单词和正则表达式
单词是程序的基本组成单元，它的种类包括：关键字、标识符、符号和常量等；
注：标识符即各种自定义的变量名，用来代表各种实体；
一般使用正则表达式的记法形式来描述单词，例如：
1 | |
注：这才是正则表达式的用法起源，它原来用来规范化描述单词，之后才被延伸使用到各种语言和工具中；
不同语言使用的字符集可能有所差别，同时还会有一些格式上面的不同规定，例如最大长度限制、行截断的意义、缩进的意义等；
上下文无关文法
在上下文无关文法中，用一条“产生式”来代表一条规则，例如：
1 | |
产生式的左边是一个非终结符，而右边则是一个终结符；终结符一般是各种单词；终结符不能放在产生式的左边，因为终结符无法再进行分解；
注：该文法有时被称为 BNF 形式；
推导和语法分析树
推导的目的是为了生成由终结符组成的终结符串；为了达到这个目的，可以有多种推导的方法，例如最右、最左、中间等；推导的结果可以表示成一棵语法分析树；但是，根据推导方法的不同，这棵树并不是唯一的；这意味着需要额外加入一些限制条件，才能消除这种歧义性；
2.2 扫描
扫描器有如下的作用：
- 通过将字符转成单词，极大简化了语法分析器的输入项，使得语法分析器的设计复杂度大大降低；
- 删除了注释等不必要的干扰信息；
- 增加了行号、列号等信息，方便后续的出错调试；
2.2.1 生成一个有穷自动机
什么是有穷自动机？
答：它的全称是确定有限状态自动机(DFA)。自动机可以根据一个给定的状态和一个给定的字符，按照事先拟好的转移函数进行计算判断，然后转移进入下一个状态；
构造有穷自动机的方法
有穷自动机可以手工编写，优点是没有冗余代码，执行效率比较高；缺点是一旦规则有增加或修改，维护起来的工作量很大；
自动机也可以用生成器来自动生成，只要给定一组正则表达式，生成器就可以自动帮忙构造出自动机；
自动生成器工作原理
自动生成器一般经过三个步骤来生成 DFA
epsilon 转换表示存在多种可能性的转换结果；
- 从正则表达式到 NFA：NFA 与 DFA 的不同点在于，它表示多种状态可能并行存在；
- 从 NFA 到 DFA：用状态集来表示一个节点，根据输入，转移到下一个状态集；若状态集中包含原 NFA 中的结束节点，则该状态集标记为结束状态；
- 最小化 DFA：先按状态集按终止状态和非终止状态分为两类；如果非终止状态类存在歧义，就逐步拆分它，直到不存在歧义为止；