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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019-8-17,谢谢观赏,*,编译原理,任课教师：,信息科学技术学院计算语言所,什么是编译原理？,为什么要学习编译原理？,1,谢谢观赏,2019-8-17,编译原理1谢谢观赏2019-8-17,编译器的设计,一般的软件设计：,文本编辑器、自动排版、模式识别、程序自动验证、程序自动调试,为计算机分析和理解自然语言提供参考,2,谢谢观赏,2019-8-17,编译器的设计2谢谢观赏2019-8-17,编译原理,上课时间：周二上午,1-2,节 （单周）,周五上午,1-2,节,上课地点：一教,309,上机地点：中文系机房,学习方式：课堂讲解,+,课后作业,+,上机实践,考试成绩：试卷成绩,+,作业成绩,+,上机成绩,3,谢谢观赏,2019-8-17,编译原理上课时间：周二上午1-2节 （单周）3谢谢观赏201,参考教材,编译原理，清华大学出版社 张素琴、吕映芝 等编著，,2005,年,编译程序设计原理 北京大学出版社，杜淑敏等编著，,1986,年,陈火旺 刘春林等 程序设计语言编译原理 国防工业出版社，,2000,年,4,谢谢观赏,2019-8-17,参考教材编译原理，清华大学出版社 张素琴、吕映芝 等编著，,教学要求,掌握编译系统的一般构造原理,掌握编译系统的基本实现技术,熟悉一些自动构造工具,5,谢谢观赏,2019-8-17,教学要求掌握编译系统的一般构造原理5谢谢观赏2019-8-1,授课内容,第一章 编译程序概述,第二章,PL/0,编译程序的实现,第三章 文法和语言,第四章 词法分析,第五章 自顶向下语法分析方法,第六章 自底向上优先分析方法,第七章,LR,分析方法,第八章 语法制导翻译和中间代码生成,第九章 符号表,第一,章 代码优化,第一一章 代码生成,6,谢谢观赏,2019-8-17,授课内容第一章 编译程序概述6谢谢观赏2019-8-17,编译程序概述,什么是编译程序,编译过程和编译程序的结构,编译技术和软件工具的介绍,7,谢谢观赏,2019-8-17,编译程序概述什么是编译程序7谢谢观赏2019-8-17,过程式语言,Fortran,Pascal,C,函数式语言,Lisp,逻辑式语言,Prolog,对象式语言,C+,汇编语言,机器语言,程序设计语言：,用来编写计算机程序的语言。,程序设,计语言,高级语言,低级语言：面向机器的语言,什么是编译程序,8,谢谢观赏,2019-8-17,过程式语言 Fortran,Pascal,C程序设计语言,程序设计语言,机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。由二进制的指令代码组成。,1 + 3,表示为,10000001 00000001 00000011,是最底层的计算机语言，不需要翻译就可以直接被计算机硬件识别。对应不同的计算机硬件有不同的机器语言。,特点：执行速度快，但编写程序的难度大，修改、调试不方便，直观性差，不易移植。,9,谢谢观赏,2019-8-17,程序设计语言机器语言：直接用计算机能够识别的二进制代码指令来,程序设计语言,汇编语言：又称为符号语言。与机器语言一一对应，采用能帮助记忆的英文缩写符号（指令助记符）来代替机器语言指令中的操作码，用地址符号来代替地址码。用指令助记符及地址符号书写的指令称为汇编指令，用汇编指令编写的程序称为汇编语言源程序。,将,X,、,Y,中的内容相加 表示为,ADD X Y,机器不能直接识别汇编语言程序，必须把它翻译为机器语言程序才能执行。,特点：比机器语言直观，容易理解和记忆，比高级语言的执行效率高，但通用性和移植性较差。,10,谢谢观赏,2019-8-17,程序设计语言汇编语言：又称为符号语言。与机器语言一一对应，采,程序设计语言,高级语言：与具体的计算机硬件无关，是面向问题的程序设计语言，其表达方式接近于自然语言和数学语言，易于人们接受和掌握。,采用类似于数学公式的书写方式：,x,= 1 + 3,特点：独立于具体的计算机硬件，程序的编制和调试方便，通用性和可移植性好。在计算机执行之前，需要通过编译程序翻译成目标语言程序，或需要通过解释程序边解释，边执行。时间与空间效率比较低。,目前比较流行的高级语言有：,Visual C, Visual Basic, Java,，,FoxPro,，,Pascal,Lisp, Cobol,等。,11,谢谢观赏,2019-8-17,程序设计语言高级语言：与具体的计算机硬件无关，是面向问题的程,12,谢谢观赏,2019-8-17,12谢谢观赏2019-8-17,源程序,目标程序,可执行程序,编辑,程序,汇编或,编译程序,连接,程序,用于编写高级语言程序,把目标程序以及所需的功能库等转换成一个可执行的装入程序。完成此功能的程序叫连接程序。,编译方式是将高级语言编写的源程序整个地翻译成机器语言表示的目标程序的方式。完成此功能的程序叫编译程序。,13,谢谢观赏,2019-8-17,源程序目标程序可执行程序 编辑汇编或连接 用于编写高级语言程,什么是编译程序,编译程序的功能：把高级语言程序翻译成等价的低级语言程序。,源程序,编译程序,目标程序,编译程序是现代计算机系统的基本组成部分。,从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言,(,称作源语言,),书写的程序翻译成另一种语言,(,称作目标语言,),的等价的程序。,14,谢谢观赏,2019-8-17,什么是编译程序编译程序的功能：把高级语言程序翻译成等价的低级,编译和解释程序：,目标程序,源,程,序,编,译,程,序,初始数据,计,算,结,果,源程序,解,释,程,序,初始数据,计,算,结,果,15,谢谢观赏,2019-8-17,编译和解释程序：目标程序源编初始数据计源程序解初始数据计15,解释程序和编译程序的区别,解释程序和编译程序,的,根本区别,：,是否生成目标代码,16,谢谢观赏,2019-8-17,解释程序和编译程序的区别解释程序和编译程序的根本区别：16谢,编译程序概述,什么是编译程序,编译过程和编译程序的结构,编译技术和软件工具的介绍,17,谢谢观赏,2019-8-17,编译程序概述什么是编译程序17谢谢观赏2019-8-17,编译过程概述,编译器内部包括了许多步骤或称为阶段，它们执行不同的逻辑操作。将这些阶段设想为编译器中一个个单独的片断是很有用的，尽管在应用中它们是经常组合在一起的，但它们确实是作为单独的代码操作来编写的。,18,谢谢观赏,2019-8-17,编译过程概述编译器内部包括了许多步骤或称为阶段，它们执行不同,编译过程概述,编译工作的基本过程是：,词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等,6,个阶段。,每个阶段都有表格管理和出错处理部分。,19,谢谢观赏,2019-8-17,编译过程概述编译工作的基本过程是：19谢谢观赏2019-8-,词法分析,语法分析,语义分析,目标代码生成,中间代码生成,代码优化,目标程序,源程序,出 错 处 理,表 格 管 理,20,谢谢观赏,2019-8-17,词法分析语法分析语义分析目标代码生成中间代码生成代码优化目标,编译过程概述,机器翻译：让计算机翻译人类语言，例如：将汉语翻译为英文。,编译：让计算机翻译程序设计语言（人工语言），例如：将,C,语言编译为机器语言。,21,谢谢观赏,2019-8-17,编译过程概述机器翻译：让计算机翻译人类语言，例如：将汉语翻译,编译逻辑过程,词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成,22,谢谢观赏,2019-8-17,编译逻辑过程词法分析22谢谢观赏2019-8-17,词法分析,（自动分词,+,词性标注）,像翻译英文句子一样，先要分析单词，弄清各单词的意义和句中的作用，才能对句子进行翻译。,主要任务：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。,单词包括：保留字、标识符、运算符、分界符等。,例：,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,词法分析（自动分词+词性标注） position :=,又如一个,C,源程序片断：,int,a;,a = a + 2;,词法分析后可能返回,:,单词类型,单词值,保留字,int,标识符,(,变量名,),a,界符,;,标识符,(,变量名,),a,算符,(,赋值,) =,标识符,(,变量名,),a,算符,(,加,) +,整数,2,界符,；,25,谢谢观赏,2019-8-17,又如一个C源程序片断： int a;25谢谢观赏2019-8,有关术语,词法分析,(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.,单词,-token,保留字,-reserved word,标识符,-identifier(user-defined name),26,谢谢观赏,2019-8-17,有关术语词法分析(lexical analysis or s,语法分析,（自动句法分析）,语法分析程序与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。,主要任务：在词法分析的基础上，将单词分解成各类语法短语。,一般语法短语可表示成语法树。,功能,:,层次分析,.,依据,源程序的,语法规则,把源程序,的单词序列组成语法短语,(,表示成语法树,).,position := initial + rate * 60 ;,27,谢谢观赏,2019-8-17,语法分析（自动句法分析） 语法分析程序与自然语言中句子的语法,语法分析,（自动句法分析）,规则,:=“:=”,:=“+”,:=“*”,:=“(”“)”,:=,:=,:=,28,谢谢观赏,2019-8-17,语法分析（自动句法分析）规则28谢谢观赏2019-8-17,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,29,谢谢观赏,2019-8-17,赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:,id1:=id2+id3*N,:=,+,N 60,*,id1 Position,id2 initial,id3 rate,30,谢谢观赏,2019-8-17,id1:=id2+id3*N:=+N 60*id1 Pos,术语,语法分析,(syntax analysis or parsing),The purpose 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,tree),31,谢谢观赏,2019-8-17,术语语法分析(syntax analysis or pars,语义分析,语义审查,(,静态语义,),按照语法树的层次关系和先后次序，逐个语句地进行语义处理。,主要任务： 进行类型审查，审查每个算符是否符合语言规范，不符合时应报告错误。,类型匹配,类型转换,例,:Program p();,Var rate:real;,procedure initial;,position := initial + rate * 60,/* error */ /* error */ /* warning */;,32,谢谢观赏,2019-8-17,语义分析语义审查(静态语义)例:Program p();3,又如,:,Program p();,Var rate:real;,Var initial :real;,Var position :real ;,position := initial + rate * 60,33,谢谢观赏,2019-8-17,33谢谢观赏2019-8-17,语义分析,60,:=,+,*,Id1 position,Id2 initial,Id3 rate,inttoreal,34,谢谢观赏,2019-8-17,语义分析60:=+*Id1 positionId2 init,术语,语义分析,(semantic analysis),The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules, type rules,e.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration.,35,谢谢观赏,2019-8-17,术语语义分析(semantic analysis)35谢谢观,4,、中间代码生成：,如：,sum,：,first,count10,生成四元式序列：,（,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,4、中间代码生成： 如：sum：firstcount,中间代码生成,(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 three-address code or 4- tuple code.,37,谢谢观赏,2019-8-17,中间代码生成(intermediate code gener,代码优化,主要任务：对中间代码进行变换，使目标代码更为高效。（节省时间和空间）,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 optimization,The optimizer accepts input in the intermediate 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 optimization,39,谢谢观赏,2019-8-17,代码优化(code optimization)Interme,目标代码生成,(*id360.0t1),(+id2t1id1),MOVid3,R2,MUL#60.0,R2,MOVid2,R1,ADDR2,R1,MOVR1,id1,主要任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。,40,谢谢观赏,2019-8-17,目标代码生成(*id360.0t1)MOVid3,符号表管理,记录源程序中使用的名字,收集每个名字的各种属性信息,类型、作用域、分配存储信息,41,谢谢观赏,2019-8-17,符号表管理记录源程序中使用的名字41谢谢观赏2019-8-1,符号表,(symbol table),Symbol table is a data structure which is employed to associate 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,符号表(symbol table)Symbol table,出错处理,编译程序在各个阶段应,诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。,编译程序应,报告出错地点，并给出简明准确的提示信息。,43,谢谢观赏,2019-8-17,出错处理编译程序在各个阶段应诊断和报告源程序中的错误，包括,出错处理,(error handling)(error reporting 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 should try to get itself into a state where analysis of the source program can continue as normally as possible,.,44,谢谢观赏,2019-8-17,出错处理(error handling)(error rep,编译程序结构,(components),词法分析程序,语法分析程序,语义分析程序,中间代码生成程序,代码优化程序,目标代码生成程序,符号表管理程序,出错处理程序,45,谢谢观赏,2019-8-17,编译程序结构(components)词法分析程序45谢谢观赏,出,错,处,理,语法分析程序,语义分析程序,目标代码生成程序,词法分析程序,中间代码生成程序,代码优化程序,表,格,管,理,46,谢谢观赏,2019-8-17,出语法分析程序语义分析程序目标代码生成程序词法分析程序中间代,编译阶段的组合,前端和后端,源程序 中间代码 目标代码,仅依赖源程序 仅依赖目标计算机,遍（,PASS),：,对输入文件（源程序或其等价的中间形式）从头到尾扫视，完成预定的处理。,前端,后端,输入文件,遍,输出文件,47,谢谢观赏,2019-8-17,编译阶段的组合前端和后端,编译阶段的组合,编译过程分为,前端：词法分析、语法分析、语义分析、中间代码生成、优化工作。,后端：目标代码生成、出错处理、符号表操作。,一个编译程序可由一遍、两遍或多遍完成。每一遍可完成不同的阶段或多个阶段的工作。,从时间和空,间角度看,多遍编译,少占内存，多耗时间,一遍编译,多占内存，少耗时间,主要与源语言有关,主要与目标代码有关,48,谢谢观赏,2019-8-17,编译阶段的组合编译过程分为前端：词法分析、语法分析、语义分析,编译技术和软件工具,用到编译原理与技术的常见软件工具：,1,、语言的结构化编辑器：,提供关键字及其匹配的关键字。,可减少语法错误，加快源程序调试。,2,、语言程序的调试工具,提供判定程序的算法与功能是否正确。,3,、程序格式化工具：使程序呈现清晰的结构,4,、语言程序的测试工具：,49,谢谢观赏,2019-8-17,编译技术和软件工具用到编译原理与技术的常见软件工具：49谢谢,测试工具,静态分析器,对源程序进行语法分析,动态测试器,测试用例、对程序进行动态测试。,4,、高级语言之间的转换工具：,一种高级语言转化成另一种高级语言。,50,谢谢观赏,2019-8-17,测试工具静态分析器 对源程序进行语法分析4、高级语言之间,编译技术和软件工具,实现方式,手工,机器语言,汇编语言,系统程序设计语言,自动构造工具,lex yacc,51,谢谢观赏,2019-8-17,编译技术和软件工具实现方式51谢谢观赏2019-8-17,