第1章-编译概述.ppt

高级语言汇编语言SOURCE PROGRAMAssemble PROGRAM？翻译程序？翻译程序？TRANSLATER 为什么要学习编译原理为什么要学习编译原理程序设计语言是计算机软件专业的重要核心程序设计语言是计算机软件专业的重要核心学习编程的历程：学习编程的历程：C C语言汇编语言数据结构语言汇编语言数据结构 北京林业大学信息学院北京林业大学信息学院为什么要学习编译原理为什么要学习编译原理必修主干课程必修主干课程，操作系统和编译系统构成程序，操作系统和编译系统构成程序设计者与计算机之间的基本界面。设计者与计算机之间的基本界面。通过学习该课程，掌握编译的基本理论、常用通过学习该课程，掌握编译的基本理论、常用的编译技术，了解编译过程及编译系统结构和的编译技术，了解编译过程及编译系统结构和机理。能运用所学技术解决实际问题，能机理。能运用所学技术解决实际问题，能独立独立编写一个小型编译系统编写一个小型编译系统。此外，通过学习编译原理可以更好地理解程序此外，通过学习编译原理可以更好地理解程序语言的内部机制语言的内部机制,从而更好地理解和运用程序从而更好地理解和运用程序设计语言。能运用编译程序构造的原理和技术设计语言。能运用编译程序构造的原理和技术完成完成相关软件工具的设计和开发相关软件工具的设计和开发工作。工作。北京林业大学信息学院北京林业大学信息学院为什么要学习编译原理为什么要学习编译原理计算机软件学科计算机软件学科理论与实践相结合理论与实践相结合的典范。的典范。在学习过程中既要注重该领域在理论上取得在学习过程中既要注重该领域在理论上取得的完美结论，也要注重这些理论在实际中的的完美结论，也要注重这些理论在实际中的应用。应用。北京林业大学信息学院北京林业大学信息学院先修课程先修课程要求先学习以下课程要求先学习以下课程1.程序设计语言程序设计语言2.算法与数据结构算法与数据结构：栈分配、堆分配、静态分配等各：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。种数据结构。3.离散数学离散数学：集合论与数理逻辑是进一步学习形式语：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。言与自动机理论的数学基础。最好学习过或同时学习以下课程最好学习过或同时学习以下课程1.软件工程软件工程：掌握大型程序设计以及工程化的软件生：掌握大型程序设计以及工程化的软件生产方法。产方法。2.形式语言与自动机形式语言与自动机：相当于本课程中词法分析与语：相当于本课程中词法分析与语法分析的理论基础。法分析的理论基础。北京林业大学信息学院北京林业大学信息学院李冬梅，施海虎，李冬梅，施海虎，编译原理编译原理，人民邮电出版社，人民邮电出版社教材教材参考书参考书李建中译，李建中译，编译原理编译原理（龙书龙书），机械工业出版社，机械工业出版社陈火旺陈火旺 刘春林等，刘春林等，程序设计语言编译原理程序设计语言编译原理，国，国防工业出版社防工业出版社吕映芝，张素琴等，吕映芝，张素琴等，编译原理编译原理，清华大学出版社，清华大学出版社 北京林业大学信息学院北京林业大学信息学院要求及学习方法要求及学习方法平时（平时（30%30%）无故旷课：无故旷课：一本教材，一本教材，认真听课认真听课：以讲义为主，板书为：以讲义为主，板书为辅辅-做适当的笔记做适当的笔记认真完成课堂和课后认真完成课堂和课后作业作业完成要求的完成要求的课外实验课外实验内容内容期末（期末（70%70%）:闭卷笔试闭卷笔试课程特点：理论性强，算法复杂课程特点：理论性强，算法复杂 北京林业大学信息学院北京林业大学信息学院第第1 1章章编译概述编译概述1.1.掌握编译程序中所涉及的有关名词术语掌握编译程序中所涉及的有关名词术语2.2.理解编译程序总的框架，明确编译程序工理解编译程序总的框架，明确编译程序工作的基本过程及各阶段的基本任务作的基本过程及各阶段的基本任务教学目标教学目标 北京林业大学信息学院北京林业大学信息学院1.1.程序的翻译程序的翻译1.2.编译程序的组成编译程序的组成1.3.编译程序构造编译程序构造 1.4.编译技术的应用及发展编译技术的应用及发展教学内容教学内容 北京林业大学信息学院北京林业大学信息学院低级语言低级语言（LowlevelLanguage)字位码、机器语言、汇编语言字位码、机器语言、汇编语言特特点点：与与特特定定的的机机器器有有关关，功功效效高高，但但使使用用复复杂杂、繁繁琐、费时、易出错琐、费时、易出错高级语言高级语言-Fortran、Pascal、C语言等语言等特点：不依赖具体机器，移植性好、对用户要求低、特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。易使用、易维护等。1.11.1程序的翻译程序的翻译 北京林业大学信息学院北京林业大学信息学院源程序源程序 用汇编语言或高级语言编写的程序称为源程序用汇编语言或高级语言编写的程序称为源程序目标程序目标程序 用用目标语言目标语言所表示的程序所表示的程序 目标语言：可以是介于源语言和机器语言之间的目标语言：可以是介于源语言和机器语言之间的“中间中间语言语言”，可以是某种机器的机器语言，可以是某种机器的机器语言,也可以是某机器的汇也可以是某机器的汇编语言。编语言。翻译程序翻译程序将将源程序源程序转换为转换为目标程序目标程序的程序称为翻译程序。它是的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。程序、编译程序以及各种变换程序的总称。北京林业大学信息学院北京林业大学信息学院源程序、翻译程序、目标程序源程序、翻译程序、目标程序三者关系：三者关系：源程序源程序翻译程序翻译程序目标程序目标程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM即源程序是翻译程序的输入，目标程序是翻译程序的输出即源程序是翻译程序的输入，目标程序是翻译程序的输出SOI 北京林业大学信息学院北京林业大学信息学院汇编程序汇编程序若源程序用汇编语言书写，经过翻译程序得到用机器语言若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为程称为“汇编汇编”(Assemble）编译程序编译程序若源程序是用高级语言书写，经加工后得到目标程序，上述若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称翻译过程称“编译编译”（Compile)汇编程序与编译程序都是汇编程序与编译程序都是翻译程序翻译程序，主要区别是加工对象的，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多应的关系。汇编程序所要做的翻译工作比编译程序简单的多。北京林业大学信息学院北京林业大学信息学院源程序的编译和运行源程序的编译和运行编译或汇编阶段编译或汇编阶段运行阶段运行阶段源程序源程序目标程序目标程序编译程序编译程序或汇编程序或汇编程序输出数据输出数据目标程序目标程序+运行子程序运行子程序输入数据输入数据 北京林业大学信息学院北京林业大学信息学院工作过程工作过程解释程序（解释程序（Interpreter）（类似于口译，不生成目标代码）（类似于口译，不生成目标代码）对源程序进行解释执行的程序。对源程序进行解释执行的程序。输出数据输出数据解释程序解释程序输入数据输入数据源程序源程序 特点：与编译系统比较，解释系统较简单、特点：与编译系统比较，解释系统较简单、可移植性好，易于查错，但速度慢可移植性好，易于查错，但速度慢 北京林业大学信息学院北京林业大学信息学院“编译编译-解释执行解释执行”系统系统源程序源程序编译程序编译程序源程序的中间形式源程序的中间形式输出数据输出数据解释程序解释程序输入数据输入数据 北京林业大学信息学院北京林业大学信息学院.java java源程序文件.class 二进制字节码文件编译例例如如JavaJava语言语言 北京林业大学信息学院北京林业大学信息学院 所谓编译过程是指将所谓编译过程是指将高级语言程序高级语言程序翻译为等价的翻译为等价的目标目标程序程序的过程。的过程。翻译外文资料：翻译外文资料：1、能识别出句子中的一个单词；、能识别出句子中的一个单词；2、分析句子的语法结构；、分析句子的语法结构；3、根据句子的含义进行初步翻译；、根据句子的含义进行初步翻译；4、对译文进行修饰；、对译文进行修饰；5、写出最后的译文。、写出最后的译文。1.21.2编译程序的组成编译程序的组成 北京林业大学信息学院北京林业大学信息学院翻译和编译工作的比较翻译和编译工作的比较翻译外文翻译外文编译程序编译程序分析分析识别单词识别单词分析句子分析句子根据语义进根据语义进行初步翻译行初步翻译词法分析词法分析语法分析语法分析语义分析、生成中间代码语义分析、生成中间代码综合综合修辞加工修辞加工写出译文写出译文代码优化代码优化目标代码生成目标代码生成编译过程编译过程 北京林业大学信息学院北京林业大学信息学院词法分析词法分析语法分析语法分析语义分析及中间代码生成语义分析及中间代码生成代码优化代码优化目标代码生成目标代码生成习惯上是将编译过程划分为习惯上是将编译过程划分为5 5个基本阶段：个基本阶段：编译过程编译过程 北京林业大学信息学院北京林业大学信息学院单词单词：是语言的基本语法单位 保留字保留字（如:if、else、while）标识符标识符（如:max、min、str）常数常数 （如:12、6.8、a）分界符分界符（如:+、-、*、/、;、（、）字符序列字符序列任务：任务：根据根据词法规则词法规则分析和识别单词单词一、词法分析一、词法分析编码形式编码形式 北京林业大学信息学院北京林业大学信息学院词法分析程序的结果词法分析程序的结果-二元式二元式y=x+r*6单词值单词值单词类别单词类别y标识符标识符=分界符（赋值）分界符（赋值）x标识符标识符+分界符（加号）分界符（加号）r标识符标识符*分界符（乘号）分界符（乘号）6常数常数 北京林业大学信息学院北京林业大学信息学院有关术语有关术语词法分析词法分析(lexical analysis or scanning)(lexical analysis or scanning)-The stream of characters making up a-The stream of characters making up a source program is read from left to right source program is read from left to right and grouped into tokens,which are and grouped into tokens,which are sequences of characters that have a sequences of characters that have a collective meaning.collective meaning.单词单词-token-token保留字保留字-reserved word-reserved word标识符标识符 -identifier(user-defined name)-identifier(user-defined name)北京林业大学信息学院北京林业大学信息学院任务：任务：根据根据语法规则语法规则（即语言的文法），分析并识（即语言的文法），分析并识别出各种别出各种语法成分语法成分（如表达式、语句、函数等），（如表达式、语句、函数等），并进行并进行语法正确性检查语法正确性检查。二二、语法分语法分析（编译程序的核心）析（编译程序的核心）文法文法:=:=“=”:=:=“+”|“*”:=:=“(”“)”|北京林业大学信息学院北京林业大学信息学院赋值语句赋值语句标识符标识符标识符标识符整数整数标识符标识符表达式表达式=yx表达式表达式表达式表达式+r6表达式表达式表达式表达式*:=:=“=”:=:=“+”|“*”:=:=“(”“)”|y =x+r*6 北京林业大学信息学院北京林业大学信息学院赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6语语法法分分析析的的结结果果-语语法法树树 北京林业大学信息学院北京林业大学信息学院有关术语有关术语语法分析语法分析(syntaxanalysisorparsing)Thepurposeofsyntaxanalysisistodeterminethesourceprogramsphrasestructure.Thisprocessisalsocalledparsing.Thesourceprogramisparsedtocheckwhetheritconformstothesourcelanguagessyntax,andtoconstructasuitablerepresentationofitsphrasestructure.北京林业大学信息学院北京林业大学信息学院任务：任务：依据语义规则对识别出的各种语法成依据语义规则对识别出的各种语法成分析其分析其含义含义，并进行初步翻译，生成，并进行初步翻译，生成中间代码中间代码。三、语义分析及中间代码生成三、语义分析及中间代码生成静态：静态：分析语法成份的含义，进行语义上的正确性检查分析语法成份的含义，进行语义上的正确性检查动态：动态：根据相应语义，生成根据相应语义，生成中间代码（中间代码（介于源语言和目标介于源语言和目标语言之间的中间语言形式）语言之间的中间语言形式）北京林业大学信息学院北京林业大学信息学院生成中间代码的目的：生成中间代码的目的：1、利于代码优化、利于代码优化2、利于目标代码的移植、利于目标代码的移植中间代码的形式：中间代码的形式：四元式、三元式、逆波兰表示四元式、三元式、逆波兰表示 北京林业大学信息学院北京林业大学信息学院四元式四元式其中t1、t2、t3为编译程序引入的临时工作单元例：y =x+r*6运算符左运算对象 右运算对象 结果(1)inttoreal 6-t1(2)*rt1t2(3)+t2xt3(4)=t3y 北京林业大学信息学院北京林业大学信息学院有关术语有关术语语义分析语义分析(semanticanalysis)Theparsedprogramisfurtheranalyzedtodeterminewhetheritconformstothesourcelanguagescontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.北京林业大学信息学院北京林业大学信息学院有关术语有关术语中间代码生成中间代码生成(intermediatecodegeneration)Thisiswheretheintermediaterepresentationofthesourceprogramiscreated.Wewantthisrepresentationtobeeasytogenerate,andeasytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.北京林业大学信息学院北京林业大学信息学院任务：任务：对中间代码进行加工变换加工变换，以得到高质量的目标代码四、代码优化四、代码优化运算符左运算对象 右运算对象 结果(1)Inttoreal6-t1(2)*rt1t2(3)+t2xt3(4)=t3y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xy(1)inttoreal6-t1(4)=t3y例：y =x+r*6 北京林业大学信息学院北京林业大学信息学院有关术语有关术语代码优化代码优化(Intermediatecodeoptimization)Theoptimizeracceptsinputintheintermediaterepresentationandoutputaversionstillintheintermediaterepresentation.Inthisphase,thecompilerattemptstoproducethesmallest,fastestandmostefficientrunningresultbyapplyingvarioustechniques.北京林业大学信息学院北京林业大学信息学院五、目标代码生成五、目标代码生成任务：任务：把中间代码变换成特定机器上的低级语言代码低级语言代码movr,R1mul#6.0,R1movx,R2addR1,R2movR2,y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xy 北京林业大学信息学院北京林业大学信息学院目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序编译过程小结编译过程小结S.PO.P 北京林业大学信息学院北京林业大学信息学院按逻辑功能不同，可将编译过程划分为五个基本阶按逻辑功能不同，可将编译过程划分为五个基本阶段，与此相对应，我们将实现整个编译过程的编译程序划段，与此相对应，我们将实现整个编译过程的编译程序划分为五个逻辑阶段（即五个逻辑子过程）。分为五个逻辑阶段（即五个逻辑子过程）。每个阶段中都要有：符号表管理符号表管理和错误处理错误处理 北京林业大学信息学院北京林业大学信息学院诊察错误，并能报告用户错误性质和位置诊察错误，并能报告用户错误性质和位置错误处理能力的优劣是衡量编译程序质量好坏的错误处理能力的优劣是衡量编译程序质量好坏的一个重要指标。一个重要指标。填表：把源程序中的信息和编译过程中所产生的填表：把源程序中的信息和编译过程中所产生的信息登记在表格中信息登记在表格中查表：在随后的编译过程中同时又要不断的查找查表：在随后的编译过程中同时又要不断的查找这些表格中的信息这些表格中的信息符号表管理符号表管理错误处理错误处理编译程序的逻辑结构编译程序的逻辑结构 北京林业大学信息学院北京林业大学信息学院典型的编译程序具有典型的编译程序具有7个逻辑部分个逻辑部分S.PO.P语义分析及语义分析及生成中间代码生成中间代码程序程序代码生成程序代码生成程序代码优化代码优化程序程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理 北京林业大学信息学院北京林业大学信息学院根据编译程序各部分功能，将编译程序分成根据编译程序各部分功能，将编译程序分成前端前端和和后端后端 前端前端：通常将与：通常将与源程序源程序有关的编译部分称为前端。有关的编译部分称为前端。词法分析、语法分析、语义分析、中间代码生成词法分析、语法分析、语义分析、中间代码生成 -分析部分分析部分 特点：与特点：与源语言源语言有关有关 后端后端：与：与目标机目标机有关的部分称为后端。有关的部分称为后端。代码优化、代码生成代码优化、代码生成-综合部分综合部分 特点：与特点：与目标机目标机有关有关编译程序的前端和后端编译程序的前端和后端 北京林业大学信息学院北京林业大学信息学院.java java源程序文件.class 二进制字节码文件编译同一前端同一前端+不同后端不同后端 不同机器构成同一语言的编译程序不同机器构成同一语言的编译程序例例如如JavaJava语言语言 北京林业大学信息学院北京林业大学信息学院 同一前端同一前端+不同后端不同后端 不同机器构成同一语言的编译程序不同机器构成同一语言的编译程序例例如如.NET.NET框架框架 北京林业大学信息学院北京林业大学信息学院 不同前端不同前端+同一后端同一后端 同一机器生成几个语言的编译程序同一机器生成几个语言的编译程序例例如如GCCGCC 北京林业大学信息学院北京林业大学信息学院第一遍第一遍第二遍第二遍S.P中间形式中间形式1S.P中间形式中间形式2C2C1S.PO.P上一遍的结果是下一遍的输入，最后一遍生成目标程序。上一遍的结果是下一遍的输入，最后一遍生成目标程序。对源程序（包括源程序中间形式）从头到尾扫描对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理一次，并做有关的加工处理，生成新的源程序中，生成新的源程序中间形式或目标程序，通常称之为一间形式或目标程序，通常称之为一遍遍。遍遍 北京林业大学信息学院北京林业大学信息学院一遍扫描即可完成整个编译工作的称为一遍扫描即可完成整个编译工作的称为一遍扫描编译程序一遍扫描编译程序遍的划分视具体情况而定（内存的大小、源语言的繁简、遍的划分视具体情况而定（内存的大小、源语言的繁简、目标程序质量的高低）目标程序质量的高低）优点优点：1 1、减少对内存容量的要求、减少对内存容量的要求2 2、编译程序结构清晰、各遍功能独立、相互联系简单、编译程序结构清晰、各遍功能独立、相互联系简单缺点缺点：增加读写中间文件的次数，降低效率增加读写中间文件的次数，降低效率 北京林业大学信息学院北京林业大学信息学院构造编译程序必须精通构造编译程序必须精通:源源语语言言目标语言目标语言编译方法编译方法1.31.3编译程序的构造编译程序的构造 北京林业大学信息学院北京林业大学信息学院开发编译程序的途径开发编译程序的途径:自展法自展法工具法工具法自动生成法自动生成法移植法移植法 北京林业大学信息学院北京林业大学信息学院自展法自展法 北京林业大学信息学院北京林业大学信息学院应用：应用：大部分软件工具的开发，都要使用大部分软件工具的开发，都要使用编译技术和方法编译技术和方法语法制导的结构化编辑器语法制导的结构化编辑器程序格式化工具程序格式化工具软件测试工具软件测试工具静态分析器：不可能执行的代码、定义后未引用的变量静态分析器：不可能执行的代码、定义后未引用的变量动态测试工具：运行后与期望结果比较动态测试工具：运行后与期望结果比较程序理解工具：确定调用关系，画出流程图程序理解工具：确定调用关系，画出流程图高级语言的翻译工具高级语言的翻译工具1.41.4编译技术的应用及发展编译技术的应用及发展 北京林业大学信息学院北京林业大学信息学院其它应用：其它应用：v文本编辑器文本编辑器v信息检索系统信息检索系统v模式识别器模式识别器v排版、绘图系统排版、绘图系统 北京林业大学信息学院北京林业大学信息学院并行编译技术并行编译技术目的：提高并行计算机体系结构的性能，超目的：提高并行计算机体系结构的性能，超大规模计算的日益增长的需求大规模计算的日益增长的需求两种实现方法两种实现方法利用重构技术将串行程序并行化利用重构技术将串行程序并行化直接编写并行程序直接编写并行程序交叉编译技术交叉编译技术发展发展 北京林业大学信息学院北京林业大学信息学院交叉编译器由于目标机指令系统与宿主机的指令系统不同，编译由于目标机指令系统与宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，时将应用程序的源程序在宿主机上生成目标机代码，称为称为交叉编译交叉编译。SOIOAB 北京林业大学信息学院北京林业大学信息学院q语言开发环境中的伙伴程序语言开发环境中的伙伴程序编辑器（编辑器（editor）预处理器（预处理器（preprocessor）连接程序（连接程序（linker）装配程序（装配程序（loader）调试程序（调试程序（debugger）北京林业大学信息学院北京林业大学信息学院小结小结内容内容1 1 什么是编译程序什么是编译程序2 2 编译过程和编译程序的结构编译过程和编译程序的结构3 3 为什么要学习编译程序为什么要学习编译程序重点重点对编译程序的功能和结构做一综述对编译程序的功能和结构做一综述难点难点了解编译程序各个成分在编译阶段的逻辑关系了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的以及他们怎样作为一个整体完成编译任务的小结小结 北京林业大学信息学院北京林业大学信息学院习题习题1 1、2 2、3 3小结小结小结小结小结小结小结小结小结小结小结小结小结小结思考题思考题 北京林业大学信息学院北京林业大学信息学院1.1.判断下面的陈述是否正确。判断下面的陈述是否正确。（1）编译程序的五个组成部分缺一不可。）编译程序的五个组成部分缺一不可。（2）高级语言程序到低级语言程序的转换是基）高级语言程序到低级语言程序的转换是基于语义的等价变换。于语义的等价变换。（3）含有优化部分的编译程序的执行效率高。）含有优化部分的编译程序的执行效率高。（4）因为编译程序和解释程序具有不同的功能，）因为编译程序和解释程序具有不同的功能，所以它们的实现技术也完全不同。所以它们的实现技术也完全不同。（5）编译程序和解释程序的根本区别在于解释）编译程序和解释程序的根本区别在于解释程序对源程序并没有真正进行翻译。程序对源程序并没有真正进行翻译。（6）无论一遍扫描的编译器还是多遍扫描的编）无论一遍扫描的编译器还是多遍扫描的编译器都要对源程序扫描一遍。译器都要对源程序扫描一遍。北京林业大学信息学院北京林业大学信息学院2 2计计算算机机执执行行用用高高级级语语言言编编写写的的程程序序有有哪哪些些途途径？它们之间的主要区别是什么？径？它们之间的主要区别是什么？3 3画画出出编编译译程程序序的的总总体体逻逻辑辑结结构构图图，简简述述各各部部分的主要功能。分的主要功能。北京林业大学信息学院北京林业大学信息学院练习练习请指出下列错误信息是编译的哪个阶段报告的请指出下列错误信息是编译的哪个阶段报告的(1)else没有匹配的没有匹配的if；(2)使用的函数没有定义；使用的函数没有定义；(3)在数中出现非数字字符。在数中出现非数字字符。北京林业大学信息学院北京林业大学信息学院