目录

编译原理

1. 编译器概述

为什么学习编译原理

  • 编译原理集中体现了计算机科学的很多核心思想:算法,数据结构,软件工程等

  • 编译器是其它领域的重要研究基础

  • 编译器本身就是非常重要的研究领域:新的语言设计,大型软件的构造和维护

编译器的高层结构

  • 编译器具有非常模块化的高层结构

  • 可看成多个阶段构成的“流水线”结构:一层一层降低抽象,也使模块可维护
    未优化的编译器结构

更复杂的编译器结构

2. 词法分析

词法分析任务
词法分析器实现

手工构造词法分析器

构造转移图

转移图的伪代码
标识符的转移图

  • 需注意,语言的关键字和标识符有交集,从词法分析角度来看,关键字是标识符的一部分
    识别关键字

使用关键字表区分关键字与标识符

关键字表

正则表达式

  • 正则表达式 >> 自动机 >> 算法

  • 用正则表达式来阐述语法的规则

  • 图灵机只需要两个运算就能完成所有操作:赋值和跳转

有限状态自动机

  • 工具:flex

10. 代码优化概述

  • 代码优化是对被优化的程序进行的一种语义保持的变换,程序的可观察行为(I/O, File, Network)不能改变

  • 使程序更小、更快、cache行为更好、更节能等等

  • 不存在"完全优化",等价与"停机问题"

  • 编译优化是无止境的,“编译器从业者用不失业定理”

代码优化很困难

  • 不能保证优化总能产生“好”的结果

  • 优化的顺序和组合很关键

  • 很多优化问题是非确定的

  • 优化的正确性论证很微妙