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

编译原理任课教师：信息科学技术学院计算语言所什么是编译原理？为什么要学习编译原理？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/0PL/0编译程序的实现编译程序的实现第三章第三章 文法和语言文法和语言第四章第四章 词法分析词法分析第五章第五章 自顶向下语法分析方法自顶向下语法分析方法第六章第六章 自底向上优先分析方法自底向上优先分析方法第七章第七章 LRLR分析方法分析方法第八章第八章 语法制导翻译和中间代码生成语法制导翻译和中间代码生成第九章第九章 符号表符号表第一第一章章 代码优化代码优化第一一章第一一章 代码生成代码生成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-1712谢谢观赏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 Positionid2 initialid3 rate30谢谢观赏2019-8-17id1:=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*6033谢谢观赏2019-8-1733谢谢观赏2019-8-17语义分析60:=+*Id1 positionId2 initialId3 rateinttoreal34谢谢观赏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 rulese.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：firstcount10 生成四元式序列：（inttoreal 10 t1）（id3 t1 t2）（id2 t2 t3）（：t3 id1）运算符运算对象1运算对象2结果语法分析和语义分析之后，有时将源程序变成一种内部表示形式，这种内部表示形式叫中间代码，该代码是一种简单的记号系统。三元式、四元式等四元式的形式为：（算符，运算对象1，运算对象2，结果）id1id2id3t1，t2，t3是临时变量36谢谢观赏2019-8-174、中间代码生成：如：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 optimizationThe 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 optimization39谢谢观赏2019-8-17代码优化(code optimization)Interme目标代码生成(*id360.0t1)(+id2t1id1)MOV id3,R2MUL#60.0,R2MOV id2,R1ADDR2,R1MOV R1,id1主要任务：将中间代码变换成特定机器上的绝对指令代码或可重定位的汇编指令代码。主要与硬件系统结构和指令含义有关。40谢谢观赏2019-8-17目标代码生成(*id3 60.0t1)MOV id3,符号表管理记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息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 yacc51谢谢观赏2019-8-17编译技术和软件工具实现方式51谢谢观赏2019-8-17