编译原理 第一章 引 论 南京大学计算机科学与技术系 戴新宇

课程概要 戴新宇 daixinyu@nju.edu.cn 学时：72学时(课堂) 学分：4 周三: 8-10am，周五 10-12am 计楼228 教材：编译原理（龙书第二版） 讲义：http://cs.nju.edu.cn/daixinyu/compiler.htm 助教: …... 课程考核： 课堂 课后作业 实习项目

为什么要学这门课？ compiler

我们能学到什么？ 能够帮助我们更好的理解程序设计语言和机器体系结构 目标：掌握编译原理理论和技术 形式语言与自动机，属性文法等 帮助我们写出更加高效的程序

什么是编译器 一个编译器就是一个程序，读入以某一种语言（源语言）编写的程序，并把该程序翻译成为一个等价的、用另一种语言（目标语言）编写的程序。 如果翻译过程发现源程序有错，则报错 狭义： 程序设计语言 → 机器代码 广义：程序变换 C++ → C →汇编 Python → C 编译器 源程序 目标程序

编译器简介 编译器 vs. 解释器 编译器的结构 编译的构造工具 编译器 源程序 目标程序

编译器 源程序 编译器 目标程序 程序输出 程序输入 效率高，一次编译，多次运行 通常目标程序是可执行的

解释器 解释器 源程序 程序输出 程序输入 直接利用用户提供的输入，执行源程序中指定的操作。 不生成目标程序，而是根据源程序的语义直接运行。 边解释，边执行，错误诊断效果好。

编译器 vs. 解释器 Javac Hello.java Java Hello Java结合了两者：

典型语言（如C）的编译 预处理器 汇编器 链接器 加载器

source file (.c .pas ) Compiler assembly file (.a .asm) Assembler Object file (.o .obj .dcu) Linker libraries (.lib) executable file (.exe) Loader process OS (.dll, .so)

编译器简介 编译器 vs. 解释器 编译器的结构 编译的构造工具

编译器的结构 分析部分（Analysis） 综合部分（Synthesis） 源程序 - 语法结构 - 中间表示 源程序 - 语法结构 - 中间表示 搜集源程序中的相关信息，放入符号表 分析、定位程序中可能存在的错误信息（语法、语义错误） 又称编译器的前端（front end），是于机器无关的部分 综合部分（Synthesis） 根据符号表和中间表示构造目标程序 又称编译器的后端（back end），是于机器相关的部分

编译器中的若干步骤 每个步骤把源程序的一种表示方式转换成另一种表示方式。 实践中，某些中间表示不需要明确的构造出来。 符号表存放源程序的相关信息，可由各个步骤使用

符号表管理 记录源程序中使用的变量的名字，收集各种属性 符号表可由编译器的各个步骤使用 名字的存储分配 类型 作用域 过程名字的参数数量、参数类型等等 符号表可由编译器的各个步骤使用

词法分析（lexical analysis, scanning） 词法分析/扫描读入源程序的字符流，输出有意义的词素(lexeme) 基于词素，产生词法单元： <token-name, attribute-value> token-name由语法分析步骤使用 attribute-value指向相应的符号表条目，由语义分析/代码生成步骤使用 例子 position = initial + rate * 60 <id,1> <=, > <id, 2> <+, > <id,3> <*, > <number, 4>

语法分析（syntax analysis/parsing） 词法分析后，需要得到词素序列的语法结构 语法分析/解析 根据各个词法单元的第一个分量来创建树形中间表示形式。通常是语法树（syntax tree） 指出了词法单元流的语法结构。

语义分析(Semantic Analysis) 得到语义(meaning)，对于编译器来说比较难 语义分析 使用语法树和符号表中的信息，检查源程序是否满足语言定义的语义约束。 同时收集类型信息，用于代码生成。 类型检查，类型转换。

语义分析(Interesting examples) Jack said Jerry left his assignment at home. Jack said Jack left his assignment at home? 该例子来源于compiler@stanford 讲义

中间代码生成(Intermediate-Code Generation) 根据语义分析的输出，生成类机器语言的中间表示 三地址代码： 每个指令最多包含三个运算分量 t1 = inttofloat(60)； t2 = id3 * t1; t3 = id2 + t2;

