编译原理及实现技术 计算机科学与技术学院 申春 课件网址：cc.jlu.edu.cn->课程资源->课程总览->计算机科学与技术学院->编译原理与实现

第一章 编译引论 编译程序及功能 编译程序的逻辑结构 编译程序的实现途径 课程学习的意义和学习方法

1.1 编译程序及功能 编译程序:（Compiler，compiling program）也称为编译器，是指把用高级程序设计语言书写的源程序，翻译成等价的机器语言格式目标程序的翻译程序。 翻译程序 计算机源程序A 计算机源程序B 编译程序 高级语言 源程序 机器语言目标程序

高级语言程序的处理过程 源程序文件(.c) 编辑器 预处理器 标准源程序文件(.i) 编译程序 目标汇编代码(.asm,.s) 汇编程序 可重定位的目标机器代码（.obj,.o） 连接/装配程序 绝对机器代码(.exe, .out)

1.2 程序设计语言的发展 机器语言：能够被计算机的硬件系统直接执行的机器指令序列，如“1011011000000000”。 1.2 程序设计语言的发展 机器语言：能够被计算机的硬件系统直接执行的机器指令序列，如“1011011000000000”。 汇编语言：将硬件指令用一些助记符表示，即符号化的机器语言，如“ADD AX ,15”。 高级语言：模仿便于理解的自然语言和数学语言，采用一组形式规则来描述的人工语言。

