编译原理笔记01：引论

语言处理系统：把用软件语言书写的各种程序翻译成可在计算机上执行的程序，或最终的计算结果，或其他中间形式。

如何完成翻译？

语言处理系统总则

1. 预处理：删除注释、宏扩展、文件包含（. i 文件）
2. 编译：将源程序翻译成汇编语言（.s 文件）
   1. 词法分析，创建符号表
      1. 把源代码中的字符串（关键字、标识符、操作符、界符等）转换成 token
      2. 正则表达式、flex（词法文件 calc.l）
   2. 语法分析
      1. 把 token 串转换成 AST 抽象语法树，生成清晰的代码结构
      2. 按照语法结构的递归定义从上到下匹配
      3. Bison/Yacc（语法文件 calc.y）
   3. 语义分析
      1. 理解语句要做什么（唯一的含义）
      2. 收集信息：引用消解、上下文信息
      3. 类型分析和检查
   4. 中间代码生成
      1. LLVM IR (Intermediate Representation)
         1. 基本单位是 module
         2. module 中可以包含多个顶层实体（函数/全局变量）
         3. 函数由一系列 basic block 组成，每个 block 里有若干 instruction
      2. 得到. bc 二进制中间语言和. ll 可读代码（两种格式等价）
      3. pipeline：不同高级语言对应的前端将其转换成 IR，统一优化、链接后再传给不同 target (x86/arm/risc-v/mips/…) 的后端，转换成对应的二进制代码
      4. 在这一步，高级语言的差异消失了
   5. 代码优化
      1. LLVM 后端优化
      2. 数据流分析、基于 basic block 生成的控制流图 CFG 优化
      3. e.g. 代数优化、常数折叠、死代码删除
   6. 代码生成
      1. 确定变量的内存位置、指定寄存器
3. 汇编：将汇编语言翻译成机器语言，并打包成可重定位目标程序（. o 文件）
   1. 指令选择
   2. 寄存器分配
   3. 指令重排
   4. 指令编码
4. 链接/加载：将可重定位机器代码和相应的目标文件、库文件链接在一起，形成能运行的程序

• ← Previous Post
• Next Post →