1、编译原理任课教师：信息科学技术学院计算语言所什么是编译原理？为什么要学习编译原理？1谢谢观赏2019-8-17 编译器的设计 一般的软件设计：文本编辑器、自动排版、文本编辑器、自动排版、模式识别、程序自动验证、程序自动调试模式识别、程序自动验证、程序自动调试 为计算机分析和理解自然语言提供参考为计算机分析和理解自然语言提供参考2谢谢观赏2019-8-17编译原理 上课时间：周二上午1-2节（单周）周五上午1-2节 上课地点：一教309 上机地点：中文系机房 学习方式：课堂讲解+课后作业+上机实践 考试成绩：试卷成绩+作业成绩+上机成绩3谢谢观赏2019-8-17参考教材 编译原理，清华大学出版
2、社 张素琴、吕映芝 等编著，2005年 编译程序设计原理 北京大学出版社，杜淑敏等编著，1986年 陈火旺 刘春林等 程序设计语言编译原理 国防工业出版社，2000年4谢谢观赏2019-8-17教学要求 掌握编译系统的一般构造原理 掌握编译系统的基本实现技术 熟悉一些自动构造工具5谢谢观赏2019-8-17授课内容第一章第一章 编译程序概述编译程序概述第二章第二章 PL/0PL/0编译程序的实现编译程序的实现第三章第三章 文法和语言文法和语言第四章第四章 词法分析词法分析第五章第五章 自顶向下语法分析方法自顶向下语法分析方法第六章第六章 自底向上优先分析方法自底向上优先分析方法第七章第七章 L
3、RLR分析方法分析方法第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成第九章第九章 符号表符号表第一第一章章 代码优化代码优化第一一章第一一章 代码生成代码生成6谢谢观赏2019-8-17编译程序概述 什么是编译程序 编译过程和编译程序的结构 编译技术和软件工具的介绍7谢谢观赏2019-8-17程序设计语言：程序设计语言：用来编写计算机程序的语言。什么是编译程序8谢谢观赏2019-8-17程序设计语言 机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。由二进制的指令代码组成。1+3 表示为表示为 10000001 00000001 00000011 是最底层的计
4、算机语言，不需要翻译就可以直接被计算机硬件识别。对应不同的计算机硬件有不同的机器语言。特点：执行速度快，但编写程序的难度大，修改、调试不方便，直观性差，不易移植。9谢谢观赏2019-8-17程序设计语言 汇编语言：又称为符号语言。与机器语言一一对应，采用能帮助记忆的英文缩写符号（指令助记符）来代替机器语言指令中的操作码，用地址符号来代替地址码。用指令助记符及地址符号书写的指令称为汇编指令，用汇编指令编写的程序称为汇编语言源程序。将将X、Y中的内容相加中的内容相加 表示为表示为 ADD X Y 机器不能直接识别汇编语言程序，必须把它翻译为机器语言程序才能执行。特点：比机器语言直观，容易理解和记忆
5、，比高级语言的执行效率高，但通用性和移植性较差。10谢谢观赏2019-8-17程序设计语言 高级语言：与具体的计算机硬件无关，是面向问题的程序设计语言，其表达方式接近于自然语言和数学语言，易于人们接受和掌握。采用类似于数学公式的书写方式：x=1+3 特点：独立于具体的计算机硬件，程序的编制和调试方便，通用性和可移植性好。在计算机执行之前，需要通过编译程序翻译成目标语言程序，或需要通过解释程序边解释，边执行。时间与空间效率比较低。目前比较流行的高级语言有：Visual C,Visual Basic,Java，FoxPro，Pascal,Lisp,Cobol等。11谢谢观赏2019-8-17 比较
6、 机器语言汇编语言高级语言硬件识别是唯一可以识别的语言不可识别不可识别是否可直接执行 可直接执行不可，需汇编、连接不可，需编译/解释、连接 特点面向机器占用内存少执行速度快使用不方便面向机器占用内存少执行速度快较为直观与机器语言一一对应v面向问题/对象v占用内存大v执行速度相对慢v标准化程度高v便于程序交换，使用方便 定位低级语言，极少使用低级语言，很少使用高级语言，种类多，常用12谢谢观赏2019-8-17源程序源程序目标程序目标程序可执行程序可执行程序 编辑编辑 程序程序汇编或汇编或编译程序编译程序连接连接 程序程序用于编写高用于编写高级语言程序级语言程序把目标程序以及所需的功能库等转换成
7、一个可执行的装入程序。完成此功能的程序叫连接程序。编译方式是将高级语言编写编译方式是将高级语言编写的源程序整个地翻译成机器的源程序整个地翻译成机器语言表示的目标程序的方式。语言表示的目标程序的方式。完成此功能的程序叫编译程完成此功能的程序叫编译程序。序。13谢谢观赏2019-8-17什么是编译程序 编译程序的功能：把高级语言程序翻译成等价的低级语言程序。源程序编译程序目标程序 编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。14谢谢观赏2019-8-17编译和解释程序：15谢
8、谢观赏2019-8-17功能功能工作结果工作结果实现技术上实现技术上编译编译程序程序源程序的一个转换转换系统源程序的目标代码目标代码把中间代码转换成目标程序解释解释程序程序源程序的一个执行执行系统源程序的执行结果执行结果执行中间代码解释程序和编译程序的区别解释程序和编译程序的：是否生成目标代码16谢谢观赏2019-8-17编译程序概述 什么是编译程序 编译过程和编译程序的结构 编译技术和软件工具的介绍17谢谢观赏2019-8-17编译过程概述 编译器内部包括了许多步骤或称为阶段，它们执行不同的逻辑操作。将这些阶段设想为编译器中一个个单独的片断是很有用的，尽管在应用中它们是经常组合在一起的，但它
9、们确实是作为单独的代码操作来编写的。18谢谢观赏2019-8-17编译过程概述 编译工作的基本过程是：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等6个阶段。每个阶段都有表格管理和出错处理部分。19谢谢观赏2019-8-17词法分析语法分析语义分析目标代码生成中间代码生成代码优化目标程序源程序出 错 处 理表 格 管 理20谢谢观赏2019-8-17编译过程概述 机器翻译：让计算机翻译人类语言，例如：将汉语翻译为英文。编译：让计算机翻译程序设计语言（人工语言），例如：将C语言编译为机器语言。21谢谢观赏2019-8-17编译逻辑过程 词法分析 语法分析 语义分析 中间代码
10、生成 代码优化 目标代码生成22谢谢观赏2019-8-17词法分析（自动分词+词性标注）像翻译英文句子一样，先要分析单词，弄清各单词的意义和句中的作用，才能对句子进行翻译。主要任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。单词包括：保留字、标识符、运算符、分界符等。例：position :=initial +rate *60;23谢谢观赏2019-8-17词法分析（自动分词+词性标注）position :=initial +rate *60;单词类型单词类型单词值单词值 标识符1(id1)position 算符(赋值):=标识符2(id2
11、)initial 算符(加)+标识符3(id3)rate 算符(乘)*整数 60 界符 ；24谢谢观赏2019-8-17又如一个C源程序片断：int a;a=a+2;词法分析后可能返回:单词类型单词类型单词值单词值 保留字 int标识符(变量名)a界符 ;标识符(变量名)a算符(赋值)=标识符(变量名)a 算符(加)+整数 2界符 ；25谢谢观赏2019-8-17有关术语 词法分析(lexical analysis or scanning)-The stream of characters making up a source program is read from left to righ
12、t and grouped into tokens,which are sequences of characters that have a collective meaning.单词-token 保留字-reserved word 标识符-identifier(user-defined name)26谢谢观赏2019-8-17语法分析（自动句法分析）语法分析程序与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。主要任务：在词法分析的基础上，将单词分解成各类语法短语。一般语法短语可表示成语法树。功能:层次分析.依据依据源程序的语法
13、规则语法规则把源程序的单词序列组成语法短语(表示成语法树).position :=initial +rate *60 ;27谢谢观赏2019-8-17语法分析（自动句法分析）规则规则:=“:=”:=“+”:=“*”:=“(”“)”:=:=:=28谢谢观赏2019-8-17 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*29谢谢观赏2019-8-17id1:=id2+id3*N:=+N 60*id1 Positionid2 initialid3 rate30谢谢观赏2019-8-17术语 语法分析(syntax analysis or parsing)The purpose
14、 of syntax analysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure.语法树(推导树)(parse tree or derivation t
15、ree)31谢谢观赏2019-8-17语义分析语义审查(静态语义)按照语法树的层次关系和先后次序，逐个语句地进行语义处理。主要任务：进行类型审查，审查每个算符是否符合语言规范，不符合时应报告错误。类型匹配 类型转换例:Program p();Var rate:real;procedure initial;position:=initial +rate*60/*error*/*error*/*warning*/;32谢谢观赏2019-8-17又如:Program p();Var rate:real;Var initial:real;Var position:real;position:=init
16、ial +rate*6033谢谢观赏2019-8-17语义分析60:=+*Id1 positionId2 initialId3 rateinttoreal34谢谢观赏2019-8-17术语 语义分析(semantic analysis)The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules,type rulese.g.To relate each applied occurrence of
17、an identifier in the source program to the corresponding declaration.35谢谢观赏2019-8-174、中间代码生成：如：sum：firstcount10 生成四元式序列：（inttoreal 10 t1）（id3 t1 t2）（id2 t2 t3）（：t3 id1）运算符运算对象1运算对象2结果语法分析和语义分析之后，有时将源程序变成一种内部表示形式，这种内部表示形式叫中间代码，该代码是一种简单的记号系统。三元式、四元式等四元式的形式为：（算符，运算对象1，运算对象2，结果）id1id2id3t1，t2，t3是临时变量36谢
18、谢观赏2019-8-17中间代码生成(intermediate code generation)This is where the intermediate representation of the source program is created.We want this representation to be easy to generate,and easy to translate into the target program.The representation can have a variety of forms,but a common one is called th
19、ree-address code or 4-tuple code.37谢谢观赏2019-8-17代码优化主要任务：对中间代码进行变换，使目标代码更为高效。（节省时间和空间）id1:=id2+id3*60(1)(inttoreal60-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)变换变换 （1）(*id360.0t1)(2）（+id2 t1id1)38谢谢观赏2019-8-17代码优化(code optimization)Intermediate code optimizationThe optimizer accepts input in the int
20、ermediate representation and output a version still in the intermediate representation.In this phase,the compiler attempts to produce the smallest,fastest and most efficient running result by applying various techniques.Object code optimization39谢谢观赏2019-8-17目标代码生成(*id360.0t1)(+id2t1id1)MOV id3,R2MU
21、L#60.0,R2MOV id2,R1ADDR2,R1MOV R1,id1主要任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。40谢谢观赏2019-8-17符号表管理 记录源程序中使用的名字 收集每个名字的各种属性信息 类型、作用域、分配存储信息名 字 种 类类 型层 次偏移量m过 程 0 a变 量 real1db变 量 real1d+4c变 量 real1d+841谢谢观赏2019-8-17符号表(symbol table)Symbol table is a data structure which is employed to as
22、sociate identifiers with their attributes.An identifiers attribute consists of information relevant to contextual analysis,and is obtained from the identifiers declaration.42谢谢观赏2019-8-17出错处理 编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。编译程序应报告出错地点，并给出简明准确的提示信息。43谢谢观赏2019-8-17出错处理(error handling)(error r
23、eporting and error recovery)The compiler should report the location of each error,together with some explanation.The major categories of compile-time error:syntax error,scope error,type error.After detecting and reporting an error,the compiler should attempt error recovery,means that the compiler sh
24、ould try to get itself into a state where analysis of the source program can continue as normally as possible.44谢谢观赏2019-8-17编译程序结构(components)词法分析程序 语法分析程序 语义分析程序 中间代码生成程序 代码优化程序 目标代码生成程序 符号表管理程序 出错处理程序45谢谢观赏2019-8-17出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理46谢谢观赏2019-8-17编译阶段的组合 前端和后端 源程序 中
25、间代码 目标代码 仅依赖源程序 仅依赖目标计算机 遍（PASS)：对输入文件（源程序或其等价的中间形式）从头到尾扫视，完成预定的处理。前端后端输入文件遍输出文件47谢谢观赏2019-8-17编译阶段的组合编译过程分为前端：词法分析、语法分析、语义分析、中间代码生成、优化工作。后端：目标代码生成、出错处理、符号表操作。一个编译程序可由一遍、两遍或多遍完成。每一遍可完成不同的阶段或多个阶段的工作。从时间和空间角度看多遍编译 少占内存，多耗时间一遍编译 多占内存，少耗时间主要与源语言有关主要与目标代码有关48谢谢观赏2019-8-17编译技术和软件工具用到编译原理与技术的常见软件工具：1、语言的结构化编辑器：提供关键字及其匹配的关键字。可减少语法错误，加快源程序调试。2、语言程序的调试工具 提供判定程序的算法与功能是否正确。3、程序格式化工具：使程序呈现清晰的结构4、语言程序的测试工具：49谢谢观赏2019-8-17测试工具静态分析器 对源程序进行语法分析动态测试器 测试用例、对程序进行动态测试。4、高级语言之间的转换工具：一种高级语言转化成另一种高级语言。50谢谢观赏2019-8-17编译技术和软件工具 实现方式 手工 机器语言 汇编语言 系统程序设计语言 自动构造工具lex yacc51谢谢观赏2019-8-17
