课程的性质与任务

• 本课程地位属于计算机科学与技术专业的一门重要的专业必修课。
• 本课程的学习有助于对语言的执行系统、程序语言的理解。
• 通过本课程的学习，要掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造方法。各种语法分析技术和中间代码生成符号表的构造、代码优化、并行编译技术常识及运行时存储空间的组织等基本方法和主要实现技术。

课程的地位

                                 

语言的发展

• 机器语言
• 汇编语言
• 高级语言
• 查询语言、标注语言

1.1什么是编译程序

• 语言处理程序：把较高级语言编写的程序语义等价地变换成较低级语言程序的程序
• 语言处理程序分类
  • 汇编程序
  • 解释程序
  • 编译程序
• 
• 语言的执行方式
  • 解释方式（Basic)
    口译
  • 编译方式(C,pascal)
    笔译

汇编程序

• 汇编程序：把用汇编语言编写的程序翻译成机器语言的程序。


• 


• 汇编语言是为特定的计算机或计算机系统设计的面向机器的语言。如：8086/8088 PC、Z-80、VAX汇编语言


• 汇编的过程就是对汇编指令逐行进行处理，最终得到机器代码的过程。

解释程序

• 解释程序：对用高级语言编写的程序进行逐句分析并立即得到结果。
• 


• 解释程序按源程序中语句的动态顺序逐句进行分析翻译，并立即予以执行，它不产生目标代码。BASIC APL LISP Java等语言就是采用解释方法实现的。

高级语言解释系统(interpreter)

• 功能：让计算机执行高级语言（basic,lisp,prolog)
• 与编译程序的不同
  • 不生成目标代码
  • 能支持交互环境
    （同增量式编译系统）
• 

解释系统

• 直接对源程序中的语句进行分析，执行其隐含的操作。
• 

编译程序

• 编译程序：把用高级语言编写的源程序翻译成等价的低级语言(称作目标语言)程序。
• 
• 编译系统是编译程序和运行系统的合称。
• 一个编译程序把一个高级语言源程序翻译成目标程序的工作可分为前后衔接的六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化及目标代码生成。
• 大多数高级语言是采用编译的方法实现的。如 PASCAL、FORTRAN、ADA、C、C++、PL/1、 ALGOL 60、 ALGOL 68,等等。

什么是编译程序(compiler)

• 编译程序是现代计算机系统的基本组成部分.
• 从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序.
• 编译程序的功能

• 术语
  • 编译程序的源语言(源程序)
  • 编译程序的目标语言(目标程序)
  • 编译程序的实现语言
    

高级语言程序的处理过程(1)

• 软件：计算机系统中的程序及其文档
• 系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。
  
• 语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。
• 软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言

高级语言程序的处理过程(2)

高级语言程序的处理过程(3)

术语

• 编译程序(compiler)
• 编译程序的源语言(源程序) (source language)(source program)
• 编译程序的目标语言(目标程序) (object or target language)(object or target program)
• 编译程序的实现语言(implementation language)
• 语言处理程序(language processor)
• 语言转（变）换(language transformation)

1.2 编译过程概述

• 编译逻辑过程
• 词法分析
• 语法分析
• 语义分析
• 中间代码生成
• 代码优化
• 目标代码生成

词法分析(1)

• 这个阶段的任务是从左至右、从上到下一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。

var sum,first,count:real;
  sum :=first + count * 10

• 单词类型          单词值
  标识符1(id1)         sum
  算符(赋值)            :=
  标识符2(id2)         first
  算符(加)               +
  标识符3(id3)         count
  算符(乘)                *
  整数                    10
  分号                    ；

词法分析(2)

• 又如一个C源程序片断：

int a;
a = a + 2;

• 词法分析后可能返回:
  单词类型                单词值
  保留字                      int
  标识符(变量名)          a
  界符                           ;
  标识符(变量名)          a
  算符(赋值)                  =
  标识符(变量名)          a
  算符(加)                      +
  整数                          2
  界符                          ；
  

有关术语

• 词法分析---从左到右读字符流的源程序、 识别（拼）单词。
• 单词---具有独立意义的基本语法单位。
• 保留字---具有特殊规定的意义，不允许用户将它们作为别用，是用户定义标识符的禁区。
• 标识符 ---用来表示程序、过程、函数、类型、常量和变量等名称的符号。

