编译原理

编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。本思维导图是编译原理课程概述，个人学习笔记，希望对你有帮助。

编译原理

• 思路
  • 机器语言：上下文无关文法 => 语法制导翻译
  • 分析-综合模型
    • 中间表示形式：树； -- 其中叶子节点为操作数，内部节点为操作符
• 应用
  • 浏览器渲染、数据库查询...
  • 格式化编辑器、格式化打印、静态检查、解释器、排版软件...
  • 数据压缩（压缩文法）
  • 大量新的应用领域，产生更多抽象方式，应生大量新的语言
• 技术细节
  • 词法分析（线性分析）
    • 工具：lex 技术：正则表达式【有穷自动机】
    • - 对原始字符序列进行预处理 - 转换为tokens - 方便建树处理
    • 主要的预处理内容：（均以'#'开头） - 宏（#define ...，进行批量处理） - 文件包含（#include, #pragma once ...） - 条件编译（#ifdef, #endif, #ifndef）
      • 可以进行语言拓展...
      • 每个阶段都要通过symbol-table-manager维护符号表， 借助error handler处理错误
        • 符号表：数据结构【记录表】
          • 用于记录标识符属性信息
          • 创建于词法分析时
          • 用于后续阶段使用、修改属性
        • 错误分析
          • 多数产生自语法分析、语义分析阶段
          • - 词法分析时，检查非法单词； - 语法分析时，检查是否违背语法结构； - 语义分析时，检测无意义语义
            • 存疑
  • 语法分析
    • 将词法树产生的单词组合成语法短语（建语法树）
    • 工具：yacc
  • 语义分析
    • - 检查语义错误 - 做类型检查 - 进行信息的收集
    • 工具：yacc 技术：类型表达式，类型系统等价判定
  • 中间代码生成
    • 三地址码是常见的中间语言
      • 每个指令都可以分解为一个四元组： （运算符，操作数1，操作数2，结果）
      • 每个阶段都要通过symbol-table-manager维护符号表， 借助error handler处理错误
        • 符号表：数据结构【记录表】
          • 用于记录标识符属性信息
          • 创建于词法分析时
          • 用于后续阶段使用、修改属性
        • 错误分析
          • 多数产生自语法分析、语义分析阶段
          • - 词法分析时，检查非法单词； - 语法分析时，检查是否违背语法结构； - 语义分析时，检测无意义语义
            • 存疑
    • 中间语言特点： - 不依赖实际体系结构 - 容易生成 - 容易翻译为目标程序
    • 技术：backpatching；基本块、流图；寄存器分配与指定；窥孔优化
  • 代码优化
    • 中间代码优化/目标代码优化
    • - 局部优化 - 循环优化 - 全局优化
      • 一些简单的思路： 1. 删除多余运算 2. 代码外提 3. 强度削弱 4. 变换循环控制条件 5. 合并已知量、复写传播 6. 删除无用赋值 ......
      • 还有一些“数据流分析”等比较高级的技术
      • 每个阶段都要通过symbol-table-manager维护符号表， 借助error handler处理错误
        • 符号表：数据结构【记录表】
          • 用于记录标识符属性信息
          • 创建于词法分析时
          • 用于后续阶段使用、修改属性
        • 错误分析
          • 多数产生自语法分析、语义分析阶段
          • - 词法分析时，检查非法单词； - 语法分析时，检查是否违背语法结构； - 语义分析时，检测无意义语义
            • 存疑
    • 技术：数据流分析，各种类型的优化
  • 目标代码生成
    • - 生成可重定位的【机器码/汇编码】 - 确定变量内存位置 - 中间代码指令 => 机器指令 - 为变量指定寄存器
      • 1，3相同？
      • 每个阶段都要通过symbol-table-manager维护符号表， 借助error handler处理错误
        • 符号表：数据结构【记录表】
          • 用于记录标识符属性信息
          • 创建于词法分析时
          • 用于后续阶段使用、修改属性
        • 错误分析
          • 多数产生自语法分析、语义分析阶段
          • - 词法分析时，检查非法单词； - 语法分析时，检查是否违背语法结构； - 语义分析时，检测无意义语义
            • 存疑
  • *加载、链接
  • 每个阶段都要通过symbol-table-manager维护符号表， 借助error handler处理错误
    • 符号表：数据结构【记录表】
      • 用于记录标识符属性信息
      • 创建于词法分析时
      • 用于后续阶段使用、修改属性
    • 错误分析
      • 多数产生自语法分析、语义分析阶段
      • - 词法分析时，检查非法单词； - 语法分析时，检查是否违背语法结构； - 语义分析时，检测无意义语义
        • 存疑
• 两个主要阶段
  • 前端，front end
    • 依赖于源语言的部分
  • 后端，back end
    • 只依赖目标机器、中间代码；包括部分代码优化、代码生成部分