待复习，做复习题

一：引言：本书的核心 3、6、7、8、10

编译：从一种语言到另一种语言的非平凡的自动翻译
预处理器、编译器、汇编器
自举、迟约束、字节码和即时编译器、微代码（固件）

核心章节

名字、作用域和约束
控制流
数据类型

核心感悟

子程序是控制抽象，类是数据抽象：刚好是对冯.诺依曼计算机的两个大类程序和数据的进一步拆分。
动态与静态一般根据运行是否区分，只是一个非常粗略的说法。
命名：使用模块等进行信息隐藏，增加信息量，减少使用别名

程序员工具箱

编辑器
美观打印程序
风格检查程序
配置管理工具
精读工具
剖析 profile 性能分析工具、排错程序

趋势：集成化

编译概览

前端和语义
后端和目标程序
编译遍

词法分析：单词
语法分析：语法分析树/上下文无关文法
语义分析：符号表，抽象语法树（简称语法树）
代码改进

二：程序设计语言的语法

扫描器-正则表达式-词法
编译器-上下文无文法-语法制导翻译

推导、句型、句子，规范推导=最右推导，通常最左或最右
语法的歧义：一个串生成多个语法分析树

LL：从左向右，最左推导，自上而下，预测性
LR：从左向右，最右推导，自下而上，移入规约
递归下降语法分析器
语法错误恢复，应急模式，异常处理机制，局部最小代价错误恢复

理论基础

正则表达式和有穷自动机等价

三：名字、作用域和约束

加工：激活各个声明，创建约束，分配堆栈空间
值的一级、二级、三级：值至少是三级，二级的值可作为参数传递，一级的值可以作为返回值可赋给变量

约束和约束时间

语言设计时、语言实现时、写程序时、编译时、连接时、装入时、运行时

生命周期和存储管理

约束的生存期与对象的生存期不一定重合
生命周期和存储管理：静态对象-绝对地址，栈对象-后进先出，堆对象-任意
堆分配算法：最佳适配算法-伙伴系统和斐波那契堆
显示释放堆对象 vs 废料收集（垃圾回收）机制

作用域规则

静态/词法作用域

通过检查程序正文确定约束
嵌套：最内嵌套作用域规则，运行时使用静态链寻找外围作用域
模块：封装一组对象，内部可见，外部导入。是否显式导入区分闭作用域和开作用域。
在不同语言有各种名字，聚合、包、名字空间等。
以模块作为管理器/类型

动态作用域

一个给定名字的当前约束是最近遇到的还没有撤销的约束
该方式令程序更难以理解，好处不突出。

引用环境的约束

深约束：创建时建立引用环境
浅约束：调用时建立引用环境
闭包：将显式的引用环境与有关子程序的引用捆绑的整体。

重载 overloading

同一个名字引用多个对象。
符号重载：+-等对应不同值的计算。
枚举常量重载：根据类型不同
函数重载：根据参数不同

六：控制流

表达式求值

优先级和结合性
赋值：命令式语言高度依赖副作用
变量的值模型和引用模型：Java 对内部类型采用值模型，对类采用引用模型
正交性：让语言特性尽可能任意组合
表达式重整：通过括号阻止
短路求值，短路运算符和非短路运算符

Goto 结构化和非结构化的流程

结构化程序设计强调自顶向下
都被替代了：

循环中退出
子程序提前返回
错误和异常

顺序复合

{}

选择

短路条件： elif 的条件可能不执行
分情况开关：case/switch，线性转跳表、顺序检查、散列、折半搜索

迭代

枚举控制
逻辑控制，前检查后检查
组合循环
迭代器

递归

都可以改写为迭代，或改写为尾递归
应用序求值和正则序求值

非确定性 nondeterminacy

并列执行/并列语句，卫式命令
卫式命令的大多数实现都不能证明是公平的

七：数据类型

类型系统

类型的定义
类型等价、类型相容、类型推理的规则

类型检查目的是保证程序遵守类型相容性规则
声明：引入一个名字和作用域
定义：描述了名字约束的类型

强类型：有时作为形容词形容贯彻类型规则的程度
- 静态类型：编译时执行所有类型检查
- 动态类型：运行时类型检查，迟约束的一种形式

标量类型/简单类型

离散/序数类型
- 整数
- 布尔
- 字符
有理数类型
实数类型
复数类型

枚举类型：一组命名元素
子界类型：某个离散的基类型的某个连续子集

复合类型/结构类型

类型构造符+简单类型

类型检查

类型等价

结构等价：每种结构算一个类型
名字等价：每次定义算一个类型

严格名字等价：别名不同
宽松名字等价：别名等价

类型转换

非变换的类型转换：改变类型但并不修改基础二进制位

八：子程序和控制抽象

语言列表

Algol 60
Algol 68
Pascal
C
ML
Java
Clu
Perl
Euclid
Turing
Ada