语法分析(1)

• 在词法分析的基础上，根据语言的语法规则（文法规则），把单词符号串分解成各类语法单位，如“短语”、“句子”、“程序段”和“程序”。
• 通过语法分解，确定整个输入串是否构成一个语法上正确的程序. 例: 符号串 X+0.168*Y, 经语法分析就可识别出这个字符串属于算术表达式。 Y:= X+0.168*Y;
• 语法分析所依循的是语言的语法规则，用产生式描述。
• 语法分析器读入单词，将它们组合成按产生式规定的各类语法单位。 sum :=first + count * 10

规则

• <赋值语句>::=<标识符>“:=”<表达式>
• <表达式>::=<表达式>“+”<表达式>
• <表达式>::=<表达式>“*”<表达式>
• <表达式>::=“(”<表达式>“)”
• <表达式>::=<标识符>
• <表达式>::=<整数>
• <表达式>::=<实数>

语法分析(2)

语法分析(3)

• id1:=id2+id3*N

• 术语
  • 语法：定义语言各语法成分的形式或结构。
  • 语法分析：依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树) 。
  • 语法树(推导树)：表示句型推导（或归约）的树型结构。语法树有助于理解一个句子语法结构的层次。

语义分析(1)

• 语义审查(静态语义)
• 上下文相关性
• 类型匹配
• 类型转换

Program p();
Var rate:real;
procedure initial;
   …	
“position := initial     +     rate * 60
 /* error */ 	 /* error */  /* warning */;

• 语义分析的一个重要内容是类型检查,对表达式及语句中的各语法成分作类型检查和分析.

如：Var  count:real;
 Var  first :real;
 Var  sum :real ;
     …
 sum := first     +    count* 10

语义分析(2)

• 语义分析的一个重要内容是类型检查，上例中进行类型检查之后增加了内部节点inttoreal.

• 术语
  • 语法：用来定义语言中各语法成份的形式或结构。
  • 语义：用来规格各语法成份的含义和功能，即规定它们的属性或在执行时应进行的运算或操作。
  • 语义分析：检查源程序是否包含语义错误，并搜集类型，供后面的代码生成阶段使用，只有语法和语义正确的源程序才可被翻译成目标代码。 语义分析程序需要进行频繁的造表和查表工作。

中间代码生成(1)

• 语义分析之后生成一种介于源语言和目标语言之间的中间语言代码。
• 中间代码有多种形式：
  三元式、四元式、逆波兰表示、树型结构
• 例:a:=b*c
  三元式：
  (1) (*, b, c)
  (2) (:=,a,(1))
  四元式：
  （*, b, c, a)
  
  
  

中间代码生成(2)

• id1:= id2 + id3 * 10
  因运算需要，需设置临时变量t1,t2,t3来存放中间运算结果。
  
  
• 中间代码的几种形式
  • 逆波兰表示：运算符在其运算量之后的表达式。
  • 三元式：（OP，ARG1，ARG2）
  • 四元式：（OP，ARG1，ARG2，RESULT）
  • 树：根结点OP，左子树ARG1，右子树ARG2 。

代码优化(1)

• 对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和省空间）的目标代码
• 例如：
  
  

代码优化(2)

• 例：
  
  
• 在本例中，b、c的值没有改变，故t1=t3，由 第二个表达式知道t2=t1。

目标代码生成

• 将前阶段产生的中间代码翻译为机器语言或汇编语言形式的目标程序。
• 目标程序总是按某一具体计算机的机器语言或汇编语言来产生的。
• 例：
  
  

符号表管理(1)

• 记录源程序中使用的名字
• 收集每个名字的各种属性信息类型、作用域、分配存储信息
• Const1 常量 值：35
  Var1 变量 类型：实 层次：2
• 在编译过程中，源程序中的标识符及其各种属性都要记录在符号表中，这些属性可以提供标识符的存储分配信息、类型信息、作用域信息等等。对于过程标识符，还要有参数信息，包括参数的个数和类型、实参和形参的结合方式等等。
• 符号表结构
  
  • 符号表是一种含记录的数据结构，通常一个标识符在符号表中占一个记录，记录中除了标识符的名字域之外，还有记录该标识符属性的域。

