编译原理笔记 2025/4/22

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