《编译原理 第一章》由会员分享，可在线阅读，更多相关《编译原理 第一章（51页珍藏版）》请在金锄头文库上搜索。
1、关于本课程v编译原理是计算机专业的一门核心专业基础课程（程序与 编译），该课程介绍编译器构造的一般原理、基本实现方 法。主要内容包括词法分析、语法分析、语义分析、中间 代码生成、代码优化和目标代码生成等。v学习意义：对程序设计语言的设计和实现有深刻的理解，对和程 序设计语言有关的理论有所了解，对宏观上把握程序 设计语言来说能起一个奠基的作用。 有助于学生快速理解、定位和解决在程序编译、测试 与运行中出现的问题。 编译程序是软件工程的一个很好的实例大多数程序员同时又是一些简单语言（如输入输出、 脚本语言）的设计者，掌握编译知识有助于提高他们 设计这些语言的水平。 编译技术在软件安全和软件逆向工程
2、等方面有着广泛 的应用课程难点 v编译程序规模庞大，一门课程无法将所有的细节 都讲清楚，这使学生对编译程序各逻辑部分之间 的接口和一些算法的实现是模糊的 v课程涉及不少理论知识，如形式语言和自动机理 论、语法制导的理论等。 v课程包含了很多算法，大的有LL（1）分析算法和 各种LR（1）分析算法等，小的有DFA 化简算法 、计算开始符号集合和后继符号集合的算法、各 种数据流方程的迭代求解算法。 本课程安排v第一章 引论v第二章 文法与语言v第三章 词法分析v第四章 语法分析v第五章 编译程序的数据结构和符号表v第六章 语法制导翻译与中间代码生成（语义分析）v第八章 编译程序1.1 基本观念程序
3、、语言v计算机、程序、语言计算机接受指令，然后执行指令指令组成的序列，称为程序符合一定规则（文法）的程序的集合，称为语言v语法（形式）v语义（意义） /形式与意义之间的对应关系？v讨论：C语言与C语言程序之间的关系1.1 基本观念程序、语言v语言的作用设计程序(选出特定的程序构造程序)v程序的作用由计算机执行在人之间的交流想法，由于程序没有歧义v如何定义语言本课程要学习的内容以有限的规则，定义无限多的程序 。1.1 基本观念语言的多样性与翻译v语言的多样性机器语言、汇编语言、C语言、java、VC机器喜欢低级语言，程序员喜欢高级语言方便在特定领域的应用，有利于提高工作效率v多样性需要翻译计算机
4、语言由单一的机器语言发展到现今数十种高级语 言，就是因为有了编译技术 。v翻译的策略编译（整体翻译）解释（逐句的翻译、执行）1.1 基本观念-编译与解释v高级语言程序通常采用两种方式执行：解释方 式和翻译方式v解释方式：逐个语句地分析和执行，如Basic， Prolog优点：易于查错，易于移植缺点：效率低，运行速度慢v编译方式：对整个程序进行分析，翻译成等价 机器语言程序后执行，如Pascal，Fortran，C优点：只需分析和翻译一次，缺点：在运行中发现的错误必须在源程序中查找功能工作结果实现技术上解释 程序源程序的一 个执执行系统源程序的 执执行结结果执行中间代码编译 程序源程序的一 个转
5、换转换 系统源程序的 目标标代码码把中间代码转 换成目标程序解释程序和编译程序的区别解释程序和编译程序的区别解释程序和编译程序的根本区别根本区别： 是否生成目标代码编译和解释程序编译和解释程序目标目标 程序程序源源 程程 序序编编 译译 程程 序序初始数据初始数据计计 算算 结结 果果源程序源程序解解 释释 程程 序序初始数据初始数据计计 算算 结结 果果1.2 什么是编译程序？ v定义：是一种语言转换系统编译程序高级语言书 写的程序（ 源程序）低级语言 程序（目 标程序）Gcc编译器C可执行程序 (机器程序)常用T形图来表示编译程序涉及的三个语言：S O I例如：其中： S:源语言(程序)，
6、 O:目标语言(程序), I:实现语言,编译程序运行系统目标程序输入数据计算结果源程序编译程序的基本功能v从功能上看，一个编 译程序就是一个语言 翻译程序。v源语言通常是一个高 级语言，如java，C 或Pascal。v目标语言通常是一个 低级语言,如汇编或机 器语言。 编译程序源语言程序目标语言程序出错和警告信息编译程序在计算机系统中的作用v编译系统是一种软件，一种系 统软件。软件：计算机系统中的程序及其 文档。系统软件：居于计算机系统中最 靠近硬件的一层，其他软件一般 都通过系统软件发挥作用。和具 体的应用领域无关，如编译系统 和操作系统等。语言处理系统：把软件语言书写 的各种程序处理成可
7、在计算机上 执行的程序，如编译系统。裸机操作系统语言处理系统应用软件层翻译外文资料编译源程序分析阅读原文 识别单词 分析句子输入并扫描源程序 词法分析 语法分析综合修辞加工 写出译文代码优化 目标代码生成1.3 编译程序的结构翻译外文资料与编译源程序进行类比编译程序完成从源程序到目标程序的翻译工作 ，是一个复杂的整体的过程。从概念上来说，一个 编译程序的整个工作过程是划分成阶段进行的，每 个阶段将源程序的一种表示形式转换成另一种表示 形式，各个阶段进行的操作在逻辑上是紧密连接在 一起的，下面给出了一个编译过程的各个阶段，这 是一种典型的划分方法。 编译过程概述编译程序的功能和组织结构表 处 理
8、词 法 分 析源 程 序目 标 程 序错 误 处 理语 法 分 析语 义 分 析目 标 代 码 生 成前 端后 端中 间 代 码 优 化中 间 代 码 生 成编译程序的前端前端：与源语言有关，而与目标机无关的编译程序编译程序的后端后端：与目标机有关，而与源语言无关的编译程序相关概念(1) 词法分析(Lexical analysis)v识别单词v词法分析程序又称扫描程序。v是编译过程的第一个阶段，其任务是：读 源程序的字符流、识别单词（如标识符、 整数、界限符等），并转换成内部形式。输入字符串（即源程序）输出单词符号（最基本的语法单位） 。读字符流的源程序、识别单词例： position :=
9、initial + rate * 60词法分析举例单词类型单词值 标识符1(id1)position算符(赋值) := 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 分号 ；(2) 语法分析（Syntax analysis）v识别句子v语法分析的任务：在词法分析的基础上 将单词序列分解成各类语法短语，如“语 句”，“表达式”等等。一般这种语法短语 ，也称语法单位，可表示成语法树。v语法分析所依据的是语言的语法规则， 即描述程序结构的规则。通过语法分析 确定整个输入串是否构成一个语法上正 确的程序。（语法检查）id1：=id2 +
10、id3 * 10 经语法分析得知其是 PASCAL语言的“赋值语句” 。语法分析所依据的是语言的语法规则，即描述程 序结构的规则。通过语法分析确定整个输入串是 否构成一个语法上正确的程序。语法检查语法分析id1:=id2+id3*60:=+60*Id1 Id2 Id3 id1：=id2 + id3 * 10 经语法分析得知其是PASCAL语言的“赋值语句” 。程序的结构通常是由递归规则表示的，例如，我们 可以用下面的规则来定义表达式： （1）任何标识符是表达式。 （2）任何常数（整常数、实常数）是表达式。 （3）若表达式1和表达式2都是表达式，那么：表达式1+表达式2表达式1 * 表达式2（表
11、达式1） 都是表达式功能：把源程序的单词序列组成语法短语(表示成语法树)例: :=“:=” :=“+” :=“*” :=“(”“)” := := :=赋值语句标识符表达式表达式+表达式表达式标识符常数标识符:=表达式*词法分析和语法分析本质上都是对源程序的 结构进行分析。但词法分析的任务仅对源程序进 行线性扫描即可完成，比如识别标识符，因为标 识符的结构是字母打头的字母和数字串，这只要 顺序扫描输入流，遇到即不是字母又不是数字字 符时，将前面所发现的所有字母和数字组合在一 起而成单词标识符。但这种线性扫描则不能用于 识别递归定义的语法成分，比如就不能用此办法 去匹配表达式中的括号。 （3）语义
12、分析 v 语义:对各种语法成份赋予具体的意义v 语义审查上下文相关性类型匹配类型转换表达语义规则的主要工具是属性文法例:Program p(); Var rate:real; procedure initial; position := initial + rate * 60/* error */ /* error */ /* warning */; 如：某些语言规定运算对象可被强制，那么当二 目运算施于一整型和一实型时，编译程序应将整 型转换成实型而不能认为是源程序的错误，假如 在语句id1:= id2 + id3 * 60中，* 的两个运算对象 ：id3是实型，60是整型，则语义分析阶段进
13、行 类型审查之后，在语法分析所得到的分析树上增 加一语义处理结点，表示整型变成实型的一目算 符inttoreal 。60:=+*Id1 Id2 Id3 inttorealid1:=id2+id3*60插入语义处理结点的语法树 (4)中间代码生成v 源程序的内部(介于源语言和目标语言中间)表示 “中间代码”是一种结构简单、含义明确的记号系统 ，这种记号系统可以设计为多种多样的形式。重要 的设计原则为两点：一是容易生成；二是容易将它 翻译成目标代码. v很多编译程序采用了一种近似“三地址指令”的“四元 式”中间代码，这种四元式的形式为：（运算符，运算对象1，运算对象2，结果）。 id1:= id2
14、 + id3 * 60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)(5) 代码优化v优化（在理论上不是必须的）是对前阶段产生的中间代码进行变换或进行 改造，目的是使生成的目标代码更为高效， 即省时间和省空间 。删除无用代码/ 减少冗余id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1)变换 （1） ( *id360.0t1)( 2）（ + id2 t1id1)(6) 目标代码生成v这一阶段的任务是把中间代
15、码变换成特定机器上的 绝对指令代码或可重定位的指令代码或汇编指令代 码。这是编译的最后阶段，它的工作与硬件系统结 构和指令含义有关，这个阶段的工作很复杂，涉及 到硬件系统功能部件的运用、机器指令的选择、各 种数据类型变量的存储空间分配以及寄存器和后缓 寄存器的调度等目标代码生成v可以根据目标机的模型，对目标代码进一步进行优 化(*,id3， 60.0， t1)(+,id2， t1， id1)movfid3,R2 mulf#60.0,R2 movfid2,R1 addfR2,R1 movfR1,id1符号表管理v记录源程序中使用的名字(标识符)v收集每个名字的各种属性信息类型、作用域、分配存储信息名字信息出错处理v检查错误、报告出错信息、排错、恢复编译 工作v出错处理程序对词法和语法分析遇到的错误 给出在源程序中出错的错误性质、位置等。 v语义错误常采用下列方式查出：静态模拟检查：动态调试检查：编译程序的结构v词法分析程序v语法分析程序v语义分析程序v中间代码生成程序v代码优化程序v目标代码生成程序v符号表管理程序v出错管理程序编译程序的结构框图编译的各个阶段编译的各个阶段一个编译过程可由一遍、两遍或多遍完 成。所谓“遍”，也称作“趟”，是对源程序或其等 价的中间语言程序从头到尾扫视并完成规定任 务的过程。每一遍扫视