出错处理(error handling)

• 编译的每一个阶段都会发现源程序的错误，在发现错误之后，一般要对其有一定的处理措施，因而编译还可继续执行，不会一有错误就停止编译工作。
• 在词法分析中，能发现单词拼写错误。
• 在语法分析中，检查单词串是否符合语法的结构规则。
• 在语义分析中，编译程序进一步查出语法上虽正确但含有无意义的操作部分，如两个标识符相加，一个是数组名，一个是过程名，虽然语法上允许，但语义上不允许，各种错误，都应在相应的阶段进行处理。
• 出错处理过程：
  • 检查错误
  • 报告出错信息（错误种类及位置）
  • 校错及排错
  • 恢复编译工作

1.3 编译程序的结构(components)

• 词法分析程序
• 语法分析程序
• 语义分析程序
• 中间代码生成程序
• 代码优化程序
• 目标代码生成程序
• 符号表管理程序
• 出错处理程序

编译程序的结构图

1.4 编译阶段的组合

• 分析，综合(synthesis)
• 源程序的分析
• 线性分析
• 层次分析
• 语义分析
• 目标程序的综合
• 术语
  • 编译的前端（front end）:这些阶段以来于源语言、与目标机无关。
  • 编译的后端（back end）：依赖于目标机器的阶段。
  • 遍（趟）从头到尾扫描源程序（各种形式）一遍(pass)

编译阶段和运行阶段存储结构

1.5 编译技术和软件工具

• 编译程序实现方式
  • 手工
  • 机器语言
  • 汇编
  • 系统程序设计语言
  • 自动构造工具lex yacc gcc
  

编译程序的发展(1)

编译程序的发展(2)

• 语言范型(paradigms)
  • 命令式(imperative language)
  • 应用式(applicative)
  • 基于规则的（rule-based）
  • 面向对象的（object-oriented）
• 编译程序执行环境
  • 批处理
  • 交互环境
  • 嵌入系统环境

(1)语言范型（支持的计算模式）

• 应用式（函数式）：
  程序特点： Function n(…funetion2(funetion1(data))…)
• 程序执行：执行一个个函数施用在数据上的变换最终得到的结果
• 编译：
  • 语法分析容易；
  • 语义处理复杂；

基于规则的语言（prolog,yacc)：

• 程序特点：

• 面向对象语言：抽象数据类型，继承机制
• 编译：动态绑定

(2) 执行环境

• 批处理环境：
  • 将源程序作为整体处理
  • 排除程序错误不能依靠用户的外部帮助
• 交互环境：
  • 解释
  • 增量式编译
• 嵌入式系统环境：交叉编译
• 分布并行环境：并行编译
• 程序创建和测试环境：
  • 独立编译
  • 编译和调试同时设计考虑

编译技术和软件工具

• 结构化编辑器
• 程序调试工具
• 
• 高级语言转换工具
• 

研究领域

• 并行编译技术
• 交叉编译技术
• 自展编译技术

并行化编译技术(1)

• 目的：提高并行计算机体系结构的性能。

• 

并行化编译技术(2)

嵌入式

其它编译技术

• 交叉编译技术
  • 由于目标机指令系统与宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，称为交叉编译。
  
• 自展编译技术
  • 用被编译的语言来书写该语言自身的编译程序。

第1章 小结

• 内容
  • 什么是编译程序
  • 编译过程和编译程序的结构
  • 为什么要学习编译程序
• 本章重点对编译程序的功能和结构做了综合概述,要求学生了解编译程序各个成分在编译阶段的逻辑关系以及它们怎样作为一个整体完成编译任务的。

参考书

• 《Compilers: Principles, Techniques, and Tools/编译原理技术与工具（英文版）》 ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN.
• 《程序设计语言编译原理》 陈火旺，国防工业出版社， 2000
• 《编译原理及编译程序构造》高仲仪、金茂忠，北京航空学院出版社，1990.12
• 《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002年
• 《编译程序原理与技术》李赣生、王华民编著，清华大学出版社
• 《编译原理技术》陈意云，中国科技大学出版社
• 《编译原理习题精选》陈意云、张昱著，中国科技大学出版社

习题

• 1. 什么是编译程序？
• 2. 简要介绍编译过程的六个阶段，并给出编译程序的结构。