编译原理

什么是编译器

• 计算机设备包括个人计算机、大型机、嵌入式系统、只能设备等
• 核心的问题都是软件的构造

• 目前绝大部分软件都是由高级语言书写
• 成百种高级语言

• 这些语言如何运行在计算机上的呢

• 编译器

int main()
{
  printf("hello world!\n");
  return 0;
}

  .text
str:
  .string "hello world\n"
  .globl main
main:
  pushl  %ebp
  movl   %esp, %ebp
  pushl  $str
  call   printf
  leave
  ret

• 编译器是一个程序
• 核心功能是将源程序代码翻译成目标代码

编译器和解释器

• 解释器也是处理程序的一种程序

编译器简史

• 计算机科学史上出现的第一个编译器是Fortran语言的编译器
• Fortran语言的编译器的成功给计算机科学发展产生巨大的影响

• 理论上：形式语言，文法，自动机，语法制导的翻译等
• 实践上：算法，数据结构
• 编译器架构：

为什么学编译原理

• 编译原理集中体现了计算机科学的很多核心思想
  
• 编译器是其他领域的重要的研究基础
  
• 编译器本身就是非常重要的研究领域

• 新的语言的设计
• 大型软件的构造和维护

• 编译器设计是理论和实践高度结合的一个领域

• 理论：深入学习掌握各种算法和数据结构
• 实践：将理论应用于解决实际问题

编译器的结构

• 编译器是具有非常模块化的高层结构
• 编译器可以看成多个阶段构成的流水线结构

无优化的编译器结构：

=》词法分析=》语法分析=》语义分析=》代码生成=》

一种更复杂的编译器结构：

=》词法分析=》语法分析=》语法树构造=》语义分析=》翻译=》正规化=》指令选择=》控制流分析=》寄存器分析=》代码生成=》汇编器=》连接器=》

• 编译器是由多个阶段组成，每个阶段要处理不同的问题

• 使用不同的理论、数据结构和算法

• 因此，编译器设计中的重要问题是如何合理划分组织各个阶段

• 接口清晰
• 编译器容易实现和维护

编译器实例

源语言加法表达式Sum

• 两种语法形式：

• 整形数字n
• 加法 e1 + e2

目标机器：栈式计算机stack

• 一个操作数栈
• 两条指令

• 压栈指令：push n
• 加法指令：add

任务：编译程序1+2+3到栈式计算机

• 阶段1：词法语法分析
• 阶段2：语法树的构建
• 阶段3：代码生成

编译器的构造和具体的目标相关，目前的结构是：

前端=》tree=》栈式计算机代码