### 编译原理复习大纲详解
#### 一、编译器的基本概念与阶段
- **编译器定义**: 编译器是一种计算机程序，用于将一种编程语言（源代码）转换为另一种语言（目标代码），通常是从高级语言到低级语言（如汇编语言或机器语言）。
- **编译器的主要阶段**:
- **词法分析** (Lexical Analysis): 将源代码分解成一系列有意义的符号或标记(Token)。
- **语法分析** (Syntax Analysis): 使用上下文无关文法(Context-Free Grammar, CFG)对词法分析得到的Token进行解析，构建出抽象语法树(Abstract Syntax Tree, AST)。
- **语义分析** (Semantic Analysis): 在语法正确的基础上进行更深层次的检查，例如类型检查。
- **中间代码生成** (Intermediate Code Generation): 生成一种简单的中间表示形式，便于后续优化。
- **代码优化** (Code Optimization): 对中间代码进行优化，提高运行效率。
- **目标代码生成** (Target Code Generation): 最终生成可执行的目标代码。
#### 二、正则表达式与自动机理论
- **正则表达式**(Regular Expression, R.E.): 一种用于描述字符序列的语言模式。
- **非确定有限自动机**(Non-Deterministic Finite Automaton, NFA): 可以在某些状态下有多个选择路径。
- **确定有限自动机**(Deterministic Finite Automaton, DFA): 每个状态下的每种输入都只有一个确定的输出状态。
- **正则表达式到DFA的转换**:
- 首先根据正则表达式构造出NFA。
- 通过子集构造算法将NFA转换为DFA。
- **最小化DFA**: 使用等价类的方法去除冗余状态，减少DFA的状态数量，从而简化识别过程。
#### 三、上下文无关文法
- **上下文无关文法**(Context-Free Grammar, CFG):
- 定义: 由一组生产规则组成的集合，用于描述语法结构。
- 表达方式: S -> AB | a, 其中S是起始符号，A和B是非终结符，a是终结符。
- **推导**(Derivation):
- 左最左推导: 从左到右每次替换最左边的非终结符。
- 右最右推导: 从左到右每次替换最右边的非终结符。
- **语法树**(Parse Tree)与**抽象语法树**(Abstract Syntax Tree, AST):
- 语法树: 展示了源代码的语法结构。
- 抽象语法树: 去除了语法树中的冗余信息，只保留重要的语法结构。
#### 四、递归下降解析与LL(1)语法
- **递归下降解析**(Recursive-Descent Parsing):
- 方法: 通过递归函数来实现语法分析。
- 适用场景: 适用于没有左递归且左因子化的文法。
- **LL(1)文法**:
- 定义: 如果一个文法可以通过单次向前查看(Look-Ahead)来决定如何展开当前非终结符，则该文法称为LL(1)文法。
- **First集合**与**Follow集合**:
- First集合: 给定一个非终结符，其First集合包含了从这个非终结符出发可以产生的所有终结符的集合。
- Follow集合: 给定一个非终结符，其Follow集合包含了出现在所有可能的推导结果中紧随其后的终结符的集合。
- **LL(1)分析表**:
- 构建方法: 根据文法的First集合和Follow集合构建。
#### 五、LR(0)解析与SLR(1)解析
- **LR(0)解析**:
- 定义: 一种自底向上的解析技术，LR(0)解析器能够处理所有上下文无关文法(CFG)。
- LR(0)项: 描述了每个文法规则的所有可能位置的信息。
- DFA构造: 通过对LR(0)项构造DFA来实现解析。
- **SLR(1)解析**:
- SLR(1)是在LR(0)基础上增加了Follow集合信息，以解决某些二义性问题。
- 解析表构造: 根据Follow集合信息构建解析表，解决冲突。
#### 六、属性文法与依赖图
- **属性文法**(Attribute Grammar):
- 定义: 在上下文无关文法的基础上添加属性和规则，用于描述程序的语义信息。
- 属性分类: 合成属性(Synthesized Attributes)和继承属性(Inherited Attributes)。
- **依赖图**(Dependency Graphs):
- 用于表示语法树中节点间的依赖关系。
- 属性计算: 根据依赖关系进行属性值的计算。
#### 七、参数传递机制
- **完全静态环境**(Fully Static Environment):
- 参数传递发生在编译时。
- **基于栈的环境**(Stack-Based Environment):
- 参数传递发生在运行时，利用栈来管理函数调用和返回。
- **完全动态环境**(Fully Dynamic Environment):
- 参数传递和管理完全由运行时系统负责。
#### 八、中间代码
- **中间代码**(Intermediate Code):
- 定义: 在编译过程中产生的简洁、易于理解和优化的代码形式。
- 类型: 三地址码、四元组等。
- **中间代码生成**:
- 过程: 在语法分析后生成一种简单形式的中间代码。
- 目的: 便于后续的代码优化和目标代码生成。
