蒋伟进 教授 jwj_nudt163.com 13973303666 *1编译原理计算机能广泛地被应用，应归功于高级 程序设计语言。而计算机语言能由最初单一 的机器语言发展到现今数千种高级语言，就 是因为有了编译程序。编译理论与技术也是 计算机科学中发展得最迅速、最成熟的一个 分支，它集中体现了计算机发展的成果与精 华。 *2编译原理文法和语言的基本知识编译概述词法分析与有穷自动机语法分析语法制导翻译和中间代码生成 符号表的组织和管理1 2 3 4 5 6Date3编译原理代码优化静态存储分配目标代码生成789Date4编译原理编 译 原 理开设编译原理的目的 ：系统地向学生讲述编译系统的结构、工作流程及编译程序各组成部分的设计原理和实现技术，使学生通过本课程的学习之后，既掌握编译理论和方法方面的基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。所学的主要内容 ：v程序的查错与处理v 文法和形式语言 v自动机理论v词法分析v语法和语义分析v中间语言、代码生成v优化v存贮组织与分配Date5编译原理q 、计算机系统组成v硬件：主板、CPU风扇、内存、显示器、显卡、硬盘、声卡、光驱（刻录机、DVD机）、软驱（优盘）、机箱电源、鍵盘、鼠标、音箱、调制解调器、打印机、网卡、扫描仪、耳麦、摄像头、电视接收盒（电视接收卡）v软件：操作系统、磁盘整理软件、分区软件、备份软件、办公软件、播放器软件、压缩软件、杀毒软件、输入法软件、看图软件、图片处理软件、动画制作软件、网页制作软件、浏览器软件、下载软件、防火墙软件、搜索软件、聊天软件Date6编译原理第一章 编译程序概论 n什么是编译程序编译原理这门课程主要介绍设计 和构造编译程序的基本原理和常用的 技术和方法。本章重点介绍编译程序的基本概念。n n编译的过程编译的过程n n编译程序的结构编译程序的结构 Date7编译原理1.1 什么是编译程序翻译程序是指这样一个程序,它把 一种语言(称作源语言)所写的程序(源 程序)翻译成等价的另一种语言(称作 目标语言)的程序(目标程序)。 高级语言程序机器语言程序翻译程序Date8编译原理1.1 什么是编译程序编译程序是一种翻译程序，它将 高级语言所写的源程序翻译成等价的 机器语言或汇编语言的目标程序。 源程序高级语言程序编译程序目标程序汇编语言或者 机器语言程序Date9编译原理程序运行阶段采用编译方式在计算机上执行用高级 语言编写的程序，需分阶段进行。第一种情况 ：源程序编 译 程 序机器语言 目标程序初始数据运行系统结果编 译 阶 段运 行 阶 段高级语言程序Date10编译原理第二种情况 ：源程序编 译 程 序机器 语言 目标 程序初始数据运行系统结果编 译 阶 段运行阶段汇 编 程 序汇编 语言 目标 程序汇 编 阶 段高级语言程序程序运行阶段Date11编译原理1.2 编译过程和编译程序的基本结构 将英文句子 “I wish you success ”翻译成中文句子的大致过程是：q 词法分析 q 语法分析 q 语义分析 q 修饰工作 q 翻译成文 Date12编译原理编译过程 编译程序是将一种语言形式翻译成 另一种语言形式，因此，其工作过程一 般可划分为如下五个阶段： q 词法分析 q 语法分析 q 语义分析和中间代码生成 q 代码优化 q 目标代码生成Date13编译原理float r，h，s；s = 2*3.1416 * r *(rh);例如 计算圆柱体表面积的程序 片断如下：编译过程 Date14编译原理词法分析阶段的任务是对构成 源程序的字符串从左到右进行扫描 和分解，根据语言的词法规则，识 别出一个一个具有独立意义的单词( 也称单词符号, 简称符号 )。1. 词法分析词法分析Date15编译原理词法规则是单词符号的形成规则, 它规定了哪样的字符串构成一个单词 符号。词法规则float r，h，s；s = 2*3.1416*r*(hr);例如Date16编译原理上述源程序通过词法分析识别出 如下单词符号：基本字 float 标识符 r、h、s常数 3.1416、2 算符 * 、 界符 （、 ）、 ；、 ，、= 词法规则Date17编译原理2. 语法分析语法分析的任务是在词法分析的基础上, 根据语言的语法规则从单词符 号串中识别出各种语法单位 ( 如表达式、说明、语句等 ) ,并进行语法检查,即检查各种语法单位在语法结构上的正确性。 Date18编译原理语法规则语言的语法规则规定了如何从单 词符号形成语法单位，语法规则是语 法单位的形成规则。 float r，h，s；s = 2*3.1416*r*(hr);例如Date19编译原理语法规则单词符号串 s=2*3.1416 * r *(hr) 中，“s” 是，单词符号串“2 * 3.1416 * r *(hr)” 组合成这样的语法单位 , 由 =构成这 样的语法单位。Date20编译原理3. 语义分析和中间代码生成语义分析的任务是首先对每种语 法单位进行静态的语义审查，然后分 析其含义，并用另一种语言形式 (比源语言更接近于目标语言的一种中间 代码或直接用目标语言 ) 来描述这种语义。Date21编译原理例如，前例中将s = 2*3.1416 * r *(hr)翻译成如下 形式的四元式中间代码：(1) ( *, 2, 3.1416, T1 )(2) ( *, T1, r, T2 ) (3) ( +, h, r, T3 ) (4) ( *, T2, T3, T4 ) (5) ( =, T4, _, s )Date22编译原理4. 代码优化代码优化的任务是对前阶段产生的 中间代码进行等价变换或改造，以期获得 更为高效即省时间和空间的目标代码。优 化主要包括局部优化和循环优化等，例如 上述四元式经局部优化后得：(1) ( *, 6.28, r, T2 ) (2) ( +, h, r, T3 ) (3) ( *, T2, T3, T4 )(4) ( =, T4, _, s )Date23编译原理5.目标代码生成 目标代码生成的任务是将中间 代码变换成特定机器上的绝对指令 代码或可重定位的指令代码或汇编 指令代码。 Date24编译原理表格管理和错误处理编译程序在工作过程中需要建立一 些表格，以登记源程序中所提供的或在 编译过程中所产生的一些信息，编译各 个阶段的工作都涉及到构造、查找、修 改或存取有关表格中的信息，因此，在 编译程序中必须有一组管理各种表格的 程序。在编译程序的各个阶段中，都要涉及 表格管理和错误处理。Date25编译原理表格管理和错误处理一个好的编译程序在编译过程中，应 具有广泛的程序查错能力，并能准确地报 告错误的种类及出错位置，以便用户查找 和纠正，因此，在编译程序中还必须有一 个出错处理程序。 Date26编译原理编译程序的结构源程序语义分析和中间代码生成程序语法分析程序词法分析程序代码优化程序目标代码生成程序目标程序表格管理程序出错处理程序( 字符串 )Date27编译原理1.3 编译程序的生成方法q 对源语言和目标语言认真分析 q 设计编译算法 q 选择语言编制程序 q 调试编译程序 q 提交相关文档资料编译程序是一个复杂的系统程序，要 生成一个编译程序一般要考虑以下几方面 ：Date28编译原理编译程序的自动生成如目前已广为使用词法分析程序的自 动生成系统LEX和语法分析程序自动生成 系统YACC等，此外, 还有可用来自动产 生整个编译程序的软件工具：编译程序产 生器, 它的功能是将任一语言的词法规则 、语法规则和语义解释的描述作为输入， 自动生成该语言的编译程序。随着编译技术和自动机理论的发展, 近 年来已研制出了一些编译程序的自动生成 系统。Date29编译原理编译程序的自动生成生成编译程序的方法还常采用自编译 方式和移植方式。随着并行技术和并行语言的发展，处 理并行语言的并行编译技术和将串行程序 转换成并行程序的自动并行编译技术正在 深入研究之中。Date30编译原理1.4 编译技术在软件开发中的应用虽然我们只有少数人从事构造或 维护程序语言编译程序的工作,但是， 大部分系统软件和应用软件的开发， 通常要用到编译的原理和技术。Date31编译原理1.4 编译技术在软件开发中的应用例如,设计词法分析器的串匹配 技术已用于正文编辑器、信息检索 系统和模式识别程序; 上下文无关 文法和语法制导定义已用于创建诸 如排版、绘图系统和语言结构化编 辑器中，代码优化技术已用于程序 验证器和从非结构化的程序产生结 构化程序的编程之中。 Date32编译原理本章小结q 什么是编译程序q 编译过程的五个阶段q 编译程序的结构框图编译程序是一种翻译程序，它将高 级语言所写的源程序翻译成等价的 机器语言或汇编语言的目标程序。词法分析、语法分析、语义分析和 中间代码生成、代码优化、目标代 码生成Date33编译原理本章小结源程序语义分析和中间代码生成程序语法分析程序词法分析程序代码优化程序目标代码生成程序目标程序表格管理程序出错处理程序( 字符串 )Date34编译原理习题、复习、考试 Date35编译原理