1.3 高级语言的几种执行方式 1.编译方式：源语言为高级语言，目标语言是低级语言（汇编或机器语言）的翻译程序。 源程序 目标程序 (*.C) (*.OBJ/*.EXE) 编译程序 程序的输入数据 运行结果

1.3 高级语言的几种执行方式 2.解释方式：对源程序直接逐句地分析执行。解释器相当于源程序的抽象执行机，是语言的实现系统。 (basic， 解释程序 源程序 运行结果 (basic， 脚本语言) 输入数据

1.3 高级语言的几种执行方式 3.语言的转换执行方式：将A语言程序转换为B语言程序，用B语言已有的编译器去编译执行。（同级程序设计语言） 转换程序 A语言程序 B语言程序 编译、解释 运行结果

1.4 编译程序的逻辑结构 表 处 理 错 误 处 理 目 标 代 码 生 成 中 间 优 化 语 义 分 析 法 词 程 序 源 1、 源语言的种类成千上万，从常用的诸如FORTEAN,PASCAL和C语言，到各种各样的计算机应用领域的专用语言。 2、目标语言也是成千上万的。 3、编译程序根据它们构造的不同、所执行的具体功能的差异又分成多种类型，比如：一趟编译的、多趟编译的、具有调试和优化功能的等等。 尽管存在这些明显的复杂因素，任何编译程序所必需执行的主要任务基本是一样的，通过理解这些任务，使用同样的基本技术，我们可以为各种各样的源语言和目标语言设计和构造编译程序。

词法分析(Lexical Analysis) 依据语言的词法规则，扫描源程序的字符序列，识别每 一个单词及其种类，并将其表示成所谓的机内表示TOKEN记号形式。 for(i=1;i<30;i++) 单词种类: 关键字: if、then、for、while等; 标识符; 常量; 运算符 特殊符 分界符: 标点符号、 左右括号等等. <保留字,for> <界限符,(> <标识符,i> <运算符,=> <常量,1> <界限符,;> <标识符,i> <运算符,< > <常量,30> <界限符,;> <标识符,i> <运算符,++> <界限符,)>

语法分析（Syntax Analysis) 依据语言的语法规则，将单词分解成各类语法短语（可表示为语法树），确定整个输入串是否构成一个语法上正确的程序。 赋值语句 sum:= first + count * 10 标识符 := 表达式 1.<赋值语句> ::= 标识符:=<表达式> 2.<表达式> ::= <表达式>+<表达式> 3.<表达式> ::= <表达式>*<表达式> 4.<表达式> ::= (<表达式>) 5.<表达式> ::= 标识符 6.<表达式> ::= 常数 sum 表达式 + 表达式 标识符 表达式 * 表达式 常数 first 标识符 10 count

语义分析（Semantic Analysis） 检查源程序有无语义错误，为代码生成阶段收集信息。（标识符是否声明、类型检查、强制类型转换、下标越界检查等） int i, a[20]=0; for(i=1; i<30; i++) a[10]=a[10]+i;

中间代码生成（Intermediate Code Generation） 为便于对程序的优化、移植和修改,将源程序转换成一种称为中间代码的内部表示形式。中间代码是一种简单的、含义明确的记号系统，例如四元式（运算符，对象1，对象2，结果）。 例： sum:=first + count * 10 生成如下四元式形式的中间代码序列： 1、（int-to-real, 10 , - ,t1 ) 2、（*, count , t1 ,t2 ) 3、（+, first , t2 ,t3 ) 4、（:=, t3 ,- , sum )

中间代码优化（ Intermediate Code Optimization） 在不改变源程序语义的前提下变换或改造中间代码，使生成的目标代码更为高效，即缩短运行时间或节省存储空间。 1、（int-to-real, 10 , - ,t1 ) 2、（*, count , t1 ,t2 ) （*, count , 10.0 ,t2 )

中间代码变换为特定机器上的机器指令代码（绝对指令代码或可重定位的指令代码）或汇编指令代码。 目标代码生成（Code Generation） 中间代码变换为特定机器上的机器指令代码（绝对指令代码或可重定位的指令代码）或汇编指令代码。 例：sum:=first + count * 10 生成如下汇编代码： 1. MOV count , R1 2. MULT R1 , #10.0 3. MOV first , R2 4. ADD R1, R2 5. MOV R1, sum 四元式中间代码序列： 1、（*, count , 10.0 ,t2 ) 2、（+, first , t2 ,t3 ) 3、（:=, t3 ,- , sum )

表格管理（Symbol-Table Management) 较大的编译程序用到很多表格，为了合理地管理表格（构造、查找、更新），很多编译程序设立一些专门子程序（称为表格管理程序）负责管理表格。 错误处理（Error Detection and Reporting) 编译程序各个阶段还存在着错误处理模块，当有错误出现时，由相应的错误处理模块给出解决方案，使得编译器能够继续进行下去。词法和语法错误检查集中一次完成，而语义错误检查要分散在语法分析以后的各个阶段。

遍 （Pass）所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次，并作加工处理，生成新的中间结果或目标程序。 代 码 生 成 中 间 优 化 语 义 分 析 法 词 程 序 源 前端 后端

1.5 编译程序实现方法 转换法：将A语言程序转换成B语言的程序，再利用B语言的编译器实现A语言。 1.5 编译程序实现方法 转换法：将A语言程序转换成B语言的程序，再利用B语言的编译器实现A语言。 自展法：实际上就是用低级语言先实现一个简单的编译器，然后用这个编译器的语言再去编写一个更高级的编译器，这个新编译器是旧编译器的扩展的过程。 移植法：修改目标代码或者修改编译程序的后端。 工具法：Lex、Yacc等工具生成语法分析程序。（软件自动化研究成果）

1.5 课程的意义 加深对高级语言的工作原理的理解； 提高设计大型软件的能力； 提高形式化、抽象化的理解和运用能力； 1.5 课程的意义 加深对高级语言的工作原理的理解； 提高设计大型软件的能力； 提高形式化、抽象化的理解和运用能力； 编译技术的应用。可以将该原理应用于软件逆向工程、程序分析/验证、模型转换及和软件安全等涉及元级操作的领域；受资源限制的嵌入式系统；可以灵活设计、实现自定义语言；

学习编译原理的方法 理论教学 64 学时 实践教学 16 学时（第9周-12周）

自定义SNL语言（Small Nested Language），实现该语言的编译程序