信息科学技术学院计算语言课件.ppt

《信息科学技术学院计算语言课件.ppt》由会员分享，可在线阅读，更多相关《信息科学技术学院计算语言课件.ppt（51页珍藏版）》请在三一办公上搜索。

1、编译原理,任课教师：信息科学技术学院计算语言所什么是编译原理？为什么要学习编译原理？,1,谢谢观赏,2019-8-17,编译器的设计一般的软件设计：文本编辑器、自动排版、模式识别、程序自动验证、程序自动调试为计算机分析和理解自然语言提供参考,2,谢谢观赏,2019-8-17,编译原理,上课时间：周二上午1-2节 （单周） 周五上午1-2节上课地点：一教309上机地点：中文系机房学习方式：课堂讲解+课后作业+上机实践考试成绩：试卷成绩+作业成绩+上机成绩,3,谢谢观赏,2019-8-17,参考教材,编译原理，清华大学出版社 张素琴、吕映芝 等编著，2005年编译程序设计原理 北京大学出版社，杜淑

2、敏等编著，1986年陈火旺 刘春林等 程序设计语言编译原理 国防工业出版社，2000年,4,谢谢观赏,2019-8-17,教学要求,掌握编译系统的一般构造原理掌握编译系统的基本实现技术熟悉一些自动构造工具,5,谢谢观赏,2019-8-17,授课内容,第一章 编译程序概述第二章 PL/0编译程序的实现第三章 文法和语言第四章 词法分析第五章 自顶向下语法分析方法第六章 自底向上优先分析方法第七章 LR分析方法第八章 语法制导翻译和中间代码生成第九章 符号表第一章 代码优化第一一章 代码生成,6,谢谢观赏,2019-8-17,编译程序概述,什么是编译程序编译过程和编译程序的结构编译技术和软件工具的

3、介绍,7,谢谢观赏,2019-8-17,过程式语言 Fortran,Pascal,C函数式语言 Lisp逻辑式语言 Prolog对象式语言 C+汇编语言机器语言,程序设计语言：用来编写计算机程序的语言。,程序设计语言,高级语言低级语言：面向机器的语言,什么是编译程序,8,谢谢观赏,2019-8-17,程序设计语言,机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。由二进制的指令代码组成。1 + 3 表示为 10000001 00000001 00000011是最底层的计算机语言，不需要翻译就可以直接被计算机硬件识别。对应不同的计算机硬件有不同的机器语言。 特点：执行速度快，但编写

4、程序的难度大，修改、调试不方便，直观性差，不易移植。,9,谢谢观赏,2019-8-17,程序设计语言,汇编语言：又称为符号语言。与机器语言一一对应，采用能帮助记忆的英文缩写符号（指令助记符）来代替机器语言指令中的操作码，用地址符号来代替地址码。用指令助记符及地址符号书写的指令称为汇编指令，用汇编指令编写的程序称为汇编语言源程序。将X、Y中的内容相加 表示为 ADD X Y机器不能直接识别汇编语言程序，必须把它翻译为机器语言程序才能执行。 特点：比机器语言直观，容易理解和记忆，比高级语言的执行效率高，但通用性和移植性较差。,10,谢谢观赏,2019-8-17,程序设计语言,高级语言：与具体的计算

5、机硬件无关，是面向问题的程序设计语言，其表达方式接近于自然语言和数学语言，易于人们接受和掌握。 采用类似于数学公式的书写方式：x = 1 + 3特点：独立于具体的计算机硬件，程序的编制和调试方便，通用性和可移植性好。在计算机执行之前，需要通过编译程序翻译成目标语言程序，或需要通过解释程序边解释，边执行。时间与空间效率比较低。 目前比较流行的高级语言有：Visual C, Visual Basic, Java，FoxPro，Pascal,Lisp, Cobol等。,11,谢谢观赏,2019-8-17,12,谢谢观赏,2019-8-17,源程序,目标程序,可执行程序,编辑 程序,汇编或编译程序,连

6、接 程序,用于编写高级语言程序,把目标程序以及所需的功能库等转换成一个可执行的装入程序。完成此功能的程序叫连接程序。,13,谢谢观赏,2019-8-17,什么是编译程序,编译程序的功能：把高级语言程序翻译成等价的低级语言程序。源程序编译程序目标程序编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。,14,谢谢观赏,2019-8-17,编译和解释程序：,15,谢谢观赏,2019-8-17,解释程序和编译程序的区别,解释程序和编译程序的根本区别：是否生成目标代码,16,谢谢观赏,2

7、019-8-17,编译程序概述,什么是编译程序编译过程和编译程序的结构编译技术和软件工具的介绍,17,谢谢观赏,2019-8-17,编译过程概述,编译器内部包括了许多步骤或称为阶段，它们执行不同的逻辑操作。将这些阶段设想为编译器中一个个单独的片断是很有用的，尽管在应用中它们是经常组合在一起的，但它们确实是作为单独的代码操作来编写的。,18,谢谢观赏,2019-8-17,编译过程概述,编译工作的基本过程是：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等6个阶段。每个阶段都有表格管理和出错处理部分。,19,谢谢观赏,2019-8-17,词法分析,语法分析,语义分析,目标代码生

8、成,中间代码生成,代码优化,目标程序,源程序,出 错 处 理,表 格 管 理,20,谢谢观赏,2019-8-17,编译过程概述,机器翻译：让计算机翻译人类语言，例如：将汉语翻译为英文。编译：让计算机翻译程序设计语言（人工语言），例如：将C语言编译为机器语言。,21,谢谢观赏,2019-8-17,编译逻辑过程,词法分析语法分析语义分析中间代码生成代码优化目标代码生成,22,谢谢观赏,2019-8-17,词法分析（自动分词+词性标注）,像翻译英文句子一样，先要分析单词，弄清各单词的意义和句中的作用，才能对句子进行翻译。主要任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分