代码优化(Code Optimization) 通过对中间代码的分析，改进中间代码，得到更好的目标代码 运行的更快、占用更少的内存：少占资源 优化有具体的设计目标

代码生成(Code Generation) 把中间表示形式映射到目标语言 寄存器的分配 指令选择 内存分配

编译器的趟（Pass） “步骤”是逻辑组织方式 “趟”和具体的实现相关 趟：以文件为输入输出单位的编译过程的个数，每趟可由一个或若干个步骤构成 “步骤”是逻辑组织方式 “趟”和具体的实现相关

编译器简介 编译器 vs. 解释器 编译器的结构 编译的构造工具

编译器的构造工具 扫描器的生成器: lex/flex 语法分析器的生成器： yacc/bison 语法制导的翻译引擎 代码生成器的生成器 根据一个语言的词法单元的正则表达式描述生成词法分析器 语法分析器的生成器： yacc/bison 根据一个程序设计语言的语法描述自动生成语法分析器 语法制导的翻译引擎 生成一组用于遍历分析树并生成中间代码的程序 代码生成器的生成器 依据中间语言的每个运算如何翻译成目标机上机器语言的一组规则，生成一个代码生成器 数据流分析引擎 收集数据流信息，用于优化 编译器构造工具集

编译器的处理对象-程序语言 编译器 源程序 目标程序

程序设计语言 语言的代分类 面向对象语言 第一代语言：机器语言 第二代语言：汇编语言 第三代语言：高级程序设计语言 Fortran, Pascal, Lisp, Modula, C 第四代：特定应用语言：NOMAD, SQL, Postscript 第五代：基于逻辑和约束的语言，Prolog、OPS5 面向对象语言 Simula, Smalltalk, Modula3, C++, Object Pascal, Java, C# 数据抽象、继承 脚本语言

程序设计语言和编译器之间的关系 程序设计语言的新发展向编译器设计者提出新要求 通过降低高级语言的执行开销，推动这些高级语言的使用 设计相应的算法和表示方法来翻译和支持新的语言特征 通过降低高级语言的执行开销，推动这些高级语言的使用 编译器设计者还需要更好地利用新硬件的能力。

编译技术的应用（1） 高级程序设计语言的实现 针对计算机体系结构的优化 新体系结构的设计 高级程序设计语言的抽象层次的提高有利于编程，但是直接生成的代码却相对低效率 聚合类型/高级控制流/面向对象/垃圾自动收集机制 针对计算机体系结构的优化 并行性：指令级并行，处理器层次并行 内存层次结构 新体系结构的设计 RISC 专用体系结构 一个新的体系结构特征能否被充分利用，取决于编译技术

编译技术的应用（2） 程序翻译 二进制翻译/硬件合成/数据查询解释器/编译后模拟 软件生产率工具 类型检查 边界检查 内存管理工具

程序设计语言的基础概念（1） 静态/动态 作用域 静态：语言策略支持编译器静态决定某个问题 动态：只允许在程序运行时刻作出决定 Java类声明中的static指明了变量的存放位置可静态确定。 作用域 x的一个声明的作用域是指程序中的一个区域，其中对x的使用都指向这个声明。 静态作用域：通过静态阅读程序即可确定作用域 动态作用域：程序运行时，同一个对x的使用会指向好几个x的声明中的一个

程序设计语言的基础概念（2） 环境与状态 环境的改变需要遵守语言的作用域规则 环境：是从名字到存储位置的映射 状态：从内存位置到它们的值的映射 环境的改变需要遵守语言的作用域规则

程序设计语言的基础概念（3） 静态作用域和块结构 C族语言使用静态作用域。 作用域规则基于程序结构，声明的作用域由它在程序中的位置隐含决定。 函数内部可以声明变量（局部变量/参数），这些声明的作用域在它出现的函数内 一个顶层声明的作用域包括其后的所有程序。除去那些具有同样名字的变量声明的函数体。 作用域规则基于程序结构，声明的作用域由它在程序中的位置隐含决定。 也通过public、private、protected进行明确控制

程序设计语言的基础概念（4） 块作用域的例子

程序设计语言的基础概念（5） 参数传递机制 值调用 (call by value)：对实在参数求值/拷贝，再存放到被调用过程的形参的内存位置上。 引用调用(call by reference)：实际传递的是实在参数的地址。 名调用：早期使用，现在已经废弃。