编译原理笔记 2025/4/22
基本概念
汇编语言与高级程序设计语言的关系/汇编干嘛的：高级语言与硬件无关，汇编语言的定义与CPU的指令系统直接相关。只要将高级语言编写的程序等价地转换成特定硬件平台所支持的方式来实现（汇编程序或机器指令序列），那么软件设计师就不必为每种硬件平台重写编写具有相同功能的软件。
编译器：1.狭义的编译器，将高级语言翻译成等价的可执行指令序列（或先翻译成汇编，再翻译成可执行指令序列）；2.广义的编译器，只要程序在功能和含义上与原来的程序一致就行，（不管能不能执行。）
解释器：除了编译执行之外，还有解释执行。由于高级语言和底层指令系统差别较大，因此要实现对程序的解释执行，必须在程序解释执行的过程中进行程序的翻译。由于不是被CPU直接执行，解释执行的程序在性能上比编译执行的程序慢。
虚拟机：如java虚拟机，定义了一套标准的指令集合（字节码）。java编译器将java程序翻译成具有相同功能的字节码程序，然后由虚拟机对字节码程序进行解释执行。（字节码和CPU二进制指令接近，解释的就更快。）Java编译器还采用即时编译JIT提高执行效率。
编译技术：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。
- 词法分析：将源代码转换为词法单元序列（词法分析程序又称为扫描程序，对源程序每个字符进行线性读取）
- 语法分析：构建（抽象）语法树AST。（成功表明程序符合语法，否则存在某种语法错误）
- 语义分析：验证语义规则。（语法分析只给了程序格式正确性的要求，语义则给出了程序含义正确的规定）
- 中间代码生成：生成中间表示（获得了程序语义信息理论上就可以将其翻译成汇编代码或二进制机器代码。不过只是理论上这样，实际上要先把程序转换为某种形式的中间表示或中间代码，对其进行性能、存储优化处理，再翻译成可执行代码）(一般采用抽象语法树AST中间表示，AST前面进行语法、语义分析时已经逐步建立和完善了)
- 代码优化：优化以提高性能（执行时间与存储空间两方面）
- 目标代码生成：输入优化后中间代码，产生汇编代码或目标机器代码的指令序列（具体操作是为每个变量分配具体存储地址，使用实际机器的寄存器，将每个中间代码指令映射到一条或一组等价且高效的机器指令等）
编译器按功能分前端和后端：
- 前端：词法分析、语法分析、语义分析
- 后端：代码优化、目标代码生成等
- 前后端通过中间表示和中间代码进行信息交换
形式语言与自动机理论基础
词法分析
语法分析——自顶向下分析方法
三个重要集合
自顶向下语法分析条件
？
LL1分析方法
求三个集合例子👇
E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → (E) | i
构造LL(1)分析表👇
分析表构造好后分析👇
判断是否满足LL(1)文法的例子👇
语法分析——自底向上分析方法
简单优先分析
1.简单优先文法及其优先关系
2.矩阵的构造
3.简单优先分析算法
例👇
判断是否是简单优先文法👇
完整例子👇
LR分析法
这里的L表示从左向右扫描输入串，R表示构造一个最右推导的逆过程。
由于LR(k)分析方法对文法的限制很少，因而大多数能用上下文无关文法描述的程序设计语言都可用LR分析法进行有效的分析。
因此，LR分析法是当前最一般的语法分析方法。
LR(0)：已知文法，构造状态机和分析表的例子👇
例子👇