9、解，从而识别出一个个单词。 单词包括：保留字、标识符、运算符、分界符等。例： position := initial + rate * 60;,23,谢谢观赏,2019-8-17,词法分析（自动分词+词性标注） position := initial + rate * 60;,单词类型单词值 标识符1(id1) position 算符(赋值) := 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 界符 ；,24,谢谢观赏,2019-8-17,又如一个C源程序片断： int a; a = a + 2;词法分析后可能返回:单词类型单词值

10、 保留字 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 right and grouped into tokens,which are sequences of characters that have a collective meaning.单词-tok

11、en保留字-reserved word标识符 -identifier(user-defined name),26,谢谢观赏,2019-8-17,语法分析（自动句法分析）,语法分析程序与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。主要任务：在词法分析的基础上，将单词分解成各类语法短语。 一般语法短语可表示成语法树。功能:层次分析.依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).position := initial + rate * 60 ;,27,谢谢观赏,2019-8-17,语法分析（自动句法分析）,规则

12、:=“:=” :=“+” :=“*” :=“(”“)” := := :=,28,谢谢观赏,2019-8-17,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,29,谢谢观赏,2019-8-17,id1:=id2+id3*N,30,谢谢观赏,2019-8-17,术语,语法分析(syntax analysis or parsing)The purpose of syntax analysis is to determine the source programs phrase structure.This process is also called

13、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 tree),31,谢谢观赏,2019-8-17,语义分析,语义审查(静态语义)按照语法树的层次关系和先后次序，逐个语句地进行语义处理。主要任务： 进行类型审查，审查每个算符是否符合语言规范，不符合时应报告

14、错误。类型匹配类型转换,例: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 := initial + rate * 60,33,谢谢观赏,2019-8-17,语义分析,34,谢谢观赏,2019-8-17,术语,语义分析(s

15、emantic 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 an identifier in the source program to the corresponding declaration.,35,谢谢观赏,2019-8-17,4、中间代码生成：,

16、如：sum：firstcount10 生成四元式序列：（inttoreal 10 t1 ） （ id3 t1 t2） （ id2 t2 t3） （： t3 id1）,运算符,运算对象1,运算对象2,结果,语法分析和语义分析之后，有时将源程序变成一种内部表示形式，这种内部表示形式叫中间代码，该代码是一种简单的记号系统。三元式、四元式等四元式的形式为： （算符，运算对象1，运算对象2，结果）,id1,id2,id3,t1，t2，t3是临时变量,36,谢谢观赏,2019-8-17,中间代码生成(intermediate code generation),This is where the inter

17、mediate 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 three-address code or 4- tuple code.,37,谢谢观赏,2019-8-17,代码优化,主要任务：对中间代码进行变

18、换，使目标代码更为高效。（节省时间和空间） 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 intermediate representation and output a version

19、 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 optimization,39,谢谢观赏,2019-8-17,目标代码生成,(*id360.0t1)(+id2t1id1),MOVid3,R2MUL#60.0,R2MOVid2,R1ADDR2,R1MOVR1,id1,主要任

20、务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。,40,谢谢观赏,2019-8-17,符号表管理,记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息,41,谢谢观赏,2019-8-17,符号表(symbol table),Symbol table is a data structure which is employed to associate identifiers with their attributes .An identifiers attribute consists of information r

21、elevant to contextual analysis,and is obtained from the identifiers declaration.,42,谢谢观赏,2019-8-17,出错处理,编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。编译程序应报告出错地点，并给出简明准确的提示信息。,43,谢谢观赏,2019-8-17,出错处理(error handling)(error reporting and error recovery),The compiler should report the location of each error,t

22、ogether 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 should try to get itself into a state where analysis of the source program can co

23、ntinue as normally as possible.,44,谢谢观赏,2019-8-17,编译程序结构(components),词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序,45,谢谢观赏,2019-8-17,出错处理,表格管理,46,谢谢观赏,2019-8-17,编译阶段的组合,前端和后端 源程序 中间代码 目标代码 仅依赖源程序 仅依赖目标计算机遍（PASS)： 对输入文件（源程序或其等价的中间形式）从头到尾扫视，完成预定的处理。,前端,后端,输入文件,遍,输出文件,47,谢谢观赏,2019-8-17,编译阶段的组合,

24、编译过程分为,前端：词法分析、语法分析、语义分析、中间代码生成、优化工作。后端：目标代码生成、出错处理、符号表操作。,一个编译程序可由一遍、两遍或多遍完成。每一遍可完成不同的阶段或多个阶段的工作。,从时间和空间角度看,多遍编译 少占内存，多耗时间一遍编译 多占内存，少耗时间,主要与源语言有关,主要与目标代码有关,48,谢谢观赏,2019-8-17,编译技术和软件工具,用到编译原理与技术的常见软件工具：1、语言的结构化编辑器： 提供关键字及其匹配的关键字。 可减少语法错误，加快源程序调试。2、语言程序的调试工具 提供判定程序的算法与功能是否正确。3、程序格式化工具：使程序呈现清晰的结构4、语言程序的测试工具：,49,谢谢观赏,2019-8-17,测试工具,静态分析器 对源程序进行语法分析动态测试器 测试用例、对程序进行动态测试。,4、高级语言之间的转换工具：一种高级语言转化成另一种高级语言。,50,谢谢观赏,2019-8-17,编译技术和软件工具,实现方式手工机器语言汇编语言系统程序设计语言自动构造工具lex yacc,51,谢谢观赏,2019-8-17,