编程语言是向人以及机器描述计算过程的 notations。
关于翻译
没办法，编译器是外国人发明的，所以很多词汇在编译原理中含义是不一样的，按惯用法翻译成中文，就无法一一对应（说实话，有些词语在英文里也是混用的）。比如有很多个单词，翻译成中文就都成了 “符号”。但是我实在不想中英夹杂， 因为切换输入法太麻烦了 所以我干脆自己做一个翻译规则表，当然也不是乱翻的，参考了别人的翻译。
| 英语 | 汉语 |
|---|---|
| concept/notion | 概念 |
| character | 字符 |
| notation | 记号 / 记法 |
| annotation | 标注 / 注解 |
| denotation | 直指 |
| mark | 标记 |
| symbol | (象征) 符号 |
| token | 词符 |
| entry | （符号表的）条目 |
| sign | 正负号 / 征象 |
| - signifier | 能指 |
| - signified | 所指 |
| signification | 意义 |
| semiotics | 符号学 * |
| semantic | 语义的 * |
| pragmatic | 语用的 * |
| string | 字符串 |
| identifier | 标识符 |
| lexeme | 词素 |
| lexical | 词法 |
| syntax | 句法 |
| grammer | 文法 |
| pattern | 规式 |
| paradigm | 范式 |
| schema | 方案 |
| schema | 章法 |
| diagram | 简图 |
| model | 模型 |
| specification | 规格 |
| normal form | 规范型 |
| sentence | 句子 |
| clause | 子句 |
| function | 函数 |
| tag | 挂签 |
| label | 标签 |
| category | 范畴 / 分类 |
| parameter | 形参 |
| argument | 实参 |
| attribute | 字段 |
| property | 函数属性 |
| statement | 陈述 |
| assignment | 赋值 |
| operator | 运算符 |
| operand | 运算对象 |
| representation | 表示法 |
1.1 语言处理器
编译器和解释器的差别
编译器（compiler）：将源语言翻译为目标语言的程序。翻译的结果称为目标程序（target program）。
目标程序的运行过程：
解释器（interpreter）：基于输入，直接执行源程序规定的操作。
解释器的运行过程：
二者比较
- 使用编译通常有更高的执行性能（如 C/C++/Go）
- 使用解释通常有更好的兼容能力（如 Java/C#/Python）
1.2 编译器的结构
编译器包含两部分： 分析和综合（analysis and synthesis）
分析：将源程序分解为组分（constituents），在其上施加一个语法结构（grammatical structure）。然后利用这个结构，制造源程序的中间表示（intermediate representation）。如果有句法（syntactical）或（semantical）的问题，就会反馈一些提示消息（informative message）。分析部分还会收集关于源程序的信息，然后存储在符号表（symbol table）中。符号表和中间表示会传递到综合部分。
编译是分阶段（phases）进行的，每一阶段都会将程序的一种表示变换为另一种。典型的阶段划分如下：
1.2.1 词法分析
词法分析（lexical analysis），又称扫描（scanning）会读取字符流输入，将其划分为有意义的序列，称为词素，对于每个词素，词法分析器产生如下形式的词符（Token）输出：
词符的 词符名 是一个用于下阶段 句法分析（syntax analysis）的抽象符号， 字段值 则指向一个符号表中的条目（entry）。
例如有一个赋值陈述：
position = initial + rate * 60
则会产生如下词素：
position：将会被映射到一个词符<id, 1>，其中id是一个表示标识符（identifier）抽象符号，1表示标识符的条目（entry）在符号表的位置。=：将会映射到词符<=>initial：将会映射到词符<id, 2>+：将会映射到词符<+>rate：将会映射到词符<id, 3>*：将会映射到词符<*>60：将会映射到词符：<number, 60>
于是经过词法分析，我们得到了这样的序列：
<id,1> <=> <id,2> <+> <id,3> <*> <60>
1.2.2 句法分析
句法分析（syntax analysis，也叫 parsing）将会使用词符作为输入，用来创建一个树状中间层，从而表示词符流的语法结构。以上例，输出将是：
=
/ \
id,1 \
+
/ \
/ \
id,2 *
/ \
/ \
id,3 60
这称为句法树（syntax tree）
1.2.3 语义分析
语义分析（semantic analysis）利用句法树和符号表检查源程序，保证同语言定义（language definition）的语义一致性（semantic consistency）。同时收集类型信息并将其保存在句法树或符号表中，以便下一步生成中间代码。
语义分析的一个重要部分是类型检查，从而保证运算符与运算对象匹配。（比如数组取数操作要求索引值为非负整数）。
语言规格（language specification）有可能允许隐式类型转换（type coercions）。例如例子中可能要把 60 转换为浮点数，则语义分析需要指明这种转换（例中 inttofloat）
1.2.4 中间码生成
在编译过程中，有可能用到不止一种中间表示，表示的形式也可以各有不同。在句法分析和语义分析之后，编译器往往会生成一种详细、低级或者像机器码一样的中间表示层，其特点是结构非常简单，容易生成，页容易翻译成目标机器的机器语言。例：
t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
这种中间形式（intermediate form）称为三地址码（three-address code），即一个运算符，三个运算数：
f = OP(R1, R2, R3)
1.2.5 代码优化
就字面意思，比如上面的可以优化成：
t1 = id3 * 60.0
id1 = id2 + t1
1.2.6 代码生成
就生成机器码，比如生成下面的 RISC 码：
LD R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1
1.2.7 符号表管理
编译器的一个基本功能是记录源程序使用的变量名，并收集每个名称的字段信息。这些字段包括：分配的存储空间、类型、作用域、参数的数量和类型、传参的方式（引用还是值）。
符号表是一个保存变量名、名称的字段信息的数据结构。
1.2.8 Pass
几个阶段（phase）的组合称为一个 Pass（没想到合适的翻译），它能读入一个文件并输出一个文件。
例如，编译的前端（front-end）阶段包括：词法分析、句法分析、语义分析和中间代码生成。这些合起来是一个 Pass。
而代码优化可以是一个选择性的 Pass。而后端 Pass 则是生成具体的目标语言代码。
这体现了一种分层抽象接口的原则，因此可以让不同的前端编译出相同的中间代码，然后共用一个后端，生成目标机器码。
1.2.9 编译 - 构建工具
解析器生成器（Parser generators）：能够从语法描述生成句法分析器。
扫描器生成器（Scanner generators）：能够从语言的词符的正则描述生成词法分析器。
面向句法的翻译引擎（Syntax-directed translation engine）：能够生成 routine 集，以便遍历解析树并生成中间代码。
代码生成器生成器（Code-generator generators）：从规则生成代码生成器，以便将中间语言的每个操作，翻译到目标机器语言。
数据流分析引擎（Data-flow analysis engines）：分析数据在程序各部分之间的传输。
编译器 - 构建工具包（Compilers-construction toolkits）：提供 routine 的集成，以便构建一个编译器的不同阶段。
1.3 编程语言的演进
1.3.1 走向高级语言
第一代语言：机器语言
第二代语言：汇编语言
第三代语言：高级语言，如 Fortran，Cobol，Lisp，C，C#，Java
第四代语言：领域应用语言，如 NOMAD（报表生成），SQL（数据库查询），Markdown。
第五代语言：基于逻辑和约束的语言，比如 Prolog 和 OPS5。
命令式语言（imperative）：程序指明计算的流程（how to）
声明式语言（declarative）：指明程序要进行的计算（what to）
函数式语言（functional）：将一切运算视为函数，抗拒引入状态
老组合逻辑电路了
声明式语言包括函数式语言如 ML、Haskell 以及 Prolog。
冯诺依曼语言：计算模型基于冯诺依曼体系结构。
面向对象语言：支持面向对象编程的语言，程序视为对象之间的交互。
脚本语言：解释执行的语言。
1.4 设计编译器的科学
1.4.1 编译器设计的建模以及实现
主要涉及自动机和规则式理论、代码优化以及程序的结构表示和翻译等。
1.4.2 代码优化
编译器优化必须满足以下设计目标
- 优化必须是正确的。即不改变程序的含义
- 优化必须能提高大量程序的性能
- 编译时间要合理
- 整个工程要便于管理
1.5 编译技术的应用
可以用来：
- 实现高级编程语言
- 针对计算机架构优化
- 设计新的计算机架构
- 程序翻译（比如用于硬件设计的 VHDL）
- 软件生产力工具（如类型检查、边界检查）
1.6 编程语言的基础
1.6.1 静态和动态之分
- 在编译时可完成判定，则是静态语言
- 在运行时可完成判定，则是动态语言
作用域（scope）：在某范围内，所有对 $x$ 的引用都指向某个声明，则此范围是 $x$ 的作用域。
静态作用域：在编译时可以确定一个声明的作用域。又称词法作用域（lexical scope）。否则成为动态作用域。
例如 static 修饰的 Java 类变量，在编译期就可以确定其内存位置（相对位置），则是静态的。而去除 static 修饰之后，必须在程序运行之后，对象的内存分配之后，才知道其内存位置，这就是动态的。
1.6.2 环境与状态
从名称到值存在两步映射
- 从名称到内存位置的映射。这个映射称为环境（environment）
- 从内存位置到值的映射。这个映射称为状态（state）
名称、标识符和变量
标识符：一个字符串，用于指代一个数据对象
名称：编译时的名字
变量：运行时的内存地址
1.6.3 静态作用域和块结构
块：声明和语句的组合。C 使用 {} 进行块的界定。
静态作用域就是可以在编译器确定的作用域，一个声明的作用域在声明的位置隐式地决定。
1.6.4 显式访问控制
一些 OO 语言提供 public, private, protected 这样的关键字，用于控制对超类成员名称的访问权限。
- 公有：可以被任何地方访问
- 私有：只能被自己访问
- 保护：只能被自己和后代访问
声明：告知名称的类型。如 int i
定义：告知名称的值。如 i = 1
1.6.5 动态作用域
动态作用域：作用域要在程序执行时才知道
传参机制
实参：在调用时使用的参数
形参：在定义时表示的参数
值调用（call-by-value）：使用值局限于过程，不会修改实参。
引用调用（call-by-ref）：实参的地址被传给被调者，因此有可能修改参数。