编译原理课程笔记

第一章 引论

编译器概述

  • 翻译器:
    • 把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序
  • 解释器：
    • 把源语言（高级语言）写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序
  • 编译器：
    • 把一种高级语言程序等价地转换成另一种低级语言程序(汇编语言或机器语言程序)的程序

编译前端与后端

  • 编译前端：
    • 与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化
  • 编译后端：
    • 与目标机有关，与目标机有关的优化，目标代码产生

编译过程

  1. 词法分析
  2. 语法分析
  3. 语义分析
  4. 中间代码产生
  5. 优化
  6. 目标代码产生

词法分析

任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：有限自动机

语法分析

任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则,语法树描述工具：上下文无关文法

语义分析和中间代码产生

任务:对各类不同语法范畴按语言的语义进行初步翻译。–声明语句和操作语句依循的原则：语义规则中间代码:三元式，四元式，树形结构等

优化

任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则

目标代码产生

任务: 把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:绝对指令代码: 可直接运行 汇编指令代码: 需要进行汇编可重新定位指令代码: 需要连接装配

编译技术的应用

编译技术广泛应用于计算机领域核心场景：

  1. 程序开发：将高级语言（C/Java/Python）编译为机器码或字节码，支撑编程语言生态；解释器实现动态执行；
  2. 性能优化：通过代码精简、内联扩展、循环优化提升效率，JIT技术（如Java/JavaScript）实现运行时加速；
  3. 跨平台支持：交叉编译生成多平台目标代码，虚拟机（如JVM）通过中间码实现“一次编写，到处运行”；
  4. 静态分析：检测代码漏洞、内存泄漏，支撑IDE智能提示与代码规范检查；
  5. 硬件与嵌入式：编译Verilog/VHDL生成电路，为物联网设备生成低功耗固件；
  6. 安全防护：代码混淆防止反编译，静态分析识别恶意代码；
  7. 领域专用：实现SQL、正则表达式等DSL，提升领域开发效率。
    此外，编译技术还用于代码生成工具、并行计算框架（如CUDA）和教育研究领域，是软件与硬件协同的核心纽带。（199字）

第二章 词法分析

词法分析的任务

​ 从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。

  • 法分析器(Lexical Analyzer) 又称扫描器(Scanner)：
    • 是执行词法分析的程序

词法分析器构造

方法一: 通过状态转换图编写词法分析器

  • 词法分析器手工编制方法

  • 词法分析器的功能和输出形式

    • 功能:输入源程序、输出单词符号

状态转换图

  • 状态转换图是一张有限方向图。
    1. 结点代表状态，用圆圈表示。
    2. 状态之间用代箭头的弧线连结，弧线上的标记(字符或其他)代表射出结点状态下可能出现的输入字符或字符类。
    3. 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态双圆圈

编译原理作业

**1. ** 词法分析器以源程序的字符流为输入，按词法规则将其识别为一个个单词，并转换为统一的（单词类别，单词值）二元组内部表示形式。它还负责检查词法错误，如非法字符、错误关键字等，之后将单词逐个传递给语法分析器，为其提供输入单元，同时在预处理时简化源程序，提高编译效率。

**2. ** 状态转换图是由状态节点与带条件或事件标注的有向转换边构成的有向图 。它能直观展现系统或对象的运行逻辑，清晰呈现各种状态及转换关系，在系统设计时辅助架构规划，开发中用于检测错误、辅助调试，也是团队沟通的有力工具，在算法设计与分析领域，还能描述算法执行、助力性能分析 。

**3. **

知识点：

  1. 词法分析器、输入输出
  2. 语法分析器
  3. 状态转换图