### 编译原理知识点概述
#### 第一章 引论
1. **宿主机与目标机**：
- **宿主机**：指编译器运行所在的计算机系统。
- **目标机**：编译后的程序将在此计算机系统上运行。
2. **编译程序的概念及其输入输出**：
- **概念**：编译程序是一种软件工具，用于将一种编程语言（源语言）编写的程序转换成另一种编程语言（目标语言）或机器语言的程序。
- **输入**：源程序，即用源语言编写的应用程序。
- **输出**：目标程序，即可以被目标机直接执行的程序。
3. **编译程序的组成**：
- **前端**：负责处理源程序的语言特性，包括词法分析、语法分析、语义分析等。
- **后端**：负责生成目标代码，包括优化、目标代码生成等。
- **与目标机的关系**：前端关注源语言的特性，而后端则更多地考虑目标机的具体细节。
4. **构建编译器所需的知识内容**：
- 源语言的语法规则。
- 目标机的架构、指令集等信息。
- 编译原理的基础理论，如词法分析、语法分析等。
- 代码优化的技术和方法。
5. **编译程序各阶段输入输出与规则**：
- **词法分析**：将源程序分解为一系列有意义的词法单元。
- **语法分析**：根据语法规则验证并分析词法单元的结构。
- **语义分析**：检查程序的逻辑错误，如类型不匹配等。
- **优化**：改进代码质量，提高程序执行效率。
- **目标代码生成**：将中间代码或优化后的代码转换为目标代码。
#### 第二章 高级语言及其语法描述
1. **语言定义**：
- **定义**：程序设计语言是一套规定了符号、词法、语法和语义规则的集合。
- **表示**：由文法G定义的语言可以通过生成的所有句子的集合来表示。
2. **语法规则**：
- **描述**：语法规则描述了语言的形式结构，即如何将词汇组合成有效的程序。
- **上下文无关文法**：大多数程序设计语言的语法规则可以用上下文无关文法(CFG)来描述。
- **组成部分**：由终结符、非终结符、起始符号、产生式组成。
3. **推导与语法分析树**：
- **最左/最右推导**：分别是从左到右或从右到左进行的推导过程。
- **语法分析树**：反映了句子的结构，帮助理解句子的组成。
4. **二义文法**：
- **定义**：存在多个不同的推导路径生成同一句子的文法称为二义文法。
- **识别**：如果一个文法对于某个句子存在两种或以上的语法树，则该文法是二义的。
5. **乔姆斯基文法分类**：
- **0型**：无限制文法，可以生成任何可递归枚举的语言。
- **1型**：上下文敏感文法，生成的语言具有上下文敏感性。
- **2型**：上下文无关文法，适用于描述大多数程序设计语言。
- **3型**：正则文法，用于描述词法规则。
#### 第三章 词法分析
1. **词法分析器功能**：
- **功能**：将源程序字符串分解成一个个有意义的符号。
- **输入**：源程序。
- **输出**：标记流，即将源程序转换为一系列标记。
2. **状态转换图**：
- **定义**：一种图形化的方法，用于描述状态之间的转移。
- **用途**：常用于设计词法分析器中的有限状态自动机。
3. **预处理程序基本功能**：
- **去除注释**：从源程序中删除注释。
- **替换宏**：用实际值替换宏定义。
4. **词法规则**：
- **表示**：大多数程序设计语言的词法规则可以使用正则表达式表示。
5. **正规式的用途**：
- 在词法分析程序自动生成理论中，正规式用于描述词法规则。
#### 第四-五章 语法分析
1. **语法分析任务**：
- **任务**：检查源程序是否符合语言的语法结构。
- **输入**：标记流。
- **输出**：抽象语法树或其他表示形式。
2. **语法分析方法分类**：
- **两大类**：自顶向下和自底向上。
- **分类依据**：解析器的构建方式。
3. **LL(1)文法**：
- **定义**：一种自顶向下的解析方法，其中LL表示自左至右扫描输入串，1表示需要向前查看1个符号。
- **判定条件**：一个文法是LL(1)文法当且仅当对于文法中的每一个非终结符A，其所有产生式对应的FIRST集合两两之间没有交集，并且对于每一个产生式A→α，如果FIRST(α)中包含ε，则FOLLOW(A)与α的LAST集合之间也没有交集。
4. **LR分析法**：
- **含义**：LR分析是一种自底向上的语法分析方法。
- **模型**：LR分析器基于LR项目和LR项目集的概念。
5. **LR与二义文法的关系**：
- **二义文法与LR分析**：二义文法不一定不能使用LR分析方法。
- **LR文法与二义性**：LR文法一定是非二义性的，但非二义性文法不一定是LR文法。
#### 第六章 属性文法和语法制导翻译
1. **属性文法**：
- **定义**：属性文法是带有属性的文法，属性是用来计算和传递信息的。
- **语义规则**：为产生式配备的一组属性计算规则。
2. **语法制导翻译**：
- **概念**：在语法分析的过程中，根据语义规则生成中间代码的过程。
- **语义动作**：在翻译模式中，属性计算规则也称为语义动作。
3. **一遍扫描的语法制导翻译方法**：
- **定义**：在语法分析过程中同时完成语义处理的一种方法。
4. **综合属性与继承属性**：
- **综合属性**：依赖于子节点的属性值。
- **继承属性**：从父节点传给子节点的属性值。
5. **抽象语法树**：
- **概念**：一种树形结构，表示程序的语法结构。
#### 第七章 语义分析和中间代码产生
1. **语义分析与中间代码生成的任务**：
- **任务**：对程序进行更深入的分析，检测程序的逻辑错误，并生成中间代码。
2. **工作依据**：
- **依据**：语言的语义规则。
3. **中间语言形式**：
- **常见形式**：三地址码、四元式等。
4. **中间代码生成的好处**：
- **优点**：方便后续的优化处理，提高代码质量。
#### 第八章 符号表
1. **符号表的作用**：
- **作用**：管理程序中的标识符，记录其相关信息。
- **基本信息**：变量名、类型、地址等。
2. **符号表处理方式**：
- **处理方式**：线性表、散列表、树等。
- **优缺点**：线性表简单但查找效率低；散列表查找效率高但可能存在冲突；树结构便于查找但也可能消耗更多空间。
3. **PASCAL的符号表组织**：
- **组织方式**：使用散列技术进行组织，以提高查找效率。
#### 第九章 运行时存储空间组织
1. **过程活动与参数传递**：
- **过程活动**：一个过程执行期间的状态。
- **参数传递**：实参和形参之间的数据传输方式。
2. **活动记录**：
- **用途**：存储函数调用时的信息。
- **内容**：局部变量、参数、返回地址等。
- **结构**：通常以栈的形式组织。
3. **嵌套过程语言的栈式实现**：
- **实现方式**：通过栈来管理嵌套过程的活动记录，以支持非局部名字的访问。
4. **过程子程序的“活动”**：
- **唯一性**：一个过程子程序的“活动”不是唯一的，因为每次调用都会创建一个新的活动记录。
