编译原理引论
1. 编译器
1.1 什么是编译器
语言处理器：本质上都是一个语言翻译程序，将用源语言书写的源程序转变到用目标语言书写的语义等价程序
编译器（compiler）：将用高级语言编写的源代码转换成用汇编语言编写的中间代码
为什么编译得到的是汇编语言而不是直接得到机器语言？
- 汇编代码相比机器码更接近人类可读形式，便于开发者检查、定位和调试编译器生成的中间代码
- 汇编语言作为中间层，能够更容易地适配不同硬件平台，提高编译器的可移植性和适应性
- 将编译和汇编独立地进行模块化，可以大大降低编译器设计的复杂度，使其更专注于语言级别的语法和语义处理
常见的 C 语言编译器
- GCC：用于编译 C、C++、Fortran 等多种语言，生成汇编代码/机器码，由 GNU 汇编器和链接器进一步处理
- Clang：基于 LLVM 的前端编译器，支持 C、C++、Objective-C 等语言，以优美的错误信息和高效的优化著称，生成 LLVM 中间表示再生成机器码
- MSVC：微软提供的编译器，主要用于 Windows 平台上的 C 和 C++ 程序开发，与 Visual Studio 紧密集成，生成高效的目标代码
1.2 高级语言程序转换过程
以 C 语言为例
| 语言处理器 | 宏观过程 | 微观处理 |
|---|---|---|
| 预处理器（preprocessor） | 源代码（.c）->源代码（.i） | 对源代码中的预处理指令展开，如宏替换、条件编译、文件包含等 |
| 编译器（complier） | 源代码（.i）->汇编代码（.s） | 词法分析、语法分析、语义分析、代码优化及生成 |
| 汇编器（assembler） | 汇编代码（.s）->机器代码（.o） | 产生包含符号和重定位信息的目标文件 |
| 链接器（linker） | 机器代码（.o）->可执行文件 | 将多个目标文件和库文件合并，进行符号解析、地址重定位，消除外部符号引用 |
| 加载器（loader） | 外存中的可执行文件->内存中的可执行程序 | 负责内存分配、地址重定位、动态链接等工作，使程序可以在内存中正确运行 |
1.3 解释器
| 特性 | 编译器（Compiler） | 解释器（Interpreter） |
|---|---|---|
| 定义 | 将整个源代码一次性翻译成目标代码，然后生成独立的可执行文件 | 逐行或逐块读取并即时翻译执行源代码，不生成独立的可执行文件 |
| 翻译时机 | 先翻译再执行 | 翻译和执行同步进行 |
| 执行效率 | 生成的目标代码直接运行，通常具有较高的执行效率 | 实时翻译会带来额外的时间和空间开销，效率低 |
| 错误检测 | 在编译阶段一次性检查整个程序，发现并报告多数语法和类型错误 | 错误通常在执行到出错语句时才被检测到，有助于调试但可能延后错误暴露 |
| 跨平台性 | 编译结果通常针对特定平台，需要为不同平台重新编译 | 只要目标平台有相应解释器环境，同一源代码可直接运行 |
1.4 不同语言区别
C/C++：采用静态编译，先将源代码转换成机器码（.o），然后链接生成独立的可执行文件
Python：采用解释，先被编译成平台无关的字节码（.pyc），然后由解释器逐行解释执行
Java：采用即时编译，先将源代码编译成平台无关的字节码（.class），最初由解释器逐行解释执行，但是运行过程中即时编译器会将被频繁执行的“热点字节码”动态编译成机器码，从而大幅提高性能
2. 编译过程
2.1 前端：分析
- 词法分析（lexical）：识别源代码字符流中的单词、关键字、数字、运算符、标识符、界符等词素（lexeme），忽略空格、换行符、注释等不影响程序逻辑的内容，将识别出的词素单元转换成记号（token）
- 语法分析（syntax）：使用文法规则解析记号序列，将记号流分解为各类语法单元，如程序、语句、表达式等，检查源程序在语法上是否正确，构建出语法树
- 语义分析（semantic）：审查源程序是否有语义错误，进行类型检查、作用域检查、参数匹配检查等，为代码生成阶段收集信息
语法错误
- 缺少必要的符号：例如缺少分号、右括号或大括号
- 错误的语句结构：如关键字使用错误、语句顺序不符合文法规则
- 拼写错误：关键字或标识符拼写错误导致无法匹配正确的语法规则
语义错误
- 类型不匹配：变量或表达式的类型不符合运算符要求或赋值操作不兼容
- 未声明的变量或函数：在使用变量或函数前未进行声明或定义
- 作用域错误：变量的使用超出了其作用域范围
- 参数不匹配：函数调用时传递的参数个数、类型与函数定义不符
- 错误操作：例如对空指针解引用，或试图执行非法的数组下标操作
- 返回值错误：函数返回值与声明的返回类型不一致，或者函数缺少必要的返回值
2.2 后端：综合
中间代码生成（intermediate code）：遍历上述语法树，生成等价的近似“三地址指令”的四元式中间代码，是一种结构简单、含义明确的记号系统，具有容易生成、易于转换的特点，表示为
(运算符, 运算对象1, 运算对象2, 结果)中间代码优化（optimization）：改进程序结构，减少冗余，从而节省时间和空间
目标代码生成（generation）：把优化后的中间代码转化为目标代码，通常需要进行指令选择、寄存器分配、内存计算和调度等工作
同一源语言的前端加上不同的后端可以为不同机器提供同一源语言的编译，不同源语言的前端加上相同的后端可以为同一机器提供不同源语言的编译
2.3 辅助程序
表格管理程序：管理和操作各种编译器中使用的数据表，如符号表、关键字表、操作码表等，为语义分析、代码生成等阶段提供必要的信息支持，
出错处理程序：负责检测、记录和报告编译过程中的各种错误，如语法错误、语义错误等，并在可能的情况下尝试进行错误恢复，以继续处理后续代码
3. 符号表
符号表（symbol table）：在编译器中用于记录和管理源程序中各种标识符如变量和函数以及其属性信息如名称、类型、作用域、内存地址、初始值的数据结构
- 管理不同作用域下标识符的可见性和生命周期，处理嵌套作用域、全局与局部变量的冲突问题
- 利用符号表进行类型检查、重定义检查、引用检查等，确保程序中标识符的使用符合语言的语义规则
- 确定变量在内存中的布局、寄存器分配等，从而支持生成正确且高效的目标代码
4. 软件工具
- 结构化编辑器：自动维护代码的语法和结构完整性，避免低级语法错误，通过树状视图或语法高亮，帮助开发者直观理解代码结构
- 调试工具：提供单步执行、断点设置、变量观察和内存检查等功能，帮助开发者跟踪程序执行流程、定位逻辑或运行时错误
- 程序格式化工具：自动调整缩进、换行、空格等，统一代码风格，提升代码可读性和维护性
- 程序测试工具：静态分析器在不运行程序的情况下，检查是否存在已经定义过的常见错误，动态分析器在程序的适当位置加入测试语句，以在运行时显示测试结果帮助开发者定位问题
- 程序理解工具：通过静态代码分析、依赖关系图、代码度量等手段，帮助开发者快速掌握复杂系统
- 转译器：将一种高级程序设计语言的源代码转换为另一种高级程序设计语言的源代码，用于匹配底层环境、实现代码迁移和扩展语言功能
许多编译器会使用转译器将其他高级语言的源代码变为 C 语言后再进行编译，这是因为 C 语言已经拥有完善和成熟的编译器和优化器，且 C 语言具有良好的跨平台特性，同时在语法上更接近汇编语言，有助于进行高效的目标代码生成和优化
5. 程序设计语言
根据语言的发展历程分类
- 机器语言：由二进制数（0和1）组成，是计算机唯一能直接执行的语言
- 汇编语言：用助记符代替机器码中的数字指令，并利用符号来表示地址，如 x86、ARM
- 高级程序设计语言：接近自然语言和数学符号，抽象程度高，屏蔽了底层硬件细节，如 C、Java、Python
- 特定应用设计语言：具有专门的语法和语义，如 SQL、HTML、Verilog
- 基于逻辑和约束的语言：通过描述问题的条件和关系来求解问题，如 Prolog、OPS5
根据语言的编程范式分类
- 命令式：描述计算过程，通过一系列明确的语句和指令来改变程序状态，如 C、Pascal
- 函数式：将计算视为数学函数的求值，强调不可变性和无副作用，常用递归和高阶函数来构建程序，如 Haskell、Lisp、OCam
- 声明式：关注“做什么”而不是“如何做”，让系统自动决定求解步骤，如 SQL、Prolog
- 面向对象：以对象和类为核心组织程序，强调封装、继承和多态，如 C++
- 脚本：具有高层次运算符的解释语言，将多个计算过程粘合在一起，通常用于自动化、快速开发和系统管理，如 Python、Ruby、JavaScript
